owned this note
owned this note
Published
Linked with GitHub
# 克拉瑪公式
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}}$
```python
from lingeo import random_int_list
```
## Main idea
Let $A$ be an $n\times n$ invertible matrix
and $\bb\in\mathbb{R}^n$.
To solve the equation $A\bx = \bb$, one may calculate the reduced echelon form of the augmented matrix as follows.
$$
\left[\begin{array}{c|c} A & \bb \end{array}\right]
\rightarrow
\left[\begin{array}{c|c} I_n & \bx \end{array}\right]
$$
This means there is an invertible matrix $E$
such that $EA = I_n$ and $E\bb = \bx$.
(So actually $E = A^{-1}$.)
Let $A_j$ be the matrix obtained from $A$ by replacing the $j$-th column with the vector $\bb$.
Then we have
$$
EA_j =
\begin{bmatrix}
~ & | & | & | & ~ \\
\cdots & \be_{j-1} & \bx & \be_{j+1} & \cdots \\
~ & | & | & | & ~
\end{bmatrix}.
$$
If $\bx = (x_1,\ldots, x_n)$, then by taking the determinant of the above equality on both sides, we get
$$
\det(E)\det(A_j) = x_j.
$$
This leads to Cramer's rule below.
##### Theorem (Cramer's rule)
Let $A$ be an $n\times n$ invertible matrix and $\bb\in\mathbb{R}^n$.
Let $A_j$ be the matrix obtained from $A$ by replacing the $j$-th column with $\bb$.
Then the solution $\bx = (x_1,\ldots,x_n)$ to the equation $A\bx = \bb$ can be solved by
$$
x_j = \frac{\det(A_j)}{\det(A)}.
$$
## Side stories
- unimodular
- totally unimodular
## Experiments
##### Exercise 1
執行以下程式碼。
```python
### code
set_random_seed(0)
print_ans = False
n = 3
while True:
A = matrix(n, random_int_list(n^2,3))
if A.det() != 0:
break
b = vector(random_int_list(n, 3))
print("n =", n)
pretty_print(LatexExpr("A ="), A)
pretty_print(LatexExpr(r"{\bf b} ="), b)
if print_ans:
for j in range(n):
Aj = copy(A)
Aj[:,j] = b
print("j =", j+1)
pretty_print(LatexExpr("A_j ="), Aj)
print("det(Aj) =", Aj.det())
print("det(A) =", A.det())
print(A \ b)
```
:::warning
- [x] 用文字串起來：當 `seed = 49` 時，題目給的是 ...
:::
當 `seed = 49` 時，題目給的是
$n=3$,
$A=\begin{bmatrix}
0 & 1 & -2\\
-1& -2 & 1 \\
0 &-3 & 2
\end{bmatrix},$
$\bb = \begin{bmatrix}
2 \\ 2 \\ 1
\end{bmatrix}.$
##### Exercise 1(a)
對所有 $j = 1,\ldots, n$，寫下 $A_j$ 並求出 $\det A_j$。
:::warning
- [x] 說明一下 $A_j$ 的定義。
:::
ans:
令$A=\begin{bmatrix}
| & | & |\\
\ba_1 &\ba_2& \ba_3 \\
| & | & |
\end{bmatrix},$
$A_j=A$ 的第 $j$ 列改成 $\bb$
$A_1=
\begin{bmatrix}
| & | & |\\
\bb &\ba_2&\ba_3 \\
| & | & |
\end{bmatrix}=
\begin{bmatrix}
2 & 1 & -2\\
2 & -2 & 1 \\
1 &-3 & 2
\end{bmatrix},\det(A_1)=3,$
$A_2=
\begin{bmatrix}
| & | & |\\
\ba_1 &\bb& \ba_3 \\
| & | & |
\end{bmatrix}=
\begin{bmatrix}
0 & 2 & -2\\
-1& 2 & 1 \\
0 & 1 & 2
\end{bmatrix},\det(A_2)=6,$
$A_3=
\begin{bmatrix}
| & | & | \\
\ba_1 &\ba_2& \bb \\
| & | & |
\end{bmatrix}=
\begin{bmatrix}
0 & 1 & 2\\
-1& -2 & 2 \\
0 &-3 & 1
\end{bmatrix},\det(A_3)=7.$
##### Exercise 1(b)
計算 $\det(A)$ 並用克拉瑪公式求出 $A\bx = \bb$ 的解 $\bx$。
:::warning
- [x] 經計算可得 $\det(A) = -4$。（$A$ 應該不用再寫一次，然後你們的 $A$ 好像打成 $A_1$。）
- [x] 依照克拉瑪公式可得 ...
:::
ans:
經計算可得 $\det(A)=-4.$
依照克拉瑪公式可得,
$\begin{aligned}
\bx_1=\frac{\det(A_1)}{\det(A)}=-\frac{3}{4},\\
\bx_2=\frac{\det(A_2)}{\det(A)}=-\frac{3}{2},\\
\bx_3=\frac{\det(A_3)}{\det(A)}=-\frac{7}{4}.
\end{aligned}$
$\bx=\begin{bmatrix}
-\frac{3}{4}\\-\frac{3}{2}\\-\frac{7}{4}
\end{bmatrix}.$
## Exercises
##### Exercise 2
根據拉普拉斯展開，計算行列式值時只會用到加法和乘法。
所以一個整數矩陣的行列式值也會是整數、
而一個有理數矩陣的行列式值也會是有理數。
利用這個性質回答以下問題。
##### Exercise 2(a)
說明若 $A$ 是一個可逆有理數矩陣、
而 $\bb$ 是一個有理數向量，
則 $A\bx = \bb$ 的解 $\bx$ 也會是有理數向量。
:::warning
- [x] $det$ --> $\det$
- [x] 純量 $x_1,\ldots, x_n$ 不用粗體
:::
Let $A\in\mathbb{Q}^{n\times n}$ and $\bb\in \mathbb{Q}^{n}$, where $A$ is invertible.\
By Cramer's rule, $x_{j}=\frac{\det(A_{j})}{\det(A)}$, where $j=1,\cdots,n$, and $\bx=\left[\begin{matrix}
x_{1} \\ \vdots \\ x_{n} \
\end{matrix}\right]$.
Because elements of $A$ and $A_{j}$ are all rational numbers, $\det(A)$ and $\det(A_{j})$ are rational, too.
Then, we get $b_{j}$ is rational, for all $j$.
QED
##### Exercise 2(b)
找一個可逆的整數矩陣 $A$、以及一個整數向量 $\bb$，
使得 $A\bx = \bb$ 的解 $\bx$ 並不是整數向量。
Let $A=\left[\begin{matrix}
2&0\\0&2 \\ \end{matrix}\right]$ and $\bb=\left[\begin{matrix}1\\1 \\ \end{matrix}\right]$.\
Clearly, $A$ is invertible, but $\bx= \left[\begin{matrix}
\frac{1}{2} \\ \frac{1}{2}
\end{matrix}\right] \notin \mathbb{Z}^{2}.$
##### Exercise 2(c)
回顧一個整數方陣如果行列式值為 $\pm 1$，
則被稱為么模矩陣 。
說明若 $A$ 是一個么模矩陣、
而 $\bb$ 是一個整數向量，
則 $A\bx = \bb$ 的解 $\bx$ 也會是整數向量。
:::warning
- [x] $det$ --> $\det$
- [x] 純量 $x_1,\ldots, x_n$ 不用粗體
- [x] 最後的 $b_j$ 是不是寫錯？好像是 $x_j$？
:::
Let $A\in \mathbb{Q}^{n\times n}$ and $\bb\in \mathbb{Q}^{n}$, where $\det(A)=\pm 1$.
By Cramer's rule, $x_{j}=\frac{\det(A_{j})}{\det(A)}=\pm {\det(A_{j})}$, where $j=1,\cdots,n$, and $\bx=\left[\begin{matrix}
x_{1} \\ \vdots \\ x_{n} \\
\end{matrix}\right]$.\
Because elements of $A$ and $A_{j}$ are all integers, and we don't use division to calculate $\det(A_{j})$, $x_{j}$ is integer, too, for all $j$.
QED
##### Exercise 3
令
$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
$$
且 $\bb = (1,0,1)$。
##### Exercise 3(a)
利用列運算將 $A$ 消成 $I_3$、
並記錄每一步的列運算。
:::warning
- [x] 在原始碼前面加 `>` 是引用模式，寫答案應該是不用用到這個。
:::
ans:
$$
\begin{split}
A =
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_2: + (-1) \rho_1}
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
0 & 1 & 3 \\
1 & 3 & 9
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: + (-1) \rho_1}
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 2 & 8
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_1: + (-1) \rho_2}
& \left[\begin{array}{ccc}
1 & 0 & -2 \\
0 & 1 & 3 \\
0 & 2 & 8
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: + (-2) \rho_2}
& \left[\begin{array}{ccc}
1 & 0 & -2 \\
0 & 1 & 3 \\
0 & 0 & 2
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: \times \frac
{1}{2}}
& \left[\begin{array}{ccc}
1 & 0 & -2 \\
0 & 1 & 3 \\
0 & 0 & 1
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_1: + 2 \rho_3}
& \left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 3 \\
0 & 0 & 1
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_2: + (-3) \rho_3}
& \left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}\right] \\
= & I_3
\end{split} $$
##### Exercise 3(b)
對 $A_2$ 進行與上一題相同的列運算，求其得到的結果 $R$。
ans:
$$ \begin{split}
A_2 =
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
1 & 0 & 4 \\
1 & 1 & 9
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_2: + (-1) \rho_1}
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
0 & -1 & 3 \\
1 & 1 & 9
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: + (-1) \rho_1}
& \left[\begin{array}{ccc}
1 & 1 & 1 \\
0 & -1 & 3 \\
0 & 0 & 8
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_1: + (-1) \rho_2}
& \left[\begin{array}{ccc}
1 & 2 & -2 \\
0 & -1 & 3 \\
0 & 0 & 8
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: + (-2) \rho_2}
& \left[\begin{array}{ccc}
1 & 2 & -2 \\
0 & -1 & 3 \\
0 & 2 & 2
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_3: \times \frac{1}{2}}
& \left[\begin{array}{ccc}
1 & 2 & -2 \\
0 & -1 & 3 \\
0 & 1 & 1
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_1: + 2 \rho_3}
& \left[\begin{array}{ccc}
1 & 4 & 0 \\
0 & -1 & 3 \\
0 & 1 & 1
\end{array}\right] \\
%%
%%
\underrightarrow{\rho_2: + (-3) \rho_3}
& \left[\begin{array}{ccc}
1 & 4 & 0 \\
0 & -4 & 0 \\
0 & 1 & 1
\end{array}\right]. \\
\end{split} $$
因此
$$ R = \left[\begin{array}{ccc}
1 & 4 & 0 \\
0 & -4 & 0 \\
0 & 1 & 1
\end{array}\right].$$
##### Exercise 3(c)
求一個矩陣 $E$ 使得 $EA = I_3$ 且 $EA_2 = R$。
ans:
因為 $A_1$ 與 $A_2$ 的列運算相同，所以其基本矩陣E相同。
$$EA = I_3, \, EA_2 = R.$$
其中
$$E_1
= \left[\begin{array}{ccc}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & 0 & 1
\end{array}\right], \,
E_2
= \left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & 0 & 1
\end{array}\right], \,
E_3 =
\left[\begin{array}{ccc}
1 & -1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}\right], \\
E_4 =
\left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -2 & 1
\end{array}\right], \,
E_5 =
\left[\begin{array}{ccc}
1 & 0 & 2 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}\right], \,
E_6 =
\left[\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & -3 \\
0 & 0 & 1
\end{array}\right].
$$
因此
$$\begin{split}
E
= E_6 E_5 E_4 E_3 E_2 E_1
= \left[\begin{array}{ccc}
3 & -3 & 1 \\
-\frac{5}{2} & 4 & -\frac{3}{2} \\
\frac{1}{2} & -1 & \frac{1}{2}
\end{array}\right].
\end{split}
$$
##### Exercise 4
克拉瑪公式也可以由伴隨矩陣及餘因子矩陣的性質得到。
依照以下步驟給出克拉瑪公式的另一種證明。
令 $A$ 為一 $n\times n$ 可逆矩陣、而 $\bb\in\mathbb{R}^n$。
令 $\bx = (x_1,\ldots, x_n)$ 為 $A\bx = \bb$ 的解。
##### Exercise 4(a)
令 $\bc_j$ 為 $A\cof$ 的第 $j$ 行。
說明 $\det(A_j) = \inp{\bb}{\bc_j}$。
:::warning
- [x] 依照定義 $A\cof$ 的第 $i,j$-項為 ${A\cof}_{ij} = (-1)^{i+j}\det(A_{i,j})$，其中 $A_{i,j}$ 為 $A$ 去掉第 $i$ 列和第 $j$ 行後的矩陣。
- [x] $c_j$ 粗體
:::
**Ans:**
依照定義， $A_j$ 為將 $A$ 的第 $j$ 行換成 $\bb$ 的矩陣。
而因 $A\cof$ 的第 $j$ 行的產生和 $A$ 的第 $j$ 行沒有關係，則 $A\cof$ 的第 $j$ 行和 ${A_j}\cof$ 的第 $j$ 行是一樣的。
又因 ${A_j}\adj = {{A_j}\cof}\trans$ 且 ${A_j}\adj A_j = \det(A_j)I$ 。
觀察 ${A_j}\adj A_j$ ，若令其所得出的矩陣為 $B$ ，則 $B$ 的 $j,j-$ 項為 ${A_j}\adj$ 的第 $j$ 列和 $A_j$ 的第 $j$ 行內積所得出的結。
相當於 $\det(A_j) = \inp{\bb}{\bc_j}$。
##### Exercise 4(b)
利用 $A\adj = (A\cof)\trans = \det(A)A^{-1}$ 等性質，
說明 $x_j = \frac{1}{\det(A)}\inp{\bb}{\bc_j} = \frac{\det(A_j)}{\det(A)}$。
:::warning
- [x] $\bc\bb$ 是內積嗎？寫清楚
:::
**Ans:**
由題目得知 $A\bx = \bb$ 且 $A\adj = \det(A)A^{-1}$。
則
$$
A\bx = \bb。\\
A^{-1}A\bx = A^{-1}\bb。\\
\bx = \frac{\det(A)}{\det(A)}A^{-1}\bb。\\
\bx = \frac{1}{\det(A)}A\adj\bb。
$$
令
$$
A\adj = \begin{bmatrix}
- & \bc_1 & - \\
\vdots & ~ & \vdots \\
- & \bc_n & -
\end{bmatrix},
\bx = \begin{bmatrix}
b_1 \\
\vdots \\
b_n
\end{bmatrix}.
$$
則
$$
\begin{bmatrix}
x_1 \\
\vdots \\
x_n
\end{bmatrix}
=\frac{1}{\det(A)}\begin{bmatrix}
\bb\cdot\bc_1 \\
\vdots \\
\bb\cdot\bc_n
\end{bmatrix}.
$$
即 $x_j = \frac{\bb\ \cdot\ \bc_j}{\det(A)}$ 。
而由 4(a) 可知， $\bb\cdot\bc_j = \det(A_j)$ 。
故 $x_j = \frac{\bb\ \cdot\ \bc_j}{\det(A)} = \frac{\det(A_j)}{\det(A)}$ 。
##### Exercise 5
令
$$
A = \begin{bmatrix}
1 & 1 \\
0 & 1 \\
1 & 0
\end{bmatrix}
$$
且 $\bb = (3,1,1)$。
##### Exercise 5(a)
寫出所有 $A$ 的 $2\times 2$ 子矩陣，並計算它們的行列式值。
是否全部為 $\pm 1$？
Ans:
$A$ 的 $2\times 2$ 子矩陣有
$A_1=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ ，
$A_2=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ ，和
$A_3=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ 。
計算其行列式可得
$$\det(A_1) = 1 \times 1 - 0 \times 1 = 1$$
$$\det(A_2) = 1 \times 0 - 1 \times 1 = -1$$
$$\det(A_3) = 0 \times 0 - 1 \times 1 = -1
$$
確實皆為 $\pm 1$。
##### Exercise 5(b)
畫出 $A\bx \leq \bb$ 的圖形，
並計算圖形中的所有頂點。
（這裡 $\bx = (x,y)$
而 $A\bx \leq \bb$ 的意思是 $\bb - A\bx$ 每一項都大於等於 $0$。）
:::danger
你們寫的是對的，不過我出錯題目，應該是
$$
A = \begin{bmatrix}
1 & 1 \\
0 & -1 \\
-1 & 0
\end{bmatrix}
$$
且 $\bb = (3,-1,-1)$。
講一下而已，不用改。
:::
Ans:
$$\bb - A\bx = \begin{bmatrix} 3 \\ 1 \\ 1 \end{bmatrix} - \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 3-x-y \\ 1-y \\ 1-x \end{bmatrix}$$
因此，原題意即
$$\begin{cases} \begin{aligned}
3-x-y \geq 0 \\
1-y \geq 0 \\
1-x \geq 0\\
\end{aligned} \end{cases}$$
即
$$\begin{cases} \begin{aligned}
x+y \leq 3 \\
y \leq 1 \\
x \leq 1 \\
\end{aligned} \end{cases}$$
簡單的觀察可以發現第一條不等式是多餘的，因此此題的解為
$$\begin{cases} \begin{aligned}
y \leq 1 \\
x \leq 1 \\
\end{aligned} \end{cases}
$$
在座標平面上即為直線 $x=1$ 以左，直線 $y=1$ 以下的區域。
其頂點為等號成立時的點 $(1,1)$。
##### Exercise 5(c)
利用 (a) 小題的結果
說明為什麼 (b) 小題算出來的頂點都是格子點（座標都是整數）。
:::warning
- [x] $A$ 的各個子矩陣之行列式值也都是 $\pm 1$（只是整數不夠）
:::
Ans:
前一題的解題過程中，解出了三條不等式，即 $\bb - A\bx$ 的三項大於等於零。以線性規劃的觀點來看，可分別在座標平面上畫出三條直線來框出符合條件的範圍，而三條直線兩兩有一交點，因此會有三個交點。
考慮 $\bb = (b_1,b_2,b_3)$ ，令 $\bb_1=(b_1,b_2)$ ， $\bb_2=(b_1,b_3)$ ， $\bb_3=(b_2,b_3)$ 。
則三個交點分別為 $\bb_1 - A_1\bx={\bf 0}$ ， $\bb_2 - A_2\bx={\bf 0}$ ， $\bb_3 - A_3\bx={\bf 0}$ 的解，即 $A_1^{-1}\bb_1$ ， $A_2^{-1}\bb_2$ ， $A_2^{-1}\bb_2$。
由於 $A$ 和 $\bb$ 的各項皆為整數，且由 a 小題知 $A$ 的各個子矩陣之行列式值也都是 $\pm 1$ ，因此各個頂點的解也都會是整數。
##### Remark
一個整數矩陣 $A$ 如果
所有的 $k\times k$ 子矩陣其行列式值皆為 $0,1,-1$，
則稱其為**全么模矩陣（totally unimodular）**。
而當 $A$ 是全么模矩陣且 $\bb$ 是整數向量時
$$
\begin{aligned}
A\bx &\leq \bb \\
\bx &\geq \bzero
\end{aligned}
$$
所圍出的圖形，其頂點都會是格子點。
這表示在做線性規劃的時候，所求出來的最佳解都會是整數。
:::info
目前分數 = 6.5
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
