# 線性代數 (下)

相似性
---

* assume $A,B\in F^{n\times n}$，若有一可逆矩陣$P\in F^{n\times n}$使的$P^{-1}AP=B$則，$A\sim B$

* $\sim$為**等價關係**
$A\sim A$
$A\sim B$則$B\sim A$
$A\sim B$且$B\sim C$則$A\sim C$

* $A\sim \alpha I\Leftrightarrow A=\alpha I$，可知道$\alpha I$只與自己相似

* $T\in L(V,V)$，$\beta,\gamma$為$V$的基底，則$[T]_{\beta}\sim [T]_{\gamma}$

<img src="https://i.imgur.com/chgevM6.png">

* if $A\sim B$, then
(1) $tr(A)=tr(B)$
(2) $det(A)=det(B)$
(3) $rank(A)=rank(B)$
(4) $nullity(A)=nullity(B)$
(5) $A^T\sim B^T$
(6) $A^k\sim B^k,\forall k\in N$
(7) $\alpha A\sim \alpha B,\forall \alpha \in F$
(8) $A+\alpha I\sim B+\alpha I$
(9) $f(A)\sim f(B),\forall f(x)\in F[x]$
(10) $A^{-1}\sim B^{-1}$，if they are invertible
(11) $p_A(x)=p_B(x)$ (有相同的特徵根，但**特徵向量不一定相同**)
上述1~4皆成立的話，也不保證$A\sim B$，但要是有任何一項不成立，則代表$A$與$B$不相似

* 相似矩陣有相同的特徵根，特徵向量不一定相同

* <img src="https://i.imgur.com/iG2QK72.png">

不變子空間
---

* **不變子空間**:
假設$T\in L(V,V)$，W為V的子空間且$T(W)\subseteq W,\forall w\in W,T(w)\in W$

* $T\in L(V,V)$
1. $\{0\},V,ker(T),Im(T)$皆為T-不變子空間
2. T在W上的限制函數，$T_W: W\rightarrow V$定義為$T_W(v)=T(v),\forall v\in W$，可視為$T_W:W\rightarrow W,T_W\in L(W,W)$

* $\{0\},V,ker(T),Im(T)$都是T-invariant subspace

* $T:V\rightarrow V$，所有的T-invariant subspace的交集也是T-invariant subspace，和空間也是

* <img src="https://i.imgur.com/hqeSFlM.png">

特徵根及特徵向量
---

* eigen value與eigen vector就對應到不變子空間，投影後仍在同一個subspace上

* 相對於$\lambda$的特徵向量的任意線性組合，若不為0向量，則仍為$\lambda$的特徵向量

* $det(T)=det([T]_\beta)$
$tr(T)=tr([T]_\beta)$

* $\lambda$為$A$的特徵根 $\Leftrightarrow$ $det(A-\lambda I)=0$

* $p_A(x)=char_A(x)=det(A-xI)$

* $p_A(0)=det(A),p_A(x)$中$(-x)^{n-1}$的係數為$tr(A)$

* <img src="https://i.imgur.com/XIaDnRe.png">

* $V(\lambda)=\{v\in V|T(v)=\lambda v\}$，稱為T相對於$\lambda$的特徵空間，$V(\lambda)$是T的不變子空間

* $V(\lambda)=ker(T-\lambda I)$

* 若$Ax=\lambda x$，則若$A=[T]_{\beta},x=[v]_\beta$，則$[T]_\beta=\lambda[v]_\beta$

* $V(\lambda_1),..,V(\lambda_k)$為獨立子空間，$\forall v_i\in V(\lambda_i)$，$v_1,...,v_k$為線性獨立 (證明)

* 若$A\sim B$，則$p_A(x)=p_B(x)$，具有相同特徵根(特徵向量不一定)，反之未必成立

* $A,A^T$具有相同特徵根但未必具有相同特徵向量

* $A,A^{-1},A^m,f(A)$有相同的特徵根

* $AB,BA$具有相同特徵根，且連特徵多項式也相同

* <img src="https://i.imgur.com/haRRCjL.png">

* $A$為可逆 $\Leftrightarrow$ 0不為$A$的特徵根
若$A$可逆且$Ax=\lambda x$，則$A^{-1}x=\cfrac{1}{\lambda}x$
$\forall m\in Z^+,A^mx=\lambda^mx$
若$f(x)\in P$或馬式級數，則$f(A)x=f(\lambda)x$

對角化
---

* 假設$T\in L(V,V)$為一個線性映射且存在$V$的一組基底$\beta$使得$[T]_{\beta}=D$為對角矩陣，則稱$T$為可對角化

* 假設$A\in F^{n\times n}$，若存在一可逆矩陣$P\in F^{n\times n}$使得$P^{-1}AP=D$為對角矩陣，則稱$A$為可對角化

* 有些人會誤以為方形矩陣存在rref就代表可對角化(例如我) 但其實不是這樣

* $T$可對角化$\Longleftrightarrow T$具$dim(V)$個線性獨立特徵向量

* $T$可對角化$\Longleftrightarrow$ $p_T(x)$在F中可分解且$am(\lambda_i)=gm(\lambda_i),\forall i=1,2,..,r \Longleftrightarrow$ $V=V(\lambda_1)\bigoplus V(\lambda_2)\bigoplus ...\bigoplus V(\lambda_r)$

* $\beta$中的元素為$T$的n個線性獨立特徵向量且$D$的對角項元素依序為這n個特徵向量對應的根，用矩陣$A$來看的話則是$P$的行向量為$A$的n個線性獨立特徵向量

* $\lambda$在$p_T(x)$中的**重根數**為$\lambda$的代數重數$am(\lambda)$

* $dim(V(\lambda))$為幾何重數$gm(\lambda)$

* $gm(\lambda)=dim(V(\lambda))=dim(ker(A-\lambda I))=nullity(A-\lambda I)=n-rank(A-\lambda I)$

* $1\le gm(\lambda)\le am(\lambda)\le n$，n是$p_T(x)$為n次多項式的意思

* **可分解**: 假設$f(x)\in F[x]$且$f(x)$可完全分解成佈於$F$的**一次因式乘積**，則稱$f(x)$ is split over $F$

* 假設$A\in F^{n\times n}$且$p_A(x)$ is split over $F$且$p_A(x)=(\lambda_1-x)...(\lambda_n-x)$，則
$det(A)=\lambda_1...\lambda_n$
$tr(A)=\lambda_1+...+\lambda_n$

* $\left\lceil
\begin{matrix}
a & b & b & ... & b\\
b & a & b & ... & b\\
b & b & a & ... & b\\
...\\
...\\
b & b & b & ... & a
\end{matrix}
\right\rceil$
有兩個eigen value,$\lambda_1=a-b,\lambda_2=a+(n-1)b$
用$tr(A)$來解

* $A\in F^{n\times n}$，如果$A$有n個相異eigen value，則A可對角化

* 假設$A,B$可同步對角化，則$AB=BA$，逆命題未必成立
假設$A,B$皆可對角化，則上述逆命題成立

* <img src="https://i.imgur.com/MBT9kRQ.png">

對角化的應用
---

* 求$f(A)$時，先做$A=PDP^{-1}$，之後得$f(A)=Pf(D)P^{-1}$，但$A$的所有eigen value都要落在$f(x)$的收斂區內

* 如果$X\in F^{n\times n}, X^n=A$，則定義$A^{\cfrac{1}{n}}=X$，先將$A$對角化得$D$再求出$D^{\cfrac{1}{n}}$

* 可以解微分方程系統，$x^ˊ=Ax$，且$A$可對角化，$v_1,...,v_n$為$A$的n個線性獨立eigen vector，此時$x=\sum_{i=1}^{n}{c_ie^{\lambda_1t}\vec{v_i}}$

* 可以解線性遞迴關係式

冪等算子與矩陣
---

* $T\in L(V,V)$，若$T^2=T$，則$T$為$V$上的Idempotent operator或稱為projection operator，同理套用在矩陣上

* $T(A)=\cfrac{A+A^T}{2}$是一個idempotent operator

* 假設$T\in L(V,V)$，則
$ker(T)\subseteq ker(T^2)$
$Im(T^2)\subseteq Im(T)$
且下列敘述等價
(1)$Im(T^2)=Im(T)$
(2)$rank(T^2)=rank(T)$
(3)$nullity(T^2)=nullity(T)$
(4)$ker(T^2)=ker(T)$

* **Sylvester第二定理**
假設$T\in L(V,V)$，則下列敘述等價
(1)$V=ker(T)\bigoplus Im(T)$
(2)$V=ker(T)+Im(T)$
(3)$ker(T)\bigcap Im(T)=\{0\}$
**要證明(1)只需要證明(2)或(3)**

* 假設$T$為$V$上的idempotent operator，則$V=ker(T)\bigoplus Im(T)$
假設$A\in F^{n\times n}$為idempotent matrix，則$F^{n\times 1}=ker(A)\bigoplus CS(A)$

* eigen value不是0就是1
$V(0)=ker(T),V(1)=Im(T)$
可對角化

* 對於冪等算子而言，$rank(T)=tr(T)$

冪零算子
---

* 假設$T=L(V,V)$且存在正整數k使得$T^k=O$，則$T$為nilpotent operator，且最小的k為$T$的index

* 零矩陣$O$為冪零算子，單位矩陣$I$不為冪零算子

* 假設$T$為冪零算子，且$V=span(\beta)$，則$[T]_{\beta}$為冪零算子

* 嚴格上三角或下三角矩陣都是index = n冪零矩陣

* 下列敘述等價
(1)$T$為index=$k$的冪零算子
(2)$T^k=O$ 且 $T^{k-1}\neq O$
(3)$ker(T^k)=V$ 且 $ker(T^{k-1})\neq V$
(4)$\forall v\in V, T^k(v)=0$且存在$u\in V, T^{k-1}(u)\neq 0$

* k階下移矩陣: $(S_k)_{ij}=1, \forall i=j+1$ 且 $(S_k)_{ij}=0, \forall i\neq j+1$
$(S_k)_{ij}^t=1, \forall i=j+t$
$(S_k)^k=O$

* $ker(T^k)$和$Im(T^k)$都為T-不變子空間

* 局部冪零: $T_W$為冪零算子，局部可逆: $T_W$為局部可逆
若$W$為使$T_W$為冪零算子的最大不變子空間，則$W$為最大冪零區
若$W$為使$T_W$為可逆算子的最大不變子空間，則$W$為最大可逆區

* 若$ker(T^k)=ker(T^{k+1})$,則$ker(T^{k+1})=ker(T^{k+2})$
若$Im(T^k)=Im(T^{k+1})$,則$Im(T^{k+1})=Im(T^{k+2})$

*

* $ker(T^k)\subseteq ker(T^{k+1}), Im(T^k)\supseteq Im(T^{k+1})$
因此$\{0\}\subseteq ker(T)\subseteq ... \subseteq ker(T^i)\subseteq ... \subseteq V$
$Im(T)\supseteq Im(T^2)\supseteq \supseteq ...\supseteq Im(T^i)\supseteq ...$

* $ker(T^k)=ker(T^{k+1})\Leftrightarrow Im(T^k)=Im(T^{k+1})$

* 存在最小正整數k使得$ker(T^k)=ker(T^{k+1})=...$，也存在這樣的k使得$Im(T^k)=Im(T^{k+1})=...$
$W=\bigcup_{i=1}^{\infty}ker(T^i)=ker(T^k)$且W為最大冪零區且$T_W$的指標為k
$W=\bigcap_{i=1}^{\infty}Im(T^i)=Im(T^k)$且W為最大冪零區且$T_W$的指標為k
上述定理告訴我們，T的次方愈大，則它的核集愈大，但不會一直變大
次方愈大，像集愈小，但不會一直變小

* $T\in L(V,V),dim(V)=n < \infty$，則存在一正整數k使得
$V=ker(T^k)\bigoplus Im(T^k)$
$ker(T)=ker(T^2) \Leftrightarrow V=ker(T)\bigoplus Im(T)$

* 所以要是T為冪零算子，則$V=ker(T)\bigoplus Im(T)$且$det(T)=0,T^n=O$
T的eigen value $\lambda=0$所以**T的矩陣A保證為不可逆矩陣**
反之不一定成立，但要是A為可逆，則A為不為可冪矩陣

* T為具有指標k的冪零算子，則存在$v\in ker(T^k)-ker(T^{k-1})$使得$\{v,T(v),...,T^{k-1}(v)\}$為線性獨立集

循環子空間及循環分解
---

* T-cyclic subspace generated by $v$, $C_v(T)=span\{v,T(v),T^2(v),..,T^k(v),...\}$

* $v=0 \Leftrightarrow C_v(T)=\{0\}\Leftrightarrow dim(C_v(T))=0$

* $C_v(T)$為$T-$不變子空間

* $T\in L(V,V),v\in ker(T^k)-ker(T^{k-1}),\beta=\{v,T(v),...,T^{k-1}(v)\}$為$W=C_v(T)$的一組基底且$[T_W]_{\beta}=S_k$，$\beta$稱為$W$的循環基底
如果$\beta=\{T^{k-1}(v),...,v\}$，則$[T_W]_{\beta}=S_k^T$

* 只要$dim(W)=k$就可保證$\beta=\{v,T(v),...,T^{k-1}(v)\}$為$W$的基底，但此時$T^k(v)$未必為0

:::warning
**循環分解定理 cyclic decomposition theorem**
若$T\in L(V,V)$為具有指標k的冪零算子，則存在$v_1,...,v_r\in V$使得
$V=C_{v_1}(T)\oplus \cdots \oplus C_{v_r}(T)$，
其中$dim(C_{v_i}(T))=n_i,n_1\ge n_2\ge \cdots \ge n_r$，且$v_i\in ker(T^{n_i})-ker(T^{n_i-1})$
且$dim(ker(T))=r, k=n_1$
:::

Jordan form
---

* 假設$T\in L(V,V),dim(V)=n<\infty ,dim(\bigcup_{i=1}^{\infty}ker(T^i))=m$
1. $m=0$,0不為$p_T(x)=0$的根
2. $m\ge 1$,0為$p_T(x)$的m重根

* 假設$T\in L(V,V),dim(V)=n<\infty$
1. $\lambda$不為$p_T(x)=0$的根$\Leftrightarrow 0$不為$p_{T-\lambda I}(x)=0$的根
2. $\lambda$為$p_T(x)=0$的m重根$\Leftrightarrow 0$為$p_{T-\lambda I}(x)=0$的m重根

* $T\in L(V,V),dim(V)=n<\infty,\lambda$為$T$的特徵根，$W=\bigcup_{i=1}^{\infty}ker((T-\lambda I)^i)$，若$dim(W)=n$
1. 因為0為$p_{T-\lambda I}(x)$的m重根，所以$\lambda$為$p_T(x)$的m重根，$am(\lambda)=m$
2. $(T-\lambda I)_W$為冪零算子

* **廣義特徵空間**
$K(\lambda)=\bigcup_{i=1}^{\infty}ker((T-\lambda I)^i)$，T相對於$\lambda$的廣義特徵空間
也可定義為$K(\lambda)=\{v\in V|(T-\lambda I)^p(v)=0\}$，for some $p\in Z^+$
**廣義特徵向量**
$v\in K(\lambda),v\neq 0$，v為T相對於$\lambda$的廣義特徵向量
也可定義為$(T-\lambda I)^p(v)=0$

* $K(\lambda)$為$V$的子空間也為T-不變子空間

* $J_k(\lambda)=S_k+\lambda I_k$為k階Jordan矩陣

* $u,\lambda$為$T$的相異特徵根
1. $K(u)$為$(T-\lambda I)^i$-不變子空間 (證明)
2. $(T-uI)_{K(\lambda)}$為一對一函數 (證明)
3. $((T-uI)^i)_{}K(\lambda)$為一對一函數

## Cayley Hamilton定理及應用

* **Cayley-Hamilton**定理
$A\in F^{n\times n},f(x)=p_A(x)=det(A-xI)$，則$f(A)=O$

* $T\in L(V,V),W$為T-invariant，則$T_w$的特徵多項式整除$T$的特徵多項式

* $p_A(x)$可分解，則，$A$為idempotent matrix $\Leftrightarrow A$的所有特徵根都為0 (證明)

* $A\in F^{n\times n},g(x)\in P$，若$g(x)$除以$p_A(x)$的餘式為$r(x)$，則$g(A)=r(A)$

* 若$A$為可逆，可以證明$A^{-1}\in span\{I,A,A^2,\cdots,A^{n-1}\}$

內積
---

* $<\cdot , \cdot>:V\times V \rightarrow F$
1. $\forall u,v,w\in V,<u+v,w>=<u,w>+<v,w>$
2. $\forall u,v\in V,\alpha \in F,<\alpha u,v>=\alpha <u,v>$
3. $\forall u,v\in V,<u,v>=\overline{<v,u>}$
4. $\forall v\in V,v\neq 0,<v,v> > 0$
則稱$<\cdot,\cdot>$為V上的內積

* 要證明內積，只須證明以下三個
1. $<\alpha u+\beta v,w>=\alpha <u,w>+\beta <v,w>$
2. $<u,v>=\overline{<v,u>}$，若$F=R$，則證明$<u,v>=<v,u>$
3. $<v,v>=0 \Leftrightarrow v=0$

Gram-Schmidt正交化及QR分解
---

* $S=\{v_1,...,v_k\}\subseteq V$為一個不含零向量的正交集，若$v\in span(S),v=\sum_{i=1}^k\alpha_iv_i,\alpha_j=\cfrac{<v,v_j>}{<v_j,v_j>}=\cfrac{<v,v_j>}{||v_j||^2}$

* $a_j$為$v$相對於$S$的傅立葉級數

* $S\subseteq V$為不含零向量的正交集，則$S$為線性獨立集

* $S\subseteq V$為線性獨立集，令$u_1=v_1,u_k=v_k-\sum_{i=1}^{k-1}\cfrac{<v_k,u_i>}{<u_i,u_i>}u_i$，則$\{u_1,..,u_n\}$為不含零向量的正交集且$span\{v_1,...,v_n\}=span\{u_1,...,u_n\}$

* $A\in F^{m\times n},rank(A)=n,A=QR,Q\in F^{m\times n}$，他的行向量形成單範正交集，$R$為可逆的上三角矩陣

* 任何矩陣皆可做QR分解

### 正交投影

* $W$為$V$的子空間，$v\in V$，若存在$v_0\in W$使$<v-v_0,w>=0,\forall w\in W$，則稱$v_0$為$v$在$W$上的正交投影向量

* $\beta = \{v_1,...,v_k\}$為$W$的一組基底，$<v,w>=0,\forall w\in W \Leftrightarrow <v,v_i>=0,\forall v_i\in \beta$

* $\beta = \{v_1,...,v_k\}$為$W$的一組正交基底，$v$在$W$上存在唯一的正交投影向量$proj_Wv=v_0=\sum_{i=1}^k\cfrac{<v,v_i>}{<v_i,v_i>}v_i$ (第一種找正交投影的方法)

* $W$為$V$的子空間，$v\in W \Leftrightarrow proj_Wv=v$
$proj_W0=0$
若$v\perp W,proj_Wv=0$

* $P:V \rightarrow V,P(v)=proj_Wv,\forall v\in V$
1. $P$為線性映射
2. $\forall v\in W,P(v)=v$
3. $Im(P)=W$
4. $P^2=P$

* $W$為$V$的子空間，$\beta=\{v_1,..,v_k\}$為$W$的一組正交基底
1. $||P(v)||^2=\sum_{i=1}^k\cfrac{|<v,v_i>|^2}{||v_i||^2},\forall v\in V$ (證明)
2. $||P(v)||\le ||v||,\forall v\in V$ (Bessel不等式)
3. $||P(v)||=||v||,\forall v\in W$

* $||v-P(v)||\le ||v-w||,\forall w\in W$，$v$與$P(v)$的距離永遠小於等於v與w的距離
**$P(v)$為$W$上與$v$最靠近的向量**，也是$v$在$W$上的最佳逼近best approximation

* $ker(A^HA)=ker(A)$，$rank(A^HA)=rank(A)$
當$A\in R^{m\times n},A^H=A^T,rank(A^TA)=rank(AA^T)$

* 假設$A\in F^{m\times n}$，$A$為行獨立$\Leftrightarrow$ $A^HA$為可逆矩陣
$W=R(A),b\in F^{m\times 1},proj_Wb=A(A^HA)^{-1}A^Hb$

* 假設$A\in F^{m\times n},W=R(A),b\in F^{m\times 1}$，$x\in F^{n\times 1}$使得$||Ax-b||$為最小 $\Leftrightarrow$ $A^HAx=A^Hb$ (證明)

* $A^HAx=A^Hb$稱為正規方程式，必定有解，當A不為行獨立時，$rank(A^HA)=rank(A)<n$，則有無限多組解，但$proj_Wb=Ax$必定唯一，也就是可能解出很多$x$(最小平方解)，但$Ax$必定唯一，這個$Ax$就是$b$在$CS(A)$的正交投影，

* <img src="https://i.imgur.com/TvvuVLb.png">

* $Ax$就是$proj_Wb$了，為甚麼還要用那個麻煩的公式? 因為你不知道$x$，只知道b，要從b得到x就要解正規方程式，直接套那個公式比較快

* 當$Ax=b$為inconsistent的時候，可以用最小平方解來得到最近的答案

* 求最小平方直線也是用相同方法

* $A\in F^{m\times n},rank(A)=n,b\in F^{m\times 1},A=QR$，則$||Ax-b||$為最小 $\Leftrightarrow$ $Rx=Q^Hb$ (證明)

* $A\in F^{m\times n}$為行獨立，$P=A(A^HA)^{-1}A^H$為正交投影矩陣，則$P^2=P,P^H=P$
若反過來，$P\in F^{n\times n},P^2=P,P^H=P$，則$P$為投影在$W=R(P)$上的正交投影矩陣 (證明)

* $Q\in F^{m\times n}$，其中$Q$的行向量為單範正交集，$W=P(Q)$，則$proj_Wb=QQ^Hb$，投影在$R(Q)$的正交投影矩陣為$QQ^H$

* <img src="https://i.imgur.com/eQqIHND.png">

正交補空間
---

* $V$為佈於$F$的內積空間，$S\subseteq V$，定義$S^{\perp}=\{v\in V|<v,s>=0,\forall s\in S\}$，稱為S的正交補空間

:::warning
注意!!! 沒有規定$S$必須是subspace，只需要是$V$的subset即可
:::

* $S\subseteq V$
1. $\{0\}^{\perp}=V$且$V^{\perp}=\{0\}$
2. $S^{\perp}$為$V$的子空間
3. $S\subseteq S^{\perp \perp},S^{\perp \perp}=(S^{\perp})^{\perp}$，如果S為一個subspace，則$S=S^{\perp\perp}$
4. $S\bigcap S^{\perp}=\begin{cases}
\{0\} \ \text{if 0} \in S\\
\emptyset \ \text{if 0} \notin S\\
\end{cases}$ (證明)

* 在$R^n$中，一條方程式決定的平面稱為hyperplane，若hyperplane通過原點時，它為一個子空間$W$，，此hyperplane的法向量會是$W^{\perp}$的basis

* $P$為$V$在$W$上的正交投影算子，$ker(P)=W^{\perp}$

* $V=W\oplus W^{\perp}$ (證明)
$V=W^{\perp}\oplus W^{\perp\perp}$

* 根據以上定理可知
1. $dim(V)=dim(W)+dim(W^{\perp})$
2. $W^{\perp\perp}=W$
3. $\forall v\in V$，存在唯一$w\in W,u\in W^{\perp}$使得$v=w+u$

* $P$為$V$在$W$上的正交投影算子，$proj_{W^{\perp}}v=v-proj_Wv$，$(I-P)$為$V$在$W^{\perp}$上的正交投影算子

* $W_i \perp W_j,\forall i\neq j$，稱$W_1,...,W_k$為正交子空間

* 若$W_1,..,W_k$為正交子空間，則她們也為獨立子空間

* $A\in R^{m\times n}$
1. $R(A^T)^{\perp}=N(A)$ (證明)
2. $R(A)^{\perp}=N(A^T)$
3. $N(A)^{\perp}=R(A^T)$
4. $N(A^T)^{\perp}=R(A)$

* 根據以上可以得出
若$rank(A)=n$，$A$行獨立，所以$R(A)$為一個subspace
$A(A^TA)^{-1}A^T$為$R^m$投影在$R(A)$的正交投影矩陣
$I-A(A^TA)^{-1}A^T$為$R^m$投影在$N(A^T)$的正交投影矩陣
若$rank(A)=m$，$A$列獨立
$A^T(AA^T)^{-1}A$為$R^n$投影在$R(A^T)$的正交投影矩陣
$I-A^T(AA^T)^{-1}A$為$R^n$投影在$N(A)$的正交投影矩陣

* $A\in R^{m\times n},b\in R^{m\times 1}$
$Ax=b$有解 $\Leftrightarrow$ $\forall y,A^Ty=0$,則$b^Ty=0$

* **極小解**
$Ax=b$若有解，極小解$s$是指$As=b$且$||s||\le ||u||,\forall u,Au=b$
也就是所有解當中長度最小的

* $A\in F^{m\times n},b\in F^{m\times 1}$，若$Ax=b$有解
1. 唯一存在$s\in R(A^H)$使得$s$為極小解
2. 若$(AA^H)u=b$，則$s=A^Hu$

## 內積上的算子及其應用

### 伴隨算子

* $V$為內積空間，$T\in L(V,V)$，若存在$T^*:V\rightarrow V$為線性映射使得$<T(u),v>=<u,T^*(v)>,\forall u,v\in V$，稱$T^*$為$T$的adjoint operator

* $f:V\rightarrow F$為一個線性泛函，存在唯一$v\in V$使得$f(u)=<u,v>,\forall u\in V$

* $T^*$存在唯一

* $\beta=\{v_1,\cdots,v_n\}$為$V$的單範正交基底，則$[T^*]_{\beta}=[T]_{\beta}^{H}$ (可用此方法求伴隨算子)

* $<Ax,y>=<x,A^Hy>,\forall x,y\in F^{n\times 1}$

1. $(\alpha T+\beta U)^*=\overline{\alpha}T^*+\overline{\beta}U^*$
2. $(T^*)^*=T$
3. $(TU)^*=U^*T^*$
4. $I^*=I$
5. 若$T$為可逆函數，則$(T^*)^{-1}=(T^{-1})^*$
6. 若$\lambda$為$T$的eigen value，則$\overline{\lambda}$為$T^*$的eigen value，但不保證eigen vector相等

### 正規算子

* $T^*T=TT^*$，T稱為normal operator
$A^HA=AA^H$，A稱為normal matrix

* 旋轉矩陣為正規矩陣

* 正規算子會有以下特性
1. $|T(v)|=|T^*(v)|,\forall v\in V$
2. $\forall c\in F,T-cI$為正規算子
3. 若$Tv=\lambda v$，則$T^*(v)=\overline{\lambda}v$
4. 若$Tv_1=\lambda_1v_1,Tv_2=\lambda_2v_2,\lambda_1\neq \lambda_2$，則$v_1\perp v_2$

* 若$T^*=T$，稱$T$為自伴算子(self-adjoint operator)
所以$[T^*]_{\beta}=[T]_{\beta}$，為Hermitian matrix
若$T^*=-T$，稱$T$為斜自伴算子(skew self-adjoint operator)
所以$[T^*]_{\beta}=[-T]_{\beta}$，為skew-Hermitian matrix

* 若$A\in C^{n\times n}$為Hermitian matrix，若$A\in R^{n\times n}$，以下也同樣成立
1. A為normal matrix
2. A的eigen value為實數
3. A的相異eigen value對應的eigen vector必正交
4. A的主對角項元素皆為實數
5. $det(A)\in R$

* $A\in C^{n\times n}$未必保證$A$為正規矩陣

* 若$A\in C^{n\times n}$為skew-Hermitian matrix，若$A\in R^{n\times n}$，以下也同樣成立
1. A為normal matrix
2. A的eigen value為0或純虛數
3. A的相異eigen value對應的eigen vector必正交
4. A的主對角項元素皆為0或純虛數
5. 當n為偶數時，$det(A)\in R$，當n為奇數時，$det(A)$為0或純虛數

* 若$T^*T=I$，$F=C$時稱為么正算子unitary operator
$F=R$時稱為正交算子orthogonal operator
正交矩陣，$A^{-1}=A^T$
么正矩陣，$A^{-1}=A^H$

* $A\in C^{n\times n},A^{-1}=A^H$
1. A為normal matrix
2. $|\lambda|=1$
3. 相異eigen value對應的eigen vector必正交
4. $|det(A)|=1$

* $A\in C^{n\times n},A^{-1}=A^T$
1. A為normal matrix
2. $\lambda=\pm 1$
3. 相異eigen value對應的eigen vector必正交
4. $det(A)=\pm 1$

### 么正及正交算子的特性

* $T\in L(V,V),V$為複內積空間
1. 若$<T(u),v>=0,\forall u,v\in V$，則$T=O$ (在實內積空間也成立)
2. 若$<T(v),v>=0,\forall v\in V$，則$T=O$ (證明) (在實內積空間不成立)

* $T\in L(V,V),V$為複內積空間，以下等價 (實空間也成立)
1. $T$為么正算子
2. $T$保內積，$<T(u),T(v)>=<u,v>,\forall u,v\in V$
3. $T$保長度，$|T(v)|=|v|,\forall v\in V$

* **polar identity**
$V$為佈於$F$的內積空間
$F=R,<u,v>=\cfrac{1}{4}|u+v|^2-\cfrac{1}{4}|u-v|^2,\forall u,v\in V$
$F=C,<u,v>=\cfrac{1}{4}\sum_{k=1}^4i^k|u+i^kv|^2,\forall u,v\in V$

* $A,B\in F^{n\times n}$，下列敘述等價
1. $A=B$
2. $y^HAx=y^HBx,\forall x,y\in F^{n\times 1}$

若$F=C$
1. $A=B$
2. $x^HAx=x^HBx,\forall x\in C^{n\times 1}$

* $A\in C^{n\times n}$，下列等價
1. $A$為么正矩陣
2. $A$保內積，$<Ax,Ay>=<x,y>,\forall x,y\in C^{n\times 1}$
3. $A$保長度，$|Ax|=|x|,\forall x\in C^{n\times 1}$

* $A\in R^{n\times n}$，下列等價
1. $A$為正交矩陣
2. $A$保內積，$<Ax,Ay>=<x,y>,\forall x,y\in R^{n\times 1}$
3. $A$保長度，$|Ax|=|x|,\forall x\in R^{n\times 1}$

* $T\in L(V,V),V$為複內積空間，下列等價
1. $T$為么正算子
2. 若$\beta$為$V$的orthonormal basis，則$T(\beta)$也為$V$的orthonormal basis
3. 存在$V$的一個orthonormal basis使得$T(\beta)$也為$V$的orthonormal basis

* $A\in C^{n\times n}$，下列等價
1. $A$為么正矩陣
2. 若$\beta=\{v_1,\cdots,v_n\}$為$C^{n\times 1}$的orthonormal basis，則$\{Av_1,\cdots,Av_n\}$也為$C^{n\times 1}$的orthonormal basis
3. 存在$C^{n\times 1}$的一個orthonormal basis $\beta=\{v_1,\cdots,v_n\}$使得$\{Av_1,\cdots,Av_n\}$也為$C^{n\times 1}$的orthonormal basis
4. $A$的行向量形成orthonormal set
5. $A$的列向量形成orthonormal set

* $A\in R^{n\times n}$，下列等價
1. $A$為么正矩陣
2. 若$\beta=\{v_1,\cdots,v_n\}$為$R^{n\times 1}$的orthonormal basis，則$\{Av_1,\cdots,Av_n\}$也為$R^{n\times 1}$的orthonormal basis
3. 存在$R^{n\times 1}$的一個orthonormal basis $\beta=\{v_1,\cdots,v_n\}$使得$\{Av_1,\cdots,Av_n\}$也為$R^{n\times 1}$的orthonormal basis
4. $A$的行向量形成orthonormal set
5. $A$的列向量形成orthonormal set

### 正定及正半定算子與矩陣

* $A\in C^{n\times n}$，$A$為Hermitian matrix $\Leftrightarrow x^HAx\in R,\forall x\in C^{n\times 1}$
$T\in L(V,V)$，$V$為佈於$C$的內積空間
$T$為self-adjoint operator $\Leftrightarrow <T(v),v>\in R,\forall v\in V$

* **二次式 quadratic form**
$A\in C^{n\times n}$，$Q(x)=x^HAx,\forall x\in C^{n\times 1}$
$A\in R^{n\times n}$，$Q(x)=x^TAx,\forall x\in R^{n\times 1}$

* 任何矩陣都有一個對應的對稱矩陣其二次式完全一樣 (這樣不就相等了?)

* 以下定義需要滿足$Q(x)\in R$，也就是$A$為Hermitian
**positive definite matrix(operator)**: $A\in C^{n\times n},A^H=A,Q(x)>0,\forall x\neq 0$ 或 $T$為自伴算子且$<T(v),v>\ > 0,\forall v\neq 0$
**positive semidefinite matrix(operator)**: $A\in C^{n\times n},A^H=A,Q(x)\ge0,\forall x\neq 0$ 或 $T$為自伴算子且$<T(v),v>\ \ge 0,\forall v\neq 0$

* 若$A\in R^{n\times n}$，則要改為對稱矩陣

* $A\in C^{n\times n}$為正定矩陣
1. $A$為normal matrix，因為$A$為Hermitian matrix
2. $A$為正半定矩陣
3. 所有eigen value都為正
4. 所有相異eigen value對應的eigen vectors都正交(normal matrix特性)
5. $A$為可逆矩陣(證明)
6. 主對角項元素皆為正(證明)

* $A\in C^{n\times n}$為正半定矩陣
1. $A$為normal matrix，因為$A$為Hermitian matrix
2. 所有eigen value都為非負
3. 所有相異eigen value對應的eigen vectors都正交(normal matrix特性)
4. 主對角項元素皆為非負(證明)

### 么正及正交對角化

* **unitarily similar**
$A,B\in C^{n\times n}$，存在unitary matrix $P^HP=I$使得$P^HAP=B$
**orthogonally similar**
$A,B\in R^{n\times n}$，存在orthogonal matrix $P^TP=I$使得$P^TAP=B$

* 算子的么正對角化
$T\in L(V,V)$，若存在$V$的一組單範正交基底$\beta$使得$[T]_{\beta}$為對角矩陣，則稱$T$為unitarily diagonalizable

* **Schur's定理**
$T\in L(V,V)$，若$p_T(x)$在$F$中可分解，則存在$V$的一組單範正交基底$\beta$使得$[T]_{\beta}$為上三角矩陣
$A\in C^{n\times n}$，則存在一個么正矩陣$P\in C^{n\times n}$使得$P^HAP$為上三角矩陣
$A\in R^{n\times n}$且$p_A(x)$在$R$中可以分解，則存在一個正交矩陣$P\in R^{n\times n}$使得$P^TAP$為上三角矩陣

* $V$為佈於$C$的內積空間，若$T$為normal operator，則$T$可么正對角化
$V$為佈於$R$的內積空間，若$T$為self-adjoint operator，則$T$可正交對角化
$A\in C^{n\times n}$，$A$可么正對角化$\Leftrightarrow A$為normal operator
$A\in R^{n\times n}$，$A$可正交對角化$\Leftrightarrow A$為對稱矩陣

* $A\in C^{n\times n}$，$A$為正規且上三角矩陣$\Leftrightarrow A$為對角矩陣
$A\in R^{n\times n}$，$A$為對稱且上三角矩陣$\Leftrightarrow A$為對角矩陣

* $A\in C^{n\times n}$，$A$為正規矩陣$\Leftrightarrow A$可么正對角化(Hermitian矩陣一定可以么正對角化)
$A\in R^{n\times n}$，$A$為對稱矩陣$\Leftrightarrow A$可正交對角化

* **光譜定理spectral theorem**
$T\in L(V,V),\lambda_1,\cdots,\lambda_k$為其相異eigen value，$F=C$時假設$T$為normal operator，$F=R$時假設$T$為self adjoint operator，$W_i=V(\lambda_i),T_i$為$V$投影在$W_i$上的正交投影算子
1. $V=W_1\oplus W_2 \oplus \cdots \oplus W_k$
2. $W_i^{\perp}=\sum_{j\neq i}W_j$
3. $T_iT_j=\delta_{ij}T_i$ (證明)
4. $T_1+T_2+\cdots+T_k=I$ (證明)
5. $T=\lambda_1T_1+\lambda_2T_2+\cdots+\lambda_kT_k$ (證明)

### 正定及正半定矩陣的特性

* **principal minors**
<img src="https://i.imgur.com/CjCVuVV.png">

* **LDU分解**: $A=LDU=LDL^T$，$L$為對角線皆為1的下三角矩陣，$D$為對角矩陣
先做LU分解，再把U的對角項拿出來變成D

* $A\in R^{n\times n}$為對稱矩陣(代表可以正交對角化)，則以下等價
1. $A$為正定
2. $A$的所有eigen values都為正
3. $\Delta_k(A)>0,\forall k=1,\cdots,n$

* 可用以上定理檢查一個矩陣是否正定，若該矩陣不是對稱矩陣，可以先把他轉為對稱矩陣

* $A\in R^{n\times n}$為對稱矩陣，若$A$為正定矩陣，則$A=LDL^T$，L為對角線皆為1的下三角矩陣且$D$為對角項元素皆為正的對角矩陣 (特徵根皆為正)

* $A\in C^{n\times n},A^H=A$
1. $A$為正定 $\Leftrightarrow A$的所有eigen values都為正
2. $A$為正半定 $\Leftrightarrow A$的所有eigen values都為非負

* **Cholesky分解**
假設$A\in R^{n\times n}$為對稱矩陣，若$A$為正定矩陣，則$A=L'D(L')^T=L'\sqrt{D}\sqrt{D}(L')^T=L'\sqrt{D}^T(L'\sqrt{D}^T)^T=LL^T$，其中$L=L'\sqrt{D}^T$為下三角矩陣且對角項元素皆為正

* $A\in C^{n\times n}$
$A$為正定矩陣 $\Leftrightarrow$ 存在$B\in C^{m\times n},rank(B)=n,A=B^HB$

* $A\in R^{n\times n}$，$A$為對稱矩陣
$A$為正定矩陣 $\Leftrightarrow$ 存在$B\in R^{m\times n},rank(B)=n,A=B^TB$

* 假設$A\in C^{n\times n}$，則$A$為正半定矩陣$\Leftrightarrow$ 存在$B\in C^{m\times n}$使得$A=B^HB$
假設$A\in R^{n\times n}$，則$A$為正半定矩陣$\Leftrightarrow$ 存在$B\in R^{m\times n}$使得$A=B^TB$

* 假設$A\in C^{m\times n}$，則$A^HA,AA^H$都是正半定矩陣
假設$A\in R^{m\times n}$，則$A^TA,AA^T$都是正半定矩陣

* $A\in C^{n\times n}$，則
$A$為正定矩陣 $\Leftrightarrow$ 存在$B$為正定矩陣使得$A=B^2$
$A$為正半定矩陣 $\Leftrightarrow$ 存在$B$為正半定矩陣使得$A=B^2$
$A\in R^{n\times n}$，則
$A$為正定矩陣 $\Leftrightarrow$ 存在$B$為正定矩陣使得$A=B^2$
$A$為正半定矩陣 $\Leftrightarrow$ 存在$B$為正半定矩陣使得$A=B^2$

### 二次式的應用

* **主軸定理principal axis theorem**
假設$A\in C^{n\times n}$為Hermitian matrix，$Q(x)=x^HAx=\lambda_1|y_1|^2+\cdots+\lambda_n|y_n|^2$
假設$A\in R^{n\times n}$為symmetric matrix，$Q(x)=x^HAx=\lambda_1y_1^2+\cdots+\lambda_ny_n^2$

* **Rayleigh商式**
$A\in C^{n\times n}$為Hermitian matrix，$A\in R^{n\times n}$為對稱矩陣，$\rho(x)=\cfrac{Q(x)}{||x||^2},x\neq 0$稱為Rayleigh quotient

* **Rayleigh principle**
$A\in F^{n\times n}$，$F=C$時為Hermitian matrix，$F=R$時為對稱矩陣，$\lambda_1\le \lambda_2\le \cdots \le \lambda_n$為$A$的特徵根
1. $\lambda_1\le \rho(x)\le \lambda_n$
2. $max_{x\neq 0}\rho(x)=\lambda_n$
3. $min_{x\neq 0}\rho(x)=\lambda_1$

* $x$取$A$相對於$\lambda_n$的特徵向量$x_n$，則$\rho(x_n)=\lambda_n$，所以$max\rho(x)=\rho(x_n)$
$x$取$A$相對於$\lambda_1$的特徵向量$x_1$，則$\rho(x_1)=\lambda_1$，所以$max\rho(x)=\rho(x_1)$

### Householder 轉換

* $u\in R^{n\times 1},||u||=1$，稱$H=I-2uu^T$為相對於u的Householder matrix，也稱為elementary reflextor
1. $H$為對稱矩陣
2. $H$為正交矩陣，所以$H^{-1}=H^T=H$

* $x,y\in R^{n\times 1},x\neq y,||x||=||y||,u=\cfrac{x-y}{||x-y||},H=I-2uu^T$，則
1. $||x-y||^2=2(x-y)^Tx$
2. Hx=y (證明)

* 對任意$x\in R^{n\times 1}$，若$\alpha = ||x||,y=\alpha e_1,u=\cfrac{x-y}{||x-y||},H=I-2uu^T$，則$Hx=\alpha e_1$
就是x經過Householder轉換後，第一項之外元素都變成0

* $x\in R^{n\times 1}$，則存在一個Householder矩陣使得$Hx=\alpha_1 e_1+\cdots+\alpha_k e_k$，也就是$Hx$的後面n-k項為0

### 奇異值分解

* $\sigma_i,\forall i=1,2,\cdots,s$稱為$A$的奇異值singular value

* $A\in C^{m\times n},s=\{m,n\}$，若$A=U\Sigma V^H,U\in C^{m\times m},V\in C^{n\times n},\Sigma\in C^{m\times n}$
其中$U^HU=I,V^HV=I$為么正矩陣，$(\Sigma)_{ij}=0,\forall i\neq j$且$(\Sigma)_{ii}=\sigma_i,\sigma_1\ge \sigma_2\ge \cdots \ge \sigma_s$

* $A\in R^{m\times n},s=\{m,n\}$，若$A=U\Sigma V^H,U\in R^{m\times m},V\in R^{n\times n},\Sigma\in R^{m\times n}$
其中$U^TU=I,V^TV=I$為正交矩陣，$(\Sigma)_{ij}=0,\forall i\neq j$且$(\Sigma)_{ii}=\sigma_i,\sigma_1\ge \sigma_2\ge \cdots \ge \sigma_s$

* $\Sigma$可以不為方陣

* 當$A$為方陣，$U=V$時，$A=V\Sigma V^H$，此為么正對角化

* 做$A$的奇異值分解步驟如下
假設$U=[u_1 \ \ u_2 \ \ \cdots \ \ u_m],V=[v_1 \ \ v_2 \ \ \cdots \ \ v_n]$
1. 首先找$A^HA$的eigen value $\lambda_1,\cdots,\lambda_n$
則$A$的singular value為$\sigma_i=\sqrt{\lambda_i}$，記得要照大小排好

2. 找$V$，因為$V$的行向量都是$A^HA$的eigen vectors且為單範正交集，所以用$\lambda_i$找$V(\lambda_i)=ker(A^HA-\lambda_iI)$的基底並做成單範正交集

3. 找$U$分為兩部分，首先因為知道$AV=U\Sigma$，所以$Av_i=\sigma_iu_i$，所以可先找$u_1,\cdots,u_n$
再來$u_{n+1},\cdots,u_m$形成$N(A^H)$的單範正交基底，所以解$A^H=0$並化成單範正交基底就行

* 經過證明可以知道任何矩陣都可以做SVD分解，並且有以下幾個特性
* 若$A^HA$的eigen values是$\lambda_1,\cdots,\lambda_n$，則$A$的singular value就是$\sigma_i=\sqrt{\lambda_i}$
* $A$的奇異值唯一，但$U$跟$V$未必唯一
* $V$的行向量都是$A^HA$的eigen vectors且形成一個單範正交集
* $U$的行向量都是$AA^H$的eigen vectors且形成一個單範正交集
* $Av_i=\sigma_i u_i,\forall i=1,\cdots,n$，因為$AV=U\Sigma$
* $A^Hu_i=\sigma_iv_i,\forall i=1,\cdots,n$ 並且$A^Hu_i=0,\forall i=n+1,\cdots,m$
* $v_i$稱為$A$的right singular vector，$u_i$稱為$A$的left singular vector
* 若$rank(A)=r$，則
* $v_1,\cdots,v_r$形成$R(A^H)$的單範正交基底
* $v_{r+1},\cdots,v_n$形成$N(A)$的單範正交基底
* $u_1,\cdots,u_r$形成$R(A)$的單範正交基底
* $u_{r+1},\cdots,u_m$形成$N(A^H)$的單範正交基底
* $A^HA$和$AA^H$有相同的non zero eigenvalues

### 虛反矩陣

* $A\in F^{m\times n},s=min\{m,n\}$，$A=U\Sigma V^H$
定義$A$的pseudoinverse為$A^+=V\Sigma^+U^H$
其中$\Sigma^+\in F^{n\times m},(\Sigma^+)_{ij}=0,\forall i\neq j$
$(\Sigma^+)_{ij}=\begin{cases}
\cfrac{1}{\sigma_i}, \ \ if \ \ \sigma_i \neq 0\\
0, \ \ if \ \ \sigma_i =0
\end{cases}$
又稱為Moore-Penrose廣義反矩陣

* $\Sigma^+$就是把$\Sigma$轉置之後把非零元素都變倒數

* $O^+=O$

## 統整算子

:::info
所有operator經過座標化都可以得到對應matrix，伴隨算子對應到$A^H$
:::

| 名稱 | 定義 | 備註 |
| -------- | -------- | -------- |
| Adjoint operator | $<T(v),v>=<v,T^*(v)>$，$[T^*]_{\beta}=[T]_{\beta}^H$ | |
| Normal operator | $T^*T=TT^*$，$A^HA=AA^H$ ||
| self-adjoint operator | $T*=T$，$A^H=A$ | 也是normal operator，Hermitian matrix |
| skew self-adjoint operator | $T^*=-T,A^H=-A$ |也是normal operator，skew Hermitian matrix|
| unitary operator | 在$C$中，$T^*T=I,A^HA=I$ ||
| orthogonal operator | 在$R$中，$T^*T=I,A^TA=I$ ||