# 分配律、拉普拉斯展開

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}$

from lingeo import random_int_list

## Main idea

The determinant function satisfies the **distributive law** on each row.
That is,
$$
\det\begin{bmatrix}
- & \ba\trans + \bb\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}
=
\det\begin{bmatrix}
- & \ba\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}
+
\det\begin{bmatrix}
- & \bb\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}.
$$
Since one may swap two rows or take the transpose without chaning the determinant, the distributive law holds for any row and any column.

If we think of the determinant $\det(A)$ as a function on $n$ row vectors $f(\br_1,\ldots,\br_n)$,
then $f$ is linear on each vector individually.
That is,
$$
\begin{aligned}
f( \ldots, \ba + \bb, \ldots ) &= f( \ldots, \ba, \ldots ) + f( \ldots, \bb, \ldots ), \\
f( \ldots, k\ba, \ldots ) &= k f( \ldots, \ba, \ldots ).
\end{aligned}
$$
A function with this property is said to be **multilinear**.

Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ matrix.
Let $\br_1, \ldots, \br_n$ be the rows of $A$.
Define $A(i,j)$ as the submatrix obtained from $A$ by removing the $i$-th row and the $j$-th column.

By expanding the first row, we have
$$
\begin{aligned}
\det(A) &=
\det\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix} \\
&=
\det\begin{bmatrix}
a_{11} & 0 & \cdots & ~ & 0 \\
- & ~ & \br_2\trans & ~ & - \\
~ & ~ & \vdots & ~ & ~ \\
- & ~ & \br_n\trans & ~ & -
\end{bmatrix}
+
\det\begin{bmatrix}
0 & a_{12} & 0 & \cdots & 0 \\
- & ~ & \br_2\trans & ~ & - \\
~ & ~ & \vdots & ~ & ~ \\
- & ~ & \br_n\trans & ~ & -
\end{bmatrix}
+
\det\begin{bmatrix}
0 & \cdots & ~ & 0 & a_{1n} \\
- & ~ & \br_2\trans & ~ & - \\
~ & ~ & \vdots & ~ & ~ \\
- & ~ & \br_n\trans & ~ & -
\end{bmatrix} \\
&=
a_{11}\det A(1,1) - a_{12}\det A(1,2) + \cdots + (-1)^{1+n}a_{1n}\det A(1,n).
\end{aligned}
$$

Again, this formula works for any row and column.
We may expand the $i$-th row and get
$$
\det(A) = \sum_{j=1}^n (-1)^{i + j} a_{ij} \det A(i,j).
$$
The formula for expanding a column is similar.
This identity is called the **Laplace expansion**.

## Side stories

- variable matrix
- differentiation

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

n = 4
A = matrix(n, random_int_list(n^2,3))

expr = []
dets = []
for j in range(n):
    expr.append(LatexExpr(r"\det"))
    B = copy(A)
    for k in range(n):
        if k != j:
            B[0,k] = 0
    dets.append(B.det())
    expr.append(copy(B))
    if j != n-1:
        expr.append(LatexExpr("+"))
    
print("n =", n)
pretty_print(LatexExpr(r"\det"), A, LatexExpr("="), *expr)

if print_ans:
    print("%s = "%A.det() + " + ".join("%s"%d for d in dets))

##### Exercise 1(a)

對每一個 $j = 1, ..., n$，
計算 $\det A(1,j)$。

**[由林柏仰同學提供]**
以 `seed = 10` 執行程式碼後得到
$$
A = \begin{bmatrix}
1 & 0 & -1 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix}.
$$
依照定義， $A(i,j)$ 為 $A$ 去掉第 $i$ 列、第 $j$ 行後的矩陣。
則
$$
\det A(1,1) = \det \begin{bmatrix}
-3 & -3 & 0 \\
0 & -2 & 0 \\
2 & -2 & 0
\end{bmatrix} = 0,\\
\det A(1,2) = \det \begin{bmatrix}
0 & -3 & 0 \\
-2 & -2 & 0 \\
3 & -2 & 0
\end{bmatrix} = 0,\\
\det A(1,3) = \det \begin{bmatrix}
0 & -3 & 0 \\
-2 & 0 & 0 \\
3 & 2 & 0
\end{bmatrix} = 0,\\
\det A(1,4) = \det \begin{bmatrix}
0 & -3 & -3 \\
-2 & 0 & -3 \\
3 & 2 & -2
\end{bmatrix} = 51.\\
$$

##### Exercise 1(b)

計算題目給的等式中的每一個行列式值、
並驗證等式成立。

**[由林柏仰同學提供]**
以 `seed = 10` 執行程式碼後得到等式
$$
\det \begin{bmatrix}
1 & 0 & -1 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} =
\det \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} +
\det \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} +
\det \begin{bmatrix}
0 & 0 & -1 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} +
\det \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix}。
$$
經過計算後得到
$$
\det \begin{bmatrix}
1 & 0 & -1 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} = 0,
$$
以及
$$
\det \begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} =
\det \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} =
\det \begin{bmatrix}
0 & 0 & -1 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} =
\det \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & -3 & -3 & 0 \\
-2 & 0 & -2 & 0 \\
3 & 2 & -2 & 0
\end{bmatrix} = 0。
$$
可知題目給出之等式成立。

## Exercises

##### Exercise 2

以下題目探討矩陣中單一一項對行列式值的影響。

##### Exercise 2(a)

令
$$
A = \begin{bmatrix}
1 + x & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}.
$$
求 $\det(A)$。

:::warning

- [x] 說明行列式值怎麼算的，比如說：用 $3\times 3$ 矩陣的行列式值公式...
:::

$Ans:$
運用 $3\times 3$ 矩陣行列式值公式得到
$$
\det(A)=(-3x).
$$
##### Exercise 2(b)

觀察到
$$
(1+x,2,3) = (1,2,3) + (x,0,0).
$$
利用這個性質，
將 $\det(A)$ 的常數項寫成一個 $3\times 3$ 矩陣的行列式值、
並將其一次項寫成一個 $2\times 2$ 矩陣的行列式值。

$Ans:$

根據矩陣行列式值分配律，$\det(A)$ 可表示成
$$
\det\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}+
\det\begin{bmatrix}
x & 0 & 0 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}，
$$

因此 $\det(A)$ 常數項為
$$
\det\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}=0，
$$
$\det(A)$ 一次項為
$$
\det\begin{bmatrix}
x & 0 & 0 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}=
x·\det\begin{bmatrix}
5 & 6 \\
8 & 9
\end{bmatrix}
=(-3x).
$$
##### Exercise 2(c)

把 $\det(A)$ 看成 $x$ 的函數，求 $\frac{d\det(A)}{dx}$。

搭配上一題，
這說明當一個矩陣 $A$ 的 $i,j$-項增加 $x$ 的時候，
其行列式值會增加 $x\cdot (-1)^{i+j}\det A(i,j)$。

**[由林柏仰同學提供]**
由 2(b) 得知， $\det(A) = -3x$ 。
則 $\frac{d\det(A)}{dx} = -3$ 。

由第一題可知，要計算一矩陣 $A$ 的行列式值可透過對其經分配律得到若干個矩陣，並將這些矩陣的行列式值加總得出。
例
$$
\det \begin{bmatrix}
1 & 2 \\
3 & 4
\end{bmatrix} = \det
\begin{bmatrix}
1 & 2 \\
3 & 0
\end{bmatrix} + \det
\begin{bmatrix}
1 & 2 \\
0 & 4
\end{bmatrix}
$$
由第二題可知，變數也可以拆出來，即
$$
\det \begin{bmatrix}
1 & 2 \\
3 & 4+x
\end{bmatrix} = \det
\begin{bmatrix}
1 & 2 \\
3 & 0
\end{bmatrix} + \det
\begin{bmatrix}
1 & 2 \\
0 & 4
\end{bmatrix} + \det
\begin{bmatrix}
1 & 2 \\
0 & x
\end{bmatrix}
$$
令
$$
B = \begin{bmatrix}
1 & 2 \\
0 & x
\end{bmatrix}
$$
令 $i = 2,j = 2$
若對 $B$ 進行列運算(第 $i$ 列往上換 $i-1$ 次)及行運算(第 $j$ 行往左換 $j-1$ 次)，會得到一矩陣
$$
\begin{bmatrix}
x & 2 \\
0 & 1
\end{bmatrix}
$$
且此矩陣的行列式值乘以 $(-1)^{(i-1) + (j-1)} = (-1)^{i+j}$ 即為 $B$ 的行列式值。
將此矩陣視為區塊矩陣可得其行列式值為
$$
\det \begin{bmatrix}
x
\end{bmatrix}\cdot\det
\begin{bmatrix}
1
\end{bmatrix} =
x\cdot\det A(i,j)
$$
則 $\det(B) = x\cdot(-1)^{i+j}\cdot\det A(i,j)$ 。
故當一矩陣的第 $i,j$-項增加 $x$ 時，其行列式值會增加 $\det(B) = x\cdot(-1)^{i+j}\cdot\det A(i,j)$ 。

##### Exercise 3

對以下 $n\times n$ 矩陣，
將每列寫成兩個向量相加，
其中一個向量只有常數，另一個向量只有 $x$。

如此可以將 $\det(A)$ 寫成 $2^n$ 個行列式值相加。
計算這些行列式值並計算 $\det(A)$。

##### Exercise 3(a)

$$
A = \begin{bmatrix}
1 - x & 2 \\
3 & 4 - x
\end{bmatrix}.
$$
$Ans:$
根據矩陣行列式值分配律
$$
\det(A) = \det\begin{bmatrix}
1 - x & 2 \\
3 & 4 - x
\end{bmatrix}.
$$
可表示成
$$
\det(A) = \det\begin{bmatrix}
1 & 2\\
3 & 4
\end{bmatrix}
+
\det\begin{bmatrix}
1 & 2\\
0 & -x
\end{bmatrix}
+
\det\begin{bmatrix}
-x & 0 \\
3 & 4
\end{bmatrix}
+
\det\begin{bmatrix}
-x & 0\\
0 & -x
\end{bmatrix}
$$
$$
=(-2)+(-x)+(-4x)+(x^2)=x^2-5x-2.
$$

##### Exercise 3(b)
$$
A = \begin{bmatrix}
1 - x & 2 & 3 \\
4 & 5 - x & 6 \\
7 & 8 & 9 - x
\end{bmatrix}.
$$

:::warning

- [x] 最後句點
:::

$Ans:$
根據矩陣行列式值分配律
$$
\det(A) = \det\begin{bmatrix}
1 - x & 2 & 3 \\
4 & 5 - x & 6 \\
7 & 8 & 9 - x
\end{bmatrix}.
$$
可表示成
$$
\det(A)= \det\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}+
\det\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
0 & 0 & -x
\end{bmatrix}
$$
$$
+\det\begin{bmatrix}
1 & 2 & 3 \\
0 & - x & 0 \\
7 & 8 & 9
\end{bmatrix}+
\det\begin{bmatrix}
-x & 0 & 0 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}+
\det\begin{bmatrix}
1 & 2 & 3 \\
0 & - x & 0 \\
0 & 0 & - x
\end{bmatrix}
$$
$$
+\det\begin{bmatrix}
- x & 0 & 0 \\
4 & 5 & 6 \\
0 & 0 & - x
\end{bmatrix}+
\det\begin{bmatrix}
- x & 0 & 0 \\
0 & - x & 0 \\
7 & 8 & 9
\end{bmatrix}+
\det\begin{bmatrix}
- x & 0 & 0 \\
0 & - x & 0 \\
0 & 0 & - x
\end{bmatrix}
$$
$$
=0+(3x)+(12x)+(3x)+(9x^2)+(x^2)+(5x^2)+(-x^3) \\
=(-x^3)+15x^2+18x.
$$
##### Exercise 4

令
$$
A = \begin{bmatrix}
a & b & c & d \\
e & f & g & h \\
i & j & k & \ell \\
m & n & o & p
\end{bmatrix}.
$$
求 $\det(A)$。

:::warning

- [x] 要把 $24$ 項寫出來
- [x] 前面加一些文字：利用拉普拉斯展開，我們 .... 等等
:::

$Ans:$
利用拉普拉斯展開，可知
$$
\det(A)=\det\begin{bmatrix}
a & b & c & d \\
e & f & g & h \\
i & j & k & \ell \\
m & n & o & p
\end{bmatrix}
$$
$$
=\det\begin{bmatrix}
a & 0 & 0 & 0 \\
0 & f & g & h \\
0 & j & k & \ell \\
0 & n & o & p
\end{bmatrix}
+(-1)\det\begin{bmatrix}
0 & b & 0 & 0 \\
e & 0 & g & h \\
i & 0 & k & \ell \\
m & 0 & o & p
\end{bmatrix}
+\det\begin{bmatrix}
0 & 0 & c & 0 \\
e & f & 0 & h \\
i & j & 0 & \ell \\
m & n & 0 & p
\end{bmatrix}
+(-1)\det\begin{bmatrix}
0 & 0 & 0 & d \\
e & f & g & 0 \\
i & j & k & 0 \\
m & n & o & 0
\end{bmatrix}
$$
$$
=a\det\begin{bmatrix}
f & g & h \\
j & k & \ell \\
n & o & p
\end{bmatrix}
+(-b)\det\begin{bmatrix}
e & g & h \\
i & k & \ell \\
m & o & p
\end{bmatrix}
+c\det\begin{bmatrix}
e & f & h \\
i & j & \ell \\
m & n & p
\end{bmatrix}
+(-d)\det\begin{bmatrix}
e & f & g \\
i & j & k \\
m & n & o
\end{bmatrix}
$$
$$
=af\det\begin{bmatrix}
k & \ell \\
o & p \\
\end{bmatrix}
+a(-g)\det\begin{bmatrix}
i & \ell \\
n & p \\
\end{bmatrix}
+ah\det\begin{bmatrix}
j & k \\
n & o \\
\end{bmatrix}
$$
$$
+(-b)e\det\begin{bmatrix}
k & \ell \\
o & p \\
\end{bmatrix}
+(-b)(-g)\det\begin{bmatrix}
i & \ell \\
m & p \\
\end{bmatrix}
+(-b)h\det\begin{bmatrix}
i & k \\
m & o \\
\end{bmatrix}
$$
$$
+ce\det\begin{bmatrix}
j & \ell \\
n & p \\
\end{bmatrix}
+c(-f)\det\begin{bmatrix}
i & \ell \\
m & p \\
\end{bmatrix}
+ch\det\begin{bmatrix}
i & j \\
m & n \\
\end{bmatrix}
$$
$$
+(-d)e\det\begin{bmatrix}
j & k \\
n & o \\
\end{bmatrix}
+(-d)(-f)\det\begin{bmatrix}
i & k \\
m & o \\
\end{bmatrix}
+(-d)g\det\begin{bmatrix}
i & j \\
m & n \\
\end{bmatrix}
$$

$$
=afkp-af\ell o-agip+ag\ell n+ahjo-ahkn-bekp+be\ell o
$$
$$
+bgip-bg\ell m-bhio+bhkm+cejp-ce\ell n-cfip+cf\ell m
$$
$$
+chin-chjm-dejo+dekn+dfio-dfkm-dgin+dgjm.
$$
##### Exercise 5

給定向量 $\ba$、$\bb$、以及 $\br_2,\ldots,\br_n$。
令
$$
M = \begin{bmatrix}
- & \ba\trans + \bb\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}
,\quad
A = \begin{bmatrix}
- & \ba\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}
,\text{ and}\quad
B = \begin{bmatrix}
- & \bb\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}.
$$

依照以下步驟證明行列式值的分配律 $\det(M) = \det(A) + \det(B)$。

##### Exercise 5(a)

證明當 $\{\br_2,\ldots,\br_n\}$ 線性相依的時候，$\det(M) = \det(A) = \det(B) = 0$。
因此等式成立。

:::warning

- [x] 向量粗體
- [x] 數學進數學模式
- [x] 中英數之間空格
:::

$Ans:$
因為線性相依因為線性相依，所以
$$
0 = a_2\br_1 + \cdots + a_n\br_n.
$$
可以透過 $n-1$ 個基本矩陣使 $\ M,A,B$ 最後一列為零向量
故
$\det(M) = \det(A) = \det(B) = 0$。
##### Exercise 5(b)

假設 $\{\br_2,\ldots,\br_n\}$ 線性獨立。
找一個向量 $\br_1$ 使得 $\beta = \{\br_1,\br_2,\ldots,\br_n\}$ 是 $\mathbb{R}^n$ 的一組基底。
因此可以將 $\ba$ 和 $\bb$ 寫成 $\beta$ 的線性組合：
$$
\begin{aligned}
\ba &= a_1\br_1 + \cdots + a_n\br_n \\
\bb &= b_1\br_1 + \cdots + b_n\br_n
\end{aligned}
$$
藉由列運算說明行列式值的分配律成立。

**[由林柏仰同學提供]**
對 $M$ 進行列運算可得矩陣
$$
\begin{bmatrix}
- & (a_1 + b_1)\br_1\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}。
$$
因一矩陣的行列式值可看成其列向量在空間中所張出的超平行體的體積，故 $\det(M) = (a_1 + b_1)\cdot\det(R)$，其中
$$
R = \begin{bmatrix}
- & \br_1\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}。
$$
對 $A,B$ 進行列運算可得到矩陣
$$
\begin{bmatrix}
- & a_1\br_1\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix},
\begin{bmatrix}
- & b_1\br_1\trans & - \\
- & \br_2\trans & - \\
~ & \vdots & ~ \\
- & \br_n\trans & -
\end{bmatrix}。
$$
因一矩陣的行列式值可看成其列向量在空間中所張出的超平行體的體積，故 $\det(A) = a_1\cdot\det(R),
\det(B) = b_1\cdot\det(R)$ 。
而 $\det(A) + \det(B) = (a_1 + b_1)\cdot\det(R) = \det(M)$ 。

:::info
目前分數 = 6.5
:::