411-Cramer's-rule

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

In [ ]:

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.

$$ \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

Exercise 1¶

執行以下程式碼。

Run the code below.

In [ ]:

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

For each $j = 1,\ldots, n$, find $A_j$ and $\det A_j$.

Exercise 1(b)¶

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

Find $\det(A)$ and use Cramer's rule to find the solution $\bx$ to $A\bx = \bb$.

Exercise 2¶

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

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.

Exercise 2(a)¶

說明若 $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.

Exercise 2(b)¶

找一個可逆的整數矩陣 $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.

Exercise 2(c)¶

回顧一個整數方陣如果行列式值為 $\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.

Exercise 3¶

令

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

Exercise 3(a)¶

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

Apply row operations to $A$ and record each step of how it becomes an identity matrix.

Exercise 3(b)¶

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

Apply the row operations you found in the previous problem to $A_2$ and find the resulting matrix $R$.

Exercise 3(c)¶

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

Find a matrix $E$ such that $EA = I_3$ and $EA_2 = R$.

Exercise 4¶

克拉瑪公式也可以由伴隨矩陣及餘因子矩陣的性質得到。
依照以下步驟給出克拉瑪公式的另一種證明。
令 $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$.

Exercise 4(a)¶

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

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

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

Exercise 5¶

令

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

Exercise 5(a)¶

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

Find all $2\times 2$ submatrices of $A$ and calculate their determinants. Are they all $\pm 1$?

Exercise 5(b)¶

畫出 $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$.

Exercise 5(c)¶

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

Use Problem (a) to explain why the vertices in problem (b) are all on grid points (points with integer coordinates).

Remark¶

一個整數矩陣 $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