Cramer's rule
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
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.
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
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.
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
### 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)
對所有 $j = 1,\ldots, n$,寫下 $A_j$ 並求出 $\det A_j$。
For each $j = 1,\ldots, n$, find $A_j$ and $\det A_j$.
計算 $\det(A)$ 並用克拉瑪公式求出 $A\bx = \bb$ 的解 $\bx$。
Find $\det(A)$ and use Cramer's rule to find the solution $\bx$ to $A\bx = \bb$.
根據拉普拉斯展開,計算行列式值時只會用到加法和乘法。
所以一個整數矩陣的行列式值也會是整數、
而一個有理數矩陣的行列式值也會是有理數。
利用這個性質回答以下問題。
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.
說明若 $A$ 是一個可逆有理數矩陣、
而 $\bb$ 是一個有理數向量,
則 $A\bx = \bb$ 的解 $\bx$ 也會是有理數向量。
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.
找一個可逆的整數矩陣 $A$、以及一個整數向量 $\bb$,
使得 $A\bx = \bb$ 的解 $\bx$ 並不是整數向量。
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.
回顧一個整數方陣如果行列式值為 $\pm 1$,
則被稱為么模矩陣 。
說明若 $A$ 是一個么模矩陣、
而 $\bb$ 是一個整數向量,
則 $A\bx = \bb$ 的解 $\bx$ 也會是整數向量。
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.
令
$$ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix} $$且 $\bb = (1,0,1)$。
Let
$$ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix} $$and $\bb = (1,0,1)$.
利用列運算將 $A$ 消成 $I_3$、
並記錄每一步的列運算。
Apply row operations to $A$ and record each step of how it becomes an identity matrix.
對 $A_2$ 進行與上一題相同的列運算,求其得到的結果 $R$。
Apply the row operations you found in the previous problem to $A_2$ and find the resulting matrix $R$.
求一個矩陣 $E$ 使得 $EA = I_3$ 且 $EA_2 = R$。
Find a matrix $E$ such that $EA = I_3$ and $EA_2 = R$.
克拉瑪公式也可以由伴隨矩陣及餘因子矩陣的性質得到。
依照以下步驟給出克拉瑪公式的另一種證明。
令 $A$ 為一 $n\times n$ 可逆矩陣、而 $\bb\in\mathbb{R}^n$。
令 $\bx = (x_1,\ldots, x_n)$ 為 $A\bx = \bb$ 的解。
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$.
令 $\bc_j$ 為 $A\cof$ 的第 $j$ 行。
說明 $\det(A_j) = \inp{\bb}{\bc_j}$。
Let $\bc_j$ be the $j$-th column of $A\cof$. Explain why $\det(A_j) = \inp{\bb}{\bc_j}$.
利用 $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)}$。
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)}$.
令
$$ A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix} $$且 $\bb = (3,1,1)$。
Let
$$ A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix} $$and $\bb = (3,1,1)$。
寫出所有 $A$ 的 $2\times 2$ 子矩陣,並計算它們的行列式值。
是否全部為 $\pm 1$?
Find all $2\times 2$ submatrices of $A$ and calculate their determinants. Are they all $\pm 1$?
畫出 $A\bx \leq \bb$ 的圖形,
並計算圖形中的所有頂點。
(這裡 $\bx = (x,y)$
而 $A\bx \leq \bb$ 的意思是 $\bb - A\bx$ 每一項都大於等於 $0$。)
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$.
利用 (a) 小題的結果
說明為什麼 (b) 小題算出來的頂點都是格子點(座標都是整數)。
Use Problem (a) to explain why the vertices in problem (b) are all on grid points (points with integer coordinates).
一個整數矩陣 $A$ 如果
所有的 $k\times k$ 子矩陣其行列式值皆為 $0,1,-1$,
則稱其為全么模矩陣(totally unimodular)。
而當 $A$ 是全么模矩陣且 $\bb$ 是整數向量時
$$ \begin{aligned} A\bx &\leq \bb \\ \bx &\geq \bzero \end{aligned} $$所圍出的圖形,其頂點都會是格子點。
這表示在做線性規劃的時候,所求出來的最佳解都會是整數。
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.