# 分配律、拉普拉斯展開

Distributive law and Laplace expansion

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}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### 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)$。

<!-- eng start -->
For each $j = 1, ..., n$, find $\det A(1,j)$.
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
Calculate each term in the equality and verify the equality holds.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## Exercises

##### Exercise 2

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

<!-- eng start -->
The following problem studies how an entry of a matrix changees the determinant.
<!-- eng end -->

##### Exercise 2(a)

令

$$
A = \begin{bmatrix}
1 + x & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}.
$$

求 $\det(A)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 + x & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}.
$$

Find $\det(A)$.
<!-- eng end -->

##### Exercise 2(b)

觀察到

$$
(1+x,2,3) = (1,2,3) + (x,0,0).
$$

利用這個性質，
將 $\det(A)$ 的常數項寫成一個 $3\times 3$ 矩陣的行列式值、
並將其一次項寫成一個 $2\times 2$ 矩陣的行列式值。

<!-- eng start -->
Use the fact that

$$
(1+x,2,3) = (1,2,3) + (x,0,0)
$$

to write $\det(A)$ as a polynomial of degree $2$ such that its constant term is the determinant of a $3\times 3$ matrix while its linear term is the determinant of a $2\times 2$ matrix.
<!-- eng end -->

##### Exercise 2(c)

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

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

<!-- eng start -->
Consider $\det(A)$ as a function of $x$. Find $\frac{d\det(A)}{dx}$.

Use the result of the previous problem, explain the determinant of $A$ increases by $x\cdot (-1)^{i+j}\det A(i,j)$ when its $i,j$-entry increases by $x$.
<!-- eng end -->

##### Exercise 3

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

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

<!-- eng start -->
For each of the following $n\times n$ matrix, write each row as the sum of two vectors, where one is composed of constants only, while the other is composed of linear terms.

Thus, we may write $\det(A)$ as the sum of $2^n$ determinants. Calculate each of them to find $\det(A)$.
<!-- eng end -->

##### Exercise 3(a)

$$
A = \begin{bmatrix}
1 - x & 2 \\
3 & 4 - x
\end{bmatrix}.
$$

##### Exercise 3(b)

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

##### 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)$。

##### 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)$。

<!-- eng start -->
Let $\ba$, $\bb$, and $\br_2, \ldots, \br_n$ be some vectors.
Let

$$
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}.
$$

Follow the steps below to show the distributive law of the determinant, that is, $\det(M) = \det(A) + \det(B)$.
<!-- eng end -->

##### Exercise 5(a)

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

<!-- eng start -->
Show that $\det(M) = \det(A) = \det(B) = 0$ when $\{\br_2,\ldots,\br_n\}$ is linearly dependent, so the equality holds.
<!-- eng end -->

##### 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}
$$

藉由列運算說明行列式值的分配律成立。

<!-- eng start -->
Suppose $\{\br_2,\ldots,\br_n\}$ is linearly independent. Find a vector $\br_1$ such that $\beta = \{\br_1,\br_2,\ldots,\br_n\}$ is a basis of $\mathbb{R}^n$. Thus, both $\ba$ and $\bb$ can be written as linear combinations of $\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}
$$

Use row operations to show the distributive law in this case.
<!-- eng end -->