## 離散
### Number Theory


範例：

### Graph

- $v-e+r=2$ 需 ++connected planar++ 才成立
- a simple graph is connnected $\leftrightarrow$ it has a spanning tree
- 不管是 simple 還是 multigraph，只要是 undirected $\rightarrow$ 具 even number of vertices of odd degree

#### Hypercube


$Q_n$ 代表的是：$2^n$ 個長度為 n 的 bit string
- $Q_n$ is regular
> <font color = "snake">regular</font>: 所有 node 的 degree 都相同
> $Q_n$ 中每個點的 degree 都是 n
>> 因為 $Q_n$ 中有邊相鄰，代表只有一個 bit 不同
>> 並且每個 $Q_n$ 中的 vertex 都是 n bit 的 binary string，所以 for arbitrary vertex in $Q_n$，和此 vertex 只差一 bit 共有 n 種可能性

- $Q_n$ 有 $2^n$ 個 vertices
> n bit binary string 的所有可能性
- $Q_n$ 有 $2^{n-1}n$ 個 edges
> ${2^n \times n \over 2} = 2^{n-1}n$
> 另一種證法：
>> 令 $E(n)$ 代表 $Q_n$ 的 edge 數
>> 因為 $Q_n$ 是由兩個 $Q_{n-1}$ 組合而成，兩個 $Q_{n-1}$ 的對應點相連，因此可得：
>> $\quad E(n) = 2E(n-1) + 2^{n-1}$
>> $\quad E(1) = 1$
>>（因為兩個 $Q_{n-1}$ 的對應點相連共會多出 $Q_{n-1}$ 的 vertices 數條邊）
- $Q_n$ 的 ++diameter++ 是 ==n==
- $n > 1$ 的 $Q_n$ 有 Hamiltonian cycle

#### Hamiltonian

- <font color = "red">$Q_n$</font> is Hamiltonian if $n > 1$
- 點數 $\ge 3$ 的情況下可用：
1. 
> 所有點的 degree 都 $\ge {n\over 2}$

2. 
> 任兩個不相鄰的點 degree 和 $\ge n$

### 一些組合公式




由上圖中偶數項減掉奇數項 = 0 的結果
可推得 奇數項和 = 偶數項和



> 108 台 4.
> 


:::success
$\dbinom{n+r-1}{r}$
- 重複組合：n 個相異物，可重複需選，選 r 個
- r 個相同球，放到 n 個相異箱，允許空箱的方法數
- 非負整數解個數 $x_1 + x_2 + x_3 + ... +x_n = r \quad x_i \ge 0$
:::

> ++重複組合++可想成畫 $r$ 個圈，用 $n-1$ 根柱子隔開（隔出 $n$ 段，每段為某種物品的個數），因此總共 $r+n-1$ 個東西在排，即 $(r+n-1)!$ 再除掉排柱子的 $(n-1)!$ 以及排圈圈的 $r!$

:::success
$onto(m,n)$
:::

### 特徵方程式

[特徵方程式筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/SyR4AjQKp)




### Fibonacci Number


<img src="https://hackmd.io/_uploads/H1fD8FIOT.png" width="40%" height="auto">


> 如果算出來的 function $h(n) \ = \ F_{n+2}$
> 例如下方第一點 $h(1)=2 \ , \ h(2)=3$ 是 $F_n$ 平移兩格
> $h(n)$ 的公式就是 $F_n$ 的公式，$n$ 改 $n+2$

- 長度為 n 的 binary string，不含連續 1 ／ 不含連續 0 的個數 $= \ F_{n+2}$
- 長度為 n 的 binary string，不含==奇數==個連續 1 ／ 不含奇數個連續 0 的個數 $= \ F_{n+1}$
- 長度為 n 的 binary string，不含==偶數==個連續 1 ／ 不含偶數個連續 0 的個數 $= \ 2F_n$
- $S \ = \ \{1,2,...,n\}$ $\quad S$ 的子集合裡面不含奇數個連續整數的個數 $= \ F_{n+1}$

---
## 線代

### 易錯是非題

> ==有限維==的內積空間（且==非零空間==）就會++有 orthonormal basis++
> 所以：<font color = "red">並非所有的內積空間都有 orthonormal basis</font>

- 零空間 $\{\vec 0\}$ 也是內積空間，滿足內積空間的定義（具某個內積的空間）
內積定義：

> rank-nullity Thm 須<font color = "red">定義域是有限維才成立</font>

- 實際上<font color = "red">所有 real / complex vector space 都可以被視為內積空間</font>
> 出自 Fridberg p.339

> 一樣也要有限維向量空間才成立
> 出自 Fridberg p.366

- 如果 $A, B$ 都是方陣且 $AB=BA$，則 $A,B$ 具共通的 eigenvectors

### Vector Space

十個公設

- Every vector space has a basis
> friedberg p.61
>> 就算是無限維向量空間，其每個 basis 的 cardinality 都相同

### det 特性

- 具兩個相同的列 $det = 0$
- 做一次列交換 $det \times -1$
把某列乘 k 倍（第二型列運算） $det \times k$
把某列乘倍數加到另一列（第三型列運算）不改變 $det$
- $n \times n$ 方陣 $rank < n$ $\rightarrow$ $det = 0$

> 是方陣 $det$ 才可拆！




> 證明
> 
> 拆法！證明時將 $CA^{-1}$ 設成 $X$，$D-CA^{-1}B$ 設成 $Y$ 去解
> 106 交 12.

> adjoint A 的行列式 = A 的行列式取 bar
> 108 台 9.

### 1-1 onto

:::danger
注意條件！
:::


> - <font color = "red">線性</font>才保證 1-1 等價 ker(A) 是零空間
> - 
> 如果 $A$ 可逆，代表
> $ker(A) = Lker(A) = \{\vec 0\}$
> $\rightarrow$ 將 $\vec b$ 「還原」回 $\vec x$ 時因為唯一有可能的 $\vec x_n = \vec 0$ 所以只有唯一的 $\vec x$ （1-1）
>


> 要<font color = "red">維度相同、有限維、是向量空間</font> 1-1 才會等價於 onto

> ==全 1-1 左必 1-1==
> ==全 onto 右必 onto==

> ==右不 1-1 全可 1-1==
> ==左不 onto 全可 onto==

> ==1-1 合成 1-1 必為 1-1==

> ==onto 合成 onto 必為 onto==

> ==bijection 合成 bijection 必為 bijection==

### rank

::: success
$rank(A) = dim(CS(A)) = dim(RS(A))$
> $row \ rank = col \ rank$
> 意義： 任何矩陣（不一定要方陣）++行所生成的空間++ 和 ++列所生成的空間++ 維度一定相同
:::

==行滿秩（full column rank）==
$\Leftrightarrow$ 行獨立
$\Leftrightarrow$ <font color = "red">1-1</font>
$\Leftrightarrow$ $ker(A) =$ 零空間
$\Leftrightarrow$ 沒有自由變數
$\Leftrightarrow$ <font color = "red">$A\vec{x} = \vec{b}$ 至**多**一解 $for$ $every$ $\vec{b}$ </font>

==列滿秩（full row rank）==
$\Leftrightarrow$ 列獨立
$\Leftrightarrow$ <font color = "red">onto</font>
$\Leftrightarrow$ 行生成（$CS(A) = R^m$）
$\Leftrightarrow$ <font color = "red">$A\vec{x} = \vec{b}$ 至**少**一解 $for$ $every$ $\vec{b}$</font>

- 如果<font color = "red">列相依</font>，代表 A 沒有行生成，即 $CS(A) \not= R^m$ （$CS(A) \subset R^m$）
因此，可能存在某個 $\vec b \in R^m$ 但 $\vec b \notin CS(A)$
這也就代表有++可能會存在 $\vec b$ 無解++

> <font color = "red">左乘可逆／右乘可逆 不改變 rank</font>

> <font color = "red">rank 越乘越小！</font>


### Linear

> 線性函數乘倍數、相加仍為線性
> 收集「所有 V 到 W 的線性變換的 function」 的空間是向量空間

### 可逆

> 如果 A 可逆， A 乘另一個矩陣 B 變成零矩陣，則 B 必為零矩陣

> 111 台

- 行 orthonormal 的矩陣不一定可逆
> $\because$ <font color = "red">可能不是方陣！記得</font>
- 正交矩陣的反矩陣也是正交矩陣


### 矩陣表示法


> 如果函數 T 可逆，
> 則 T 的反函數的矩陣表示法 = T 的矩陣表示法的反矩陣
>> <font color = "red">矩陣表示法（matrix representation） 不一定可逆</font>
>> 例如：零函數的矩陣表示法為零矩陣不可逆
>> 但<font color = "red">座標轉換矩陣一定可逆</font>

### 內積

#### 判斷是否可當內積

原始內積定義為滿足：

> 加法可以拆開、純量可以提出來
> 佈於複數的話交換要取 bar
> 只有零向量自己跟自己內積會是 0

- 積分型：<font color = "green">小積到大，權重是正</font> $\rightarrow$ 可當內積
- $\Sigma$ 型：如果<font color = "red">有權重是 0</font> $\rightarrow$ 不可當內積
- 把題目的選項寫成 $\vec p \times A \times \vec q$ 的形式
> $\vec p \in F^{1\times n}$ ， $\vec q \in F^{n\times 1}$ ， $A \in F^{n \times n}$

如果 <font color = "green">A 正定</font> $\rightarrow$ 可當內積，<font color = "red">A 非正定的話不能當內積！</font>

- 複數內積可能用到：
> $\alpha = a+bi$
> $\overline{\alpha} = a-bi$
>
> $|\alpha| = \sqrt{a^2+b^2}$
>
> $\alpha\overline{\alpha} = |\alpha|^2$


### 四大空間

- <font color = "red">方陣的非 0 eigenvalue 對應的 eigenvector 必在行空間中</font>
> 

### eigenvalue / eigenvector

> - 只要是 skew （skew-symmetric / skew-Hermitian）
> $\rightarrow$ eigenvalue 為純虛數
> - 即使佈於實數，正交矩陣的 eigenvalue 取絕對值 $=1$
> 也不能保證 eigenvalue 為 $\pm 1$
> $\rightarrow$ 有可能是 $\pm i$
>> 舉例 $|i| = ?$
>> $\rightarrow i = 0+1i$
>> $\rightarrow |i| = \sqrt{0^2+1^2}=1$
>>
>> （複數取絕對值的方法可參「內積」小節）

- 如果 $AB=BA$ （稱作 <font color = "snake">commuting matrix</font>）且 $A, B$ ++可對角化++，則有共通的 eigenvector set
> 可參考下方「對角化」小節
> 因為 $AB=BA$ 等價於可同步對角化，因此他們的 eigenvector 矩陣 $Q$ 相同
- <font color = "red">如果 $AB=BA$，則 $A$ 和 $B$ 有一個共通的 eigenvector</font>
- 如果 A 的某個 eigenvalue $\lambda$ 有多個線性獨立的 eigenvector (i.e. $gm(\lambda) > 1$)，我們可以從 $\lambda$ 的 eigenspace $v(\lambda)$ 中取互相垂直的 eigenvector （或是說做 Gram Schmidt）
但是<font color = "red">相異 eigenvalue 對應的 eigenvector 則不一定能取到垂直的</font>，除非 normal
> normal $\rightarrow$ 相異 eigenvalue 對應的 eigenvector 必垂直
> - <font color = "red">eignvectors of a symmetric matrix can be chosen to be orthonormal</font>
- 如果 <font color = "red">$A$ 是方陣，part of the eigenspace can equal the left nullspace of A</font>
> 105 台

- 若 $A = \begin{bmatrix}
A_{11} & A_{12} \\
O & A_{22}
\end{bmatrix}$ 且 $A_{11}$、$A_{22}$ 為方陣
則 $A$ 的 eigenvalue $= A_{11}$ 的 eigenvalue $\bigcup$ $A_{22}$ 的 eigenvalue
- 若實矩陣具複數的 eigenvalue $\rightarrow$ 必為共軛根

### 對角化

1. over $C$: normal $\leftrightarrow$ 可么正對角化
2. over $R$: symmetric $\leftrightarrow$ 可正交對角化

- 任何 finite size 的 unitary matrix 都可對角化
> 因為 unitary $\rightarrow$ normal $\rightarrow$ 可么正對角化
> $\exists \ V: unitary,\quad D: \ unitary \ 且 \ diagonal$
> $\ni U = VDV^*$
- $A, B$ 可同步對角化 $\leftrightarrow$ $AB = BA$
> 同步對角化（simultaneously diagonalizable）
> $A ,B \in F^{n\times n}$
> $\exists Q: invertible \ni A=QD_1Q^{-1}, B=QD_2Q^{-1}$

### 相似

> 111 台

- 若 $A \sim B$ 則 $A$ and $B$ represent the same representation w.r.t. different bases

### 么正(Unitary)

- 兩個么正矩陣相乘仍為么正
- 么正六保
:::warning
如果 $A$ 么正相似於 $B$，則
1. $A:$ normal $\leftrightarrow$ $B:$ normal
2. $A:$ Hermitian $\leftrightarrow$ $B:$ Hermitian
3. $A:$ skew-hermitian $\leftrightarrow$ $B:$ skew-hermitian
4. $A:$ 正定 $\leftrightarrow$ $B:$ 正定
5. $A:$ 正半定 $\leftrightarrow$ $B:$ 正半定
6. $A:$ 么正 $\leftrightarrow$ $B:$ 么正
:::
> 六大算子除了 symmetric, skew-symmetric, orthogonal

#### 么正相似(unitarily equivalent)

- 么正相似是++等價關係++
- 若 $A$ 么正相似於 $B$，則 $A$ 正定／正半定 $\leftrightarrow$ $B$ 正定／正半定

> 108 台 10.

### Isomorphic

> <font color = "red">是有限維向量空間、field 相同</font> ==維度相同 等價於 兩空間 Isom==

例子：

- $M_{2\times3}(F)$ 和 $F^5$ 不 isom
> 因為 $dim(M_{2\times3}(F)) = 6$ 但 $dim(F^5)=5$

- $P_n(F)$ 和 $P_m(F)$ isom $\leftrightarrow$ $n=m$


### $A^TA$ / $AA^T$

==$ker(A) \ = \ ker(A^TA)$==
$ker(A^T) \ = \ ker(AA^T)$
> 不用記，帶入 $A = A^T$ 即可

==$CS(A) \ = \ CS(AA^T)$==
$CS(A^T) \ = \ CS(A^TA)$
> 不用記，帶入 $A = A^T$ 即可

- 如果<font color = "red"> $A$ 列滿秩， $AA^T$ 正定</font>
> $A$ 列滿秩即 $A$ 列獨立
> $\leftrightarrow$ $A$ 行生成（$CS(A) = R^m$）
> 因為 $CS(A) \ = \ CS(AA^T)$，所以 $CS(AA^T) = R^m$
> 因為 $AA^T \in R^{m\times m}$，所以 $AA^T:R^m \rightarrow R^m$
> 因此 $AA^T$ 行生成
> 又因 $AA^T$ 是方陣，所以行生成等價於行獨立，等價於可逆

### Normal

- 是 Normal: symmetric, skew-symmetric, Hermitian, skew-Hermitian, Unitary

$T: normal$
$\leftrightarrow T^*: normal$
$\leftrightarrow \forall \vec x,\quad ||T(x)||=||T^*(x)||$

- 若 $T: normal$，則 $T^*$ 和 $T$ 的 kernel, range 皆相同
> i.e.
> $Ker(T) = Ker(T^*)$
> $Im(T) = Im(T^*)$
- 若 $T: normal$，則 $Ker(T)\cap Im(T) =\{\vec 0\}$
- 若 $T: normal$，則

$\lambda \in \lambda(T), \quad \vec v = \ eigenvector\ w.r.t. \lambda$

$\leftrightarrow \bar\lambda \in \lambda(T^*), \quad \vec v = \ eigenvector\ w.r.t. \bar\lambda$
> eigenvalue 差一個 bar，對應的 eigenvector 相同
- 若 $T: normal$，則 $T$ 的 characteristic polynomial splits over $C$
> Fundamental Thm of algebra

> normal 保證可對角化且 eigenspace 皆正交

### 特殊矩陣

### Markov Chain

<font color = "snake">transtion matrix</font>
A: transtion matrix $\leftrightarrow A^t\vec u = \vec u$
> transtion matrix 就是乘到某個次方後值不變
> 只要每行加起來是 1，就是 transition matrix

- transtion matrix 的 eigenvalue 一定有 1
- transtion matrix 的 eigenvalue 取絕對值必 $\le 1$

<font color = "snake">regular</font>
一個 transtion matrix 是 regular if 這個矩陣的某個次方所有 entries 皆為正
- regular transtion matrix 可能含 0 entries

求 steady state 不用求出所有的 eigenvalue，也不用對角化，取 $v(1)$（1 的 eigenspace）的 basis，再做如下例中的相加取比例（單位化）即是

例子：

### orthogonal complement

兩個 subspace 可能互相 orthogonal ，卻不互為彼此的正交補空間
> 理由：他們的維度可能太小

但如果加上<font color = "red">保證 $dim(V) + dim(W) =$ 所在空間的維度</font>，則
$V \ = W^\perp$ 且 $W \ = V^\perp$ 且 ==$(V^\perp)^\perp \ = \ V$==


> orthogonal complement [更詳細的筆記](https://hackmd.io/VELEzFCpRIWjdU7_b4zEPg)

### 投影

Given 一正交投影矩陣： $P$
- $P^2=P$
> $\Rightarrow$ 投影矩陣 Idempotent
>> 因為投影一次即把被投影的向量送到投影面上，第二次投影再對這個已在投影面上的向量作用，結果即不作用
- $I-P$ 也是正交投影矩陣，且會投影到 $P$ 的正交補空間
> 例如將向量 $\vec x$ 投影到 $A$ 的行空間
> 取 $P=A(A^TA)^{-1}A^T$，$\vec x$ 左乘 $P$ 即為解
>
> 如果要將 $\vec x$ 投影到 $A$ 的左核空間（$Lker(A)$）
> 將 $\vec x$ 左乘 $I-P$ 即為解
>> 因為 $Lker(A)$ 是 $CS(A)$ 的 orthogonal complement

### Vandermonde



### 分解

#### QR

將 $A$ 分解成 $A = QR$
$A$ 可不為方陣（$A$ 為任意的 $m \times n$ 矩陣）

$Q$：orthogonal / unitary
$R$：上三角
> right triangular

::: success
方法：
1. 對 $A$ 的行做 Gram Schmidt
2. 單位化
3. 由單位化的過程即可得到 R方法：
:::

- 如果 $A$ 可逆，$A$ 的 QR 分解唯一

#### Cholesky

也就是 ==$LL^T$== 分解
<font color = "red">$A$ 要正定才能做</font>

:::success
若 $A$ 為方陣，$A^T=A$，則：

$A$：正定 $\leftrightarrow$ $A$ 可分解成 $A=LL^T$

$L$： 下三角，對角線為正
:::
> $LL^T$ 為 $LU$ 分解的一種，只是 $LU$ 分解對 $A$ 沒有正定的要求，分解出的 $L$ 和 $U$ 也沒有關係；但當 $A$ 滿足正定時，$L$ 和 $U$ 互為轉置，且 $D$ 的對角線皆為正

步驟：
1. （檢查 A 是否為正定）
2. 做 LU 分解
> 從上面砍下面，禁止列交換，列運算後的上三角即為 $U$
> $L$ 則是對角填 1，下方為列運算對應項的倍數取負號
> 例如 $R_{23}^{\quad(3)}$ 列運算時做了第二列乘三倍加到第三列，則 $L$ 的 $l_{32}$ 項填 $-3$
3. 提出 $U$ 的對角為 $D$，使 $U$ 變成對角線皆為 $1$ 的 $L^T$
> 因為 $A$ 正定，就會剛好滿足這件事
> 提出 $D$ 的方法即直接把 $U$ 的對角填到 $D$ 的對角，$D$ 的其餘項皆 $0$
> $U$ 本身即看對角項提多少，整列就除多少
4. 把 $D$ 的對角項拆成兩個開根號的 $\sqrt{D}$ 相乘
> 因為 $A$ 正定，$D$ 的對角項就皆為正，因此可以開根號
5. $L\sqrt{D}$ 即為 C

> $A=LU$
> $\rightarrow$ $A=LDU$ 即 $A=LDL^T$
> $\rightarrow$ $A=L\sqrt{D}\sqrt{D}L^T$
>> 因為 $\sqrt{D}$ 為對角矩陣，所以 $\sqrt{D} = \sqrt{D}^T$
>>
> $\rightarrow$ $A=L\sqrt{D}\sqrt{D}^TL^T$
> $\rightarrow$ $A=L\sqrt{D}\ (L\sqrt{D})^T$

---
#### $A=U^2$

- 如果 <font color = "red">$A$ 正定，必能取到 $U$：可逆 $\ni$ ==$A=U^2$==</font>

因為 $A$ 正定，所以 $A$ 必為 Hermitian
> 因為正定 eigenvalue 皆正，要定義正負必 $\in R$，所以所有 eigenvalue 皆 $\in R \rightarrow$ Hermitian

合理假設 $A$ 佈於實數，因此 $A$ 為實對稱矩陣

因為若 $A$ over $R$ ，則
$A^T=A$ $\leftrightarrow$ A 可正交對角化

將 $A$ 正交對角化後
得到 $A=PDP^{-1}$，其中 $P:$ orthogonal（$P^T=P^{-1}$）
$\rightarrow$ 將 $D$ 拆成兩個開根號的 $\sqrt{D}$ 相乘，即：

$A=P\sqrt{D}\sqrt{D}P^T$

中間乘 <font color = "green">$P^TP$</font>
$\rightarrow$ $A=(P\sqrt{D}P^T )\ (P\sqrt{D}P^T)$

即得 $U=P\sqrt{D}P^T$ ，且 $U$ 為可逆
> 因為 $P:$ orthogonal（$P^T=P^{-1}$）
> 所以 $P$ 為可逆
>
> 因為 $A$ 正定，所以 $A$ 的 eigenvalue 皆為正
> 又 $A=PDP^{-1}$ 代表 $A \sim D$ 所以 $A$ 和 $D$ 具相同的 eigenvalue
> 因為 $D$ 為對角，所以 $D$ 的 eigenvalue 為對角項，所以 $D$ 的對角項皆正
> 因此，$\sqrt{D}$ 為對角矩陣，且對角皆正，因此 $det(\sqrt{D}) \ne 0$，$\sqrt{D}$ 可逆
>
> $\Rightarrow$ $U=P\sqrt{D}P^T$ 為三個可逆矩陣相乘，因此 $U$ 為可逆

---

> $A=B^HB$ 以及前兩種分解，三種題型整理


---
#### Polar Decomposition

++任何方陣++ 都可拆成 ==么正== 乘 ==正半定==
且如果這個方陣可逆，則拆法唯一

原因：
> 因為任何矩陣都可做 SVD 分解，在 SVD 分解的 $U$ 和 $\Sigma$ 之間插入 $V^*V$ 即可得：
> - 么正的 $W = UV^*$
>> 因為 SVD 分解的 $U$ 本來就么正，再乘上么正的 $V$ 仍然是么正
>>
> - 正半定的 $P = V\Sigma V^*$
>> 因為 SVD 分解的 $\Sigma$ 裡面的 r 個 singular value 皆 > 0，其餘對角項為零，所以 $\Sigma$ 為正半定矩陣
>> 因為 $V$ 為 unitary，所以 $P$ 么正相似於 $\Sigma$
>> 根據定理，么正相似保正半定，所以 $\Sigma$ 正半定 $\rightarrow \ P$ 正半定
>> （定理可參考上方「么正相似」）


---
#### Eigendecomposition

$A = S \Lambda S^{-1}$

- $S$ 由 $A$ 的 eigenvector 組成，通常這些 eigenvector 會單位化，但不一定要（$S^{-1}$ 會剛好將 $S$ 的大小消掉）
- 常用 $2\times2$ 不可對角化的矩陣例子：

>$\left [
\begin{array}{cc}
1 & 1\\
0 & 1\\
\end{array}
\right ]$
>> 另外這個矩陣的 eigenvalue 為 ${1,1}$ 但和單位矩陣並不相似，單位矩陣本身就是對角，但這個矩陣無法化為對角
>> - 相似的充要條件只有 Jordan Form 相同
>>
>> 這個矩陣已經是 Jordan Form 的形式，由右上角的 1 可以知道 $gm(1) = 1 < am(1) = 2$，此矩陣只有一個 Jordan Block 但單位矩陣含兩個 Jordan Block
>> 另外，由這個例子可以看到這個矩陣的 eigenvalue 為 ${1,1}$ 所以可逆，但他不可對角化
>> - <font color = "red">可逆和可對角化無關</font>

---
#### SVD

- SVD 的直觀意義：
把任何的 linear transformation $A$ 拆成旋轉、鏡射（$U, V$）和 scalar（$\Sigma$）的組合
> 如果 $det(A) > 0$
> $\rightarrow U, V$ 可以都是旋轉+鏡射，或是都只有旋轉
> 如果 $det(A) < 0$
> $\rightarrow U, V$ 必定洽有一個會包含鏡射
> 如果 $det(A) = 0$
> $\rightarrow U, V$ 可任選要是哪一種
- <font color = "red">所有矩陣都可以做 SVD 分解</font>

$U$: $m \times m$
$\Sigma$: $m \times n$
$V$: $n \times n$

$U$, $V$: orthogonal
$\Sigma$ 中的 singular value 從 $A^TA$ 來，非 $A$ 的 eigenvalue！
> singular value: $\quad$ $A^TA$ 的 eigenvalue 開根號取正，共 r 個非 0 項
>> r: $rank(A)$

:::success
SVD 步驟
1. 看 $A^TA$、$AA^T$ 哪個小，求 eigenvalue 算 $\Sigma$，取單位 eigenvector 得 $U$（$AA^T$） 或 $V$（$A^TA$）
> 接著分別算還沒算的 $U$ 或 $V$
2. 前 r 行利用 $A\vec v_i=\sigma \vec u_i$ 求出
3. 後面的行用 Gram-Schmidt 求出 $ker(A)$／$Lker(A)$ 的 orthonormal basis
> if 還沒算完的是 $U$ $\rightarrow$ 取 $Lker(A)$ 的 orthonormal basis
> if 還沒算完的是 $V$ $\rightarrow$ 取 $ker(A)$ 的 orthonormal basis
:::

- $U$ 的行： $AA^T$ 的單位 eigenvector
- $V$ 的行： $A^TA$ 的單位 eigenvector

> 

- $A$ 乘上 $V$ 的行，會等於對應的 $\sigma$ 乘上 $U$ 的行
> 
>> 幾何意義：
>> 假設 $A$ 是實矩陣，因為 $A \in R^{m\times n}$，$V \in R^{n\times n}$ 且 $U \in R^{m\times m}$
>> 則 $AV: R^n \rightarrow R^m$
>> $V \in R^{n\times n}$ 可寫成 n 個行向量，且因為 $V$ 是 orthogonal，所以這些行向量相互垂直，且非零向量，因此獨立，所以 $V$ 的行向量為 $A$ 的定義域的單位正交基底
>> 同理，$U$ 的行向量為 $A$ 的對應域的單位正交基底
>>
>> 所以，$AV$ 即是把它定義域的單位正交基底，轉換成對應域的單位正交基底乘上某個 scalar $\sigma$，再把多出來的基底向量送到 $\vec 0$


<font color = "red">$U$ 和 $V$ 的行即 $A$ 的四大空間的基底</font>
- $U$ 的前 $r$ 行 $\qquad \rightarrow$ $CS(A)$
- $U$ 的後 $m-r$ 行 $\rightarrow$ $Lker(A)$
- $V$ 的前 $r$ 行 $\qquad \rightarrow$ $RS(A)$
- $V$ 的後 $n-r$ 行 $\rightarrow$ $ker(A)$

> 102 交 6.
任何非零矩陣的實矩陣 $A$，$A^TA$ 的 SVD 分解可以和 eigenvalue decomposition 相同

#### Spectral Decomposition

條件：
- 佈於複數時要 normal
- 佈於實數時要 self-adjoint （symmetric）
> 因為 Spectral Decomposition 是可對角化的結果

> 根據此定理，如果 $A$ Hermitian on $V$，我們就必定能從 A 的 eigenvectors 中取到一組 $V$ 的 orthonormal basis
> - 需注意的是這個定理的前提：有限維、佈於複數
> 由此定理再去看 Spectral Thm 就更好理解了

> - $V$ 為所有相異 eigenvalue 產生的 eigenspace 的直和
> - 任意一個 eigenspace 的 perp 為「其他所有 eigenspace 的直和」
> - 把 $V$ 投影到每個 eigenspace 再相加會變成 identity
> - linear operator T 可拆成投影到各個 eigenspace 的分量再乘上 eigenvalue 的和
>> (e) 的式子即為 $T$ 的 Spectral Decomposition

> 用任何函數作用於 $A$ 等同用此函數作用於每個 eigenvalue

### $A^+$

$A^+$ 是 $A$ 的 pseudoinverse

如果有 $A$ 的 SVD 分解
$A = U\Sigma V^T$
則 <font color = "green">$A^+ = V\Sigma^+ U^T$</font>
> $\Sigma^+:$ $\Sigma$ 的轉置， singular value 取倒數

- 解 $A \vec x = \vec b$ 時，將 $A^+$ 乘 $\vec b$ 即可得長度最短的解
- $A$ ==行滿稚== $\rightarrow$ <font color = "red">$A^+=(A^TA)^{-1}A^T$</font>
- $A$ ==列滿稚== $\rightarrow$ <font color = "red">$A^+=A^T(AA^T)^{-1}$</font>

> $\vec x^+:$ minimum length solution
>> 因為行空間和左核空間是正交補空間，所以對所有 $A$ 的對應域中的 $\vec b$，我們都可以拆成
>> - 一個在行空間的部分（$\vec p$）
>> 加上
>> - 一個在 $Lker(A)$ 中的部分（$\vec e$）
>>
>> 當 $A$ 不可逆時，$ker(A)$ 非零空間，但是我們無法「還原」回原本在 $ker(A)$ 中的部分，$A^+$ 只能將 $\vec e$ 送回 $\vec 0$，但是 $A^+$ 可以把 $\vec p$ 還原回原本在列空間的部分，也就是 $\vec x^+$
>> 因此，$A^+ \vec b = A^+(\vec p + \vec e) = \vec x^+ + \vec 0 = \vec x^+$

### Rayleigh Quotient

先化成 $A=A^T$！

### Hessian


### minimal / least squares sol

> 更詳細的 [minimal / least squares sol 筆記](https://hackmd.io/@QOMsqOjySkenXlsfJXEJGg/Bk2TrjjPa)

所有的 $\vec x$ 都可以拆成一個++列空間的部分++（$\vec x_r$），和++一個 kernel 的部分++（$\vec x_n$）

==$\vec x = \vec x_r +\vec x_n$==

- 要注意的是，除了有無限多解時求最短的解的 minimal solution 會在列空間中，無解時用 normal equation 求誤差最小的解，即 <font color = "red">least squares solution，也會在列空間中</font>
> 因為 $A^TA\vec x = A^T\vec b$
> $\rightarrow$ $A^TA(\vec x_r +\vec x_n)= A^T\vec b$
> $\rightarrow$ $A^TA\vec x_r + A^TA\vec x_n = A^T\vec b$
> 因為 $x_n \in ker(A)$，所以 $A\vec x_n = \vec0$
> $\rightarrow$ $A^TA\vec x_r + \vec 0 = A^T\vec b$
> $\rightarrow$ $A^TA\vec x_r = A^T\vec b$

- 所有 $A^TA\vec x = A^T\vec b$ 的解 $\vec x_r$ 都相同，而且這個 $\vec x_r$ 也就是 $\vec x^+$
- 因為列空間跟 kerenl 垂直，所以所有列空間中的向量都會和所有 kernel 中的向量垂直，因此 $\vec x_r \perp \vec x_n$，又 $\vec x = \vec x_r +\vec x_n$
因此，根據畢氏定理：
$||\vec x||^2 = ||\vec x_r||^2 + ||\vec x_n||^2$

#### 例子(least squares)

題目給幾個點求 least squares error 和
> 106 交 10.

所求即下圖中的 $E$

解法：
> 先把所給的點帶入 least squares line，即題目中的 $b=C+Dt$
> 再寫成 $A\vec x = \vec b$ 的形式
> 
>
> 解出來會得 $\vec x = (1,9)^T$
> 也就是 $C=1$, $D=9$
>
> 解出 $\vec x$ 後如何求 $E$？
> 
> 此題的話即算 $||A\vec x -\vec b||^2$
> 理由如下：
> 
> 所以 算 $||A\vec x -\vec b||^2$ 其實等同一個一個點畫圖慢慢求的結果，只是我們將算所有的點的誤差這件事，大家放在一起算而已
> 無論是畫圖的算法還是帶入 $||A\vec x -\vec b||^2$，答案皆為 14

##### least squares sol 不唯一

當無解的時候，我們用 normal equation 求最佳近似解
$A^TA\vec x = A^T\vec b$
但是，當 $A$ 非行獨立時，$A^TA$ 不可逆，因此最佳近似解不唯一
如果題目進一步要求要長度最短的解

【法一】
$\rightarrow$ 直接用高中的方法求極值

【法二】
因為長度最短的解必在列空間中
normal equation 的解也可拆成 $\vec x = \vec x_r +\vec x_n$
因此，無限多個最佳近似解中，長度最短的解，也就是投影到列空間的解

$\vec x_r = \vec x - \vec x_n$

:::warning
解法：

$\rightarrow$ 求得無限多個 normal equation 的解以後，任取一個，再減掉這個解投影到 kernel 即為答案
:::

#### 例子（minimal sol）

> 103 台
$2x+y+z=4$
$4x+2y+2z=8$
$5x+y=19$
find the solution with minimum norm

> 因為 $[ \ A \ | \ b\ ]$ 的一二列相依，所以具無限多解