---
# System prepended metadata

title: 課程｜線性代數
tags: [課程]

---

# 線性代數

- [矩陣計算機](https://matrixcalc.org/zh/)
- [李宏毅教學影片](https://www.youtube.com/playlist?list=PLJV_el3uVTsNQkZFHfcdncAzoesmI6jju)
## Vectors, Matrices and their Products
- Vector 都考慮 Column Vector
- Vector set ：
    - S = {$\begin{bmatrix}1\\2\\3\end{bmatrix},\begin{bmatrix}2\\3\\4\end{bmatrix},\begin{bmatrix}0\\2\\3\end{bmatrix},\begin{bmatrix}1\\0\\3\end{bmatrix}$}
- Standard vectors：
    - $e_1=\begin{bmatrix}1\\0\\0\end{bmatrix},e_2=\begin{bmatrix}0\\1\\0\end{bmatrix},e_3=\begin{bmatrix}0\\0\\1\end{bmatrix}$
- Matrix = set of vectors
    - $A = [a_1~a_2~a_3]=\begin{bmatrix}1&0&3\\0&2&1\end{bmatrix}$
    - $A^T = \begin{bmatrix}a_1^T\\a_2^T\\a_3^T\end{bmatrix}=\begin{bmatrix}1&0\\0&2\\3&1\end{bmatrix}$
    - $(AB)^T=B^TA^T$
- Matrix-Vector Products
    - $A=\begin{bmatrix}1&0&3\\0&2&1\end{bmatrix},~~x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix},~~b=\begin{bmatrix}4\\3\end{bmatrix}$
    - Row Aspect：內積 Row 次
        - $Ax=\begin{bmatrix}1x_1+0x_2+3x_3\\0x_1+2x_2+1x_3\end{bmatrix}$
    - Column Aspect：Column的線性組合
        - $Ax=x_1\begin{bmatrix}1\\0\end{bmatrix}+x_2\begin{bmatrix}0\\2\end{bmatrix}+x_3\begin{bmatrix}3\\1\end{bmatrix}$
    - $Ae_1=\begin{bmatrix}1&0&3\\0&2&1\end{bmatrix}\begin{bmatrix}1\\0\\0\end{bmatrix}=$ first column of $A$
        - 如果對所有 $w$ 都有 $Aw=Bw$ ，則 $A=B$
## Does a system of linear equations have solutions?
- System of linear equations：$Ax=B$
    - 所有解形成的集合稱為 solution set
    - consistent：有解
    - inconsistent：無解
- Linear Combination
    - S = {$u_1,u_2,...,u_k$}
    - $v=c_1u_1+c_2u_2+...+c_ku_k$
    - $A=\begin{bmatrix}1&0&3\\0&2&1\end{bmatrix},~~x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix},~~b=\begin{bmatrix}4\\3\end{bmatrix}$
        - $Ax=x_1\begin{bmatrix}1\\0\end{bmatrix}+x_2\begin{bmatrix}0\\2\end{bmatrix}+x_3\begin{bmatrix}3\\1\end{bmatrix}=b$
- Span
    - S = {$u_1,u_2,...,u_k$}
    - span S = {$c_1u_1+c_2u_2+...+c_ku_k$| 任意的係數}
    - $b\in spanA$ 代表 $Ax=B$ 有解
## How many solutions?
- Linear Dependent
    - 定義一：S = {$u_1,u_2,...,u_k$}，存在 $u_i$ 是其他 vectors 的線性組合
    - 定義二：$c_1u_1+c_2u_2+...+c_ku_k=0$ 有非0解
        - $Sx=0$ 有非0解
    - 如果 $Sx=b$ 有解，必定無限多組
- Rank and Nullity
    - Rank = 最多的linearly independent columns
    - Nullity = columns數 - Rank
- System of linear equations：$Ax=B$
    - 無窮多組解：
        - Linear Dependent $\leftrightarrow$ Rank A < columns數 $\leftrightarrow$ Nullity A > 0
    - 唯一解：
        - Linear Independent $\leftrightarrow$ Rank A = columns數 $\leftrightarrow$ Nullity A = 0
    - 無解：
        - $b\notin spanS$
## Solving System of Linear Equations
- Elementary Operations
    - 1.Interchange
    - 2.Scaling
    - 3.Row Addition
    - 這三個操作，不會影響systems of linear equations的解
- Augmented Matrix
    - $A=\begin{bmatrix}1&0&3\\0&2&1\end{bmatrix},~~x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix},~~b=\begin{bmatrix}4\\3\end{bmatrix}$
    - $[~A~|~b~]=\begin{bmatrix}1&0&3&4\\0&2&1&3\end{bmatrix}$
- Reduced Row Echelon Form(RREF)(列階梯形矩陣)
    - Row Echelon Form
        - 1.0 rows在下半部
        - 2.leading entries呈現階梯狀
    - Reduced Row Echelon Form
        - 1.0 rows在下半部
        - 2.leading entries呈現階梯狀
        - 3.Column of leading entries 是 standard vector
    - leading entries 的座標稱為 pivot positions
    - leading entries 的 columns 稱為 pivot columns
    - RREF 是唯一的，一旦得到 Augmented Matrix 的 RREF就可以秒解出 system of linear equations
- Gaussian Elimination (高斯消去法)
    - 把 Augmented Matrix 使用 Elementary Operations 轉成 RREF 的演算法
## What can we find from RREF?
- RREF v.s. Linear Combination
    - Columns:
        - Columns 間關係不變(Column Correspondence Theorem)
        - Span columns 改變
    - Rows:
        - Rows 間關係改變
        - Span Rows 不變
- RREF v.s. Independent
    - pivot columns 彼此線性獨立
        - n\*n矩陣的 columns 線性獨立 $\leftrightarrow$ RREF 是單位矩陣
        - 瘦高矩陣的 columns 線性獨立 $\leftrightarrow$ RREF 是 $\begin{bmatrix}I\\O\end{bmatrix}$
        - 矮胖矩陣 $\leftrightarrow$ columns 線性相依
    - non pivots columns 可由 pivot columns 線性組合出
- RREF v.s. Rank
    - Rank A = 最多的linearly independent columns
        - = pivot columns
        - = Non-zero rows
        - = Number of basic variables
    - Rank A ≤ m 且 Rank A ≤ n
    - Full Rank：Rank A = min(m, n)
    - $R^m$ 中無法找到超過 m 個 independent columns
    - Nullity A = columns - Rank A
        - = Number of free variables
- RREF v.s. Span
    - 觀察 [A,b] 的 RREF 最後一個 Non-zero row，可以知道 $Ax=b$ 有沒有解
    - 以下說法等價
        - Rank A = Number of rows
        - [A] 的 RREF 沒有 zero rows
        - [A,b] 的 RREF 最後一個 Non-zero row 是合法的
        - $Ax=b$ 對任意 b 必定有解
    - m independent vectors span $R^m$ $\leftrightarrow$ more than m vectors in $R^m$ must be dependent
## Matrix Multiplication
- Meaning
    - 1.$AB=A[b_1~...~b_n]=[Ab_1~...~Ab_n]$
    - 2.$AB~x=C~x$：用 $C$ 代表composed system
- 一些性質
    - Not Communicative
    - Diagonal Matrix
    - Symmetric Matrix
    - Augment of A and B
    - Partition of A
        - Block Multiplication
- 4 Aspects
    - $A=\begin{bmatrix}1&2\\3&4\\5&6\end{bmatrix},B=\begin{bmatrix}-1&1\\3&2\end{bmatrix}$
    - 1.inner product 
        - $c_{12}=\begin{bmatrix}1&2\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix}$
    - 2.Linear combination of columns
        - $C=\begin{bmatrix}-1\begin{bmatrix}1\\3\\5\end{bmatrix}+3\begin{bmatrix}2\\4\\6\end{bmatrix}&1\begin{bmatrix}1\\3\\5\end{bmatrix}+2\begin{bmatrix}2\\4\\6\end{bmatrix}\end{bmatrix}$
    - 3.Linear combination of rows
        - $C=\begin{bmatrix}1\begin{bmatrix}-1&1\end{bmatrix}+2\begin{bmatrix}3&2\end{bmatrix}\\3\begin{bmatrix}-1&1\end{bmatrix}+4\begin{bmatrix}3&2\end{bmatrix}\\5\begin{bmatrix}-1&1\end{bmatrix}+6\begin{bmatrix}3&2\end{bmatrix}\end{bmatrix}$
    - 4.Summation of matrices
        - $C=\begin{bmatrix}\begin{bmatrix}1\\3\\5\end{bmatrix}\begin{bmatrix}-1&1\end{bmatrix}+\begin{bmatrix}2\\4\\6\end{bmatrix}\begin{bmatrix}-3&2\end{bmatrix}\end{bmatrix}$
- 運算量分析
    - ![](https://i.imgur.com/5ZmVJY5.png)
## Inverse of Matrix
- singular matrix = 不可逆矩陣
- Inverse
    - $A$ 是 $B$ 的 inverse，$B$ 是 $A$ 的 inverse
    - $AB=BA=I$
    - $A$ 是 invertible matrix
    - 可逆矩陣必為方陣，$n\times n$
    - $(AB)^{-1}=B^{-1}A^{-1}$
    - $(A^T)^{-1}=(A^{-1})^T$
- Input-Output-Model
    - Consumpttion Matrix $C=\begin{bmatrix}0.1&0.2&0.1\\0.2&0.4&0.2\\0.3&0.1&0.1\end{bmatrix}$，想生產 $x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}$
    - 則需要投入 $Cx=\begin{bmatrix}0.1x_1+0.2x_2+0.1x_3\\0.2x_1+0.4x_2+0.2x_3\\0.3x_1+0.1x_2+0.1x_3\end{bmatrix}$
- Elementary Row Operation Matrix
    - 1.Interchange $\begin{bmatrix}0&1\\1&0\end{bmatrix}$
    - 2.Scaling $\begin{bmatrix}k&0\\0&1\end{bmatrix}$
    - 3.Row Addition $\begin{bmatrix}1&0\\k&1\end{bmatrix}$
    - **這三個操作，都是可逆的**
    - 這三個操作可以把任意矩陣 $A$ 轉成 RREF
        - $E_k...E_2E_1A=R$
- Invertible
    - 考慮 $A\begin{bmatrix}x_1\\...\\x_n\end{bmatrix}=\begin{bmatrix}b_1\\...\\b_m\end{bmatrix}$
        - **重要性質：$A$ 是 One to One $\leftrightarrow$ Columns Independent**
        - **重要性質：$A$ 是 Onto $\leftrightarrow$ Rank A = Number of Rows**
        - $A$ 是矮胖，則必定不是 One to One
        - $A$ 是高瘦，則必定不是 Onto
        - $A$ 是方陣，才有可能是 One to One 和 Onto
            - 如果 $A$ 是方陣，One to One $\leftrightarrow$ Onto
            - **滿足其中一項，就是 invertible**
    - Invertible
        - $A$ 是 $n\times n$ 方陣
        - One to One
            - The columns of A are linear independent
            - The rank of A is the number of columns
            - The nullity of A is zero
            - The only solution to Ax=0 is the zero vector
            - The RREF of A is $I_n$
        - Onto
            - The columns of A span $R^n$
            - For every b in $R^n$, the system Ax=b is consistent
            - The rank of A is the number of rows
        - Others
            - A is a product of elementary matrices
                - $E_k...E_2E_1A=I_n$
            - There exists an n x n matrix B such that BA = $I_n$
                - $Ax=0~\rightarrow~BAx=0~\rightarrow~x=0$
            - There exists an n x n matrix C such that AC = $I_n$
                - $AC=I_n~\rightarrow~ACb=b~\rightarrow~Ax=b~有解~Cb$
            - $det(A)\neq0$
- 找反矩陣方法
    - 2 X 2 Matrix
        - $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$, 則$A^{-1}=\frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$
    - 一般 Matrix
        - $E_k...E_2E_1A=I_n~~~~~\rightarrow~~~~~A^{-1}=E_k...E_2E_1$
        - $E_k...E_2E_1[A~~I_n]=[I_n~~A^{-1}]$
        - $\left[\begin{array}{ccc|ccc}1&2&3&1&0&0\\2&5&6&0&1&0\\3&4&8&0&0&1\end{array}\right]~~\rightarrow~~\left[\begin{array}{ccc|ccc}1&0&0&-16&4&3\\0&1&0&-2&1&0\\0&0&1&7&-2&-1\end{array}\right]$
## Determinants
- Determinants
    - 2x2：
        - det(A)=ad-bc
        - 平行四邊形面積
    - 3x3：
        - det(A)=$a_1a_5a_9+a_2a_6a_7+a_3a_4a_8$
        - $~~~~~~~~-a_3a_5a_7-a_2a_4a_9-a_1a_6a_8$
        - 平行六面體體積
    - 3 basic properties
        - 1.det($I$)=1
        - 2.交換row，使得det變號
            - 如果 $A$ 有 2 equal rows，則 det($A$)=0
        - 3.對每一個 row 都是 linear
            - (3A) $det(\begin{bmatrix}ta&tb\\c&d\end{bmatrix})=t \cdot det(\begin{bmatrix}a&b\\c&d\end{bmatrix})$
                - $det(2A)=2^n \cdot det(A)$
                - 有一個 row 全 0，則 det($A$)=0
            - (3B) $det(\begin{bmatrix}a+a'&b+b'\\c&d\end{bmatrix})=det(\begin{bmatrix}a&b\\c&d\end{bmatrix})+det(\begin{bmatrix}a'&b'\\c&d\end{bmatrix})$
            - Row Addition 不會改變 determinant
                - $det(\begin{bmatrix}a+kc&b+kd\\c&d\end{bmatrix})=det(\begin{bmatrix}a&b\\c&d\end{bmatrix})+kdet(\begin{bmatrix}c&d\\c&d\end{bmatrix})$
            - det(上三角矩陣)=Products of diagonal
    - $可逆矩陣~~\leftrightarrow~~~det(A)\neq0$
        - RREF = $I_n$
    - $det(AB)=det(A)det(B)$
    - $det(A^T)=det(A)$
- Formula
    - $A_{ij}$ 為 A 矩陣去掉第 i 個 row ，第 j 個 column
    - Cofactor：
        - $c_{ij}=(-1)^{i+j}det(A_{ij})$
    - Determinant：
        - 定義： Det([a]) = a
        - pick row i：$det(A)=a_{i1}c_{i1}+a_{i2}c_{i2}+...+a_{in}c_{in}$
        - pick column j：$det(A)=a_{1j}c_{1j}+a_{2j}c_{2j}+...+a_{nj}c_{nj}$
    - Tridiagonal Matrix：
        - $det(A_4)=a_{i1}c_{i1}+a_{i2}c_{i2}+a_{i3}c_{i3}+a_{i4}c_{i4}=det(A_3)-det(A_2)$
        - ![](https://i.imgur.com/bu9aDBd.png)
    - Formula from Three Properties
        - $det(A)=\sum n!\cdot terms$，dynamic programming
- Cramer’s Rule
    - C： cofactors of A
    - $C^T$：adjugate of A (伴隨矩陣)
    - $A^{-1}=\frac{1}{det(A)}C^T$
    - $Ax=b~\leftrightarrow~x=\frac{1}{det(A)}C^Tb~\leftrightarrow~x_i=\frac{det(B_i)}{det(A)}$
## Subspace
- 一個 vector set V 是 subspace，要滿足三個性質
    - 0 在 V 裡
    - 加法封閉性
    - 係數乘法封閉性
- Null Space of a matrix A，記為 Null A，是 Ax=0 的 solution set
    - Null A = { $v\in R^n~~|~~Av=0$ }
    - Null A 是 subspace
    - One to one $\leftrightarrow$ Columns independent $\leftrightarrow$ Null A = {0}
- **性質：Span of vector set 必定是 subspace**
- Column Space： 
    - col A = { $Av~~|~~v\in R^n$ } = range of A
- Row Space： 
    - row A = col $A^T$
## Basis
- Basis
    - Basis = linearly independent generating set
    - 任 n 個 $R^n$ 的 independent vector 形成 $R^n$ 的 basis
    - pivot columns 形成 Column Space 的 basis
    - 性質：
        - 最小的 generating set
            - Reduction Theorem：每一個generating set裡面都有basis
        - 最大的 linearly independent vector set
            - Extension Theorem：每一個independent vector set都可以擴充成basis
        - 任兩個basis有相同的大小 -- Dimension
            - http://fanflynote.blogspot.tw/2017/11/replacement-theorem.html
- 確認basis
    - 在 $R^m$ 中，如果要檢查 S 是否為 basis，有3種檢查方法
        - 1.檢查 generating set 和 independent set
        - 2.檢查 |S| = m 和 generating set
        - 3.檢查 |S| = m 和 independent set
## Subspaces associated with a Matrix
- 考慮
    - ![](https://i.imgur.com/QSMIKuu.png)
- Col A
    - Basis ： pivoted columns of A
    - Dimension ： Rank A
- Null A
    - Basis ： 解 Ax = 0 的 free variables
    - Dimension ： Nullity A
- Row A
    - Basis ： RREF 的 non-zero rows
    - Dimension ： Rank A
- Rank A = Dim(Row A) = Dim(Col $A^T$) = Rank $A^T$
- Dimension Theorem
    - Dim of Range + Dim of Null = Dim of Domain
- 複習
    - Rank A
        - = 最多的linearly independent columns
        - = pivot columns
        - = Non-zero rows
        - = Number of basic variables
        - = Dim (Col A)
        - = Dim (Range of A)
        - = Dim (Row A)
        - = Dim (Col $A^T$)
## Coordinate System
- Coordinate Systems
    - 一個 $R^n$ 的 vector set $\beta$ 為座標系統，表示 $\beta$ 是一個 basis
        - 1.Span( $\beta$ ) = $R^n$
        - 2.$\beta$ 是 independent set
    - $\beta=\{v_1,...,v_n\}$是 $R^n$ 的 basis
        - $u=c_1v_1+c_2v_2+...+c_nv_n$，則我們記為$[u]_\beta=\begin{bmatrix}c_1\\c_2\\...\\c_n\end{bmatrix}$，表示u向量的座標
    - $\varepsilon$ is Cartesian coordinate system
    - $\beta$ is arbitary coordinate system
    - Other to Cartisian
        - ![](https://i.imgur.com/K1r5Gzn.png)
        - ![](https://i.imgur.com/wgN0E24.png)
    - Cartisan to Other
        - ![](https://i.imgur.com/VBtU2w0.png)
        - ![](https://i.imgur.com/tTmIha2.png)
- Summary
    - ![](https://i.imgur.com/DeVnP3s.png)
## Linear Function in Coordinate System
- 目標
    - ![](https://i.imgur.com/Hi5RUUo.png)
- 關係
    - $A=B~[T]_\beta~B^{-1}$
    - $[T]_\beta=B^{-1}AB$
## Review & Complement
- Rank 性質
    - If A is a m x n matrix, and B is a n x k matrix.
        - 𝑅𝑎𝑛𝑘 𝐴𝐵 ≤ 𝑚𝑖𝑛 (𝑅𝑎𝑛𝑘 𝐴 , 𝑅𝑎𝑛𝑘 𝐵)
    - If B is a matrix of rank n
        - 𝑅𝑎𝑛𝑘 𝐴𝐵 = 𝑅𝑎𝑛𝑘 𝐴
    - If A is a matrix of rank n
        - 𝑅𝑎𝑛𝑘 𝐴𝐵 = 𝑅𝑎𝑛𝑘 𝐵
    - 原因：
        - Rank AB = Rank RB ≤ Rank R = Rank A
        - Rank AB = Rank $B^TA^T$ ≤ Rank $B^T$ = Rank B
        - ![](https://i.imgur.com/CrrJLIc.png)
- 定理4.9
    - $V\subset W$為兩個subspace of $R^n$
        - $dim(V)\le dim(W)$
        - 如果$dim(V)=dim(W)$，則 $V=W$
- Determinant 性質
    - det(AB)=det(A)det(B)
        - 如果 A not invertible，等號兩邊都為0
        - 如果 A invertible，$A=E_k...E_2E_1$ 且 det(EA)=det(E)det(A)
    - det(A)=det($A^T$)
        - 如果 A not invertible，等號兩邊都為0
        - 如果 A invertible，$A=E_k...E_2E_1$ 且 det($E$)=det($E^T$)
- Rotation Matrix
    - $A_\alpha=\begin{bmatrix}cos\alpha&sin\alpha\\-sin\alpha&cos\alpha\end{bmatrix}$
## Eigenvalues and Eigenvectors
- Eigenvalues and Eigenvectors
    - $Av=\lambda v$
        - $v$ 是 $A$ 的 Eigenvector
        - $\lambda$ 是 $A$ 的 Eigenvalue 
    - $A$ 必定為方陣
    - $0$ 不算 Eigenvector
- Linear Operator $T(v)$
    - $T(v)=\lambda v$
        - $v$ 是 $T$ 的 Eigenvector
        - $\lambda$ 是 $T$ 的 Eigenvalue 
    - $T$ 可以對應到 n by n standard matrix $A$
- $\lambda$ 的 EigenSpace 為 $Null(A-\lambda I_n)$
    - 原因
        - $Av=\lambda v~~\leftrightarrow~~(A-\lambda I_n)v=0$
    - 對應的 Eigenvector
        - $Null(A-\lambda I_n)$ 中非零向量
    - 檢查 $\lambda$ 是否為 Eigenvalue
        - 只要檢查 $Null(A-\lambda I_n)$ dimension 是否為 0
- 一些 Transform
    - Shear Transform 推移，$T(\begin{bmatrix}x\\y\end{bmatrix})=\begin{bmatrix}x+my\\y\end{bmatrix}$
        - $\begin{bmatrix}1\\0\end{bmatrix}$ 是 Eigenvector， $1$ 是對應 Eigenvalue
    - Reflection 鏡射，$T(\begin{bmatrix}x\\y\end{bmatrix})$ ： 對$y=0.5x$ 鏡射
        - $\begin{bmatrix}2\\1\end{bmatrix}$ 是 Eigenvector， $1$ 是對應 Eigenvalue
        - $\begin{bmatrix}-1\\2\end{bmatrix}$ 是 Eigenvector， $-1$ 是對應 Eigenvalue
    - Expansion and Compression 伸縮， $T(\begin{bmatrix}x\\y\end{bmatrix})=\begin{bmatrix}mx\\my\end{bmatrix}$
        - 所有vector都是Eigenvector， $m$ 是對應 Eigenvalue
    - Rotation 旋轉，$T(\begin{bmatrix}x\\y\end{bmatrix})=\begin{bmatrix}0&-1\\1&0\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}-y\\x\end{bmatrix}$
        - 沒有 Eigenvector 和 Eigenvalue
## Characteristic Polynomial
- 以下說法等價
    - $t$ 是 $A$ 的 eigenvalue
    - $(A-t I_n)x=0$ 有解
    - $Null(A-t I_n)$ 的 dimension > 0
    - $Range(A-t I_n)$ 的 dimension < n
    - $A-t I_n$ 不可逆
    - $det(A-t I_n)=0$
- 定義
    - $det(A-t I_n)$： $A$ 的特徵多項式
    - $det(A-t I_n)=0$： $A$ 的特徵方程式
    - $A$ 的 Eigenvalues ： $A$ 的特徵根
- 性質
    - 1.$A$ 和 $A$的RREF，Eigenvalue不同
    - 2.$A$ 和 $B$ similar，Eigenvalue相同
        - $B=P^{-1}AP$，則 $det(B-tI)=det(A-tI)$
    - 3.特徵多項式，是一個 n 次多項式
    - 4.Eigenvalues 的數量，小於等於 n
    - 5.如果特徵多項式沒有虛根
        - n 個特徵根的和 = Trace(A)
        - n 個特徵根的積 = det(A)
    - 6.上三角矩陣的 Eigenvalues ，為對角線的 entries
- Characteristic Polynomial 和 EigenSpace 的對應
    - $det(A-t I_n)=(t-\lambda_1)^{m_1}~...~(t-\lambda_k)^{m_k}~(...)$
        - $m_1,...,m_k$ 稱為 multiplicity 重數
        
    - 1.每一個 $\lambda_i$ 都有對應的 $Null(A-\lambda_i I_n)$
    - 2.$d_i$ 必定滿足 $1\le d_i\le m_i$
## Diagonalization
- $A$ 是 diagonalizable $~\leftrightarrow~$ $A$ 和對角矩陣 similar $~\leftrightarrow~$ $A=PDP^{-1}$
    - P 是 $n\times n$ 可逆矩陣
    - D 是 $n\times n$ 對角矩陣
- 性質
    - $P=\begin{bmatrix}p_1&p_2&...&p_k\end{bmatrix}~是可逆矩陣~,~~D=\begin{bmatrix}d_1&⋯&0\\⋮&⋱&⋮\\0&⋯&d_k\end{bmatrix}$
    - $\begin{bmatrix}Ap_1&Ap_2&...&Ap_k\end{bmatrix}=AP=PD=\begin{bmatrix}d_1p_1&d_2p_2&...&d_kp_k\end{bmatrix}$
    - $p_i$ 是 Eigenvectors ， $d_i$ 是 Eigenvalues
    - $A$ 是 diagonalizable $~\leftrightarrow~$ Eigenvectors 形成 basis of $R^n$
- 定理：對應到不同 Eigenvalue 的 Eigenvector 所形成的集合，是 independent 的
- 定理：$A$ 是 diagonalizable 等價於
    - 1.$A$ 的特徵多項式，可以分解成一次多項式的乘積。
    - 2.每個 Eigenvalue 的 multiplicity = 對應 Eigenspace 的 dimension
- Application
    - $A=PDP^{-1}~~\rightarrow~~A^m=PD^mP^{-1}$
    - ![](https://i.imgur.com/dg4vYt0.png)
    - $A=\begin{bmatrix}.85&.03\\.15&.97\end{bmatrix}=\begin{bmatrix}-1&1\\1&5\end{bmatrix}\begin{bmatrix}.82&0\\0&1\end{bmatrix}\begin{bmatrix}-1&1\\1&5\end{bmatrix}^{-1}$
    - $A^m=\begin{bmatrix}.85&.03\\.15&.97\end{bmatrix}=\begin{bmatrix}-1&1\\1&5\end{bmatrix}\begin{bmatrix}.82&0\\0&1\end{bmatrix}^m\begin{bmatrix}-1&1\\1&5\end{bmatrix}^{-1}$
        - $m\rightarrow\infty, A^m=\begin{bmatrix}1/6&1/6\\5/6&5/6\end{bmatrix},~~因此~~ \begin{bmatrix}1/6&1/6\\5/6&5/6\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}1/6\\5/6\end{bmatrix}$
## Diagonalization of Linear Operator
- Example
    - $T(\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix})=\begin{bmatrix}8x_1+9x_2\\-6x_1-7x_2\\3x_1+3x_2-x_3\end{bmatrix}$
    - 對應的 standard matrix 為 $\begin{bmatrix}8&9&0\\-6&-7&0\\3&3&-1\end{bmatrix}$
    - 對應的特徵多項式為 $-(t+1)^2(t-2)$
        - 特徵值 -1 所對應的 basis $=\{\begin{bmatrix}-1\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix}\}$
        - 特徵值 -1 所對應的 basis $=\{\begin{bmatrix}3\\-2\\1\end{bmatrix}\}$
    - $T(\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix})=\begin{bmatrix}-1&0&3\\1&0&-2\\0&1&1\end{bmatrix}\begin{bmatrix}-1&0&0\\0&-1&0\\0&0&2\end{bmatrix}\begin{bmatrix}2&3&0\\-1&-1&1\\1&1&0\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}$
## Orthogonality
- Norm
    - $||v||=\sqrt{v_1^2+...+v_k^2}$
- Distance
    - $||u-v||$
- Dot Product
    - $u\cdot v=u_1v_1+...+u_kv_k$
        - 1.$u\cdot u=||u||^2$
        - 2.$u\cdot u=0~~~\leftrightarrow~~~u=0$
        - 3.$u\cdot v=v\cdot u$
        - 4.$u\cdot (v+w)=u\cdot v+u\cdot w$
        - 5.$(v+w)\cdot u=v\cdot u+w\cdot u$
        - 6.$(cu)\cdot v=c(u\cdot v)=u\cdot(cv)$
        - 7.$||cu||=|c|||u||$
        - 8.$Au\cdot v=(Au)^Tv=u^T(A^Tv)=u\cdot(A^Tv)$
- Orthogonal
    - 如果 $u\cdot v=0$ ，則兩向量 Orthogonal
- Pythagorean Theorem
    - Orthogonal$~~~~~\leftrightarrow~~~~||u+v||^2=||u||^2+||v||^2$
- Cauchy-Schwarz Inequality
    - $u\cdot v\le||u||\cdot||v||$
- Triangle Inequality
    - $||u+v||\le||u||+||v||$
## Orthogonal Projection
- Orthogonal Complement
    - $S^\perp=\{u~|~u\cdot v=0,~\forall v\in S\}$
        - the set of vectors that are orthogonal to every vector in S
    - $(R^n)^\perp=\{0\},~~\{0\}^\perp=R^n$
    - $\{\begin{bmatrix}x_1\\x_2\\0\end{bmatrix}\}^\perp=\{\begin{bmatrix}0\\0\\x_3\end{bmatrix}\}$
    - 性質：
        - 1.$S^\perp$ 一定是 subspace
        - 2.$(spanS)^\perp=S^\perp$
        - 3.B 是 W Basis，則 $B^\perp=W^\perp$
        - 4.$S\cap S^\perp=\{0\}$
        - 5.$Row(A)^\perp=Null(A)$
        - 6.$dim(W)+dim(W^\perp)=n$
        - 7.對任何vector u
            - $u=w+z$ 可以唯一拆解 $w\in W,z\in W^\perp$
- Orthogonal Projection
    - $U_W()$ 是把 向量 投影到 W 上的 function
        - operator 是 linear 的
        - 因此存在 standard matrix
    - $P_W()$ 是把 向量 投影到 W 上的 matrix
    - 最短距離的觀點
        - $U_W(u)$ 是 W 上和 $u$ 距離最短的向量
        - $||u-U_W(u)||$ 是該距離值
- How To Do Orthogonal Projection
    - 把 u 投影到 v 向量所表示的直線上
        - $w=\frac{u\cdot v}{||v||^2}~v$
        - $||z||=||u-\frac{u\cdot v}{||v||^2}~v||$
    - General情況，$C$ 是 $n\times k$ 矩陣，columns of $C$ 形成 $W$ 的 basis
        - $P_W=C(C^TC)^{-1}C^T$
        - $w=P_W\cdot u$
        - $||z||=||u-P_W\cdot u||$
    - 原因：
        - $w=Cv$
        - $0=C^T(u-w)=C^Tu-C^TCv$
        - $v=(C^TC)^{-1}C^Tu$
        - $w=C(C^TC)^{-1}C^Tu$
    - 原因：
        - 如果 $C^TCb=0$
        - 則 $b^TC^TCb=||Cb||^2=0=Cb$
        - 則 $b=0$
        - 因此 $C^TC$ 可逆
- Application
    - $Cx = b$，找一個 $z$ 使得 $||b-Cz||$最小，則 $Cz$ 即為 $b$ 在 $span(C)$ 的投影
        - $Cz=C(C^TC)^{-1}C^Tb$
        - $z=(C^TC)^{-1}C^Tb$
    - 單變數 Least Square Regression
        - $y = a+bx$， 找 $z=\begin{bmatrix}a\\b\end{bmatrix}$ 
            - error = $||\begin{bmatrix}y_1-(a+bx_1)\\⋮\\y_k-(a+bx_k)\end{bmatrix}||^2 = ||y-\begin{bmatrix}1&x_1\\⋮&⋮\\1&x_k\end{bmatrix}\cdot\begin{bmatrix}a\\b\end{bmatrix}||^2=||y-Cz||^2$
            - 答案為 y 在 $span(C)$ 上的投影
                - $Cz=C(C^TC)^{-1}C^Ty$
                - $z=(C^TC)^{-1}C^Ty$
        - $y = a+bx+cx^2$， 找 $z=\begin{bmatrix}a\\b\\c\end{bmatrix}$ 
            - error = $||\begin{bmatrix}y_1-(a+bx_1+cx_1)\\⋮\\y_k-(a+bx_k+cx_k^2)\end{bmatrix}||^2 = ||y-\begin{bmatrix}1&x_1&x_1^2\\⋮&⋮&⋮\\1&x_k&x_k^2\end{bmatrix}\cdot\begin{bmatrix}a\\b\end{bmatrix}||^2=||y-Cz||^2$
            - 答案為 y 在 $span(C)$ 上的投影
                - $Cz=C(C^TC)^{-1}C^Ty$
                - $z=(C^TC)^{-1}C^Ty$
## Orthogonal Vectors
- Orthogonal Set
    - 任兩個向量都是 Orthogonal 的 Set
    - 性質
        - 只有一個向量的 Set 必定是 Orthogonal Set
        - 定理：Orthogonal Set 只要沒有 0 就必定 independent
- Orthonormal Set
    - 任兩個向量都是 Orthogonal 且 長度都是 1 的 Set
    - 性質
        - 長度是 1 的向量稱為 unit vector
        - 定理：Orthonormal Set 必定 independent
- Orthogonal Basis：是 Orthogonal Set 的 Basis
- Orthonormal Basis：是 Orthonormal Set 的 Basis
## Orthogonal Basis
- $S = \{v_1, v_2, ⋯ , v_k\}$ 是 orthogonal basis of V
    - 任意向量 $u\in V$ 可以唯一寫成
        - $u=c_1v_1+c_2v_2+...+c_kv_l=\frac{u\cdot v_1}{||v_1||^2}v_1+\frac{u\cdot v_2}{||v_2||^2}v_2+...+\frac{u\cdot v_k}{||v_k||^2}v_k$
    - 任意向量 $u\notin V$ ， $u$ 在 $V$ 上的投影，可以唯一寫成
        - $w=c_1v_1+c_2v_2+...+c_kv_l=\frac{u\cdot v_1}{||v_1||^2}v_1+\frac{u\cdot v_2}{||v_2||^2}v_2+...+\frac{u\cdot v_k}{||v_k||^2}v_k$
- Gram-Schmidt Process
    - Basis {$u_1,...,u_k$} $~~\rightarrow~~$ Orthogonal Basis {$v_1,...,v_k$}
        - $v_1=u_1$
        - $v_2=u_2-\frac{u_2\cdot v_1}{||v_1||^2}v_1$
        - $v_3=u_3-\frac{u_3\cdot v_1}{||v_1||^2}v_1-\frac{u_3\cdot v_2}{||v_2||^2}v_2$
        - ...
        - $v_k=u_k-\frac{u_k\cdot v_1}{||v_1||^2}v_1-\frac{u_k\cdot v_2}{||v_2||^2}v_2-...-\frac{u_k\cdot v_{k-1}}{||v_{k-1}||^2}v_{k-1}$
## Orthogonal Matrices & Symmetric Matrices
- Norm-preserving ： $||T(x)||^2=||x||^2$
- Orthogonal Matrices
    - Orthogonal Matrices 定義：
        - 一個矩陣，columns 形成 **Orthonormal Basis**
    - Orthogonal operator 定義：
        - 一個 linear operator，他的 standard matrix 是 Orthogonal Matrix
    - 以下條件等價
        - $||Qu||=||u||$ **Norm Preserving**
        - $Q$ 是 **Orthogonal Matrix**
            - 1.||$u_1$||=||$u_2$||=...=||$u_k$||=1
            - 2.$u_1\perp u_2\perp ...\perp u_k$
        - $QQ^T=I_n$
        - $Q^{-1}=Q^T$
        - $Qu\cdot Qv=u\cdot v$
    - 性質：
        - 1.$Q$ 是 Orthogonal $\leftrightarrow$ $Q^T$ 是 Orthogonal
            - $Q^{-1}=Q^T~\rightarrow~(Q^T)^{-1}=(Q^T)^T$
        - 2.$Q$ 是 Orthogonal $\leftrightarrow$ $Q^{-1}$ 是 Orthogonal
            - $Q^{-1}=Q^T~\rightarrow~(Q^{-1})^{-1}=(Q^{-1})^T$
        - 3.$PQ$ 是 Orthogonal
            - $(PQ)^{-1}=(PQ)^T$
        - 4.det $Q~=~\pm1$
            - $det(QQ^T)=det(Q)det(Q^T)=1$
- Symmetric Matrices
    - 性質
        - 1.$A$ 是 symmetric $\leftrightarrow$ Eigenvalue 是實數
            - $\bar{v}^TAv=\lambda\bar{v}^Tv=(A\bar{v})^Tv=\bar{\lambda}\bar{v}^Tv~~\rightarrow~~\lambda=\bar{\lambda}~~~~(Av=\lambda v,~A\bar{v}=\bar{\lambda} \bar{v})$
        - 2.$A$ 是 symmetric $\leftrightarrow$ 對應到不同 Eigenvalue 的 Eigenvector 所形成的集合，是 Orthogonal 的
            - $u^TAv=\mu u^Tv=\lambda u^Tv~~~\rightarrow u\cdot v=0$
        - 3.$A$ 是 symmetric $\leftrightarrow$ $A=PDP^T$ 
            - P 是 Orthogonal
            - D 是 Diagonal
            - 代表 A 的 eigenvector 是 orthogonal 的
## 分解矩陣
- SVD Singular Value Decomposition
    - ![](https://i.imgur.com/8xiYhuv.png)
    - $A=U\Sigma V^T$
    - $A^TA=V\Sigma U^TU\Sigma V^T=V\Sigma^2V^T$
    - $AA^T=U\Sigma V^TV\Sigma U^T=U\Sigma^2U^T$
    - 方法：找 $AA^T$ 的特徵向量及特徵值
    - https://ccjou.wordpress.com/%E5%B0%88%E9%A1%8C%E6%8E%A2%E7%A9%B6/%E5%A5%87%E7%95%B0%E5%80%BC%E5%88%86%E8%A7%A3%E5%B0%88%E9%A1%8C/
- LU factorization
    - 把矩陣分解成下三角矩陣乘以上三角矩陣
    - 方法：轉乘RREF
    - $A=\begin{bmatrix}1&2&3\\4&-6&-6\\-7&-7&9\end{bmatrix}=\begin{bmatrix}1&0&0\\4&1&0\\-7&-0.5&1\end{bmatrix}\begin{bmatrix}1&2&3\\0&-14&-18\\0&0&21\end{bmatrix}$
- Cholesky Factorization
    - - 把矩陣分解成 $AA^T$
    - ![](https://i.imgur.com/HSv1Ykj.png)
    - ![](https://i.imgur.com/NKYeRhD.png)    
## Beyond Vectors
- Vector space:
    - 運算
        - 1.addition
        - 2.scalar multiplication
    - 滿足的性質
        - 向量群、純量場、係數乘法封閉
        - 單位純量、結合律、分配律
- Linear transformation
    - 滿足的性質
        - 1.$T(u+v)=T(u)+T(v)$
        - 2.$T(cu)=cT(u)$
    - Example
        - 矩陣轉置、微分
    - Null Space：滿足 $T(x)=0$ 的 x 所形成的集合
    - Range：$T(x)$ 取值範圍所形成的集合
- Basis
    - Linear Independent generating set
    - 任意向量可以用 basis 所成的座標系統來表示。
    - 任意 function ，可以轉到座標系統用矩陣達到。
        - Example P2之中的微分運算
            - $M=\begin{bmatrix}0&1&0\\0&0&2\\0&0&0\end{bmatrix}$，但是 M 不可逆
- Inner Product
    - 定義：
        - 1.$<u,u>$ > 0 if $u$ $\ne$ 0
        - 2.$<u,v>$ = $<v,u>$
        - 3.$<u+v,w>$ = $<u,w>$ + $<v,w>$
        - 4.$<au,v>$ = $a<u,v>$
    - Dot Product 是 special case
- Fourier Series
    - $<f,g>=\int_{0}^{2\pi}f(t)g(t)dt$
    - Orthogonal Set： { $1, cost, sint, cos2t, sin2t, ..., cosnt, sinnt$}
    - Orthonormal Set： { $\frac{1}{2\pi}, \frac{cost}{\pi}, \frac{sint}{\pi}, \frac{cos2t}{\pi}, \frac{sin2t}{\pi}, ..., \frac{cosnt}{\pi}, \frac{sinnt}{\pi}$}


