# 線性代數

- [矩陣計算機](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}$
- 運算量分析
- 
## 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)$
- 
- 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
- 考慮
- 
- 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
- 
- 
- Cartisan to Other
- 
- 
- Summary
- 
## Linear Function in Coordinate System
- 目標
- 
- 關係
- $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
- 
- 定理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}$
- 
- $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
- 
- $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$
- 
- 
## 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}$}