# 克拉瑪公式

Cramer's rule

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

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

執行以下程式碼。

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

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

##### Exercise 1(a)

對所有 $j = 1,\ldots, n$，寫下 $A_j$ 並求出 $\det A_j$。

<!-- eng start -->
For each $j = 1,\ldots, n$, find $A_j$ and $\det A_j$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
$$
A_1=\begin{bmatrix}\
-2 & 1 & 1 \\
2 & -3 & -3 \\
-1 & 3 & 1
\end{bmatrix} \\
\det(A_1)=-24 \\
A_2=\begin{bmatrix}\
-3 & -2 & 1 \\
2 & 1 & -3 \\
-1 & 2 & 1
\end{bmatrix} \\
\det(A_2)=-18 \\
A_3=\begin{bmatrix}\
-3 & 3 & -2 \\
2 & -3 & 1 \\
-1 & 3 & 2
\end{bmatrix} \\
\det(A_3)=6
$$

##### Exercise 1(b)

計算 $\det(A)$ 並用克拉瑪公式求出 $A\bx = \bb$ 的解 $\bx$。

<!-- eng start -->
Find $\det(A)$ and use Cramer's rule to find the solution $\bx$ to $A\bx = \bb$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
$$
\det(A)=-12
$$
By Cramer's rule, we know that $x_j = \frac{\det(A_j)}{\det(A)}$, then we have
$$
\bx_1=2,\bx_2=\frac{3}{2},\bx_3=-\frac{1}{2}.
$$
Thus,
$$
\bx=(2,\frac{3}{2},-\frac{1}{2}).
$$

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

**[由張永賦提供]**
Sometimes we can use augmented matrix to get the answer faster.
:::

## Exercises

##### Exercise 2

根據拉普拉斯展開，計算行列式值時只會用到加法和乘法。
所以一個整數矩陣的行列式值也會是整數、
而一個有理數矩陣的行列式值也會是有理數。
利用這個性質回答以下問題。

<!-- eng start -->
According to Laplace expansion, the computation of the determinant only uses addition and multiplication. Therefore, the determinant of an integer matrix is an integer, while the determinant of a rational matrix is a rational number. Use these properties to answer the following problems.
<!-- eng end -->

##### Exercise 2(a)

說明若 $A$ 是一個可逆有理數矩陣、
而 $\bb$ 是一個有理數向量，
則 $A\bx = \bb$ 的解 $\bx$ 也會是有理數向量。

<!-- eng start -->
Suppose $A$ is a invertible rational matrix and $\bb$ is a rational vector. Explain why the solution $\bx$ to $A\bx = \bb$ is a rational vector.
<!-- eng end -->

##### Exercise 2(b)

找一個可逆的整數矩陣 $A$、以及一個整數向量 $\bb$，
使得 $A\bx = \bb$ 的解 $\bx$ 並不是整數向量。

<!-- eng start -->
Find an invertible integer matrix $A$ and an integer vector $\bb$ such that the solution $\bx$ to $A\bx = \bb$ is not an integer vector.
<!-- eng end -->

##### Exercise 2(c)

回顧一個整數方陣如果行列式值為 $\pm 1$，
則被稱為么模矩陣 。
說明若 $A$ 是一個么模矩陣、
而 $\bb$ 是一個整數向量，
則 $A\bx = \bb$ 的解 $\bx$ 也會是整數向量。

<!-- eng start -->
Recall that an integer matrix with determinant $\pm 1$ is called a unimodular matrix. Suppose $A$ is a unimodular matrix and $\bb$ is an integer vector. Explain why the solution $\bx$ to $A\bx = \bb$ is an integer matrix.
<!-- eng end -->

##### Exercise 3

令

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
$$

且 $\bb = (1,0,1)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
$$

and $\bb = (1,0,1)$.
<!-- eng end -->

##### Exercise 3(a)

利用列運算將 $A$ 消成 $I_3$、
並記錄每一步的列運算。

<!-- eng start -->
Apply row operations to $A$ and record each step of how it becomes an identity matrix.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
\\
\xrightarrow{\rho_3:\rho_3-\rho_2}
\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
0 & 1 & 5
\end{bmatrix}
\\
\xrightarrow{\rho_2:\rho_2-\rho_1}
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 1 & 5
\end{bmatrix}
\\
\xrightarrow{\rho_3:\rho_3-\rho_2}
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 0 & 2
\end{bmatrix}
\\
\xrightarrow{\rho_3:\frac{1}{2}\rho_3}
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 0 & 1
\end{bmatrix}
\\
\xrightarrow{\rho_2:\rho_2-3\rho_3}
\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\\
\xrightarrow{\rho_1:\rho_1-\rho_2-\rho_3}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}.
$$

##### Exercise 3(b)

對 $A_2$ 進行與上一題相同的列運算，求其得到的結果 $R$。

<!-- eng start -->
Apply the row operations you found in the previous problem to $A_2$ and find the resulting matrix $R$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
$$
A_2 = \begin{bmatrix}
1 & 1 & 1 \\
1 & 0 & 4 \\
1 & 1 & 9
\end{bmatrix}
\\
\xrightarrow{\rho_3:\rho_3-\rho_2}
\begin{bmatrix}
1 & 1 & 1 \\
1 & 0 & 4 \\
0 & 1 & 5
\end{bmatrix}
\\
\xrightarrow{\rho_2:\rho_2-\rho_1}
\begin{bmatrix}
1 & 1 & 1 \\
0 & -1 & 3 \\
0 & 1 & 5
\end{bmatrix}
\\
\xrightarrow{\rho_3:\rho_3-\rho_2}
\begin{bmatrix}
1 & 1 & 1 \\
0 & -1 & 3 \\
0 & 2 & 2
\end{bmatrix}
\\
\xrightarrow{\rho_3:\frac{1}{2}\rho_3}
\begin{bmatrix}
1 & 1 & 1 \\
0 & -1 & 3 \\
0 & 1 & 1
\end{bmatrix}
\\
\xrightarrow{\rho_2:\rho_2-3\rho_3}
\begin{bmatrix}
1 & 1 & 1 \\
0 & -4 & 0 \\
0 & 1 & 1
\end{bmatrix}
\\
\xrightarrow{\rho_1:\rho_1-\rho_2-\rho_3}
\begin{bmatrix}
1 & 4 & 0 \\
0 & -4 & 0 \\
0 & 1 & 1
\end{bmatrix}.
$$
Thus,
$$
R=\begin{bmatrix}
1 & 4 & 0 \\
0 & -4 & 0 \\
0 & 1 & 1
\end{bmatrix}.
$$

##### Exercise 3(c)

求一個矩陣 $E$ 使得 $EA = I_3$ 且 $EA_2 = R$。

<!-- eng start -->
Find a matrix $E$ such that $EA = I_3$ and $EA_2 = R$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
Since we obtain $R$ from $A_2$ by doing the row operations which are same as how we obtain $I_3$ from $A$.

Therefore, $E$ is composed of the elementary matrix that doing the row operations.
Thus,
$$
E=
\begin{bmatrix}
1 & -1 & -1 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & -3 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 &\frac{1}{2}
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1
\end{bmatrix}\\
=\begin{bmatrix}
3 & -3 & 1 \\
-\frac{5}{2} & 4 & -\frac{3}{2} \\
\frac{1}{2} & -1 &\frac{1}{2}
\end{bmatrix}.
$$

##### Exercise 4

克拉瑪公式也可以由伴隨矩陣及餘因子矩陣的性質得到。
依照以下步驟給出克拉瑪公式的另一種證明。
令 $A$ 為一 $n\times n$ 可逆矩陣、而 $\bb\in\mathbb{R}^n$。
令 $\bx = (x_1,\ldots, x_n)$ 為 $A\bx = \bb$ 的解。

<!-- eng start -->
Cramer's rule can also be obtained from the adjugate and the cofactors. Use the given instructions to come up with an alternative proof of the Cramer's rule. Let $A$ be an $n\times n$ matrix and $\bb\in\mathbb{R}^n$. Let $\bx = (x_1,\ldots, x_n)$ be the solution to $A\bx = \bb$.
<!-- eng end -->

##### Exercise 4(a)

令 $\bc_j$ 為 $A\cof$ 的第 $j$ 行。
說明 $\det(A_j) = \inp{\bb}{\bc_j}$。

<!-- eng start -->
Let $\bc_j$ be the $j$-th column of $A\cof$. Explain why $\det(A_j) = \inp{\bb}{\bc_j}$.
<!-- eng end -->

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

<!-- eng start -->
Use the facts $A\adj = (A\cof)\trans = \det(A)A^{-1}$ to explain why $x_j = \frac{1}{\det(A)}\inp{\bb}{\bc_j} = \frac{\det(A_j)}{\det(A)}$.
<!-- eng end -->

##### Exercise 5

令

$$
A = \begin{bmatrix}
1 & 1 \\
0 & 1 \\
1 & 0
\end{bmatrix}
$$

且 $\bb = (3,1,1)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 \\
0 & 1 \\
1 & 0
\end{bmatrix}
$$

and $\bb = (3,1,1)$。
<!-- eng end -->

##### Exercise 5(a)

寫出所有 $A$ 的 $2\times 2$ 子矩陣，並計算它們的行列式值。
是否全部為 $\pm 1$？

<!-- eng start -->
Find all $2\times 2$ submatrices of $A$ and calculate their determinants. Are they all $\pm 1$?
<!-- eng end -->

##### Exercise 5(b)

畫出 $A\bx \leq \bb$ 的圖形，
並計算圖形中的所有頂點。
（這裡 $\bx = (x,y)$
而 $A\bx \leq \bb$ 的意思是 $\bb - A\bx$ 每一項都大於等於 $0$。）

<!-- eng start -->
Draw the region for $A\bx \leq \bb$ and find the coordinates of each of the vertices.
(Here $\bx = (x,y)$ and $A\bx \leq \bb$ means each entry of $\bb - A\bx$ is greater than or equal to $0$.
<!-- eng end -->

##### Exercise 5(c)

利用 (a) 小題的結果
說明為什麼 (b) 小題算出來的頂點都是格子點（座標都是整數）。

<!-- eng start -->
Use Problem (a) to explain why the vertices in problem (b) are all on grid points (points with integer coordinates).
<!-- eng end -->

##### Remark

一個整數矩陣 $A$ 如果
所有的 $k\times k$ 子矩陣其行列式值皆為 $0,1,-1$，
則稱其為**全么模矩陣（totally unimodular）**。

而當 $A$ 是全么模矩陣且 $\bb$ 是整數向量時

$$
\begin{aligned}
A\bx &\leq \bb \\
\bx &\geq \bzero
\end{aligned}
$$

所圍出的圖形，其頂點都會是格子點。

這表示在做線性規劃的時候，所求出來的最佳解都會是整數。

<!-- eng start -->
An integer matrix $A$ whose $k\times k$ submatrices all have determinant values in $0$, $1$, or $-1$ is called a **totally unimodular** matrix.

Suppose $A$ is a totally unimodular matrix and $\bb$ is an integer vector. Then the region defined by

$$
\begin{aligned}
A\bx &\leq \bb \\
\bx &\geq \bzero
\end{aligned}
$$

has all its vertices on grid points.

This means the result of such a linear programming problem is composed of integers.
<!-- eng end -->