# 考研筆記 - 線性代數 (偉文高成)
###### tags: `考研` `線性代數` `數學`
###### 撰寫時間 : 2022/08/01 ~ 2022/09/11

## ch1 矩陣運算
### 綱要
- 矩陣乘法為將矩陣$\mathbf{A}$中row vector與矩陣$\mathbf{B}$中column vector做內積
- 任意函數表示為赫米特矩陣與斜赫米特矩陣之和
- 正交矩陣定義為行與列向量兩兩正交
- 求解行列式 - 使用列(行)展開式與行列式的性質
- Gauss-Jordan消去法化簡為reduced row echelon form
- 反矩陣求法 - 伴隨矩陣法、Gauss-Jordan消去法
- 將Gauss消去法執行步驟化為列基本矩陣求得LU分解

---
### 矩陣介紹
矩陣的形式為
$$
\mathbf{A}_{m \times n} = [a_{m \times n}] =
\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{bmatrix}
$$
下標為矩陣的index(白話來說就是地址)，$\mathbf{A}_{m \times n}$第一個數字$m$代表row個數，第二個數字$n$代表column數目。可以將上述矩陣"看作"是$m$個row vector(row matrix) $\mathbf{A}_i'$或是$n$個column vector(column matrix) $\mathbf{A}_i$。
$$
\mathbf{A}_{m \times n}
= \left[\begin{array}{ccc}
- & \mathbf{A}_1' & -\\
- & \mathbf{A}_2' & -\\
& \vdots & \\
- & \mathbf{A}_m' & -\\
\end{array}\right]
= \left[\begin{array}{cccc}
\mid & \mid & & \mid\\
\mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_n\\
\mid & \mid & & \mid\\
\end{array}\right]
$$

---
### 矩陣類型定義
定義方陣(square matrix)為row與column數相同的矩陣；上三角矩陣(upper triangular matrix)為對角線以下的數字皆為0；下三角矩陣(low triangular matrix)為對角線以上的數字皆為0；對角線矩陣(diagonal matrix)是只有對角線上數字不全為0，其餘數字皆為0的方陣；單位矩陣(identity matrix)為對角線數字皆為1，其餘數字皆為0的方陣，屬於對角線矩陣的一種；零矩陣(zero matrix)所有entry全為0的矩陣；主子方陣(principal square-matrix)，方陣去掉相同數量與位置的row或是column所得的子方陣。

---
### 矩陣運算
矩陣相等定義為矩陣$\mathbf{A}, \mathbf{B}$中每個entry都要相同$a_{ij} = b_{ij}$；轉置(transpose)為將row變成column，把column變成row，表示為$a_{ij} \overset{T}{\longrightarrow} a_{ji}$；共軛(conjugate)為對entry上所有元素取共軛；只有在取共軛加上轉置才有物理意義(對實數矩陣來說可以簡化為轉置)，共軛轉置合稱為adjoint operator，標記如下
$$
\overline{\mathbf{A}}^T \equiv A^H = A^*
$$
共軛轉置重要性質如下
1. $(\alpha \mathbf{A})^H = \overline{\alpha} \mathbf{A}^H$
2. $(\mathbf{A} \pm \mathbf{B})^H = \mathbf{A}^H \pm \mathbf{B}^H$
3. $(\mathbf{A}^H)^H = A$
4. $(\mathbf{A} \mathbf{B})^H = \mathbf{B}^H \mathbf{A}^H$

矩陣加法為將兩個元素個別entry相加；矩陣純量乘法需要將**所有entry**都乘以純量；兩矩陣的乘法假設為$\mathbf{C} = \mathbf{A} \mathbf{B}$，首先要確保矩陣$\mathbf{A}_{m \times n}$中column數目與矩陣$\mathbf{B}_{n \times p}$的row數目相同，稱為conformable，兩矩陣乘法為將矩陣$\mathbf{A}$中row vector與矩陣$\mathbf{B}$中column vector做內積，記為
$$
c_{ij} = a_{i1} b_{1j} + a_{i2} b_{2j} + \cdots + a_{in}b_{nj} = \sum^n_{k = 1} a_{ik} b_{kj}
$$
矩陣乘法轉置重要性質如下
1. $(\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC})$，$(\mathbf{A} + \mathbf{B})\mathbf{C} = \mathbf{AC} + \mathbf{BC}$，相乘具有結合律與分配律。
2. $\mathbf{A} \mathbf{B} \neq \mathbf{B} \mathbf{A}$，不可任意對調順序，無交換律，但在兩種情況下會成立$\mathbf{A},\mathbf{B}$為對角線矩陣或是$\mathbf{A} \mathbf{I} = \mathbf{I} \mathbf{A} = \mathbf{A}$。
3. 若$\mathbf{B} = \mathbf{C}$，則$\mathbf{A} \mathbf{B} = \mathbf{A} \mathbf{C}$，反向不成立，反向成立的條件為$\mathbf{A}$可逆，等價於非奇異矩陣(nonsingular matrix)、行列式不為零$\det(\mathbf{A}) \neq0$與$\mathbf{A}^{-1}$存在。

---
### 特殊矩陣
1. 實對稱(real symmetric)矩陣，定義為$\mathbf{A} = \mathbf{A}^T$<br>
即為entry中$a_{ji} = a_{ij}$，對角線兩側元素兩兩對稱"相等"，類似"偶函數"，性質為$(\mathbf{A}^n)^T = (\mathbf{A}^T)^n, n \in N$；$\mathbf{A}$是實對稱矩陣，$\mathbf{A}^2$亦為實對稱矩陣；$(\mathbf{AB})^T = \mathbf{B}^T \mathbf{A}^T$。
2. 赫米特(Hermitian)矩陣，定義為$\mathbf{A} = \overline{\mathbf{A}}^T = A^H = A^*$<br>
將實對稱矩陣擴展至複數系，對角線兩側元素兩兩對稱"共軛"，則對角線元素必為實數。
3. 斜實對稱(real skew-symmetric)矩陣，定義為$\mathbf{A} = -\mathbf{A}^T$<br>
即為entry中$a_{ji} = -a_{ij}$，對角線元素必為$0$，類似"奇函數"。
4. 斜赫米特(skew-Hermitian)矩陣，定義為$\mathbf{A} = -\overline{\mathbf{A}}^T = -A^H = -A^*$<br>
將反實對稱矩陣擴展至複數系，對角線元素必為虛數。

參照[2022上一段日記 03/06(日)](https://hackmd.io/@HsuChiChen/2022-log-2#03/06(日))，都知道任意函數可以表示為偶函數和奇函數的合，同理任意矩陣也可以表示為對稱(赫米特)矩陣與斜對稱(赫米特)矩陣的和。
$$
\mathbf{A} = \mathbf{B} + \mathbf{C},\; \text{where } \mathbf{B} = \underbrace{\frac{\mathbf{A} + \mathbf{A}^H}{2}}_{\text{Hermitian}},\; \mathbf{C} = \underbrace{\frac{\mathbf{A} - \mathbf{A}^H}{2}}_{\text{skew-Hermitian}}
$$
5. 正交矩陣(orthogonal matrix)，定義為$\mathbf{Q}^T \mathbf{Q} = \mathbf{I}$。<br>
- (等價條件)性質一 - $\mathbf{A}$的行向量(或列向量)是一組兩兩單位正交(orthonormal)向量。行向量兩兩單位正交證明如下
$$
\begin{align*}
\mathbf{Q}^H \mathbf{Q} &=
\begin{bmatrix} \mathbf{Q}_1, & \mathbf{Q}_2, & \ldots, & \mathbf{Q}_n \end{bmatrix}^H
\begin{bmatrix} \mathbf{Q}_1, & \mathbf{Q}_2, & \ldots, & \mathbf{Q}_n \end{bmatrix}\\
&= \begin{bmatrix} \mathbf{Q}_1\\ \mathbf{Q}_2\\ \vdots\\ \mathbf{Q}_n \end{bmatrix}
\begin{bmatrix} \mathbf{Q}_1, & \mathbf{Q}_2, & \ldots, & \mathbf{Q}_n \end{bmatrix}\\
&= \begin{bmatrix}
\mathbf{Q}_1^T\mathbf{Q}_1 & \mathbf{Q}_1^T\mathbf{Q}_2 & \cdots & \mathbf{Q}_1^T \mathbf{Q}_n\\
\mathbf{Q}_2^T\mathbf{Q}_1 & \mathbf{Q}_2^T\mathbf{Q}_2 & \cdots & \mathbf{Q}_2^T \mathbf{Q}_n\\
\vdots & \vdots & \ddots & \vdots\\
\mathbf{Q}_n^T \mathbf{Q}_1 & \mathbf{Q}_n^T \mathbf{Q}_2 & \cdots &\mathbf{Q}_n^T \mathbf{Q}_n
\end{bmatrix}\\
&= \begin{bmatrix}
1 & 0 & \cdots & 0\\
0 & 1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & 1
\end{bmatrix} = \mathbf{I}_n
\end{align*}
$$
其中對角線$\mathbf{Q}_n^T \mathbf{Q}_n = <\mathbf{Q}_n, \mathbf{Q}_n> = \| \mathbf{Q}_n \| = 1$，為自己與自己做內積，代表是行向量的長度，單位向量長度是1；而其他entry是不同行向量做內積，由於行向量兩兩正交，故內積為0，得證。列向量可同理得證。
- (等價條件)性質二 - $\mathbf{Q}^T = \mathbf{Q}^{-1}$，此性質**可大幅簡化反矩陣的運算**。
$$
\begin{cases}
\mathbf{Q} \mathbf{Q}^T = \mathbf{Q}^T \mathbf{Q} = \mathbf{I}\\
\mathbf{Q} \mathbf{Q}^{-1} = \mathbf{Q}^{-1} \mathbf{Q} = \mathbf{I}
\end{cases} \Rightarrow \mathbf{A}^T = \mathbf{A}^{-1}
$$
- 性質三 - $|\mathbf{Q}| = \pm 1$，行列式幾何意義上是有向體積。
$$
\mathbf{Q}^T \mathbf{Q} = \mathbf{I} \Rightarrow |\mathbf{Q}^T \mathbf{Q}| = |\mathbf{Q}^T||\mathbf{Q}| = |\mathbf{Q}|^2 =1 \Rightarrow |\mathbf{Q}| = \pm1
$$
- 性質四 - 實特徵值是$1$或是$-1$。
$$
\begin{align*}
&\mathbf{Q} \mathbf{v} = \lambda \mathbf{v}\\
\Rightarrow\; & <\mathbf{Q} \mathbf{v}, \mathbf{Q} \mathbf{v}> = <\lambda \mathbf{v}, \lambda \mathbf{v}>\\
\Rightarrow\; & (\mathbf{Q} \mathbf{v})^T (\mathbf{Q} \mathbf{v}) = \lambda^2 < \mathbf{v}, \mathbf{v}>\\
\Rightarrow\; & \mathbf{v}^T \underbrace{\mathbf{Q}^T \mathbf{Q}}_{= \mathbf{I}} \mathbf{v} = \lambda^2 \mathbf{v}^T \mathbf{v}\\
\Rightarrow\; & \lambda^2 = 1 \Rightarrow \lambda = \pm 1
\end{align*}
$$
6. 么正矩陣(unitary matrix)，定義為$\mathbf{U}^H{U} = \mathbf{U} \mathbf{U}^H = \mathbf{I}$。<br>
正交矩陣擴展至複數系。
7. 正規矩陣(nomal matrix)，定義為$\mathbf{A}^H \mathbf{A} = \mathbf{A} \mathbf{A}^H$。<br>
代表$\mathbf{A}$與$\mathbf{A}^H$具有交換率，Hermitian, skew-Hermitian, unitary矩陣都是nomal matrix。
8. 冪零矩陣(nilpotent matrix)，定義為$\exists k \in N \ni \mathbf{N}^k = \mathbf{0}$。<br>
從英文字根上ni-為null，代表0矩陣，potent為potential，代表潛能，意思為有成為0矩陣的潛能；中文上代表乘上$k$這個次冪就會變為0矩陣。

---
### 行列式
行列式(determininat)為方陣的"數值"，只有方陣才具有行列式，記為$\det(\mathbf{A}), |\mathbf{A}|$，二階方陣和三階方陣可以公式速解，但四階以上方陣沒有速解技巧，需要找出0最多的行或是列，根據該列做列展開或是根據該行做行展開。
- Laplace列展開式
$$
|\mathbf{A}| = \sum^n_{j = 1} a_{ij} (-1)^{i + j} M_{ij} = \sum^n_{j = 1} a_{ij} \cdot \mathrm{cof}(a_{ij})
$$
其中$M_{ij}$稱為$\mathbf{A}$的子行列式(minor)，為將$\mathbf{A}$去除第$i$列與第$j$行所遺留的行列式值；再乘上$(-1)^{i + j}$以行列index相加的結果(口訣 : 正負相間)的數值稱為餘因子(confactor)。行展開式同理為$|\mathbf{A}| = \sum^n_{i = 1} a_{ij} (-1)^{i + j} M_{ij}$，由此可知對行列式來說行跟列的地位相等，許多性質只要討論列即可。

行列式性質如下
1. $|\mathbf{A}| = |\mathbf{A}^T|, |\overline{\mathbf{A}}| = \overline{|\mathbf{A}|}$，行列式的行展開與列展開相同。
2. $\mathbf{A}$任兩行(兩列)對調，行列式值為原來的$-1$倍，此為Gauss消去法第1種操作。
3. $\mathbf{A}$任一列(一行)的數字全部乘上$k$，行列式也是乘上$k$倍，此為Gauss消去法第2種操作。可以得推論欲求$\mathbf{A}$可將共同因式提出來；矩陣純量乘法每一個entry都要乘，故提出共同因式需乘上方陣的大小$|k\mathbf{A}| = k^n|\mathbf{A}|, |-\mathbf{A}| = (-1)^n|\mathbf{A}|$。
4. $\mathbf{A}$任一列(行)的倍數加到每一列(行)後，行列式不變，此為Gauss消去法第3種操作。
5. $\mathbf{A}$任兩列(行)的數字成比例或是任一列(行)的數字全為0，則$|\mathbf{A}| = 0$。
6. **三角矩陣的行列式為對角線元素相乘**，$|\mathbf{A}| = a_{11} \cdot a_{22} \cdots a_{nn}$，可使用數學歸納法證明。
7. $|\mathbf{AB}| = |\mathbf{B}||\mathbf{A}| = |\mathbf{A}||\mathbf{B}| = |\mathbf{A}\mathbf{B}|$，但$\mathbf{AB} = \mathbf{BA}$不一定相等
8. 根據7點結論，推導反矩陣的行列值為$\mathbf{A} \mathbf{A}^{-1} = \mathbf{I} \Rightarrow |\mathbf{A}||\mathbf{A}^{-1}| = \mathbf{I} = 1 \Rightarrow |\mathbf{A}^{-1}| = \frac{1}{|\mathbf{A}|}$。

行列式3階以下可使用公式速解，而4階以上行列式求法可使用性質2、性質4(類似高斯消去法，需要注意性質2行列式會正負變號)，將矩陣整理為上三角矩陣，再由行列式性質6求解。

根據矩陣類型分成以下5大題型
1. 若$\mathbf{A}$所有列元素(行)元素和皆相同，解題步驟是將所有列(行)加至首項，利用性質3提出共同因式，再利用性質2、性質4想辦法化簡為上三角矩陣。
2. 若$\mathbf{A}$為正交矩陣行列式為$\det(\mathbf{A}) = \pm 1$；么正矩陣行列式為$|\det(\mathbf{A})| = 1$，代表行列式落在複數平面單位圓上的點。
3. Vandermonde's矩陣(范德蒙矩陣)，常見於數值分析的內插，范德蒙矩陣行列式使用數學歸納法證明，結論為
$$
\begin{align*}
&\det
\begin{bmatrix}
1 & x_1 & x_1^2 & \cdots & x_1^{n - 1}\\
1 & x_2 & x_2^2 & \cdots & x_2^{n - 1}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & x_n & x_n^2 & \cdots & x_n^{n - 1}
\end{bmatrix}\\
&= (x_2 - x_1)(x_3 - x_1)(x_4 - x_1) \ldots (x_n - x_1)\\
& \qquad\qquad\quad\; (x_3 - x_2)(x_4 - x_2) \ldots (x_n - x_2)\\
& \qquad\qquad\qquad\qquad\qquad\qquad\qquad\! (x_n - x_{n - 1})\\
\end{align*}
$$
4. 經分割後的區塊矩陣- 0很多。
$$
\det \begin{bmatrix} \mathbf{A} & \mathbf{C}\\ \mathbf{0} & \mathbf{B} \end{bmatrix} = \det(\mathbf{A})\det(\mathbf{B}), \det \begin{bmatrix} \mathbf{A} & \mathbf{0}\\ \mathbf{D} & \mathbf{B} \end{bmatrix} = \det(\mathbf{A})\det(\mathbf{B})
$$
5. 經分割後的區塊矩陣- 重複性高，公式記憶口訣 : $a^2 - b^2 = (a + b)(a - b)$。
$$
\det \begin{bmatrix} \mathbf{A} & \mathbf{B}\\ \mathbf{B} & \mathbf{A} \end{bmatrix} = \det(\mathbf{A} + \mathbf{B}) \det(\mathbf{A} - \mathbf{B})
$$

---
### 矩陣基本列操作
**矩陣基本列操作**(elementary row operation)有3個，想法源自於解聯立方程組，解經矩陣基本列操作後不會改變。
1. **列交換** - 任兩列對調，記為$r_{ij}$。
2. **倍數** - 任一列乘上非0常數$k$，記為$r_i(k)$。
3. **列加法** - 任一列乘上常數倍加至另一列，記為$r_{ij}(k)$。

---
### 利用Gauss消去法化簡為列梯式
利用Gauss消去法化簡為列梯式(row echelon form)，使第一列pivot為1，將該列以下化為0，再來令第二列首項(leading entry)為1，一直持續化簡下去，若是某一列pivot為0，則需要做**列交換**才可繼續運算，因此不具有唯一性，從外觀看列梯式為上三角方陣。

由於列梯式不唯一，所以再使用Gauss-Jordan消去法，將Gauss消去法計算後的列梯式，**從最底下的列開始往上操作**，對pivot所在的行，此行其他數均為0，化簡為最簡列梯式(reduced row echelon form)，才具有唯一性。

---
### 反矩陣
只有方陣才具有反矩陣，若$\mathbf{A}$為$n$階方陣，且存在$n$階方陣$\mathbf{B}$使得
$$
\mathbf{BA} = \mathbf{AB} = \mathbf{I}_n
$$
則稱為$\mathbf{A}$為可逆(invertible)，$\mathbf{B}$為$\mathbf{A}$的反矩陣，記為$\mathbf{B} = \mathbf{A}^{-1}$。以下敘述等價
1. $\mathbf{A}$可逆
2. $\mathbf{A}^{-1}$存在
3. $\det(\mathbf{A}) \neq 0$
4. $\mathbf{A}$為nonsingular(非奇異)
> 給定$\mathbf{A}, \mathbf{B}$皆為$n$階方陣，若$\mathbf{AB} = \mathbf{I}$則$\mathbf{BA} = \mathbf{I}$，故對於可逆方陣而言，右反矩陣等於左反矩陣。證明如下
$$
\begin{align*}
\mathbf{AA}^{-1} = \mathbf{I} &\Rightarrow \mathbf{A}^{-1}(\mathbf{A}\mathbf{A}^{-1})\mathbf{A} = \mathbf{A}^{-1} \mathbf{(I)A}\\
&\Rightarrow \mathbf{A}^{-1} \mathbf{A}\mathbf{A}^{-1}\mathbf{A} = \mathbf{A}^{-1} \mathbf{A}\\
&\Rightarrow \mathbf{CC} = \mathbf{C} \quad\because \mathbf{C} \triangleq \mathbf{A}^{-1} \mathbf{A}\\
&\Rightarrow \mathbf{CC}\mathbf{C}^{-1} = \mathbf{C}\mathbf{C}^{-1}\\
&\Rightarrow \mathbf{CI} = \mathbf{I}\\
&\Rightarrow \mathbf{C} = \mathbf{I}\\
&\therefore \mathbf{A}^{-1} \mathbf{A} = \mathbf{I}
\end{align*}
$$
- **反矩陣求法一 - 伴隨矩陣法**<br>
解題上適合用於階數3的方陣以下，將伴隨矩陣，也就是"各個餘因子行列式"形成的矩陣做轉置，再除以矩陣$\mathbf{A}$的行列式。
$$
\mathbf{A}^{-1} = \frac{adj(\mathbf{A})}{|\mathbf{A}|} = \frac{[\mathrm{cof}(a_{ij})]^T}{|\mathbf{A}|}
$$
> 二階矩陣的反矩陣求法背公式 - 主對角線互換，次對角線變號，並除以行列式值。
$$
\begin{bmatrix} a & b\\ c & d \end{bmatrix}^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b\\ -c & a\end{bmatrix}
$$
- **反矩陣求法二 - Gauss-Jordan消去法**<br>
解題上適合用於階數4的方陣以上，列出以下左邊的矩陣形式，做Gauss-Jordan消去法得到右邊的矩陣形式
$$
[\mathbf{A} \mid \mathbf{I} ] \overset{\text{Gauss-Jordan elimination}}{\longrightarrow} [\mathbf{I} \mid \mathbf{A}^{-1}]
$$
- **反矩陣求法三 - 正交矩陣**$\mathbf{A}^{-1} = \mathbf{A}^H$<br>
根據正交矩陣性質快速轉置等於反矩陣快速求解。當欲求反矩陣的矩陣形式出現正負號交替出現，就有可能是正交，檢查正交
1. $<\mathbf{A}_i, \mathbf{A}_j>, i \neq j$，兩兩行向量是否正交。
2. $<\mathbf{A}_i, \mathbf{A}_i>$，自己與自己做內積，即為向量長度，檢查向量長度是否為1(單位)，若不是則需要經過適度scaling轉換為單位向量。

反矩陣性質如下
1. $(\mathbf{A}^{-1})^{-1} = \mathbf{A}$
2. $(\mathbf{AB})^{-1} = \mathbf{B}^{-1} \mathbf{A}^{-1}$，可與$(\mathbf{AB})^T = \mathbf{B}^T \mathbf{A}^T$對比。
3. $(\mathbf{A}^T)^{-1} = (\mathbf{A}^{-1})^T$
4. $(a\mathbf{A})^{-1} = \frac{\mathbf{A}^{-1}}{a}$

伴隨矩陣性質可根據定義$\mathbf{A}^{-1} = \frac{adj(\mathbf{A})}{|\mathbf{A}|}$自行移項推導，在此省略。

---
### 矩陣LU分解想法
將係數矩陣分解為上三角矩陣$\mathbf{U}$與下三角矩陣$\mathbf{L}$相乘，如此可以大幅簡化求解聯立方程式的複雜度。
$$
\begin{align*}
\mathbf{AX} = \mathbf{b} \Rightarrow\;& \mathbf{L} \underbrace{\mathbf{UX}}_{\mathbf{y}} = \mathbf{b}\\
\Rightarrow\;&
\begin{cases}
\mathbf{L} \mathbf{y} = \mathbf{b} & y_1 \to y_n \text{ forward}\\
\mathbf{U} \mathbf{x} = \mathbf{y} & x_n \to x_1 \text{ backward}
\end{cases}
\end{align*}
$$

---
### 矩陣LU分解
矩陣條件為**執行高斯消去法化簡為列梯式，不需要列交換**，將矩陣成$\mathbf{L}_0 \mathbf{U}$形式，其中$\mathbf{L}_0$代表對角線為1的下三角矩陣，步驟如下
1. 將$\mathbf{A} \overset{\text{Gauss elimination}}{\longrightarrow} \mathbf{U}$，為列梯式(屬於上三角矩陣)，並記錄執行步驟，記住**只可以使用第3個矩陣基本列操作 - 列加法**$r_{ij}(k)$，因為列交換$r_{ij}$會破壞下三角矩陣$\mathbf{L}$；倍數$r_i(k)$會破壞對角線為1的下三角矩陣$\mathbf{L}_0$。
2. 將執行步驟化為列基本矩陣$r(\mathbf{A}) = \mathbf{RA}$，如下式
$$
\begin{align*}
& (\mathbf{R}_k \cdots \mathbf{R}_2 \mathbf{R}_1) \mathbf{A} = \mathbf{U}\\
\Rightarrow\;& \mathbf{A} = \underbrace{\mathbf{R}_1^{-1} \mathbf{R}_2^{-1} \cdots \mathbf{R}_k^{-1}}_{\mathbf{L}_0} \; \mathbf{U}
\end{align*}
$$
其中列加法的列基本矩陣的逆矩陣求法很方便，只需要將對角線以外數值對調即可，$R_{ij}(k)^{-1} = R_{ij}(-k)$。

### 矩陣LDU分解
矩陣條件為**可逆**，將矩陣成$\mathbf{L}_0 \mathbf{D} \mathbf{U}_0$形式，將前一doolittle分解步驟中$\mathbf{U}$再做基本行操作 - 行加法$c_{ij}(k)$化簡為對角線矩陣$\mathbf{D}$，將執行步驟化為列基本矩陣$r(\mathbf{A}) = \mathbf{RA}$與行基本矩陣$c(\mathbf{A}) = \mathbf{AC}$，如下式
$$
\begin{align*}
& (\mathbf{R}_k \cdots \mathbf{R}_2 \mathbf{R}_1) \mathbf{A}(\mathbf{C}_1 \cdots \mathbf{C}_{j-1} \mathbf{R}_j) = \mathbf{D}\\
\Rightarrow\;& \mathbf{A} = \underbrace{\mathbf{R}_1^{-1} \mathbf{R}_2^{-1} \cdots \mathbf{R}_k^{-1}}_{\mathbf{L}_0} \; \mathbf{D} \;\underbrace{\mathbf{C}_j^{-1} \mathbf{C}_{j-1}^{-1} \cdots \mathbf{C}_1^{-1}}_{\mathbf{U}_0}
\end{align*}
$$
若再加上"矩陣是對稱且正定"的條件，則可繼續做Cholesky分解，$\mathbf{L}_0 \mathbf{D} \mathbf{U}_0 = \mathbf{L}_0 \mathbf{D} \mathbf{L}_0^T = \mathbf{L}\mathbf{L}^T$。

### PLU分解
LU分解的矩陣條件為**執行高斯消去法化簡為列梯式，不需要列交換**，若是需要列對調則要改使用PLU分解，將原始矩陣**乘上一個執行列交換的列基本矩陣**，在此稱為為排列矩陣(permutation matrix) $\mathbf{P}$，之後再做矩陣的LU分解，記為
$$
\mathbf{PA} = \mathbf{L}_0\mathbf{U}\\
\mathbf{PA} = \mathbf{L}_0 \mathbf{D} \mathbf{U}_0
$$
由於排列矩陣的列(行)向量兩兩正交，故為正交矩陣，滿足$\mathbf{P}^T = \mathbf{P}^{-1}$，可將上式$\mathbf{P}$移項得$\mathbf{A}$。

---
## ch2 向量空間
### 綱要
- 佈於體的向量空間(vector space over field)
- 子空間判斷方式與性質
- 伸展(Span)與列空間、行空間
- 線性獨立、線性相依判斷方式
- 基底 = 最小向量數目的伸展集 = 最多向量數目的線性獨立集
- 維數 = 基底S中的向量個數
- 秩數(rank) = 行向量獨立個數 = 列向量獨立個數
- rank–nullity theorem - 零核數(nullity) = 矩陣A的行數(未知數個數) - rank(A)
- 線代的非齊次方程式Ax = b有解時為b落在A的行空間
- 線代的和空間 - 將兩空間向量相加做線性組合，解決聯集不是空間的問題
- 線代的直和空間 - U+W具有唯一性

---
### 佈於體的向量空間(vector space over field)
首先要定義體(field)，參考[1: INTRODUCTION, FIELDS, VECTOR SPACES, BASES](http://www.stevenheilman.org/~heilman/teach/lalg1.pdf)、[Field Definition (expanded)](https://www.youtube.com/watch?v=KCSZ4QhOw0I)，假定$F$是一個數的集合，且集合$F$中定義二元運算(binary operation) $+ : F \times F \to F, - : F \times F \to F$，記為$(F, +, \cdot)$。假設$a, b,c \in F$，滿足以下性質

1. 加法和乘法的封閉性 - $a + b \in F, a \cdot b \in F$
2. 加法和乘法的交換律 - $a + b = b - a, a \cdot b = b \cdot a$
3. 乘法對加法的分配律 - $a \cdot(b + c) = a \cdot b + a \cdot c$
4. 加法和乘法的結合律 - $(a + b) + c = a + b(b + c), (a \cdot b)\cdot c = a \cdot (b \cdot c)$
5. 加法和乘法的單位(identity)元素 - 單位元素和其他元素結合時，並不會改變那些元素，$\exists 0 \in F, \ni \forall \alpha \in F, 0 + \alpha = \alpha$ ，0為此加法運算的單位元素；$\exists 1 \in F, \ni \forall \alpha \in F, 1 \cdot \alpha = \alpha$ ，1為此乘法運算的單位元素。
6. 加法和乘法的反(inverse)元素 - $\forall \alpha \in F, \exists - \alpha \in F, \ni \alpha + (-\alpha) = 0$ ，加法反元素可以對應到的是減法運算；$\forall \alpha \in F, \alpha \neq 0, \exists \alpha^{-1} \in F, \ni \alpha \cdot \alpha^{-1} = 0$ ，乘法反元素可以對應到的是除法運算。

則稱為數的集合$F$為一個體、域(Field)，常見的是實數系$\mathbb{R}$或是複數系$\mathbb{C}$是體，但整數系$\mathbb{Z}$不是體，因為不具有乘法的反元素，例如$3 \in \mathbb{Z}$的乘法反元素是$\frac{1}{3} \notin \mathbb{Z}$，不屬於整數系。

再來定義**佈於體$F$的向量空間$V$(vector space $F$ over field $V$)**，$V$是一個"向量"(vector)的集合，再給定一個體$F$，為"純量"(scalars)的集合，定義以下2個運算(二元運算)
1. 向量的加法 $+ : V + V \to V$，記為$\mathbf{x} + \mathbf{y}$。
2. 純量的乘法$\cdot : F \times V \to V$，記為$a \cdot \mathbf{u}$。

此二元運算須滿足封閉性
1. $\forall \mathbf{x}, \mathbf{y} \in V, \mathbf{x} + \mathbf{y} \in V$
2. $\forall a \in F, \mathbf{u} \in V, a \cdot \mathbf{u} \in V$

與以下八大公理(axiom) - $\forall \mathbf{x}, \mathbf{y}, \mathbf{z} \in V, \alpha, \beta \in F$
|文字說明|數學式|
|---|---|
|向量加法的交換律|$\mathbf{x} + \mathbf{y} = \mathbf{y} + \mathbf{x}$|
|向量加法的結合律|$(\mathbf{x} + \mathbf{y}) + \mathbf{z} = \mathbf{x} + (\mathbf{y} + \mathbf{z})$|
|向量加法的單位(identity)元素|$\exists \mathbf{0} \in V, \ni \mathbf{x} + \mathbf{0} = \mathbf{x}$|
|向量加法的反(inverse)元素|$\forall \mathbf{x} \in V, \exists -\mathbf{x} \in F, \ni \mathbf{x} + (-\mathbf{x}) = \mathbf{0}$|
|向量加法的分配律|$\alpha(\mathbf{x} + \mathbf{y}) = \alpha\mathbf{x} + \alpha\mathbf{y}$|
|純量加法的分配律|$(\alpha + \beta)\mathbf{x} = \alpha\mathbf{x} + \beta\mathbf{x}$|
|純量乘法的結合律|$(\alpha\beta)\mathbf{x}= \alpha(\beta\mathbf{x})$|
|純量乘法的單位(identity)元素|$\exists 1 \in F, \ni 1 \mathbf{x} = \mathbf{x}$|

---
### 常見向量空間
1. 歐式空間 $F^n$，零向量則為$\mathbf{0} = [0, 0, \ldots, 0]$。
2. 矩陣空間 $F^{m \times n} \equiv \{ \mathbf{A}_{m \times n} = [a_{ij}]_{m \times n}; a_{ij} \in F \}$，零向量為零矩陣。
3. 至多$n$次多項式空間 $P_n(F) \equiv \{ p(x) \mid p(x) = a_0 + a_1x + \ldots + a_nx^n ; a_i \in F \}$
4. 連續函數空間 $C[a, b] = \{ f(x) | f(x) : x \in [a, b] \to F; f(x) \text{ is continuous function}\}$

---
### 子空間(subspace)
給定一於體$F$的向量空間$V$，$W$為$V$的非空子集合，若且為若
1. 向量加法的封閉性 - $\mathbf{x}, \mathbf{y} \in S, \mathbf{x} + \mathbf{y} \in S$
2. 純量乘法的封閉性 - $\mathbf{x} \in S, \alpha \in F, \alpha\mathbf{x} \in S$

由於向量空間已為向量空間的部分集合，故子空間已自動滿足向量空間需要具備的八大公理，要證明子空間只需要證明上面兩點即可。

將$\mathbf{0}$組成的集合$\{ \mathbf{0} \}$，帶入上面兩個條件，可以證得$\{ \mathbf{0} \}$為$V$的子空間，代表**任意向量空間皆有零向量，所以可以將零空間視為最小的子空間**。欲證明子空間可以將零向量帶入檢查是否為子空間$\mathbf{0} \overset{?}{\in} W$，若符合則再檢查向量加法與純量乘法的封閉性$\alpha \mathbf{x} + \mathbf{y} \overset{?}{\in} W$；若不符合就不是子空間。

若向量空間為歐氏空間$V = \mathbb{R}^2$，從幾何意義來看向量空間(子空間)為一條無限延伸**通過原點**的直線；$V = \mathbb{R}^3$則為一個無限延伸通過原點的平面。

從向量的表列式來看
$$
W = \{ \mathbf{x} \mid \mathbf{x} \text{ satisfy governing equation}\}
$$
若是控制方程式滿足齊次$\mathbf{0} \in W$，線性$\mathbf{x} + \mathbf{y} \in W, \alpha\mathbf{x} \in W$的特性則稱$W$為子空間。因此在解題上若是題目有文字或是用矩陣形式敘述限制項，則想辦法化成控制方程式，之後判斷子空間的方式即是檢查方程式是否為齊次線性方程式。

子空間的性質
1. 交集為子空間 - 若$W_1, W_2$為$V$的子空間，則$W_1 \cap W_2$仍為$V$的子空間。
1. 聯集不一定子空間 - 若$W_1, W_2$為$V$的子空間，則$W_1 \cup W_2$不一定為$V$的子空間。聯集只有在以下條件才會成立 - $W_1 \cup W_2$為$V$的子空間 $\Leftrightarrow$ $W_1 \subseteq W_2$或是$W_2 \subseteq W_1$。

---
### 線性組合
1. 線性組合定義 - $S = \{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \}$為一向量集合，若$\mathbf{u} = \alpha_1 \mathbf{v}_1 + \alpha_2 \mathbf{v}_2 + \ldots + \alpha_n \mathbf{v}_n$，則$\mathbf{u}$為$S$之線性組合。因此可以寫作矩陣形式方便解題 $\mathbf{u} = \begin{bmatrix} \mid & \mid & & \mid\\ \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n\\ \mid & \mid & & \mid \end{bmatrix} \begin{bmatrix} c_1\\ c_2\\ \vdots\\ c_n\end{bmatrix}$
2. 列展式 - 為將矩陣的列向量做線性組合
$$
\mathbf{w} \mathbf{A} = \begin{bmatrix} \mathbf{w}_1 & \mathbf{v}_2 & \cdots & \mathbf{w}_n \end{bmatrix} \begin{bmatrix} \mathbf{A}'_1\\ \mathbf{A}'_2\\ \vdots\\ \mathbf{A}'_n \end{bmatrix} = \mathbf{w}_1 \mathbf{A}'_1 + \mathbf{w}_2 \mathbf{A}'_2 + \cdots + \mathbf{w}_n \mathbf{A}'_n, \forall \mathbf{w} \in F^{1 \times n}
$$
3. 行展式 - 為將矩陣的行向量做線性組合
$$
\mathbf{A} \mathbf{v} = \begin{bmatrix} \mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_n \end{bmatrix} \begin{bmatrix} \mathbf{v}_1\\ \mathbf{v}_2\\ \vdots\\ \mathbf{v}_n \end{bmatrix} = \mathbf{v}_1 \mathbf{A}_1 + \mathbf{v}_2 \mathbf{A}_2 + \cdots + \mathbf{v}_n \mathbf{A}_n, \forall \mathbf{v} \in F^{n \times 1}
$$

---
### 伸展(span)
1. 給定$S = \{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \}$為一向量集合，S集合的伸展為將所有可由$S$線性組合得到的向量，全部放進集合，$\mathrm{Span}(S) \equiv \{ \mathbf{x} \mid \mathbf{x} = \alpha_1 \mathbf{v}_1 + \alpha_2 \mathbf{v}_2 + \ldots + \alpha_n \mathbf{v}_n; \forall \alpha_k \in F \}$
2. 若$\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$為向量空間$V$的元素，則$\mathrm{Span}(S)$為$V$的子空間，白話來說可以使**不形成空間的向量轉換為向量空間**
3. 定義$\mathrm{Span}(S) = V$，則稱$S$為$V$的生成集(generating set)。
4. 零空間$\{ \mathbf{0} \}$為最小的子空間，定義由空集合稱生成零空間$\{ \mathbf{0} \}$，記為$\mathrm{Span}\{ \phi \} = \{ \mathbf{0} \}$。

---
### 矩陣4個基本子空間
根據前面伸展的概念 - 不形成空間的的向量轉換為向量空間，因此將將列向量伸展就可得列空間(row space)、行向量(column space)伸展就可得行空間
$$
\begin{align*}
\mathrm{RS}(\mathbf{A}) &= \mathrm{row}(\mathbf{A}) = \mathrm{Span}\{ \mathbf{A}'_1, \mathbf{A}'_2, \ldots, \mathbf{A}'_m\}\\
&= \{ \mathbf{x} \mid \mathbf{x} = \alpha_1 \mathbf{A}'_1 + \alpha_2 \mathbf{A}'_2 + \cdots + \alpha_3 \mathbf{A}'_m\}\\
&= \{ \mathbf{x} \mid \mathbf{x} = \mathbf{w} \mathbf{A}; \forall \mathbf{w} \in F^{1 \times m}\}\\
\mathrm{CS}(\mathbf{A}) &= \mathrm{col}(\mathbf{A}) = \mathrm{Span}\{ \mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_m\}\\
&= \{ \mathbf{x} \mid \mathbf{x} = \beta_1 \mathbf{A}_1 + \beta_2 \mathbf{A}_2 + \cdots + \beta_3 \mathbf{A}_m\}\\
&= \{ \mathbf{x} \mid \mathbf{x} = \mathbf{A} \mathbf{v}; \forall \mathbf{v} \in F^{n \times 1}\}\\
\end{align*}
$$
值域空間(range space/image)定義為$\mathbf{x} = \mathbf{Av}$中$\mathbf{x}$的範圍，雖與行空間(column space)定義不同，但剛好相等
$$
\mathrm{Range}(\mathbf{A}) = \mathrm{Im}(\mathbf{A}) = \{ \mathbf{x} \mid \mathbf{x} = \mathbf{A} \mathbf{v}; \forall \mathbf{v} \in F^{n \times 1}\} = \mathrm{Col}(\mathbf{A})
$$
零核空間(null space/kernel)為齊次聯立方程式$\mathbf{Ax} = \mathbf{0}$中所有解$\mathbf{x}$所形成的集合
$$
\mathrm{Null}(\mathbf{A}) = \mathrm{Ker}(\mathbf{A}) = \{ \mathbf{x} \mid \mathbf{Ax} = \mathbf{0}; \forall \mathbf{x} \in F^{n \times 1}\}
$$
左零空間(left null space)跟零核空間差別在於向量$\mathbf{x}$是乘在$\mathbf{A}$的右邊
$$
\begin{align*}
\mathrm{LNull}(\mathbf{A}) &= \{ \mathbf{x} \mid \mathbf{x}^T \mathbf{A} = \mathbf{0}; \forall \mathbf{x} \in F^{n \times 1}\}\\
&= \{ \mathbf{x} \mid (\mathbf{x}^T \mathbf{A})^T = \mathbf{A}^T \mathbf{x} = \mathbf{0}^T; \forall \mathbf{x} \in F^{n \times 1}\}\\
&= \mathrm{Null}(\mathbf{A}^T)
\end{align*}
$$

---
### 線性獨立、線性相依定義與直覺理解
令$V$為一向量空間，給定向量集合$S = \{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}, \mathbf{v}_i \in V$，若若僅存在唯一的數組$c_1 = c_2 = \cdots = c_n = 0$，使得
$$
c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots c_n \mathbf{v}_n = \mathbf{0}
$$
則稱$S$是線性獨立(LI, linearly independent)，反之稱之為線性相關 (LD. linearly dependent)。
<br>
假設一向量集合線性相關，在不失一般性之下，假設$c_1 \neq 0$，經移項$c_1 \mathbf{v}_1 = -(c_2 \mathbf{v}_2 + \cdots c_n \mathbf{v}_n)$，再同除以$c_1$得
$$
\mathbf{v}_1 = -(\frac{c_2}{c_1} \mathbf{v}_2 + \cdots \frac{c_n}{c_1} \mathbf{v}_n)
$$
有上式可知向量$\mathbf{v}_1$可由$\{\mathbf{v}_2, \cdots, \mathbf{v}_n\}$其他向量組合而成。可知得出結論線性相關為從在一向量可以由其他向量透過線性組合來表示，記為$\exists \mathbf{v_k} \in \mathrm{Span}\{S - \{\mathbf{x_k}\} \}$ ($\mathbf{v_k}$是大冗員!)；而線性獨立為任何向量都不可用其他向量透過線性組合來表示。

---
### 線性獨立、線性相依判斷方式
1. 歐式空間$F^n$、矩陣$F^{m \times n}$、多項式$P_n(x)$使用Gauss消去法化簡為列梯式，若存在零項則為線性相依；沒有零項則為線性獨立。
2. 解析函數(任意階為微分都存在)使用Wronkskian行列式，參照[2022上一段日記 03/10(四)](https://hackmd.io/@HsuChiChen/2022-log-2#03/10(四))內容，給定解析函數集$S = \{ f_1(x), \ldots, f_n(x) \}$，一般來說
$$
W(S) =
\det\begin{bmatrix}
f_1(x) & f_2(x) & \cdots & f_n(x)\\
f_1'(x) & f_2'(x) & \cdots & f_n'(x)\\
\vdots & \vdots & \ddots & \vdots\\
f_1^{(n-1)}(x) & f_2^{(n-1)}(x) & \cdots & f_n^{(n-1)}(x)
\end{bmatrix}_{n \times n}
$$
- $W(S) \neq 0$，也就是行列式消不掉，仍為$x$的函數為線性獨立(LI)。
- $W(S) = 0$，也就是行列式全部消掉為線性相依(LD)。
3. **若$S$為抽象項量集或是不可解析函數集**<br>
從定義出發，列出線性相依、線性獨立的判別式$c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots c_n \mathbf{v}_n = \mathbf{0}$，解出係數$c_1, c_2, \ldots, c_n$數值，若具有唯一解$c_1 = c_2 = \cdots = c_n = 0$則為線性獨立(LI)，反之則為線性相依(LD)。

---
### 基底(basis)
$V$為一向量空間，$S$為$V$的子空間，且滿足
1. $S = \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}$為線性獨立集，也就是$\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$為線性獨立。
2. $\mathrm{Span}(S) = V$，集合$S$有"足夠"的向量可以span成向量空間$V$。<br>
則稱為$S$是$V$的一組基底。

由定義可以得出以下性質
1. 基底不具有不唯一性，舉例來說再三維歐式空間$\mathbb{R}^3$，用直角坐標$(\hat{i},\hat{j}, \hat{k})$與極座標$(\hat{r}, \hat{\theta}, \hat{z})$這2種不同的基底都可以描述同一個向量。
2. **基底為向量空間$V$中最大的線性獨立集**，因此假設基底$\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \}$，若有另外$m > n$個向量集必為線性相依。
3. **基底為向量空間$V$最小的伸展集**，也就是說基底是要伸展出$V$所需最"精簡"的向量。
4. 基底不可以有0空間$\{ \mathbf{0}\}$，因為$\mathbf{0}$是大"冗員"，只要有0存在就是線性相依$\mathbf{0} = 0\mathbf{v}_1 + 0\mathbf{v}_2 + \cdots + 0\mathbf{v}_n$。
5. 習慣上常用標準基底表示 - $F^3$的標準基底$\{\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\} = \{ \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}, \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}, \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} \}$；$F^{2 \times 2}$的標準基底$\{ \mathbf{E}_{11}, \mathbf{E}_{12}, \mathbf{E}_{21}, \mathbf{E}_{22} \} = \{ \begin{bmatrix} 1 & 0\\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 1\\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0\\ 1 & 0 \end{bmatrix}, \begin{bmatrix} 0 & 0\\ 0 & 1 \end{bmatrix} \}$。

---
### 維數(dimension)
給定基底$S = \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$，維數就是基底$S$中的向量個數$n$，記為$\dim(V) = n$，並定義0空間的維度是0，$W = \{ \mathbf{0}\}, \dim(W) = 0$。而常見向量空間維度$\dim(F^n) = n, \dim(F^{m \times n}) = m \times n$。一個向量空間$V$的基底不唯一，但其維數是相同，就物理意義來說，維數就是自由度(degrees of freedom)的數目，等於未知數個數減去"有效"控制方程式(限制式)的個數。

- **求解控制方程式的基底與維數**<br>
在解題上給定控制方程式，解出通解，列出向量集所span成的空間，並使用Gauss消去法把"多餘"的向量去除，留下彼此線性獨立的向量集，即為基底，而線性獨立的向量個數就是維數。
$$
\begin{align*}
V &= \{ \mathbf{x} \mid \mathbf{x} \text{ satisfy governing equation}\}\\
&= \{ \mathbf{x} \mid \mathbf{x} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n \}\\
&= \mathbf{Span}\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k \} \leftarrow \text{remove redundancy}\\
&= \mathbf{Span}\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_r \}\\
& \therefore \{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_r \} \;\ldots \text{basis}\\
&\quad\; \dim(V) = r \;\ldots \text{dimension}
\end{align*}
$$

- **Gauss消去法雖然列向量被破壞了，但其線性組合的關係並沒有被影響**<br>
正常解法是列空間、行空間都做Gauss消去法把"多餘"的列或是行向量去除，但是實際上只需要做一次基本列運算的Gauss消去法化成最減列梯式，pivot element所在列就是獨立列向量，所在行就是獨立行向量，在做Gauss消去法需要記得注意列交換後各列位置的改變，至於求行空間也可使用基本列運算的Gauss消去法是因為 - 雖然列向量被破壞了，但其線性組合的關係並沒有被影響。

---
### 秩數(rank)
$\mathbf{A}$的秩數(rank)定義為 - $\mathbf{A}$中range space的dimension，記為
$$
\mathrm{rank}(\mathbf{A}) \triangleq \dim(\mathrm{Range}(\mathbf{A}))
$$
range space等同於column space，故dimension相同，而column space的dimension等於row space的dimension，因此$\mathrm{rank}(\mathbf{A})$的判斷方式為將矩陣$\mathbf{A}$做Gauss消去法化簡為列梯式，找出**pivot element的個數**，以下為秩數的重要性質
1. $\mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{A}^T)$，轉置後矩陣的秩數不變。
2. $\dim(\mathrm{Row}(\mathbf{A})) = \dim(\mathrm{Col}(\mathbf{A}))$，等價第一點推論，列向量獨立個數等於行向量獨立個數。
3. $\mathrm{rank}(\mathbf{A}_{m \times n}) \leq \min(m, n)$，秩數必小於矩陣的行數與列數。
4. $0 \leq \mathrm{rank}(\mathbf{AB}) \leq \min(\mathrm{rank}(\mathbf{A}), \mathrm{rank}(\mathbf{B}))$，**矩陣相乘，秩數越乘越小**。
5. 上式若是$\mathbf{B}$可逆，$\mathrm{rank}(\mathbf{AB}) = \mathrm{rank}(\mathbf{B})$；若是$\mathbf{A}$可逆，$\mathrm{rank}(\mathbf{AB}) = \mathrm{rank}(\mathbf{A})$，**若乘上可逆矩陣則秩數不變**。

第4點證明如下
$$
\begin{align*}
& \forall \mathbf{x} \in \mathrm{Row}(\mathbf{AB})\\
\Rightarrow\;& \exists \mathbf{w} \in F^{1 \times m}, \ni \mathbf{wAB} = \mathbf{x}\\
\Rightarrow\;& \mathbf{uB} = \mathbf{x} \quad\text{let } \mathbf{u} = \mathbf{wA}\\
\Rightarrow\;& \mathbf{x} \in \mathrm{Row}(\mathbf{B})\\
\therefore\;& \mathrm{Row}(\mathbf{AB}) \subseteq \mathrm{Row}(\mathbf{B})\\
&\dim(\mathrm{Row}(\mathbf{AB})) \leq \dim(\mathrm{Row}(\mathbf{B}))\\
\Rightarrow\;& \mathrm{rank}(\mathbf{AB}) \leq \mathrm{rank}(\mathbf{B})\\
\end{align*}
$$
同理$\mathrm{rank}(\mathbf{AB}) \leq \mathrm{rank}(\mathbf{A})$使用行空間$\mathrm{Col}(\mathbf{AB}) \subseteq \mathrm{Row}(\mathbf{A})$開始證明。

---
### 零核空間的維數(nullity)與rank–nullity theorem
給定矩陣$\mathbf{A}_{m \times n}$則零核空間的維數(nullity)為
$$
\begin{align*}
\mathrm{nullity}(\mathbf{A}) &= \dim(\mathrm{Null}(\mathbf{A}))\\
&= n - \mathrm{rank}(\mathbf{A})
\end{align*}
$$
上式稱為rank–nullity theorem，**nullity代表的是零核空間的維數，等於未知數的個數(矩陣的行數)減去"有效"的方程式數目(最簡列梯式中pivot element個數)**。

---
### 分析非齊次方程式$\mathbf{Ax} = \mathbf{b}$
由於$\mathbf{x}$乘在$\mathbf{A}$的右側，將非齊次方程式$\mathbf{Ax} = \mathbf{b}$做行展式
$$
\mathbf{A}_{m \times n} \mathbf{x}_{n \times 1} = \underbrace{\begin{bmatrix}\mid & \mid & & \mid\\ \mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_n\\ \mid & \mid & & \mid \end{bmatrix}}_{\text{column vector}} \begin{bmatrix} \mathbf{x}_1\\ \mathbf{x}_2\\ \vdots\\ \mathbf{x}_n \end{bmatrix} = \mathbf{x}_1 \mathbf{A}_1 + \mathbf{x}_2 \mathbf{A}_2 + \cdots + \mathbf{x}_n \mathbf{A}_n = \mathbf{b}
$$
上式意義在於將$\mathbf{A}$的行向量$\mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_n$做線性組合會產生非齊次解，而$\mathbf{Ax} = \mathbf{b}$中的解$\mathbf{x}^T = [\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n]$即是線性組合的係數。而由[ch2 線性組合](#線性組合)觀念可知，行空間是由行向量線性組合形成向量的集合(行向量伸展為行空間)，因此$\mathbf{b}$落在$\mathbf{A}$的行空間，記為$\mathbf{b} \in \mathrm{Col}(\mathbf{A})$。

嘗試將係數矩陣$\mathbf{A}$與非齊次$\mathbf{b}$合併為擴增矩陣$\mathbf{B} = [\mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_n, \mathbf{b}]$，若是方程式有解，則代表$\mathbf{b}$可由$\mathbf{A}$的行向量透過線性組合而成，$\mathbf{b}$是"冗員"，有$\mathbf{b}$或是沒$\mathbf{b}$都不影響方程式行向量線性獨立獨立的個數，故$\mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{B})$；反之，若$\mathbf{b}$不可由$\mathbf{A}$的行向量透過線性組合而成，代表方程式無解，$\mathbf{b}$與矩陣$\mathbf{A}$的行向量是線性獨立，故$\mathrm{rank}(\mathbf{A}) + 1 = \mathrm{rank}(\mathbf{B}) \Rightarrow \mathrm{rank}(\mathbf{A}) \neq \mathrm{rank}(\mathbf{B})$。

總結來說分析非齊次方程式$\mathbf{A}_{m \times n}\mathbf{x}_{n \times 1} = \mathbf{b}_{m \times 1}$，第一步要看有沒有解，也就是$\mathbf{b}$有沒有落在$\mathbf{A}$的行空間，第二步看唯一解或是無限多組解，也就是係數矩陣的行數(未知數個數)。
1. $\mathbf{Ax} = \mathbf{b} \text{ is consistent} \Leftrightarrow \mathbf{b} \in \mathrm{Col}(\mathbf{A}) \Leftrightarrow \mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{B}) \Leftrightarrow \mathbf{x}_1 \mathbf{A}_1 + \mathbf{x}_2 \mathbf{A}_2 + \cdots + \mathbf{x}_n \mathbf{A}_n = \mathbf{b} (\text{redundancy})$
- $\text{unique solution} : \mathrm{rank}(\mathbf{A}) = n \Leftrightarrow \{ \mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_n \} \text{ is linear independent set}$
- $\text{infinitely many solutions} : \mathrm{rank}(\mathbf{A}) = r < n \Leftrightarrow \{ \mathbf{A}_1, \mathbf{A}_2, \ldots, \mathbf{A}_n \} \text{ is linear dependent set}$
2. $\mathbf{Ax} = \mathbf{b} \text{ is inconsistent} \Leftrightarrow \mathbf{b} \not\in \mathrm{Col}(\mathbf{A}) \Leftrightarrow \mathrm{rank}(\mathbf{A}) \neq \mathrm{rank}(\mathbf{B}) \Leftrightarrow \mathbf{x}_1 \mathbf{A}_1 + \mathbf{x}_2 \mathbf{A}_2 + \cdots + \mathbf{x}_n \mathbf{A}_n \neq \mathbf{b} (\text{independent})$

---
### 分析齊次方程式$\mathbf{Ax} = \mathbf{0}$
齊次方程式$\mathbf{A}_{m \times n} \mathbf{x}_{n \times 1} = \mathbf{0}$同非齊次方程式分析，不同點是**齊次方程式必定有解**，若是係數矩陣$\mathbf{A}$的**行向量線性獨立**，則代表行滿秩$\mathrm{rank}(\mathbf{A}) = n$，**存在唯一零解**，這即是線性獨立的定義- $c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots c_n \mathbf{v}_n = \mathbf{0}$具有唯一解$c_1 = c_2 = \cdots = c_n = 0$，因此零核空間$\mathrm{Null}(\mathbf{A}) = \{\mathbf{0}\}$， 零核空間的維數$\mathrm{nullity}(\mathbf{A}) = \dim(\mathrm{Null}(\mathbf{A})) = 0$；若是矩陣$\mathbf{A}$剛好又是方陣，則$\det(\mathbf{A}) \neq 0$。

反之，係數矩陣$\mathbf{A}$的行向量線性相依$\mathrm{rank}(\mathbf{A}) = r < n$，因此線性組合的係數不唯一，具有非零的無限多組解，此時解的自由度，也就是零核空間的維數$\mathrm{nullity}(\mathbf{A}) = \dim(\mathrm{Null}(\mathbf{A})) = n - r > 0$；若是矩陣$\mathbf{A}$剛好又是方陣，則$\det(\mathbf{A}) = 0$。

---
### 和空間(sum space)
1. 觀念 - [ch2 線性組合](#線性組合)提及 - 若$W_1, W_2$為$V$的子空間，交集$W_1 \cap W_2$為子空間，但聯集$W_1 \cup W_2$不一定子空間，**為了解決聯集可能不是空間的問題**，而有了和空間的概念，不同於交集與聯集空間是屬於"集合論"內的空間，和空間是"線性組合"產生的空間。
2. 定義 - 若$U, W$為$V$的子空間，則$U, W$的和空間$U + W$定義為取$U, W$空間中的向量相加$\mathbf{u} + \mathbf{v}$，做線性組合，記為
$$
U + W = \{ \mathbf{u} + \mathbf{v} \mid \mathbf{u} \in U, \mathbf{w} \in W \}
$$
和空間$U + W$亦為向量空間$V$的子空間。
3. 解題流程 - 欲解$W_1 + W_2$的基底，第一步，先求$W_1$的基底$S_1$與$W_2$的基底$S_2$；第二步，把兩者基底取聯集並去除"冗員"，$W_1 + W_2 = \mathrm{Span} \{ S_1 \cup S_2 \} \leftarrow \text{remove redundancy} = \mathrm{Span} \{S\}$。
4. 維數定理 - 若$W_1, W_2$為$V$的子空間，$\dim(W_1 + W_2) = \dim(W_1) + \dim(W_2) - \dim(W_1 \cap W_2)$，公式形式跟集合論的排容定理類似。
5. 直和空間(direct sum) - $U, W$的和空間$U + W$其中$\mathbf{u} + \mathbf{v}$線性組合的係數可能不唯一，是我們不樂見了，因此定義和空間係數唯一的情況稱為直和空間<br>
若$W_1 + W_2$為$V$的子空間，滿足第1點$V = W_1 + W_2$與第2點$W_1 \cap W_2 = \{ \mathbf{0} \}$，則稱$V$為$W_1, W_2$的直和，記為$V = W_1 \oplus W_2$，等價於<br>
$$
\begin{align*}
&\Leftrightarrow \forall \mathbf{u} \in V, \exists !\mathbf{w}_1 \in W_1 \exists !\mathbf{w}_2 \in W_2, \ni \mathbf{u} = \mathbf{w}_1 + \mathbf{w}_2\\
&\Leftrightarrow S_1 \text{ is the basis of } W_1, S_2 \text{ is the basis of } W_2 \Rightarrow S = S_1 \cup S_2 \text{ is the basis of } V\\
&\Leftrightarrow \dim(V) = \dim(W_1) + \dim(W_2)
\end{align*}
$$
6. 獨立子空間 - 任意空間的向量皆無法以其他空間伸展而得，若$W_1, W_2, \ldots, W_n$為獨立子空間則滿足$W_1 \cap (W_2 + W_3 + \cdots + W_n) = \{ \mathbf{0} \}, \ldots$。

---
## ch3 線性轉換
### 綱要
- 線性變換 - 一種線性的函數關係
- 線性轉換版零核空間 - 定義域中對應到0向量的集合
- 線性轉換版值域 - 所有定義域都對應到的空間
- 線性函數1對1與onto的判斷方式
- 線性轉換(用"代表矩陣"表示) + 基底轉換
- 相似轉換 = (同一向量空間的)線性轉換 + 基底轉換
- 放大、旋轉、鏡射矩陣
- 判斷函數是否可逆(反函數存在) - bijection(injective + surjective)

---
### 線性轉換(linear transformation)
佈於體$F$的2個向量空間$V, W$，定義$T : Ｖ \to W$為一函數，且滿足以下線性性質
1. additivity - $\forall \mathbf{x}, \mathbf{y} \in V, \ni T(\mathbf{x} + \mathbf{y}) = T(\mathbf{x}) + T(\mathbf{y})$
2. homogeneity - $\forall \mathbf{x} \in V, \alpha \in F, \ni T(\alpha \mathbf{x}) = \alpha T(\mathbf{x}))$<br>
則稱為$T$為從$V$映射(mapping)到$W$的線性轉換。

若線性轉換得定義域與對應域相同$T : Ｖ \to V$，則稱$T$為線性算子(linear operator)，或稱$T$為在$V$中做線性轉換。

欲判斷一個函數是否為線性轉換，類似[ch2 子空間(subspace)](#子空間subspace)判斷子空間的觀念，輸入給定0向量，並觀察輸出是否是0向量$T(\mathbf{0}) \overset{?}{=} \mathbf{0}$。

---
### 線性轉換的零核空間與值域空間
線性轉換版的零核空間與值域空間，對比[ch2 矩陣4個基本子空間](#矩陣4個基本子空間)矩陣版，兩者定義上是不同的
1. 給定線性轉換$T : V \to W$，$T$的零核空間(null space/kernel)為**定義域$V$中對應到0向量的集合**
$$
\mathrm{Null}(T) = \mathrm{Ker}(T) = \{ \mathbf{x} \mid T(\mathbf{x}) = \mathbf{0}; \forall \mathbf{x} \in V\}
$$
零核空間是屬於**定義域**的子空間$\mathrm{Null}(T) \subseteq V$，而nullity即為零空間的維數，記為$\mathrm{nullity}(\mathbf{A}) = \dim(\mathrm{Null}(\mathbf{A}))$。
2. 給定線性轉換$T : V \to W$，$T$的值域(range space/image)為**所有定義域對應到的空間**
$$
\mathrm{Range}(T) = \mathrm{Im}(T) = \{ \mathbf{w} \in W \mid T(\mathbf{x}) = \mathbf{w}; \forall \mathbf{x} \in V\}
$$
值域是屬於**對應域**的子空間$\mathrm{Range}(T) \subseteq W$，而$T$的秩數$\mathrm{rank}(T)$定義為值域的維數，記為$\mathrm{rank}(T) = \dim(\mathrm{Range}(T))$。
3. 零核空間求法 - 將向量$\mathbf{x}$表示為通式，令$T(\mathbf{x}) = \mathbf{0}$解聯立方程式的根，零核空間即為方程式根的集合$\mathrm{Null}(T) = \{ \mathbf{x} = ? \} = \mathrm{Span}\{ \mathbf{w}_1, \mathbf{w}_2, \ldots, \mathbf{w}_r \}$。
4. 值域空間求法 - 觀察上式定義$\forall \mathbf{x} \in V$，實際上不可能將所有$\mathbf{x}$的數值帶入，因此需要**取能"代表"所有$\mathbf{x}$的向量，也就是基底**，將其一個個做線性轉換$T(\mathbf{x}_1) = \mathbf{w}_1, \ldots, T(\mathbf{x}_n) = \mathbf{w}_n$，並將這些對應到的值域span成值域空間$\mathrm{Span} \{ \mathbf{w}_1, \mathbf{w}_2, \ldots, \mathbf{w}_n\} \leftarrow \text{remove redundancy} = \mathrm{Span} \{ \mathbf{w}_1, \mathbf{w}_2, \ldots, \mathbf{w}_r \}$。

---
### 線性轉換的rank–nullity theorem
可與[ch2 零核空間的維數(nullity)與rank–nullity theorem](#零核空間的維數nullity與rank–nullity-theorem)矩陣版的rank–nullity theorem做比較，線性轉換版的rank–nullity theorem為
$$
\mathrm{rank}(T) + \mathrm{nullity}(T) = \dim(V)
$$
<br>
如上圖可知，線性轉換版的rank–nullity theorem比較直觀的理解是定義域$V$空間的維數由兩部分組成
1. $\mathrm{nullity}(T) \equiv \dim(\mathrm{Null}(T))$零核空間的基底$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k$ - 對應到值域空間的0向量$T(\mathbf{x}) = 0$，因此對值域空間沒有任何貢獻。
2. $\mathrm{rank}(T) \equiv \dim(\mathrm{Range}(T))$其他能撐起值域空間的基底$\mathbf{x}_{k+ 1}, \mathbf{x}_{k+ 2}, \ldots, \mathbf{x}_{n}$。

---
### 函數的分類
高中時有學到函數根據其定義域與值域的對應關係分為兩種一對一(injective, 1-to-1)和映成(surjective, onto)，如下圖所示
<br>
一對一(1-to-1)定義為$\forall \mathbf{w} \in \mathrm{Range}(T), \exists ! \mathbf{x} \in V, \ni T(\mathbf{x}) = \mathbf{w}$，由以上定義可推導對線性轉換來說，要找出$\mathbf{x}$滿足$T(\mathbf{x}) = \mathbf{0}$，只會有$\mathbf{x} = 0$，因此
$$
T \text{ is 1-to-1 linear transformation} \Leftrightarrow \mathrm{Null}(T) = \{ \mathbf{0} \} \Leftrightarrow \mathrm{nullity}(T) = 0
$$
映成(onto)定義為range(image)與codomain相等，因此
$$
T \text{ is onto linear transformation} \Leftrightarrow \mathrm{Rank}(T) = \dim(W)
$$

---
### 向量的座標化
1. 有序基底(ordered basis) - 給定向量空間$V$，若$\beta = \{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \}$為$V$的一組有順序關係的基底，則稱$\beta$為$V$的一組有序基底。
2. 座標向量(coordinate vector) - 給定一組$V$的有序基底$\beta = \{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \}$，對於所有向量$\forall \mathbf{u} \in V$，都可以表示為$\mathbf{u} = \alpha_1 \mathbf{x}_1 + \alpha_2 \mathbf{x}_2 + \cdots + \alpha_n \mathbf{x}_n$，$\mathbf{u}$相應$\beta$的座標向量為
$$
[\mathbf{u}]_{\beta} = \begin{bmatrix} \alpha_1\\ \alpha_2\\ \vdots\\ \alpha_n \end{bmatrix} \in F^n
$$

---
### 基底轉換
由[ch2 基底(basis)](#基底basis)觀念可知基底不具有唯一性，而**不同基底之間的轉換**一般式如下
$$
\begin{align*}
& \mathbf{E}[\mathbf{u}]_{\beta_1} = \mathbf{Q}[\mathbf{u}]_{\beta_2}\\
& [\mathbf{u}]_{\beta_2} = \mathbf{Q}^{-1} \mathbf{E}[\mathbf{u}]_{\beta_1} \Rightarrow \mathbf{P} = [\mathbf{I}_V]^{\beta_2}_{\beta_1} = \mathbf{Q}^{-1} \mathbf{E}\\
& [\mathbf{u}]_{\beta_1} = \mathbf{E}^{-1} \mathbf{Q}[\mathbf{u}]_{\beta_2} \Rightarrow \mathbf{P}' = [\mathbf{I}_V]^{\beta_1}_{\beta_2} = \mathbf{E}^{-1} \mathbf{Q} = (\mathbf{Q}^{-1} \mathbf{E})^{-1} = \mathbf{P}^{-1}\\
\end{align*}
$$
**其中$\mathbf{E}$為將有序基底$\beta_1 = \{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \}$拉直，行行並列組合而成；同理$\mathbf{Q}$為將有序基底$\beta_2 = \{ \mathbf{y}_1, \mathbf{y}_2, \ldots, \mathbf{y}_n \}$拉直，行行並列組合而成**；而$[\mathbf{I}_V]^{\beta_2}_{\beta_1}$代表從基底$\beta_1$轉換為基底$\beta_2$的轉換矩陣(transition matrix)。
<br><br>
解題上快速判斷方式為從非標準基底轉為標準基底$[\mathbf{I}_V]^{S}_{\beta}$，標準基底$S$在上面是天堂，所以比較好計算，乘上$\mathbf{P}$即可；反之$[\mathbf{I}_V]^{\beta}_{S}$，標準基底$S$在上面是地獄，很難算，需要乘上$\mathbf{P}^{-1}$。

---
### 使用"代表矩陣"表示線性轉換
如[ch3 線性轉換(linear transformation)](#線性轉換linear-transformation)線性轉換的觀念，給定線性轉換$T : V \to W$，且$\beta, \gamma$為$V, W$相應的有序基底，則對大部分的線性轉換還說可以找到代表矩陣(representative matrix) $[T]^\gamma_\beta$表示
$$
\underbrace{ [T(\mathbf{x})]_\gamma }_{\text{range } \mathbf{Y}} = \underbrace{ [T]^\gamma_\beta }_{\mathbf{A}} \; \underbrace{[\mathbf{x}]_\beta }_{\text{domain } \mathbf{X}}
$$
目的如同[ch1 矩陣基本列操作](#矩陣基本列操作)用矩陣表示基本列操作，因為計算機只看得懂矩陣，因此"線性轉換"這個數學語言需要化成計算機看得懂的矩陣形式。
<br><br>
欲求代表矩陣$\mathbf{A} = [T]^\gamma_\beta$，解題流程如下

1. 找出$V, W$的基底。
$$
\text{basis of } V : \beta = \{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \}\\
\text{basis of } W : \gamma = \{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \}\\
$$
2. 將$V$的基底一個個帶入線性轉換的數學式$T(\mathbf{x})$，並以$W$的基底表示其結果。
$$
T(\mathbf{x}_k) = \alpha_{1k} \mathbf{w}_1 + \alpha_{2k} \mathbf{w}_2 + \ldots + \alpha_{mk} \mathbf{w}_m \Rightarrow \mathbf{A}_k = \begin{bmatrix} \alpha_{1k}\\ \alpha_{2k}\\ \vdots\\ \alpha_{mk} \end{bmatrix}, k= 1,2, \ldots n
$$
3. 代表矩陣即每個基底所得結果的行行並列組合而成。
$$
[T]^\gamma_\beta = \mathbf{A} = [\mathbf{A}_1, \mathbf{A}_2, \ldots, , \mathbf{A}_n ]
$$

---
### 線性轉換 + 基底轉換
結合前面線性轉換與基底轉換，給定線性轉換$T : V \to W$，而$\beta, \beta'$為$V$的兩組有序基底，$\gamma, \gamma'$為$W$的兩組有序基底，若要在向量空間$V$且基底為$\beta'$映射向量空間$W$且基底$\gamma'$的代表矩陣$[T]^{\gamma'}_{\beta'}$，如果不好計算的話，**不妨"繞遠路"**，在$V$中做基底轉換，再做線性轉換，再做一次基底轉換，記為
$$
[T]^{\gamma'}_{\beta'} = [\mathbf{I}_W]^{\gamma'}_{\gamma} [T]^{\gamma}_{\beta} [\mathbf{I}_V]^{\beta}_{\beta'}
$$

---
### 相似轉換
相似轉換即是前面的線性轉換 + 基底轉換的特例，使線性轉換在同一向量空間下轉換$T : V \to V$，假設$\alpha, \beta$為$V$的兩組有序基底
$$
[T]^\alpha_\beta = [\mathbf{I}_V]^\beta_\alpha [T]^\alpha_\alpha [\mathbf{I}_V]^\alpha_\beta
$$
其中$[\mathbf{I}_V]^\beta_\alpha$與$[\mathbf{I}_V]^\alpha_\beta$互為反矩陣，因此可以寫做為$\mathbf{P}^{-1} \mathbf{A} \mathbf{P} = \mathbf{B}$的形式，這就是相似轉換一般的form。因此較嚴謹的定義為 - $\mathbf{A}, \mathbf{B} \in F^{n \times n}$，若存在可逆矩陣$\mathbf{P}$，使得$\mathbf{P}^{-1} \mathbf{A} \mathbf{P} = \mathbf{B}$，則稱$\mathbf{A} \text{ is similar to } \mathbf{B}$，記為$\mathbf{A} \sim \mathbf{B}$。

$\mathbf{A}$和$\mathbf{B}$相似，可以推得以下5個性質
1. $\mathrm{tr}(\mathbf{A}) = \mathrm{tr}(\mathbf{B})$
2. $\det(\mathbf{A}) = \det(\mathbf{B})$
3. $\mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{B})$
4. $\mathrm{nullity}(\mathbf{A}) = \mathrm{nullity}(\mathbf{B})$
5. 利用特徵方程式的根相同，證明具有相同的特徵值。

---
### 放大、旋轉、鏡射矩陣
1. **放大矩陣**<br>
將$x,y,z$軸3組基底帶入得出放大矩陣，放大$k$倍即為$k$倍的單位矩陣$\mathbf{I}_n$。
2. **旋轉矩陣**<br>
使用右手定則，先將座標軸畫出來。若沿著y軸(about y-axis)旋轉，就是固定基底y軸，轉動$x,y$軸2組基底，眼睛從y軸看過去，可以求得偏移後的基底x軸$\mathbf{x} = (\cos\theta, 0, -\sin\theta)$，基底y軸不變，基底z軸$\mathbf{z} = (\sin\theta, 0, \cos\theta)$，同理可得沿著x軸、z軸旋轉矩陣
$$
\begin{align*}
\mathbf{R}_z(\theta_z) &=
\left[ \begin{array}{c:c}
\cos\theta_z & -\sin\theta_z & 0\\
\sin\theta_z & \cos\theta_z & 0\\
0 & 0 & 1\\
\end{array} \right] \quad\ldots\text{about z-axis}\\
\mathbf{R}_x(\theta_x) &=
\left[ \begin{array}{c:c}
1 & 0 & 0\\
0 & \cos\theta_x & -\sin\theta_x\\
0 & \sin\theta_x & \cos\theta_x\\
\end{array} \right] \quad\ldots\text{about x-axis}\\
\mathbf{R}_y(\theta_y) &=
\left[ \begin{array}{c:c}
\cos\theta_y & 0 & \sin\theta_y\\
0 & 1 & 0\\
-\sin\theta_y & 0 & \cos\theta_y \\
\end{array} \right] \quad\ldots\text{about y-axis}
\end{align*}
$$
3. **鏡射矩陣**<br>
假設鏡射於yz平面，即代表跟鏡子垂直的向量經過線性轉換後為反方向，跟鏡子平行經過線性轉換後依然不變，記為
$$
\begin{align*}
&\mathbf{v}_1 \perp \text{mirror} \Rightarrow T(\mathbf{v}_1) = -\mathbf{v}_1\\
&\mathbf{v}_2 \parallel \text{mirror} \Rightarrow T(\mathbf{v}_2) = \mathbf{v}_2\\
&\;\Rightarrow \mathbf{R}_{yz} =
\left[ \begin{array}{c:c}
-1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{array} \right] \quad\ldots\text{about y-z plane}
\end{align*}
$$

---
### 合成函數
將一函數的輸出"串接"到另一函數的輸入而成的函數，給定線性轉換$T : V \to W; U : W \to Z$，從$T$到$U$的合成函數記為
$$
\forall \mathbf{v} \in V, U \circ T = U(T(\mathbf{v})) = V \to Z
$$

---
### 逆變換(反函數)
給定線性轉換$T : V \to W$，若存在$U : W \to V$滿足$T \circ U = \mathbf{I}_QW$且$U \circ T = \mathbf{I}_V$，則稱$T$為可逆，且$U$為$T$的逆變換(反函數)，記為$U = T^{-1}$，換句話說反函數撤銷了原函數的運算。

如[ch3 函數的分類](#函數的分類)，若一函數可逆等價於雙射(bijection)，符合條件一為一對一(injective, 1-to-1)，讓$U$空間向量能對應回來單一個$V$的向量；符合條件二為映成(surjective, onto)，讓$V$得對應域$W$可同時作為$U$的定義域mapping回來。

---
## ch4 特徵值與特徵向量
### 綱要
- 一維不變子空間 - 將線性轉換的代表矩陣化成對角線矩陣
- 特徵值與特徵向量解法
- 矩陣做任意方陣函數運算，特徵值跟著運算，特徵向量不改變
- 不同特徵值，對應特徵向量彼此線性獨立
- A可對角化 ⇔ A具有n個線性獨立的特徵向量 ⇔ 幾何重根數等於代數重根數
- 方陣函數的求法 - 同步對角化、Sylvester公式

---
### 不變子空間
首先把問題限制在定義域與對應域相同的線性轉換$T : V \to V$，我們試圖要尋找一組$V$的基底$\beta$使得代表矩陣變成對角線矩陣$[T]_\beta = \mathbf{D}$，化成對角線矩陣的目的是簡化合成運算，對角線矩陣自己相乘只需把對角線元素平方即可。

給定線性轉換$T : V \to V$，若$W$為$V$的子空間，$T(W) \subseteq W$，稱$W$為T-不變子空間(T-invariant subspace)，也就是說$W$子空間的所有向量，經過線性轉換$T$後的向量依然屬於$W$子空間，向量"自給自足"。

若$V$空間由$k$個T-不變子空間組合$W_1, W_2,\ldots, W_k$，則子空間的和空間為直和空間，記為$V = W_1 \oplus W_2 \oplus \ldots \oplus W_k$，因此直和空間的基底不存在"冗員"，$V$的基底為$\beta = \beta_1 \cup \beta_2 \cup \ldots \cup \beta_k$，線性轉換$T$的代表矩陣可以寫作類對角線矩陣
$$
[T]_\beta =
\begin{bmatrix}
\mathbf{A}_1 & \mathbf{0} & \cdots & \mathbf{0}\\
\mathbf{0} & \mathbf{A}_2 & \cdots & \mathbf{0}\\
\vdots & \vdots & \ddots & \vdots\\
\mathbf{0} & \mathbf{0} & \cdots & \mathbf{A}_k\\
\end{bmatrix}, \;\text{where} \mathbf{A}_i \in F^{n_i \times n_i}
$$
因此欲使線性轉換$T$的代表矩陣化成對角線矩陣，也就是只找對角線的一維方陣，即是找一維的T-不變子空間，這個基底就是特徵向量$\mathbf{v}_i$，其擴展的常數$\lambda_i$就是特徵值，定義如下

$W_i$為$T : V \to V$的一維T-不變子空間，且$\beta_i = \{ \mathbf{v}_i \}$為$W_i$的基底，故
$$
T(\mathbf{v}_i) = \mathbf{w}_i = \lambda_i \mathbf{v}_i \in W_i
$$
則稱$\lambda_i$為特徵值，$\mathbf{v}_i$為特徵向量，且$\mathbf{v}_i \neq 0$(要做基底用，基底不可為0)。

---
### 矩陣版的特徵值與特徵向量求法
將特徵值補上單位矩陣並移項，其方程式的形式即是[ch2 分析齊次方程式](#和空間sum-space)齊次方程式具有非零的無限多組解，故矩陣$\mathbf{A} - \lambda \mathbf{I}$的行向量線性相依，$\mathbf{A} - \lambda \mathbf{I}$的行列式值必為0。
$$
\begin{align*}
&\mathbf{A} \mathbf{x} = \lambda \mathbf{x} ,\;\exists \mathbf{x} \neq \mathbf{0}\\
\Rightarrow\;& (\mathbf{A} - \lambda \mathbf{I}) \mathbf{x} = \mathbf{0} ,\;\exists \mathbf{x} \neq \mathbf{0}\\
\Rightarrow\;& \mathrm{rank}(\mathbf{A}_{n \times n} - \lambda \mathbf{I}_{n \times n}) < n\\
\Rightarrow\;& \det(\mathbf{A} - \lambda \mathbf{I}) = 0
\end{align*}
$$

---
### 特徵多項式(characteristic polynomial)
$$
P_\mathbf{A}(\lambda) \triangleq \det(\mathbf{A} - \lambda \mathbf{I})
$$
求解特徵值即是求解特徵多項式的根，記為$P_\mathbf{A}(\lambda) = 0$，若為$\mathbf{A}$為$n$階方陣，則$P_\mathbf{A}(\lambda) = 0$為$n$階方程式，因此可以求解$n$個根，可能是相異實根、重根、複數根。

---
### 特徵值速算法 - 主子方陣
複習[ch1 矩陣類型定義](#矩陣類型定義)主子方陣的求法，特徵值速解法如下
$$
\begin{align*}
P_\mathbf{A}(x) &= \det(\mathbf{A} - x \mathbf{I})\\
&= (-1)^n [x^n - \beta_1 x^{n - 1} + \beta_2 x^{n - 2} + \ldots + (-1)^{n - 1} \beta_{n - 1} x + (-1)^n \beta_n 1]
\end{align*}
$$
其中$\beta_k$為$\mathbf{A}$的所有主子方行列式值的和，$\beta_1$為一階主子方行列式值的和即為$\mathbf{A}$的trace，$\beta_n$為$n$階主子方行列式值的和即為$\mathbf{A}$的行列式值。
<br><br>
將特徵方程式展開比較係數可得特徵值相加為$\mathbf{A}$的trace、特徵值相乘為$\mathbf{A}$的行列式值
$$
\begin{align*}
& \lambda_1 + \lambda_2 + \ldots + \lambda_n = \beta_1 = \mathrm{tr}(\mathbf{A})\\
& \lambda_1 \lambda_2 + \lambda_1 \lambda_3 + \ldots + \lambda_{n - 1} \lambda_n = \beta_2\\
& \lambda_1 \lambda_2 \dots \lambda_n = \beta_n = \det(\mathbf{A})
\end{align*}
$$

---
### 特徵向量解法
前面藉由主子方陣求出特徵值，下一步是求特徵向量，將特徵值帶入原矩陣$(\mathbf{A} - \lambda \mathbf{I}) \mathbf{x} = \mathbf{0}$，由Gauss消去法解出有意義的方程式並求非0的$\mathbf{x}$值。2、3階方陣有速解法，由$\det(\mathbf{A} - \lambda \mathbf{I}) = 0$可知該矩陣為奇異矩陣(singular matrix)，其秩數必小於原方陣的階數$n$
1. 2階方陣$\mathrm{rank}(\mathbf{A} - \lambda \mathbf{I}) = 1$，只要從2個方程式任選一個有意義的方程式，並解方程式的解得特徵向量。
2. 3階方陣特徵向量，若$\mathrm{rank}(\mathbf{A} - \lambda \mathbf{I}) = 2$，將2個線性獨立的列向量做外積即為特徵向量，從幾何意義上為找到一向量同時垂直於代表兩平面的法向量。

---
### 線性轉換版的特徵值與特徵向量求法
1. 把$V$的標準基底$\beta$帶入線性轉換$T$，得線性轉換的代表矩陣$[T]_\beta = \mathbf{A}$。
2. 求此代表矩陣的特徵值與特徵向量。
3. 將代表矩陣的特徵向量$\mathbf{x}$還原為原來的基底得線性轉換的特徵向量$\mathbf{v}$。

---
### 重根數(multiplicity)
1. **代數重根數(algebraic multiplicity)**
$$
\begin{align*}
P_\mathbf{A}(x) &= \det(\mathbf{A} - x \mathbf{I})\\
&= (-1)^n [x^n - \beta_1 x^{n - 1} + \ldots + (-1)^n \beta_n 1]\\
&= (-1)^n (x - \lambda_1)^{m_1} (x - \lambda_2)^{m_2} \cdots (x - \lambda_k)^{m_k}
\end{align*}
$$
顧名思義，代數重根就是從代數方程式而來，這個代數方程式就是特徵多項式，其中特徵值$\lambda_i$的代數重根數$m(\lambda = \lambda_i) = m_i$。
2. **特徵空間(eigenspace)**
$$
\begin{align*}
E(\lambda_i) &= \{ \mathbf{x} \mid (\mathbf{A} - \lambda_i \mathbf{I})\mathbf{x} = \mathbf{0} \}\\
&= \mathrm{Null}(\mathbf{A} - \lambda_i \mathbf{I})\\
&= \mathrm{Span}\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k \}
\end{align*}
$$
特徵值$\lambda_i$的特徵空間，就是將特徵值$\lambda_i$對應到特徵向量所span成的空間。
3. **幾何重根數(geometric multiplicity)**
$$
\begin{align*}
g_m(\lambda_i) &= \dim(E(\lambda_i))\\
&= \mathrm{nullity}(\mathbf{A} - \lambda_i \mathbf{I}) = n - \mathrm{rank}(\mathbf{A} - \lambda_i \mathbf{I})
\end{align*}
$$
顧名思義，幾何重根數就是從空間的概念而來，即為特徵空間的dimension。
4. **重要的定理**<br>
幾何重根數必定小於等於代數重根數，舉例來說特徵值$\lambda$有3重根，對應的的特徵向量只有可能是1、2或是3。
$$
1 \leq g_m(\lambda) \leq m(\lambda)
$$

---
### 特徵值/向量性質1 - 矩陣做任意方陣函數運算$g(\mathbf{A})$，特徵值跟著運算$g(\lambda)$，特徵向量不改變

|矩陣$\mathbf{A}$|特徵值$\lambda_i$|特徵向量$\mathbf{v}_i$|
|---|---|---|
|$\mathbf{A}^T$|$\lambda_i$|無關|
|$\mathbf{A}^H$|$\overline{\lambda_i}$|無關|
|$k\mathbf{A}$|$k \lambda_i$|$\mathbf{v}_i$|
|$\mathbf{A}^m$|$\lambda_i^m$|$\mathbf{v}_i$|
|$\mathbf{A}^{-1}$|$\frac{1}{\lambda_i}$|$\mathbf{v}_i$|
|$\mathbf{A} + \alpha \mathbf{I}$|$\lambda_i + \alpha$|$\mathbf{v}_i$|
|$g(\mathbf{A}) = \sum_{k = 0}^\infty a_k \mathbf{A} ^k$|$\sum_{k = 0}^\infty a_k \lambda_i^k$|$\mathbf{v}_i$|

證明
$$
\begin{align*}
\mathbf{A} \mathbf{x}_i = \lambda_i \mathbf{x}_i &\Rightarrow (k\mathbf{A}) \mathbf{x}_i = (k\lambda_i) \mathbf{x}_i\\
\mathbf{A} \mathbf{x}_i = \lambda_i \mathbf{x}_i &\Rightarrow \mathbf{A}\mathbf{A} \mathbf{x}_i = \lambda_i (\mathbf{A} \mathbf{x}_i)\\
&\Rightarrow \mathbf{A}^2 \mathbf{x}_i = \lambda_i^2 \mathbf{x}_i\\
\mathbf{A} \mathbf{x}_i = \lambda_i \mathbf{x}_i &\Rightarrow \mathbf{A}^{-1} \mathbf{A} \mathbf{x}_i = \mathbf{A}^{-1}\lambda_i \mathbf{x}_i\\
&\Rightarrow \mathbf{A}^{-1} \mathbf{x}_i = \frac{1}{\lambda_i} \mathbf{x}_i\\
\mathbf{A} \mathbf{x}_i = \lambda_i \mathbf{x}_i &\Rightarrow \mathbf{A} \mathbf{x}_i + \alpha \mathbf{x}_i = \lambda_i \mathbf{x}_i + \alpha \mathbf{x}_i\\
&\Rightarrow (\mathbf{A} + \alpha) \mathbf{x}_i = (\lambda_i + \alpha)\mathbf{x}_i
\end{align*}
$$

---
### 特徵值/向量性質2 - 不同特徵值，對應特徵向量彼此線性獨立
使用數學歸納法證明，給定條件$\mathbf{A} \in F^{n \times n}$，$\lambda_1, \lambda_2, \ldots, \lambda_r$為相異特徵值，且$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n$為對應的特徵向量。
1. $r = 1$，$\{ \mathbf{x}_1 \neq \mathbf{0} \}$，因此為線性獨立。
2. 假設$r = k$時，$\{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k \}$是線性獨立。
3. 當$r = k + 1$，$\{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k, \mathbf{x}_{k + 1} \}$。<br>
使線性相依/獨立的判別式，令
$$
c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \cdots + c_k \mathbf{x}_k + c_{k + 1} \mathbf{x}_{k + 1} = \mathbf{0} \tag{1}
$$
此時解題想法就是要把$\mathbf{x}_{k + 1}$ 消除，這樣就可以用到數學歸納法第2步的假設。因此把式(1)，分別乘上$\mathbf{A}$與$\lambda_{k + 1}$得式(2)與式(3)，再將式(2)減式(3)得
$$
c_1(\lambda_1 - \lambda_{k + 1})\mathbf{x}_1 + c_2(\lambda_2 - \lambda_{k + 1})\mathbf{x}_2 + \cdots + c_k(\lambda_k - \lambda_{k + 1})\mathbf{x}_k = \mathbf{0}
$$
由於特徵值相異且特徵向量不能等於0，因此得
$$
c_1 = 0, c_2 = 0, \ldots, c_k = 0
$$
並帶入式(1)得$c_{k + 1}$，得證$\{ \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k, \mathbf{x}_{k + 1} \}$是線性獨立。

---
### A可對角化 ⇔ A具有n個線性獨立的特徵向量 ⇔ 幾何重根數等於代數重根數
可對角化的定義，若$\mathbf{A} \in F^{n \times n}$，存在可逆矩陣$\mathbf{P}$使得$\mathbf{P}^{-1} \mathbf{A} \mathbf{P} = \mathbf{D}, \text{where } \mathbf{D} \text{ is diagonal matrix }$，也就是說$\mathbf{A} \sim \mathbf{D}$，稱為可對角化(diagonalize)。由定義可看出相似轉換$\mathbf{A} \sim \mathbf{B}$的特例就是對角化，就是使$\mathbf{A}$相似的矩陣$\mathbf{B}$是對角線矩陣，
1. 先證明$\mathbf{A}$可對角化 $\Rightarrow \mathbf{A}$具有$n$個線性獨立的特徵向量$\mathbf{v}_i$<br>
令$\mathbf{P}$為行向量的形式，$\mathbf{D}$為對角線矩陣
$$
\begin{align*}
\mathbf{P} &= [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n]\\
\mathbf{D} &= \begin{bmatrix}
d_1 & 0 & \cdots & 0\\
0 & d_2 & & \vdots\\
\vdots & & \ddots & 0\\
0 & \cdots & 0 & d_n
\end{bmatrix}
\end{align*}
$$
根據對角化的定義，改寫證明條件
$$
\mathbf{A} \text{ is diagonalizable} \Rightarrow \mathbf{P}^{-1} \mathbf{A} \mathbf{P} = \mathbf{D} \Rightarrow \mathbf{AP} = \mathbf{PD} \text{ and } \mathbf{P} \text{ is invertible}
$$
首先從第一式推導出特徵向量
$$
\begin{align*}
&\mathbf{AP} = \mathbf{PD}\\
\Rightarrow\;& \mathbf{A} [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n] = [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n]
\begin{bmatrix}
d_1 & 0 & \cdots & 0\\
0 & d_2 & & \vdots\\
\vdots & & \ddots & 0\\
0 & \cdots & 0 & d_n
\end{bmatrix}\\
\Rightarrow\;& \mathbf{A} [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n] = [d_1 \mathbf{v}_1, d_2 \mathbf{v}_2, \ldots, d_n \mathbf{v}_n]\\
\Rightarrow\;& \mathbf{A} \mathbf{v}_i = d_i \mathbf{v}_i,\quad i = 1, \ldots, n
\end{align*}
$$
其中$d_i$為$\mathbf{A}$的特徵值，$\mathbf{v}_i$為相應的特徵向量，由此可知$\mathbf{A}$做對角化$\mathbf{PDP}^{-1}$時，其中矩陣$\mathbf{P}$中$n$個行向量放的是$\mathbf{A}$該特徵值相應的特徵向量，而矩陣$\mathbf{D}$中$n$個對角線元素放的是$\mathbf{A}$的特徵值。
<br><br>
再來從第二式推導出線性獨立
$$
\begin{align*}
&\mathbf{P} = [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n] \text{ is invertible}\\
\Rightarrow\;& \det(\mathbf{P}) \neq 0\\
\Rightarrow\;& \mathrm{rank}(\mathbf{P}) = n\\
\Rightarrow\;& \{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \} \text{ is L.I.}
\end{align*}
$$
2. 再證明$\mathbf{A}$可對角化 $\Leftarrow \mathbf{A}$具有$n$個線性獨立的特徵向量$\mathbf{v}_i$<br>
令$\mathbf{P} = [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n]$則
$$
\begin{align*}
\mathbf{AP} &= [\mathbf{A} \mathbf{v}_1, \mathbf{A}\mathbf{v}_2, \ldots, \mathbf{A}\mathbf{v}_n]\\
&= [\lambda_1 \mathbf{v}_1, \lambda_2 \mathbf{v}_2, \ldots, \lambda_n \mathbf{v}_n]\\
&= [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n]
\begin{bmatrix}
\lambda_1 & 0 & \cdots & 0\\
0 & \lambda_2 & & \vdots\\
\vdots & & \ddots & 0\\
0 & \cdots & 0 & \lambda_n
\end{bmatrix}\\
&= \mathbf{PD}
\end{align*}
$$

3. 要判斷是否對角化需要先求出特徵向量再判斷是否線性獨立十分麻煩，因此這裡還有一個等價條件 - **幾何重根數等於代數重根數**。
$$
g_m(\lambda) = m(\lambda); \forall x
$$
若具有$n$個相異的特徵值，則根據關係式$1 \leq g_m(\lambda_i) \leq m(\lambda_i) = 1$，因此有$n$個線性獨立的特徵向量$\mathbf{v}_i$，必定可以被對角化，逆命題不恆真。
<br><br>
總結來說，欲判斷矩陣$\mathbf{A}$是否可對角化，首先判斷特徵值是否相異，皆相異則可對角化，有重根則再繼續判斷幾何重根數是否等於代數重根數$m(\lambda) = g_m(\lambda) = n - \mathrm{rank}(\mathbf{A} - \lambda \mathbf{I})$，若相同則可對角化，不同則不可對角化。
<br><br>
若不可對角化則等價以下條件
$$
\mathbf{A} \text{ isn't diagonalizable}
\Leftrightarrow \mathbf{A} \text{ is defective}
\Leftrightarrow \text{same eigenvalue }\lambda \text{ and } g_m(\lambda) \neq m(\lambda)
$$

---
### 方陣函數的求法 - 同步對角化
若$\mathbf{A},\mathbf{B}$可對角化，存在一可逆矩陣$\mathbf{P}$，同時使得
$$
\mathbf{P}^{-1} \mathbf{A} \mathbf{P} = \mathbf{D}_\mathbf{A} \text{ and } \mathbf{P}^{-1} \mathbf{B} \mathbf{P} = \mathbf{D}_\mathbf{B}
$$
稱$\mathbf{A},\mathbf{B}$可同步對角化。
<br><br>
$\mathbf{P}$存的是原矩陣的特徵向量，因此$\mathbf{A},\mathbf{B}$存在相同的矩陣$\mathbf{P}$，就是$\mathbf{A},\mathbf{B}$具有相同的特徵向量。由前面推導出來特徵值/向量性質1 - **矩陣做任意方陣函數運算$g(\mathbf{A})$，特徵值跟著運算$g(\lambda)$，特徵向量不改變**，因此若要求$g(\mathbf{A})$，可以先將$\mathbf{A}$的對角化，再利用同步對角化求得$g(\mathbf{A})$
$$
\mathbf{A} = \mathbf{P} \mathbf{D} \mathbf{P}^{-1} \Rightarrow g(\mathbf{A}) = \mathbf{P} g(\mathbf{D}) \mathbf{P}^{-1} = g(\mathbf{A}) = \mathbf{P}
\begin{bmatrix}
g(\lambda_1) & 0 & \cdots & 0\\
0 & g(\lambda_2) & & \vdots\\
\vdots & & \ddots & 0\\
0 & \cdots & 0 & g(\lambda_n)
\end{bmatrix}
\mathbf{P}^{-1}
$$

---
### 方陣函數的求法 - Sylvester公式，使用條件 - 相異特徵值
就考試而言，同步對角化法由於最後求$g(\mathbf{A})$要將$g(\mathbf{A}) = \mathbf{P} g(\mathbf{D}) \mathbf{P}^{-1}$乘開，計算量較大，因此除非題目指定用同步對角化，否則特徵值相異則用Sylvester公式法，特徵值相同則用最小多項式法。
<br><br>
Sylvester定理，若$\mathbf{A} \in F^{n \times n}$，若特徵值$\lambda_i$皆相異，則
$$
g(\mathbf{A}) = \sum^n_{i = 1} \frac{g(\lambda_i)}{\Pi^{n}_{\substack{j = 1\\ j \neq 1}}(\lambda_i - \lambda_j)} \Pi^{n}_{\substack{j = 1\\ j \neq 1}}(\mathbf{A} - \lambda_j \mathbf{I}_n)
$$
若$n = 2$則
$$
g(\mathbf{A}_{2 \times 2}) = \frac{g(\lambda_1)}{\lambda_1 - \lambda_2} (\mathbf{A} - \lambda_2 \mathbf{I}) + \frac{g(\lambda_2)}{\lambda_2 - \lambda_1} (\mathbf{A} - \lambda_1 \mathbf{I})
$$
若$n = 3$則
$$
\begin{align*}
g(\mathbf{A}_{3 \times 3}) &= \frac{g(\lambda_1)}{(\lambda_1 - \lambda_2)(\lambda_1 - \lambda_3)} (\mathbf{A} - \lambda_2 \mathbf{I}) (\mathbf{A} - \lambda_3 \mathbf{I})\\
&\; +\; \frac{g(\lambda_2)}{(\lambda_2 - \lambda_1)(\lambda_2 - \lambda_3)} (\mathbf{A} - \lambda_1 \mathbf{I}) (\mathbf{A} - \lambda_3 \mathbf{I})\\
&\; +\; \frac{g(\lambda_3)}{(\lambda_3 - \lambda_1)(\lambda_3 - \lambda_2)} (\mathbf{A} - \lambda_1 \mathbf{I}) (\mathbf{A} - \lambda_2 \mathbf{I})\\
\end{align*}
$$
Sylvester公式口訣有3步驟
1. 分子 - 矩陣做任意方陣函數運算$g(\mathbf{A})$，特徵值跟著運算$g(\lambda)$。
2. 分母 - 減去其他的特徵值。
3. 乘上矩陣，看分母減誰就減誰。

---
## ch5 Jordan form、凱雷-漢米頓定理、最小多項式
### 綱要
- 線代的Jordan form求法 - 點圖(代數重根數 = 點數；幾何重根數 = 行數)
- 線代的廣義特徵向量求法 - 先求老祖宗，再不斷乘上$(\mathbf{A} - \lambda \mathbf{I})$推得下一代
- 線代的Cayley-Hamilton定理與最小多項式的由來、定義、性質與應用
- 線代的一階齊次聯立ODE、可對角化$k$階齊次聯立ODE

---
### Jordan form想法
[ch4 A可對角化的等價條件](#A可對角化-⇔-A具有n個線性獨立的特徵向量-⇔-幾何重根數等於代數重根數)中矩陣$\mathbf{A}$可對角化的前提為$\mathbf{A}$具有$n$個線性獨立的特徵向量，反之不可對角化就代表存在重根$\lambda_k$，此重根的幾何重根數不等於代數重根數$g_m(\lambda_k) \neq m(\lambda_k)$，因此對應的特徵向量不夠。**為了解決特徵向量不夠的問題，我們嘗試用"山寨版"的特徵向量 - 廣義特徵向量來解決**，選擇$(\mathbf{A} - \lambda \mathbf{I})^k \mathbf{x} = \mathbf{0}, k = 2,3,\ldots$，並用"廣義特徵向量循環"這種排列方式將正版與山寨版的特徵向量排列起來成$\mathbf{P}$，如此不可對角化的矩陣$\mathbf{A}$就可以寫成他的Jordan form。

---
### 廣義特徵向量定義與性質
定義 - 給定線性轉換$T : V \to V$，代表矩陣$\mathbf{A} = [T]_S \in F^{n \times n}$，若$\mathbf{x} \neq \mathbf{0}$，且$\mathbf{A}$的特徵值為$\lambda$，使得
$$
(\mathbf{A} - \lambda \mathbf{I})^k \mathbf{x} = \mathbf{0}, k = 1, 2,3,\ldots
$$
會如此定義的原因是$m = 1$時$(\mathbf{A} - \lambda \mathbf{I}) \mathbf{x} = \mathbf{0}$即為一般的特徵向量，若特徵向量"不夠"，令$m = 2$，繼續補線性獨立的向量，以此類推$k = 1, 2,3,\ldots$，當不夠的向量"補夠"了，$(\mathbf{A} - \lambda \mathbf{I})^k \mathbf{x} = \mathbf{0}$再怎麼增加$k$都不會多出現線性獨立的向量。
<br><br>
用空間的觀點來看，特徵空間是廣義特徵空間的子空間，隨著$k$增加，廣義特徵空間會跟著增加，一直到廣義特徵空間補夠了，也就是補到廣義特徵空間的dimension等於代數重根數$m(\lambda)$，廣義特徵空間才不會繼續加大。
$$
\begin{align*}
\underbrace{\mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^1)}_{ \mathrm{Nullity}((\mathbf{A} - \lambda \mathbf{I})^1) = g_m(\lambda) } &\subseteq \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^2) \subseteq \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^3) \subseteq \cdots\\
&\subseteq \underbrace{ \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^k)}_{ \mathrm{Nullity}((\mathbf{A} - \lambda \mathbf{I})^k) = m(\lambda) } = \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^{k + 1}) = \cdots
\end{align*}
$$
參照[ch4 不變子空間](#不變子空間)，因為廣義特徵向量被證明出來是不變子空間，所以可以被類對角化。

---
### 廣義特徵向量循環
給定線性轉換$T : V \to V$，代表矩陣$\mathbf{A} = [T]_S \in F^{n \times n}$，若$\mathbf{x}$為廣義特徵向量，且$\mathbf{A}$的特徵值為$\lambda$，而$k$為使$(\mathbf{A} - \lambda \mathbf{I})^m \mathbf{x} = \mathbf{0}$的最小正整數，則
$$
\{ \underbrace{ (\mathbf{A} - \lambda \mathbf{I})^{k - 1}\mathbf{x}}_{ = \mathbf{v}_1 },\; \underbrace{ (\mathbf{A} - \lambda \mathbf{I})^{k - 2}\mathbf{x}}_{ = \mathbf{v}_2 } ,\; \ldots, \underbrace{ (\mathbf{A} - \lambda \mathbf{I})^1\mathbf{x}}_{ = \mathbf{v}_{k - 1} } ,\; \underbrace{\mathbf{x}}_{ = \mathbf{v}_{k} } \}
$$
稱為一組廣義特徵向量循環(cycle)。
<br><br>
可以把$\mathbf{v}_{k}$想成"老祖宗"，**欲求廣義特徵向量就要先求"老祖宗"，再不斷乘上$(\mathbf{A} - \lambda \mathbf{I})$推得下一代，最後得到後代$\mathbf{v}_1$**，由於
$$
(\mathbf{A} - \lambda \mathbf{I})\mathbf{v}_1 = (\mathbf{A} - \lambda \mathbf{I})(\mathbf{A} - \lambda \mathbf{I})^{k - 1} = 0
$$
因此只有$\mathbf{v}_1$才是正版的特徵向量，其餘都是"山寨版"的特徵向量。

---
### Jordan form求法 - 點圖(代數重根數 = 點數；幾何重根數 = 行數)
1. 求矩陣的特徵值，得代數重根數$m(\lambda)$，為點的個數，每個點代表廣義特徵向量。
2. 利用$g_m(\lambda) = n - \mathrm{rank}(\mathbf{A} - \lambda \mathbf{I})$，求幾何重根數$g_m(\lambda)$，代表"正版"特徵向量的數目，每一行，就代表是一個廣義特徵向量的循環，開頭項由"正版"特徵向量領軍一群"山寨版"特徵向量。
3. 畫出點圖，每一個廣義特徵向量循環的向量個數$n$，等於$n$階方陣，稱為喬登方塊(Jordan Block)，因此一個喬登方塊只會對應到一個特徵值與一個特徵向量。
$$
\mathbf{P}^{-1} \mathbf{A} \mathbf{P} =
\underbrace{ \begin{bmatrix}
\mathbf{J}_1 & & & \mathbf{0}\\
& \mathbf{J}_2 & &\\
& & \ddots &\\
\mathbf{0} & & & \mathbf{J}_L
\end{bmatrix} }_{\text{Jordan form}}
, \text{ where } \mathbf{J}_i =
\underbrace{ \begin{bmatrix}
\lambda_i & 1 & & \mathbf{0}\\
& \lambda_i & \ddots &\\
& & \ddots & 1\\
\mathbf{0} & & & \lambda_i
\end{bmatrix}_{r \times r} }_{\text{Jordan block}}
$$
4. 其中第$k$列的點$\in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^k)$，因此只有$k = 1$時第一列的特徵向量才是"正版"的。

---
### 廣義特徵向量求法 - 先求老祖宗，再不斷乘上$(\mathbf{A} - \lambda \mathbf{I})$推得下一代
前一步用點圖求出Jordan form，給定點圖的一組行(循環)有三個點(向量)，由上至下為$\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$，其中
$$
\cdot \quad \mathbf{v}_1 \in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^1)\\
\cdot \quad \mathbf{v}_2 \in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^2)\\
\cdot \quad \mathbf{v}_3 \in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^3)
$$
要求這三個廣義特徵向量，就要先求老祖宗$\mathbf{v}_3$ - 分別求$\mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^k), k = 1, 2, 3$，再來根據
$$
\mathbf{v}_3 \in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^2) \not\in \mathrm{Null}((\mathbf{A} - \lambda \mathbf{I})^2)
$$
得到$\mathbf{v}_3$，再一代回推下一代
$$
\mathbf{v}_2 = (\mathbf{A} - \lambda \mathbf{I}) \mathbf{v}_3 \rightarrow \mathbf{v}_1 = (\mathbf{A} - \lambda \mathbf{I}) \mathbf{v}_2
$$

---

### 凱雷-漢米頓(Cayley-Hamilton)定理與應用
定義為每一方陣$\mathbf{A} \in F^{n \times n}$，其特徵方程式$f(x) = \det(\mathbf{A} - x\mathbf{I})$，則$f(\mathbf{A}) = \mathbf{0}$。
<br>
也就是說特徵方程式為可零化$\mathbf{A}$的多項式，可以利用"方陣函數"這種類似多項式運算，欲計算原函數，先除以"特徵方程式"這個商，得到餘式，由於"特徵方程式"這個商為可零化$\mathbf{A}$的多項式，所以只須計算餘式即可得原函數值。

---
### 最小多項式(minimal polynomial)的由來、定義與性質
特徵方程式為可零化$\mathbf{A}$的多項式，但是可以零化$\mathbf{A}$的多項式很多，而由於餘式的次冪 < 除式的次冪，餘式次冪越小越好計算，故餘式的次冪也要跟著減小，因此我們要**找可零化$\mathbf{A}$的多項式中次冪最小者**，而為了維持唯一性因此最小多項式在定義上規定**最高次數的係數是1**。
<br><br>
最小多項式有3個性質

1. 最小多項式$m_\mathbf{A}(x)$可以整除所有可零化$\mathbf{A}$的多項式$g(\mathbf{A})$，記為$m_\mathbf{A}(x) \mid g(\mathbf{A}), g(\mathbf{A}) = 0$。
2. $\mathbf{A}$的所有特徵值都是最小多項式的根，記為$m_\mathbf{A}(\lambda) = 0, \forall \lambda$。
3. 最小多項式的根是所有特徵值，但是次冪不知道，需要藉由前面求Jordan form的點圖法求得。
$$
\begin{align*}
\text{If } f(x) &= \det(\mathbf{A} - x\mathbf{I})\\
&= (-1)^n (x - \lambda_1)^{m_1} (x - \lambda_2)^{m_2} \cdots (x - \lambda_k)^{m_k}, m_i : \text{algebraic multiplicity}\\
\text{Then } m_\mathbf{A} &= (x - \lambda_1)^{d_1} (x - \lambda_2)^{d_2} \cdots (x - \lambda_k)^{d_k}
\end{align*}
$$
其中$d_i$為特徵值$\lambda_i$對應的點圖中，最"長"循環的點數。

---
### Cayley-Hamilton與最小多項式的應用
解法為先求特徵多項式並用點圖求最小多項式的次冪，再根據Cayley-Hamiltion定理將矩陣帶入特徵多項式會等於0。
1. 求長串多項式$g(\mathbf{A})$ - 利用長除法，除上最小多項式這個商。
2. 複習[ch1 反矩陣](#反矩陣)中反矩陣求法前三個，Cayley-Hamilton為反矩陣求法的法四，同除以$\mathbf{A}^{-1}$，再把$\mathbf{A}^{-1}$往等號右側移項。
3. 求任意方陣函數$g(\mathbf{A})$
- 利用點圖求最小多項式$m_\mathbf{A}(x)$，為$k$次多項式。
- 因此方陣函數除以$k$次的最小多項式得到少一次也就是$k - 1$次的餘式，故令
$$
g(\mathbf{A}) = \alpha_{k - 1}\mathbf{A}^{k - 1} + \alpha_{k - 2}\mathbf{A}^{k - 2} + \cdots + \alpha_2\mathbf{A}^2 + \alpha_1\mathbf{A} + + \alpha_0\mathbf{I}
$$
- 根據[ch4 特徵值/向量性質1](#特徵值向量性質1---矩陣做任意方陣函數運算gmathbfA，特徵值跟著運算glambda，特徵向量不改變)的觀念 - 矩陣做任意方陣函數運算，特徵值跟著運算，特徵向量不改變，將相異的特徵值帶入上式求解$k$個聯立方程式，若方程式不夠，需要微分再帶入重根的特徵值，求得係數$\alpha_{k - 1}, \alpha_{k - 2}, \ldots, \alpha_2, \alpha_1, \alpha_0$。
- 最後即可求解$g(\mathbf{A})$。
4. [ch4 A可對角化的等價條件](#A可對角化-⇔-A具有n個線性獨立的特徵向量-⇔-幾何重根數等於代數重根數)可對角化的等價條件多一個 - 最小多項式每個因式都是一次
$$
\Leftrightarrow m_\mathbf{A}(x) = (x - \lambda_1)^1 (x - \lambda_2)^1 \cdots (x - \lambda_k)^1
$$
5. 求線性轉換的特徵向量 - $m_T$為$T : V \to V$的最小多項式，也就是$m_T(T) = \mathbf{0}_V$，則所有特徵值為最小多項式$m_T(x) = 0$的根。

---
### 一階齊次聯立ODE(矩陣指數法)
給定聯立方程組
$$
\frac{d \mathbf{x}}{dt} = \mathbf{A} \mathbf{x}(t), \mathbf{x}(0) = \mathbf{x}_0
$$
通解即為$\mathbf{x} = e^{\mathbf{A}t} \mathbf{c}$，欲求$e^{\mathbf{A}t}$，使用[ch5 Cayley-Hamilton與最小多項式的應用](#Cayley-Hamilton與最小多項式的應用)求任意方陣函數$g(\mathbf{A})$的方法。

- **可對角化k階齊次聯立ODE**<br>
給定可對角化(齊次解空間的基底數量夠)的聯立方程組
$$
\frac{d^k \mathbf{x}}{d t^k} = \mathbf{A} \mathbf{x}(t)
$$
令$\mathbf{x} = \mathbf{v} e^{mt}$帶入原ODE，得$\mathbf{Av} = m^k \mathbf{v}$，因此這就是一個特徵值問題，特徵值為$m^k$，對應到的特徵向量$\mathbf{v}$。

---
## ch6 內積空間、正交投影、GSO
### 綱要
- 線代的向量空間 + 3大內積定義 = 內積空間
- 線代的範數定義與證明柯西不等式、三角不等式
- 線代Gram-Schmidt process與QR分解
- 線代的正交投影、正交投影算子與最小平方近似應用、正交投影矩陣
- 線代的頻譜分解/特徵值分解
- 線代的正交補集的定義與性質
- 線代的鏡射算子(Householder算子)的幾何推導與性質

---
### 內積空間(inner product space)
$V$為佈於$F$的向量空間，若存在一函數將$V$中任意有序向量對$\mathbf{x}, \mathbf{y}$映至$F$之一純量，記為$<\mathbf{x}, \mathbf{y}>$，且滿足以下3大內積定義
1. 左線性運算 - $<\mathbf{x} + \mathbf{y}, \mathbf{z}> = <\mathbf{x}, \mathbf{z}> + <\mathbf{y}, \mathbf{z}>$
2. 左線性運算 - $<\alpha\mathbf{x}, \mathbf{z}> = \alpha<\mathbf{x}, \mathbf{z}>$
3. 共軛交換性 - $<\mathbf{x}, \mathbf{y}> = \overline{<\mathbf{y}, \mathbf{x}>}$，代表x,y交換要取共軛
4. 恆正性 - $\forall \mathbf{x} \neq 0, <\mathbf{x}, \mathbf{x}> > 0$，0向量以外的向量，內積恆正

則$V$是具有內積定義的向量空間，稱為內積空間。
> 內積空間不是一個新定義的空間，而是向量空間再加上內積條件所形成的空間。

- 內積只定義左線性運算，至於右線性運算，經以下推導需要將多取"共軛"，故向量內積就是要在後面的數值取共軛。
$$
\begin{align*}
<\mathbf{x}, \alpha \mathbf{y}> &= \overline{<\alpha \mathbf{y}, \mathbf{x}>}\\
&= \overline{\alpha <\mathbf{y}, \mathbf{x}>}\\
&= \overline{\alpha} \; \overline{<\mathbf{y}, \mathbf{x}>}\\
&= \overline{\alpha} <\mathbf{x}, \mathbf{y}>
\end{align*}
$$
- 根據內積定義三大性質可以證明加權內積的weight必大於0。
$$
<\mathbf{u}, \mathbf{v}> = \omega_1 \mathbf{u}_1 \mathbf{v}_1 + \cdots + \omega_n \mathbf{u}_n \mathbf{v}_n, \quad \omega_k > 0
$$

---
### 常見的內積空間的內積定義
1. 歐式空間
$$
\begin{align*}
V = F^n, \mathbf{x} &= \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}, \mathbf{y} = \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n \end{bmatrix}\\
\text{inner product } <\mathbf{x}, \mathbf{y}> &\triangleq x_1 \overline{y_1} + x_2 \overline{y_2} + \cdots + x_n \overline{y_n}\\
&= \overline{\mathbf{y}}^T \mathbf{x} = \mathbf{y}^H \mathbf{x} = \mathbf{y}^* \mathbf{x}
\end{align*}
$$
2. 函數空間
$$
\begin{align*}
& V = C(a, b), f(x),g(x); x \in (a, b)\\
&\text{unweighted inner product } <\mathbf{x}, \mathbf{y}> \triangleq \int^b_a 1 \cdot f(x) \overline{g(x)} dx
\end{align*}
$$
3. 矩陣空間
$$
\begin{align*}
& V = F^{n \times m}, \mathbf{A}, \mathbf{B} \in V\\
& \text{Frobenius inner product } <\mathbf{x}, \mathbf{y}> = \mathbf{tr}(\overline{\mathbf{B}}^T \mathbf{A})
\end{align*}
$$
Frobenius內積即為把矩陣拉直，跟歐式空間做一樣的內積。

---
### 範數(norm)
$V$為一內積空間，範數的定義就是向量自己跟自己內積並開根號，白話來說範數就是廣義的"長度
。
$$
\| \mathbf{x} \| = \sqrt{<\mathbf{x}, \mathbf{x}>}
$$
若norm為1則代表單位向量，若向量除以自己的norm代表normalize，重要定理有以下6個
1. $\|c \mathbf{x} \| = |c| \| \mathbf{x} \|$
$$
\|c \mathbf{x} \| = \sqrt{<c \mathbf{x}, c \mathbf{x}>} = \sqrt{c c^* <\mathbf{x}, \mathbf{x}>} = \sqrt{|c|^2 <\mathbf{x}, \mathbf{x}>} = |c| \| \mathbf{x} \|
$$
2. $\mathbf{x} = \mathbf{0} \Leftrightarrow \| \mathbf{x} \| = 0$，根據內積空間的定義 - 恆正性，norm是0的向量必定是0向量。
4. 柯西不等式(Cauchy-Schwarz inequality) - 內積取絕對值小於等於個別向量取norm相乘，從$\| \mathbf{x} - C \mathbf{y}\|^2$展開下去證明
$$
| <\mathbf{x}, \mathbf{y}> | \leq \|\mathbf{x}\|\|\mathbf{y}\|
$$
只有在向量$\mathbf{x}$平行於$\mathbf{y}$時，柯西不等式的等號才會成立。
4. 三角不等式(Triangle inequality) - 兩向量個別長度大於等於向量和的長度，從$\| \mathbf{x} + \mathbf{y}\|^2$展開下去證明
$$
\| \mathbf{x} + \mathbf{y} \| \leq \|\mathbf{x}\| + \|\mathbf{y}\|
$$
5. 畢氏定理(THe Pythagorean law) - 如果$<\mathbf{x}, \mathbf{y}> = 0$，則$\| \mathbf{x} + \mathbf{y} \|^2 = \|\mathbf{x}\|^2 + \|\mathbf{y}\|^2$。
6. 平行四邊形定理(Parallelogram law) - 平行四邊形兩對角線長度的平方和等於其四個邊長的平方和
$$
\| \mathbf{x} + \mathbf{y} \| + \| \mathbf{x} - \mathbf{y} \| = 2 \| \mathbf{x} \|^2 + 2 \| \mathbf{y} \|^2
$$

---
### 正交投影
欲求向量$\mathbf{y}$在向量$\mathbf{x}$的投影分量
$$
\begin{align*}
& \text{let projection of } \mathbf{y} \text{ on } \mathbf{x} \text{ is }\mathbf{y}' = C\mathbf{x} \quad \because \mathbf{y} \parallel \mathbf{x}\\
\Rightarrow\;& (\mathbf{y} - \mathbf{y}') \perp \mathbf{x}\\
\Rightarrow\;& <(\mathbf{y} - C\mathbf{x}, \mathbf{x}> = C<\mathbf{x}, \mathbf{x}>\\
\Rightarrow\;& C = \frac{<\mathbf{y}, \mathbf{x}>}{\| \mathbf{x} \|^2 }\\
& \therefore \mathbf{y}' = \text{Proj}_{,\mathbf{x}}(\mathbf{y}) = \frac{<\mathbf{y}, \mathbf{x}>}{\| \mathbf{x} \|^2 } \mathbf{x}
\end{align*}
$$

---
### GSO(Gram-Schmidt orthogonalization/process)的由來與計算流程
根據[ch2 基底(basis)](#基底basis)基底的定義，只需要滿足線性獨立即可，而線性獨立的基底是堪用但不是最好的基底，使用單位正交向量還表達的基底才是最好用的基底，這也是為什麼微積分都使用的座標系統 - 直角坐標、圓柱座標、球座標都是單位正交基底。
<br><br>
既然單位正交基底是很好的基底，那要怎麼求單位正交基底呢?使用GSO將線性獨立的向量集轉換為單位正交向量集。
$$
\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \} \to \{ \mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n \}\\
\text{where} <\mathbf{x}_i, \mathbf{x}_j> = 0, i \neq j\\
<\mathbf{e}_i, \mathbf{e}_j> =
\begin{cases}
1, & i = j \quad\ldots \text{unit}\\
0, & i \neq j \quad\ldots \text{orthogonal}\\
\end{cases}
$$
首先從線性獨立向量集任選一個基底
$$
\mathbf{x}_1 = \mathbf{v}_1
$$
再來將第2個基底扣除第2個基底在第1個基底投影的分量，就等於在找到正交於第1個基底的向量
$$
\begin{align*}
\mathbf{x}_2 &= \mathbf{v}_2 - \mathbf{v}_{2, \parallel}\\
&= \mathbf{v}_2 - \frac{<\mathbf{v}_2, \mathbf{x}_1>}{\| \mathbf{x}_1 \|^2 } \mathbf{x}_1
\end{align*}
$$
同理第3個基底要扣除第3個基底在第2個基底與第1個基底投影的分量
$$
\begin{align*}
\mathbf{x}_3 &= \mathbf{v}_3 - \mathbf{v}_{3, \parallel}\\
&= \mathbf{v}_3 - \frac{<\mathbf{v}_3, \mathbf{x}_1>}{\| \mathbf{x}_1 \|^2 } \mathbf{x}_1 - \frac{<\mathbf{v}_3, \mathbf{x}_2>}{\| \mathbf{x}_2 \|^2 } \mathbf{x}_2\\
\mathbf{x}_4 &= \cdots
\end{align*}
$$
再將求出來所有正交基底正規化(normalize)，也就是除以各自向量的norm，記為$\mathbf{e}_i = \frac{\mathbf{x}_i}{\| \mathbf{x}_i\|}$，得單位正交基底
$$
\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \} \overset{\text{normalize}}{\longrightarrow} \{ \mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n \}\\
$$

---
### QR分解的由來與計算流程
GSO就是線性獨立的向量集$\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \}$轉換單位正交的向量集$\{ \mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n \}$，也就是說用新的基底來表示原本的基底，故可寫做(為求簡化問題，先將原向量做正規化)
$$
\begin{align*}
\mathbf{v}_1 &= <\mathbf{v}_1, \mathbf{e}_1> \mathbf{e}_1\\
\mathbf{v}_2 &= <\mathbf{v}_2, \mathbf{e}_1> \mathbf{e}_1 + <\mathbf{v}_2, \mathbf{e}_2> \mathbf{e}_2\\
\mathbf{v}_3 &= <\mathbf{v}_3, \mathbf{e}_1> \mathbf{e}_1 + <\mathbf{v}_3, \mathbf{e}_2> \mathbf{e}_2 + <\mathbf{v}_3, \mathbf{e}_3> \mathbf{e}_3
\end{align*}
$$
將上式寫成矩陣形式
$$
\underbrace{ \begin{bmatrix}
\mid & \mid & \mid\\
\mathbf{v}_1 & \mathbf{v}_2 & \mathbf{v}_3\\
\mid & \mid & \mid
\end{bmatrix} }_{\mathbf{A}}
= \underbrace{\begin{bmatrix}
\mid & \mid & \mid\\
\mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_1\\
\mid & \mid & \mid
\end{bmatrix}}_{\mathbf{Q}} \quad
\underbrace{\begin{bmatrix}
<\mathbf{v}_1, \mathbf{e}_1> & <\mathbf{v}_2, \mathbf{e}_1> & <\mathbf{v}_3, \mathbf{e}_1>\\
0 & <\mathbf{v}_2, \mathbf{e}_2> & <\mathbf{v}_3, \mathbf{e}_2>\\
0 & 0 & <\mathbf{v}_3, \mathbf{e}_3>\\
\end{bmatrix}}_{\mathbf{R}}
$$
這就是QR分解，其中矩陣$\mathbf{A}$要求**行向量是線性獨立**，即為矩陣做QR分解的前提假設，矩陣$\mathbf{Q}$的行向量單位正交，因此為正交矩陣，矩陣$\mathbf{R}$是一個上三角矩陣。
<br><br>
首先判斷矩陣行向量是否獨立，若符合則開始做矩陣$\mathbf{A}$的QR分解 - 把矩陣的行向量拆成線性獨立的向量集，做GSO得單位正交的向量集，合成為正交矩陣$\mathbf{Q}$，再來欲求矩陣$\mathbf{R}$，除了可以根據GSO步驟的關係式求之外，可以根據以下正交矩陣好用的性質$\mathbf{Q}^{-1} = \mathbf{Q}^T$快速求得
$$
\mathbf{A} = \mathbf{Q} \mathbf{R} \Rightarrow \mathbf{R} = \mathbf{Q}^{-1} \mathbf{A} =\mathbf{Q}^T \mathbf{A}
$$

---
### 正交投影(orthogonal projection)
<br>
直觀的幾何理解如上圖，所有分量都可以拆成水平和垂直的方量，而比較數學上的嚴謹定義如下 - $V$為佈於$F$的內積空間，$W$為$V$的子空間，$\forall \mathbf{v} \in V$。若存在$\mathbf{v}_0 \in W$，使得
$$
<\mathbf{v} - \mathbf{v}_0, \omega> = 0, \quad\forall \mathbf{\omega} \in W
$$
則稱$\mathbf{v}_0$為$\mathbf{v}$在$W$的正交投影，記為$\mathbf{v}_0 = \text{Proj}_{, W}(\mathbf{v})$。
<br><br>
性質為若$\{ \mathbf{\phi}_1, \mathbf{\phi}_2, \ldots, \mathbf{\phi}_k \}$為$W$的一組正交基底，則正交投影為
$$
\mathrm{Proj}_{, W}(\mathbf{v}) = \sum^k_{i = 1} \frac{<\mathbf{v}, \mathbf{\phi}_i>}{\| \mathbf{\phi}_i \|^2} \mathbf{\phi}_i
$$
且具有唯一性。

---
### 正交投影的解題
法一是使用上述性質，給在$W$的一組基底，首先做GSO，化為單位正交基底$\{ \mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_k \}$，正交投影即為
$$
\mathrm{Proj}_{, W}(\mathbf{v}) = <\mathbf{v}, \mathbf{e}_1> \mathbf{e}_1 + <\mathbf{v}, \mathbf{e}_2> \mathbf{e}_2 + \cdots + <\mathbf{v}, \mathbf{e}_k> \mathbf{e}_k
$$
法二是根據正交投影的數學定義做，給在$W$的一組基底，令正交投影為$\mathbf{v}_0 = \text{Proj}_{, W}(\mathbf{v}) \in W$，由於在子空間$W$裡面，因此為$W$的基底的線性組合，解聯立方程式$<\mathbf{v} - \mathbf{v}_0, \omega_i> = 0, i = 1, 2, \ldots , k$，得正交投影$\mathbf{v}_0$。

---
### 正交投影算子定義與性質
正交投影算子白話來說就是一個做正交投影的函數，定義為$V$為佈於$F$的內積空間，$W$為$V$的子空間
$$
T : V \to V, T(\mathbf{v}) = \mathrm{Proj}_{, W}(\mathbf{v}), \forall \mathbf{v} \in V
$$
稱$T$是$V$在$W$的正交投影算子，性質如下
1. $T$是線性運算，使用[ch3 線性轉換(linear transformation)](#線性轉換linear-transformation)觀念證明。
2. $\mathrm{Range}(T) = W$，因為函數$T$是把定義域投影至平面$W$。
3. 正交投影算子只有2個特徵值 - 當向量平躺在投影平面$W$時，向量投影後還是自己，因此特徵值為1。
$$
\forall \mathbf{v} \in W \Rightarrow T(\mathbf{v}) = \mathbf{v}
\Rightarrow E(\lambda = 1) = W
$$
4. 正交投影算子只有2個特徵值 - 當向量垂直於投影平面$W$時，向量投影後就變成一個點，就是0向量，因此特徵值為0。
$$
\forall \mathbf{v} \perp W \Rightarrow T(\mathbf{v}) = \mathbf{0} = 0\mathbf{v}
\Rightarrow E(\lambda = 0) = \{ \mathbf{v} \mid \forall \mathbf{v} \perp W \} = \mathrm{Null}(T)
$$
5. 正交投影算子是idempotent，即$T^2 = T$，代表一個矩陣投影兩次跟投影一次是一樣。

---
### 最小平方近似(least square approximation)
定理為$T : V \to V$為$V$在$W$的正交投影算子，則
$$
\| \mathbf{v} - T(\mathbf{v})\| \leq \| \mathbf{v} - \mathbf{w} \|, \forall \mathbf{v}, \mathbf{w} \in V
$$
稱$T(\mathbf{v})$為$\mathbf{v}$在$W$上的最小平方近似。記憶口訣是**最短距離就是垂直投影，最佳近似就是正交投影**。
<br><br>
證明
$$
\begin{align*}
T(\mathbf{v}) &= \mathbf{v}_0 = \mathrm{Proj}_{, W}(\mathbf{v}) \in W \Rightarrow (\mathbf{v} - \mathbf{v}_0) \perp W, \forall \mathbf{w} \in W\\
\| \mathbf{v} - \mathbf{w} \|^2 &= \| \underbrace{\mathbf{v} - \mathbf{v}_0}_{\mathbf{x} \perp W} + \underbrace{\mathbf{v}_0 - \mathbf{w}}_{\mathbf{y} \in W} \|^2\\
&= \| \mathbf{x} + \mathbf{y} \|^2\\
&= \|\mathbf{x}\|^2 + \|\mathbf{y}\|^2 \quad \because <\mathbf{x}, \mathbf{y}> = 0\\
&\geq \|\mathbf{x}\|^2 = \|\mathbf{v} - \mathbf{v}_0\|^2
\end{align*}
$$

---
### 正交投影矩陣
[SVD篇 重點1 線性轉換](https://hackmd.io/@HsuChiChen/linear_algebra_svd#重點1-線性轉換)可知歐式空間的線性轉換相當於做矩陣乘法，因此在歐式空間中的正交投影算子使用代表矩陣表示，這個代表矩陣稱為正交投影矩陣。
<br><br>
給定$\{\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_k\}$為歐式向量空間$W$的一組**單位正交**基底，則正交投影矩陣為
$$
\mathbf{P} = \mathbf{e}_1 \overline{{\mathbf{e}_1}}^T + \mathbf{e}_2 \overline{{\mathbf{e}_2}}^T + \cdots + \mathbf{e}_k \overline{{\mathbf{e}_k}}^T
$$
使用正交投影向量下去證明
$$
\mathbf{v}_0 = \mathrm{Proj}_{, W}(\mathbf{v}) = \sum^k_{i = 1} \frac{<\mathbf{v}, \mathbf{e}_i>}{\| \mathbf{e}_i \|^2} \mathbf{e}_i = \cdots = (\underbrace{\mathbf{e}_1 \overline{{\mathbf{e}_1}}^T + \mathbf{e}_2 \overline{{\mathbf{e}_2}}^T + \cdots + \mathbf{e}_k \overline{{\mathbf{e}_k}}^T}_{\mathbf{P}}) \mathbf{v}
$$
正交投影矩陣的性質為對稱矩陣$\mathbf{P} = \mathbf{P}^T$、idempotent$\mathbf{P}^2 = \mathbf{P}$、rank-one矩陣$\mathrm{rank}(\mathbf{P}) = 1$，故正交投影矩陣是奇異矩陣。

---
### 頻譜分解/特徵值分解
給定$n$階方陣，若可對角化，則
$$
\begin{align*}
\mathbf{A} &= \mathbf{P} \mathbf{D} \mathbf{P}^{-1}\\
&= \mathbf{P} (\lambda_1\mathbf{D}_1) \mathbf{P}^{-1} + \cdots \mathbf{P} (\lambda_k\mathbf{D}_k) \mathbf{P}^{-1}\\
&= \lambda_1 \mathbf{A}_1 + \cdots \lambda_k \mathbf{A}_k\\
\end{align*}
$$
其中$\lambda_1, \lambda_2, \ldots, \lambda_k$為相異特徵值(可重根)，$\mathbf{A}_i$為在該特徵值對應到的特徵空間$E(\lambda_i)$的投影矩陣。性質如下
1. $\mathbf{A}_i \mathbf{A}_j \forall i \neq j$
2. $\mathbf{A}_1 + \mathbf{A}_2 + \cdots \mathbf{A}_k = \mathbf{I}$
3. $\mathbf{A}^2 = \lambda_1^2\mathbf{A}_1 + \lambda_2^2\mathbf{A}_2 + \lambda_k^2\mathbf{A}_k$
4. 具有投影矩陣的性質

---
### 正交補集(orthogonal complement)的定義與性質
$V$為佈於$F$的內積空間，$S$為$V$的子集合(不一定要子空間)，則正交補集為$V$中所有與$S$內每一個向量$\mathbf{x}$皆為正交的向量，全部丟進集合內。
$$
S^\perp \equiv \{ \mathbf{y} \mid <\mathbf{y}, \mathbf{x}> = 0; \forall \mathbf{x} \in S \}
$$
性質如下
1. $S^\perp$必為$V$的子空間
2. 若$S$是$V$的子集合，其補集的補集會變成子空間，而非原本的子集合，記為$(S^\perp)^\perp \neq S, S \subseteq (S^\perp)^\perp$。
3. 若$W$是$V$的子空間，其補集的補集才會是自己，記為$(W^\perp)^\perp = W$。

---
### 常見的正交補集
1. row space跟null space互為正交補集
$$
\mathrm{Row}(\mathbf{A})^\perp = \mathrm{Null}(\mathbf{A})
$$
2. column space和left null space互為正交補集
$$
\mathrm{Col}(\mathbf{A})^\perp = \mathrm{LNull}(\mathbf{A})
$$
證明第2點
$$
\begin{align*}
& \forall \mathbf{\omega} = \mathrm{Col}(\mathbf{A})\\
\Rightarrow\;& \mathbf{\omega} = \mathbf{Ax},\; \forall \mathbf{x}\\
& \forall \mathbf{y} = \mathrm{Col}(\mathbf{A})^\perp\\
\Rightarrow\;& <\mathbf{y}, \mathbf{\omega}> = 0\\
\Rightarrow\;& <\mathbf{y}, \mathbf{Ax}> = 0\\
\Rightarrow\;& (\mathbf{Ax})^H \mathbf{y} = 0\\
\Rightarrow\;& \mathbf{x}^H (\mathbf{A}^H\mathbf{y}) = 0\\
\Rightarrow\;& < \mathbf{A}^H\mathbf{y}, \mathbf{x}> = 0,\; \forall \mathbf{x}\\
\Rightarrow\;& \mathbf{A}^H\mathbf{y} = 0\\
\Rightarrow\;& \mathbf{y} \in \mathrm{Null}(\mathbf{A}^T) = \mathrm{LNull}(\mathbf{A})
\end{align*}
$$

---
### 子空間與子空間的正交補集的直和空間 = 向量空間
$V$為佈於$F$的內積空間，$W$為$V$的子空間，則$V = W \oplus W^\perp$。<br>欲此性質，參照[ch2 和空間(sum space)](#和空間sum-space)中直和空間的兩個定義
1. $V = W + W^\perp$<br>
任何向量都可以拆成水平和垂直分量，$\mathbf{v} = \mathrm{Proj}_{, W}(\mathbf{v}) + \mathrm{Proj}_{, W^\perp}(\mathbf{v})$
2. $W \cap W^\perp = \{ \mathbf{0} \}$
$$
\begin{align*}
& \forall \mathbf{x} \in W \cap W^\perp\\
\Rightarrow\;& \mathbf{x} \in W \text{ and } \mathbf{x} \in W^\perp\\
\Rightarrow\;& <\mathbf{x}, \mathbf{x}> = 0\\
\Rightarrow\;& \| \mathbf{x} \| = 0 \Leftrightarrow \mathbf{x} = 0
\end{align*}
$$
根據此性質$V = W \oplus W^\perp$，在解題上就有一個技巧，假設$V \in \mathbb{R}^4, W\in \mathbb{R}^3$，欲求向量$\mathbf{v}$在$W$空間的正交投影$\mathrm{Proj}_{, W}(\mathbf{v})$，就可以先求僅有一維空間的$W^\perp \in \mathbb{R}^1$，在使用關係式$\mathbf{v} = \mathrm{Proj}_{, W}(\mathbf{v}) + \mathrm{Proj}_{, W^\perp}(\mathbf{v})$求得。
<br><br>
另外可以推得投影至$W$的投影矩陣$\mathbf{P}$與投影至$W^\perp$的投影矩陣$\mathbf{Q}$相加即為單位矩陣$\mathbf{I}$。
$$
\begin{align*}
& \forall \mathbf{v} \in V = W \oplus W^\perp\\
\mathbf{v} &= \mathrm{Proj}_{, W}(\mathbf{v}) + \mathrm{Proj}_{, W^\perp}(\mathbf{v})\\
&= \mathbf{P} \mathbf{v} + \mathbf{Q} \mathbf{v}\\
&= (\mathbf{P} + \mathbf{Q}) \mathbf{v}\\
& \therefore \mathbf{P} + \mathbf{Q} = \mathbf{I}
\end{align*}
$$

---
### 鏡射算子(Householder算子)的幾何推導與性質
<br>
給定一面鏡子$W$，鏡子垂直的空間$U$就是$W$的正交補集，由於任意向量都可以拆解為水平和垂直距離，故將$\mathbf{Hx}$拆解為
$$
\begin{align*}
\mathbf{Hx} &= \mathbf{y} - \mathbf{z}\\
&= (\mathbf{x} - \mathbf{z}) - \mathbf{z}\\
&= (\mathbf{x} - 2\mathbf{z}\\
&= (\mathbf{x} - \mathrm{Proj}_{,U}(\mathbf{x})\\
&= \underbrace{(\mathbf{I} - 2\mathbf{uu}^T)}_{\text{Householder matrix}} \mathbf{x}
\end{align*}
$$
如[ch6 正交投影矩陣](#正交投影矩陣)，需要注意向量$\mathbf{u}$的norm是1，即$\|\mathbf{u} \| = 1$，才可推得此正交投影矩陣的形式。
<br><br>
鏡射算子有4個比較重要的性質。

1. 實對稱矩陣$\mathbf{H}^T = \mathbf{H}$，證明從計算$\mathbf{H}^H = (\mathbf{I} - 2\mathbf{uu}^T)^H$開始。
2. 正交矩陣$\mathbf{H}^T \mathbf{H} = \mathbf{I} \Leftrightarrow \mathbf{H}^T = \mathbf{H}^{-1}$，證明從計算$\mathbf{H}^T \mathbf{H} = \mathbf{H} \mathbf{H}$開始。而正交算子有個性質 - 運算前後保範數，故$\|\mathbf{x}\| = \| \mathbf{Hx}\|$。
3. 由鏡射算子性質1、2可知$\mathbf{H}^2 = \mathbf{I} \Rightarrow \mathbf{H}^2 - \mathbf{I} = 0$，故最小多項式為$m_\mathbf{H}(x) = (x - 1)^1 (x + 1)^1$可知
- 參照[ch5 最小多項式(minimal polynomial)的由來、定義與性質](#最小多項式minimal-polynomial的由來、定義與性質)，由於最小多項式每個因式都是一次，故可對角化。
- 參照[ch5 Cayley-Hamilton與最小多項式的應用](#Cayley-Hamilton與最小多項式的應用)最小多項式的根是所有特徵值，故鏡射算子的特徵值只有1和-1 - 其中特徵值是1代表躺在鏡子上的向量；特徵值是-1代表垂直於鏡子的向量，由於垂直於鏡子的空間只有1維，故幾何重根數等於1；由於可對角化，因此幾何重根數又等於代數重根數；由於垂直於鏡子的空間與鏡子的空間互為正交補集，故特徵值是1的幾何重根數為$n - 1$。
$$
\begin{align*}
& E(\lambda = -1) = U = \mathrm{Span}\{ \mathbf{u} \} \Rightarrow g_m(\lambda = -1) = 1 = m(\lambda = -1) \;\because \text{diagonalizable matrix}\\
& E(\lambda = 1) = W = U^\perp \Rightarrow g_m(\lambda = 1) = n - 1 = m(\lambda = 1) \;\because U^\perp \oplus U = \mathbb{R}^n
\end{align*}
$$
因此參照[ch4 特徵值速算法 - 主子方陣](#特徵值速算法---主子方陣)特徵值的性質可知
$$
\begin{align*}
\mathrm{tr}(\mathbf{H}) &= \lambda_1 + \lambda_2 + \ldots + \lambda_n = (n - 1)\cdot 1 + 1\cdot(-1) = n - 2\\
\det(\mathbf{H}) &= \lambda_1 \lambda_2 \dots \lambda_n = 1 \cdot 1 \cdots 1 \cdot (-1) = -1\\
\mathrm{rank}(\mathbf{H}) &= n \;\ldots\text{full rank} \quad\because \det(\mathbf{H}) \neq 0
\end{align*}
$$

---
## ch7 正交對角化、二次式、SVD
### 綱要
- 線代的最小平方近似解、最小範數解
- 線代的正規矩陣與正交對角化
- 線代的二次式的應用 - 判斷正負性、雷利商
- 線代的"平民版"的正交對角化 - 奇異值分解(SVD)

---
### 伴隨算子(adjoint operator)
與[ch1 反矩陣](#反矩陣)中提及的伴隨矩陣是完全不同的東西，
$V$是佈於$F$的內積空間，$T : V \to V$為一線性轉換，若$T^* : V \to V$為一函數，滿足
$$
<T(x\mathbf{x}), \mathbf{y}> = <\mathbf{x}, T^*(\mathbf{y})>
$$
則稱$T^*$為$T$的伴隨算子。<br>
若$\beta$為$V$的一組單位正交基底，則伴隨算子的代表矩陣為共軛加轉置
$$
[T]_\beta = \mathbf{A}, [T^*]_\beta = \mathbf{A}^* = \overline{\mathbf{A}}^T
$$

---
### 最小平方近似解
給定聯立方程式$\mathbf{Ax} = \mathbf{b}$無解，也就是說$\mathbf{b} \not\in \mathrm{Col}(\mathbf{A})$，且矩陣行獨立$\mathrm{rank}(\mathbf{A}) = n$，但問題總不能這樣就結束，因此我們"試圖"找到一個近似解的折衷方案使得
$$
\| \mathbf{Ax}_{LS} - \mathbf{b}\| \leq \| \mathbf{Ax} - \mathbf{b} \|
$$
由[ch6 最小平方近似(least square approximation)](#最小平方近似least-square-approximation)觀念可知 - 最短距離就是垂直投影，最佳近似就是正交投影，如下圖所示
<br>
令$W = \mathrm{Col}(\mathbf{A})$，則$W^\perp = \mathrm{Null}(\overline{\mathbf{A}}^T)$。由正交投影可知，存在唯一$\mathbf{v}_0 = \mathrm{Proj}_{,W}(\mathbf{b}) = \mathbf{Ax}_{LS}$使得$\| \mathbf{Ax}_{LS} - \mathbf{b}\| \leq \| \mathbf{Ax} - \mathbf{b} \|$。
$$
\begin{align*}
& \mathbf{Ax}_{LS} = \mathrm{Proj}_{,W}(\mathbf{b})\\
\Rightarrow\;& (\mathbf{Ax}_{LS} - \mathbf{b}) \perp W\\
\Rightarrow\;& <\mathbf{Ax}_{LS} - \mathbf{b}, \mathbf{w}> = 0, \forall \mathbf{w} \in W = \mathrm{Col}(\mathbf{A})\\
\Rightarrow\;& <\mathbf{Ax}_{LS} - \mathbf{b}, \mathbf{Ax}> = 0, \forall \mathbf{x}\\
\Rightarrow\;& <\mathbf{A}^*(\mathbf{Ax}_{LS} - \mathbf{b}), \mathbf{x}> = 0, \forall \mathbf{x} \quad \because \text{adjoint operator}\\
\Rightarrow\;& \mathbf{A}^*(\mathbf{Ax}_{LS} - \mathbf{b}) = 0\\
\Rightarrow\;& \mathbf{A}^* \mathbf{Ax}_{LS} = \mathbf{A}^* \mathbf{b} \quad \ldots \text{Normal equation}\\
\Rightarrow\;& \mathbf{x}_{LS} = ( \mathbf{A}^* \mathbf{A})^{-1} \mathbf{A}^* \mathbf{b} \quad \because \mathrm{rank}(\mathbf{A}) = n \Rightarrow \mathrm{rank}(\mathbf{A}^*\mathbf{A}) = n \Rightarrow \exists (\mathbf{A}^*\mathbf{A})^{-1}
\end{align*}
$$

---
### 正交投影矩陣的特殊情況解法
[ch6 正交投影矩陣](#正交投影矩陣)講到正交投影矩陣的求法，若是在矩陣$\mathbf{A}$行獨立，要投影的平面為矩陣$\mathbf{A}$的column space，則可以將正交投影矩陣寫做$\mathbf{P} = \mathbf{A} (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T$。
$$
\begin{align*}
\mathbf{A}^T (\mathbf{Ax}_{LS}) &= \mathbf{A}^T (\mathbf{b}) \Rightarrow \mathbf{x}_{LS} = ( \mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b}\\
\mathrm{Proj}_{,W}(\mathbf{b}) &= \mathbf{Ax}_{LS}\\
&= \underbrace{\mathbf{A} (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T}_{\text{(orthogonal) projection matrix } \mathbf{A}} \mathbf{b}
\end{align*}
$$

---
### 最小範數解
給定聯立方程式$\mathbf{Ax} = \mathbf{b}$無限多組解，求所有解中$\|\mathbf{x}\|$最小的解答$\mathbf{x}_{min}$，以通訊觀點而言，離原點的距離就是能量，因此就是在所有可能的條件之內找能量最小者。
<br><br>
無限多組解，可將解拆為齊次解與特解$\mathbf{x} = \mathbf{x}_h + \mathbf{x}_p$
$$
\begin{align*}
& \mathbf{A}(\mathbf{x}_h + \mathbf{x}_p) = \mathbf{b}\\
&\text{where } \mathbf{x}_h \in \mathrm{Null}(\mathbf{A}), \mathbf{x}_p \in \mathrm{Row}(\mathbf{A}), \mathrm{Null}(\mathbf{A}) \oplus \mathrm{Row}(\mathbf{A}) = F^n\\
\Rightarrow\;& \mathbf{A} \mathbf{x}_h + \mathbf{A} \mathbf{x}_p = \mathbf{b}\\
\Rightarrow\;& \mathbf{0} + \mathbf{A} \mathbf{x}_p = \mathbf{b} \quad \because \mathbf{x}_h \in \mathrm{Null}(\mathbf{A})\\
\Rightarrow\;& \mathbf{x}_p = \mathbf{b}
\end{align*}
$$
其中齊次解對解答$\mathbf{b}$沒有貢獻，屬於null space，只有特解才對解答$\mathbf{b}$有貢獻。
$$
\begin{align*}
\|\mathbf{x} \|^2 &= \| \mathbf{x}_h + \mathbf{x}_p \|^2\\
&= \|\mathbf{x}_h\|^2 + \|\mathbf{x}_p\|^2 \quad <\mathbf{x}_h, \mathbf{x}_p> = 0\\
&\geq \|\mathbf{x}_p\|^2\\
&\therefore \mathbf{x}_{min} = \mathbf{x}_p \in \mathrm{Null}(\mathbf{A}) = \mathrm{Col}(\mathbf{A}^T)
\end{align*}
$$
最小範數解就是落在$\mathbf{A}^T$的column space，因此欲解$\mathbf{Ax} = \mathbf{b}$，就是令解答$\mathbf{x}_{min} = \mathbf{A}^T \mathbf{v}$，帶入原方程式解得$\mathbf{v}$，再帶回$\mathbf{x}_{min} = \mathbf{A}^T \mathbf{v}$，解得最小範數解。

---
### 正規矩陣與正交對角化
1. (線性函數版)正規算子(normal operator)定義 - $V$是佈於$F$的內積空間，$T : V \to V$為一線性轉換，若$T^* : V \to V$為伴隨算子，若滿足$T^* \circ T = T \circ T^*$，稱$T$是normal operator。
2. (矩陣版)正規矩陣(normal matrix)定義 - $\mathbf{A} \in F^{n \times n}$，若滿足$\mathbf{A}^* \mathbf{A} = \mathbf{A} \mathbf{A}^*$，稱$\mathbf{A}$為normal matrix。參照[ch1 特殊矩陣](#特殊矩陣)內容，**赫米特(實對稱)/斜赫米特(斜實對稱)/正交(么正)矩陣都是正規矩陣**。
<br><br>
正規矩陣性質 - 不同特徵值，對應特徵向量彼此(單位)正交
$$
\begin{align*}
& \mathbf{A} \mathbf{x}_i = \lambda_i \mathbf{x}_i \Rightarrow \mathbf{A}^* \mathbf{x}_i = \overline{\lambda_i} \mathbf{x}_i\\
& \mathbf{A} \mathbf{x}_j = \lambda_j \mathbf{x}_j \Rightarrow \mathbf{A}^* \mathbf{x}_j = \overline{\lambda_j} \mathbf{x}_j\\
& \lambda_i <\mathbf{x}_i, \mathbf{x}_j>\\
&= <\lambda_i\mathbf{x}_i, \mathbf{x}_j>\\
&= <\mathbf{A} \mathbf{x}_i, \mathbf{x}_j>\\
&= <\mathbf{x}_i, \mathbf{A}^* \mathbf{x}_j> \quad \because \text{adjoint operator}\\
&= <\mathbf{x}_i, \overline{\lambda_j} \mathbf{x}_j>\\
&= \lambda_j <\mathbf{x}_i, \mathbf{x}_j>\\
\Rightarrow\;& \underbrace{(\lambda_i - \lambda_j)}_{\neq 0} \underbrace{<\mathbf{x}_i, \mathbf{x}_j>}_{= 0} = 0\\
\Rightarrow\;& \mathbf{x}_i \perp \mathbf{x}_j
\end{align*}
$$
參照[ch4 特徵值/向量性質2](#特徵值/向量性質2---不同特徵值，對應特徵向量彼此線性獨立)，任意方陣不同特徵值，對應特徵向量彼此線性獨立，若是正規矩陣則不同特徵值，對應特徵向量彼此(單位)正交。將一行行單位正交的特徵向量合併成正交矩陣，就可以利用正交矩陣好用的性質$\mathbf{Q}^{-1} = \mathbf{Q}^H$來作對角化。

|項目|一般對角化|正交(么正)對角化|
|---|---|---|
|要求|$\forall \lambda, g_m(\lambda) = m(\lambda)$|$\mathbf{A}^* \mathbf{A} = \mathbf{A} \mathbf{A}^*$|
|特徵向量|線性獨立|單位正交(若特徵值重根對應特徵空間的基底非單位正交，要用GSO化為單位正交)|
|對角化|$\mathbf{AP} = \mathbf{PD} \Rightarrow \mathbf{P}^{-1} \mathbf{AP} = \mathbf{D}$|$\mathbf{AQ} = \mathbf{QD} \Rightarrow \mathbf{Q}^T \mathbf{AQ} = \mathbf{D}$|

---
### 將任意二次式化成標準式
給定任意二次式
$$
q = \mathbf{x}^T \mathbf{C} \mathbf{x} \in \mathbb{R}, \mathbf{C} \in \mathbb{R}^{n \times n}, \mathbf{x} = \begin{bmatrix} x_1\\ \vdots\\ x_n \end{bmatrix} \in \mathbb{R}^n
$$
1. 首先須將$\mathbf{C}$化成對稱矩陣$\mathbf{A} = \mathbf{A}^T$。
2. 由於對稱矩陣為正規矩陣，可做正交對角化，$\mathbf{AP} = \mathbf{PD} \Rightarrow \mathbf{P}^T \mathbf{A} \mathbf{P} = \mathbf{D}$。
3. $\mathbf{x} = \mathbf{PY}$，將舊座標變數變換為以單位正交特徵向量為座標軸的新座標(主軸, principal axis)。
$$
q = \mathbf{x}^T \mathbf{A} \mathbf{x} = (\mathbf{PY})^T \mathbf{A} (\mathbf{PY}) = \mathbf{Y}^T \mathbf{P}^T \mathbf{APY} = \mathbf{Y}^T \mathbf{D} \mathbf{Y}, \mathbf{Y} = \begin{bmatrix} y_1\\ \vdots\\ y_n \end{bmatrix} \in \mathbb{R}^n
$$
4. 如此標準式只剩下對角線元素，在二次曲線中有雙曲線、拋物線、圓與橢圓這三種情況，就可以方便觀察二次式在幾何上的意義。

---
### 二次式的應用 - 判斷正負性
1. 正定(positive definite) - $\forall \mathbf{x}, q = \mathbf{x}^T \mathbf{C} \mathbf{x} > 0$
2. 半正定(positive semi-definite)- $\forall \mathbf{x}, q = \mathbf{x}^T \mathbf{C} \mathbf{x} \geq 0$
3. 負定(negative definite) - $\forall \mathbf{x}, q = \mathbf{x}^T \mathbf{C} \mathbf{x} < 0$
4. 半負定(negative semi-definite)- $\forall \mathbf{x}, q = \mathbf{x}^T \mathbf{C} \mathbf{x} \leq 0$
5. 正負不定(indefinite) - $\forall \mathbf{x}, q = \mathbf{x}^T \mathbf{C} \mathbf{x} \overset{>}{\underset{<}{=}} 0$

由上述任意二次式化成標準式的過程可知，判斷正負性可由特徵值判斷，舉例來說若所有特徵值都是正的，則為正定。

---
### 二次式的應用 - 雷利商(Rayleigh Quotient)
雷利商定義為二次式除上$\mathbf{x}$的長度，雷利商下界為最小特徵值、上界為最大特徵值。
$$
\lambda_{min} \leq R(\mathbf{x}) \triangleq \frac{\mathbf{x}^T \mathbf{A} \mathbf{x}}{\mathbf{x}^T\mathbf{x}} \leq \lambda_{max}
$$

---
### 奇異值分解(SVD)與虛反矩陣
正交(么正)對角化只適用於normal matrix，而奇異值分解適用於任何矩陣，就是"平民版"的正交(么正)對角化，SVD計算如[SVD篇 SVD計算步驟](https://hackmd.io/@HsuChiChen/linear_algebra_svd#SVD計算步驟)，使用SVD看4大空間的性質與低秩近似法如[SVD篇 重點3 使用SVD說明線性代數的4大空間](https://hackmd.io/@HsuChiChen/linear_algebra_svd#重點3-使用SVD說明線性代數的4大空間)，虛反矩陣如[SVD篇 重點4 最小平方+範數問題](https://hackmd.io/@HsuChiChen/linear_algebra_svd#重點4-最小平方+範數問題)，這邊在補充一個性質
$$
\begin{align*}
\mathbf{A}^+ \mathbf{A} &= (\mathbf{V} \mathbf{\Sigma}^+ \mathbf{U}^H) (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^H)\\
&= \mathbf{V} \mathbf{\Sigma}^+ \mathbf{\Sigma} \mathbf{V}^H\\
&= \mathbf{v}_1 \mathbf{v}_1^H + \cdots + \mathbf{v}_r \mathbf{v}_r^H
\end{align*}
$$
即為投影矩陣，投影至平面$\mathrm{Row}(\mathbf{A}) = \mathrm{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_r\}$。
$$
\begin{align*}
\mathbf{A} \mathbf{A}^+ &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^H)(\mathbf{V} \mathbf{\Sigma}^+ \mathbf{U}^H)\\
&= \mathbf{U} \mathbf{\Sigma} \mathbf{\Sigma}^+ \mathbf{U}^H\\
&= \mathbf{u}_1 \mathbf{u}_1^H + \cdots + \mathbf{u}_r \mathbf{v}_r^H
\end{align*}
$$
即為投影矩陣，投影至平面$\mathrm{Col}(\mathbf{A}) = \mathrm{Span}\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$。