107.08.13 線性代數 Inversion

欸豆，最近可能會整理一些之前的上課筆記 (線代、計理、OS、compiler....)
主要是想把當下有多記錄的技巧用比較好懂的方式寫出來
所以可能沒有很嚴謹也沒有很完整 QuQ
然後 Rust 系列斷有點久，我盡量不耍廢 QuQ

矩陣可逆性 (Matrix Inversion)

定義：
對於 nxn 的矩陣 $A$ 若存在一個 nxn 的矩陣 $B$，使得 $AB = BA = I$
則稱 $A$ 為可逆矩陣 (invertible)、也為非奇異矩陣 (nonsingular)
其中 $I$ 為單位矩陣 (identity matrix)、$B$ 稱作 $A$ 的逆矩陣 (inverse of A) 記作 $A^{-1}$

---

定理：若 $A$ 可逆，則 $A^{-1}$ 唯一

證明：
假設 $A$ 有兩個相異的逆矩陣 $B$、$C$
則 $AB = I$、$AC = I$
使得 $B = BI = B(AC) = (BA)C = IC = C$
與假設矛盾，故 $A$ 僅有唯一一個逆矩陣

---

定理：若 $A$ 可逆，則 $Ax = b$ 的有唯一解 $x = A^{-1}b$ 

證明：
$Ax = b \Leftrightarrow A^{-1}Ax = A^{-1}b \Leftrightarrow Ix = A^{-1}b \Leftrightarrow x = A^{-1}b$

---

定理：若 $Ax = 0$ 有非零解 $x$ 存在，則 $A$ 不為可逆

證明：
假設 $A$ 可逆下 $x$ 存在非零解
$Ax = 0 \Rightarrow A^{-1}Ax = A^{-1}0 \Rightarrow x = 0$
因為 $x$ 必為零解所以矛盾，故假設錯誤，即 $A$ 不可逆

---

定理：若對角矩陣 (diagonal matrix) 可逆，則對角線上元素皆不為 $0$

證明：(107.08.28 更正)
可以利用上一個定理證明
對角矩陣 $A = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{nn} \\ \end{bmatrix}$

假設 $a_{11} = 0$，則可使得 $Ax = 0$ 的 $x$ 存在非零解，如下 ${\color{Blue}\alpha}$ 可不為 $0$
$\begin{bmatrix} {\color{Red} 0 } & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{nn} \\ \end{bmatrix} \begin{bmatrix} {\color{Blue}\alpha} \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix}$

由上個定理可知 $Ax = 0$ 存在非零解，則 $A$ 不可逆，故矛盾，因此 $a_{11}$ 不可為 $0$
同理可知，$a_{ii} \neq 0, \forall 1 \leqslant i \leqslant n$

Note：若對角矩陣 $A$ 可逆
$A = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{nn} \\ \end{bmatrix}$ 則逆矩陣 $A^{-1} = \begin{bmatrix} \dfrac 1 {a_{11}} & 0 & \cdots & 0 \\ 0 & \dfrac 1 {a_{22}} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \dfrac 1 {a_{nn}} \\ \end{bmatrix}$
$a_{11}$ ~ $a_{nn}$ 皆不為 $0$

---

定理：若 $A$、$B$ 為可逆矩陣，則 $AB$ 亦為可逆，且 $(AB)^{-1} = B^{-1}A^{-1}$

證明：
$(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1} = AA^{-1} = I$
所以 $B^{-1}A^{-1}$ 是 $AB$ 的逆矩陣
延伸：
$(A_{1}A_{2} \cdots A_{n})^{-1} =  A_{n}^{-1} \cdots A_{2}^{-1}A_{1}^{-1}$

---

使用 Gauss-Jordan Elimination 求逆矩陣

Gauss-Jordan Elimination 為求方程式解的列運算 (elementary row operations)
Gauss Elimination 為使用 forward elimination 求出上三角矩陣 (strict
triangular form)
Gauss-Jordan Elimination 則包含 back substitution 將左方矩陣進一步化簡成單位矩陣

舉例：
$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & 2 & 2 \end{bmatrix}$ 求 $A^{-1}$

過程：
從定義知 $AA^{-1} = I$，把 $A^{-1}$ 拆作三欄方便說明
 $A\begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} e_1 & e_2 & e_3 \end{bmatrix}$

則可等價於下方三個方程式，且所求 $A^{-1}$ 為求出 $(x_1 , x_2 , x_3)$ 的向量解
$\begin{cases} Ax_1 = e_1 \Rightarrow  A^{-1}Ax_1 = x_1 = A^{-1}e_1\\ Ax_2 = e_2 \\ Ax_3 = e_3 \end{cases}$

求解可利用增廣矩陣 (augmented matrix) 與列運算把左邊化簡成單位矩陣來同時解三個方程式
$\left[\begin{array}{ccc|ccc} 2 & -1 & 0 & 1 & 0 & 0 \\ -1 & 2 & -1 & 0 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \\ \end{array} \right] \Rightarrow \left[\begin{array}{ccc|ccc} 2 & -1 & 0 & 1 & 0 & 0 \\ 0 & 2\over 3 & -1 & 1\over 2 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \\ \end{array} \right] \Rightarrow \left[\begin{array}{ccc|ccc} 2 & -1 & 0 & 1 & 0 & 0 \\ 0 & 2\over 3 & -1 & 1\over 2 & 1 & 0 \\ 0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\ \end{array} \right] \Rightarrow$

$\left[\begin{array}{ccc|ccc} 2 & -1 & 0 & 1 & 0 & 0 \\ 0 & 2\over 3 & 0 & 3\over 4 & 3\over 2 & 3\over 4 \\ 0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\ \end{array} \right] \Rightarrow \left[\begin{array}{ccc|ccc} 2 & 0 & 0 & 3\over 2 & 1 & 1\over 2 \\ 0 & 2\over 3 & 0 & 3\over 4 & 3\over 2 & 3\over 4 \\ 0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\ \end{array} \right] \Rightarrow \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 3\over 4 & 1\over 2 & 1\over 4 \\ 0 & 1 & 0 & 1\over 2 & 1 & 1\over 2 \\ 0 & 0 & 1 & 1\over 4 & 1\over 2 & 3\over 4 \\ \end{array} \right]$

所求 $A^{-1}$ 即為 $\begin{bmatrix} 3\over 4 & 1\over 2 & 1\over 4 \\ 1\over 2 & 1 & 1\over 2\\ 1\over 4 & 1\over 2 & 3\over 4 \end{bmatrix}$

詳細原理如下
$\left[\begin{array}{c|c} A & I \\ \end{array} \right] \overset{G.J.E.}{\Rightarrow} \left[\begin{array}{c|c} A^{-1}A & A^{-1}I \\ \end{array} \right]  = \left[\begin{array}{c|c} I & A^{-1} \\ \end{array} \right]$

Q: 為何可以合併運算?
A: 因為左方矩陣化為單位矩陣的列運算相同，且列運算在向量間不會互相干擾
以 $x_1$ 向量 $(a, b, c)$ 來看
$\left[\begin{array}{ccc|c} 2 & -1 & 0 & 1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & 0 \\ \end{array} \right] \overset{G.J.E.}{\Rightarrow} \left[\begin{array}{ccc|c} 1 & 0 & 0 & 3\over 4 \\ 0 & 1 & 0 & 1\over 2 \\ 0 & 0 & 1 & 1\over 4 \\ \end{array} \right]$

可得 $\begin{cases} 1a = {3\over 4} \\ 1b = {1\over 2} \\ 1c = {1\over 4} \end{cases} \Rightarrow x_1 = (a, b, c) = \begin{bmatrix} 3\over 4 \\ 1\over 2 \\ 1\over 4 \end{bmatrix}$，$x_2$、$x_3$ 同理


參考資料：
Linear Algebra (Chapter 1: Matrices and Systems of Equations) Chao-Chun Chen (NCKU)