# Material
## Group Theory
### 前言
群論主要在探討對稱性，並且對於整數論、以及其它代數結構的理解有所幫助
這裡僅探討特定一些賽場上較實用且重要的觀念
有興趣的同學可以去修數學系的抽象代數，會有更詳細的介紹
- Definition
- 一個group G定義為一個帶有"良好運算"(這裡記做$*$)的集合:
- 運算封閉: $\forall a,b \in G: a*b\in G$
- 結合律(associative): $\forall a,b,c\in G: (a*b)*c=a*(b*c)$
- 存在單位元(identity): $\exists e\in G: \forall g\in G: e*g=g*e=g$
- 任一元素有反元素(inverse): $\forall g\in G:\exists g^{-1}\in G:g^{-1}g=gg^{-1}=e$
- 一個group G下的子群H是一個G的子集，同時也是群
- 若$H\subset G$，只要滿足兩個條件就代表$H$是個子群(記做$H\leq G$)
- $H$運算封閉
- $G$的單位元$e$和對應$h\in H$的反元$h^{-1}$都在$H$內
- Notation
- 一般來說群的運算符習慣寫$*$
- 這時候$a*b$通常縮寫成$ab$
- $a*a*a...*a$寫成$a^n$
- inverse寫成$a^{-1}$
- 有交換性的群稱作Abelian Group，有時候運算符號會寫成$+$
- $a+a+a...+a$寫成$na$
- inverse寫成$-a$
- 一點點觀察
- 顯然單位元和反元唯一
- 考慮$e_1, e_2$都是identity，那麼$e_1=e_1e_2=e_2$
- 考慮$a,b$都是$c$的inverse，那麼$a=acb=b$

### 生成群
- $G$稱做有限生成代表存在某個$G$的有限子集$S$使得
- 任何$g\in G$都可以表示成$g=g_1^{\pm1}g_2^{\pm1}...g_n^{\pm1}$，且所有的$g_i\in S$
- 其中$S$稱為$G$的生成集(generating set)，我們說$S$生成$G$
- 特別地，當$S= \{a\}$只有一個元素，我們稱$G$為循環群(Cyclic Group)，而$a$為$G$的生成元(generator)
- 考慮$S=\{a_1,a_2,...a_n\}$我們記<$a_1,a_2,...a_n$>為S所生成的群
- 我們說某個$g\in G$的order是他所生成的子群的order，記為$\|g\|=\|<g>\|$

### 乘法群
- $Z_n^\times$稱為模n的乘法群是把比n小且與n互質的數蒐集起來，運算定義成普通乘法後取模n
- 特別的當n是質數，所有1~n-1的整數都囊括其中
- $\|Z_n^\times\|=\phi(n)$,$\phi$是歐拉函數
- 如果$Z_n^\times$是cyclic的，我們稱它的生成元是原根
- 當且僅當n是$2,4,p^k,2p^k$, p是奇質數，$Z_n^\times$是cyclic的

### Coset
- 考慮$H\leq G$，對某個$g\in G$我們稱
$gH = \{gh:h\in H\}$為H在G中的左陪集 (left coset)
$Hg = \{hg:h\in H\}$為H在G中的右陪集 (right coset)
- 當對所有$g\in G$都能保證H的左右陪集相等的時候，我們稱H是個正規子群(normal subgroup)
- 等價敘述：
- $\forall g\in G: gH=Hg$
- $\forall g\in G, h\in H: ghg^{-1}\in H$
- 此時我們記為：$H\triangleleft G$
- Notation
- $G/H$記為所有$H$的left coset所構成的集合$\{gH:g\in G\}$
- $G\backslash H$記為所有$H$的right coset所構成的集合$\{Hg:g\in G\}$
- 特別的，當H是正規子群，那麼$G/H = G\backslash H$構成一個自然的群
- 運算定義為$g_1H * g_2H = g_1g_2H$
- 我們稱之為一個quotient group (商群)
- 若H不是正規子群，這樣的運算不是well defined的
- 若G是abelian，那麼H必為正規子群
- **陪集所構成的集合定義了一個等價類**
- $g_1H, g_2H$若不相等則不交
- 這個性質很直接地導致Lagrange Theorem

### Lagrange Theorem
- 任何有限群$G$的order $\|G\|$必定被它的子群$H$的order $\|H\|$整除
- i.e. if $H\leq G$ are finite groups, then $\|H\|$ divides $\|G\|$
- 歐拉定理
- $\forall a\in Z_n^\times: a^{\phi(n)}=1$
- 因為根據Lagrange Theorem，$\|a\|$會整除$\phi(n)$
- 費馬小定理
- $\forall a\in Z_p^\times: a^{p-1}=1$
- 顯然費馬小定理只是歐拉定理n為質數的一個特例

### 態射(morphism)
- Definition
- homomorphism(同態映射)是兩個群$G_1, G_2$之間的映射$h:G_1→G_2$
- 其中，運算特性被保持：$\forall a,b\in G_1:h(a)h(b)=h(ab)$
- isomorphism(同構映射)是兩個群之間的homomorphism，並且它是bijection
- morphism的概念可以擴充到更多運算的代數結構，但都指涉這類映射會保持運算特性
- 兩個群之間若存在一個同構映射，我們稱它們是同構的，其結構可以視為相同
- 若考慮同態映射$h:G_1→G_2$我們稱$G_2$單位元$e_2$的pre-image $h^{-1}[e_2]=\{g\in G_1:h(g)=e_2\}$為$h$的Kernel，記為$Ker(h)$
- 特別地，kernel必為一個正規子群
- 顯然$\{e\}\subset Ker(h)$，若$Ker(h)=\{e\}$只含有一個單位元，我們稱做trivial
- 此外，Kernel對單一元素的pre-image給出了簡單的形式
- 容易證明如果$h(g_1) = g_2$ 那麼 $h^{-1}[g_2]=g_1Ker(h)$
- 因此kernel是trivial當且僅當$h$是injective
- 反過來說，任何一個正規子群$N\triangleleft G$都規範了一個自然的homomorphism
- $h:G→G/N$ where $g\mapsto gN$
- 其中$Ker(h) = N$
- 我們有時稱做Canonical Homomorphism

### 群作用(這裡要搭配圖解)
- 群通常是代表一種**對稱性**
- Definition
- 映射$g$是$X$上的一個排列(permutation)代表: $g:X→X$是一個bijection
- permutation之間有個自然的運算，複合(Composite)
- 一個作用在X上的群G，等同於一些permutation的蒐集所構成的群(我們稱G作用在X上)
- 把所有X上的排列蒐集起來構成的群，稱作X上的對稱群$Sym(X)$
- 定義G和X之間的運算$gx=g(x)$
- 例子
- $S_n$: 把$Z_n$上所有的排列蒐集起來的對稱群
- $D_4$: 一個正方形四個角點上的保距映射蒐集起來的群(空間對稱群)
- Cayley Theorem
- 任何一個群$G$同構於它的對稱群的某個子群$H\leq Sym(G)$
- 圖論觀點
- 一個X上的permutation可以視為以X為點集的一張有向圖，每個點入度出度為1，故這張圖是由許多環所構成
- 所有permutation都可以拆解為若干個不交輪換的複合
- 因此考慮X是一個G-set (G作用在X上)那麼G可以看成以X為點集的一張有向圖，這張圖每條邊都有個標籤用以標記這條邊是哪一個permutation，同個標籤的子圖由許多環所構成

### Orbit-Stablizer Theorem
$\|Gx\|\cdot\|G_x\| = \|G\|$ or to say $\|Gx\|=\|G/G_x\|$
where
$Gx:=\{gx: g\in G\}$是x所能到達的其他點的蒐集，稱作Orbit，也記做$Orb(x)$
$G_x:=\{g\in G: gx=x\}$是能夠固定x的映射的子群，稱作Stablizer，也記做$Stab(x)$
- 一個作用在X上的對稱性G可以分成兩部分，先固定$x$對其它點進行映射，然後再把$x$映射到指定點上: if $g_1x=g_2x$ then $\exists g_3\in Stab(x): g_2g_3=g_1$
- 注意，Orbit定義了一個自然的等價類，$x_1\in Orb(x_2)$ iff $x_1\sim x_2$

### Burnside's Lemma
for finite $G$ acts on finite $X$
$\|X/G\|\cdot\|G\|=\sum_{g\in G}\|X_g\|$
where
$X/G:=\{Gx:x\in X\}$ 是所有orbit所構成的集合
$X_g:=\{x\in X:gx=x\}$ 是所有能被g所固定點的蒐集
- Orbit的數量為每個對稱性所固定的點個數的平均

### Polya Enumeration Theorem
- 對於群$G$作用在有限集$X$和其上的塗色情形集$C$，其中有$k$種顏色
- 群$G$作用在$C$的情形由作用在$X$的情況自然得出
- 定義等價的塗色方法$c_1, c_2$滿足$\exists g\in G: gc_1=c_2$
- 那我們有所有不等價的塗色方法數$\frac{1}{\|G\|}\sum_{g\in G}k^{c(g)}$
- 其中$c(g) = \|\{<g>x:x\in X\}\|$是$g$不交輪換拆解的輪換個數

## Ring&Field (補充素材，有興趣再討論)
- Definition:
- Ring是帶有兩個運算$(*,+)$的集合
- 兩個運算都是封閉的
- 運算$+$構成abelian group
- 運算$*$有結合律
- 乘法對加法的分配律
- $a*(b+c)=a*b+a*c$
- $(b+c)*a=b*a+c*a$
- Integral Domain(整環)是有更好性質的交換環
- 不存在zero factor：$ab=0→a=0\lor b=0$
- 乘法有單位元：$\forall a\in R: ea=ae=a$
- Field是比Integral Domain更強性質的Ring
- 扣除0(加法單位元)後，對乘法構成abelian group
- 例如：有理數, 實數, 複數, $Z_p$

- Galois Field
- 任何Finite Field的order都是某個prime power，記為$GF(p^k)$
- 其中，當$k=1$, $GF(p)$同構於$Z_p$
- $GF(p^k)$同構於$Z_p[x]/u(x)$, 代表以$Z_p$為係數的多項式除掉$u(x)$的餘式所構成的集合，其中$u(x)$是degree k的不可約多項式

## Linear Algebra
線性代數核心在探討線性映射以及其性質，對於我們理解傅立葉轉換、矩陣算法有一定的幫助，此地我們假設大家都已熟悉中學水準的矩陣記法與基本性質，暫不贅述
### Linear Space
- $R^n$向量的推廣
- Definition
- 給定一個Field F(做為純量),其上的線性空間V是一個帶有加法與係數積$(+,\cdot)$的集合：
- 兩個運算都是封閉的
- 加法之上構成一個交換群
- 純量積的"良好"性質
- $\forall a,b\in F, v\in V: (ab)v=a(bv)$ (Compatiblity)
- $1\cdot v = v$ (scalar identity)
- $\forall a\in F, u,v\in V: a(u+v)=au+av$ (Distributive)
- $\forall a,b\in F, v\in V: (a+b)v=av+bv$ (Distributive)
- 簡而言之，V是一個F-module (如果你聽過這個詞的話)
- 以下若無特別說明，皆假設F是complex或real
- 另外我們規定一個子空間是一個線性空間的子集，並且它也是個線性空間
### Product Space
- 定義了內積的向量空間
- Definition
- 給定F上的線性空間V，內積空間額外規範了一個內積運算$*:V\times V→F$
- 共軛對稱 $u*v=\overline{v*u}$
- 半雙線性 $\forall a,b\in F:(au_1+bu_2)*v=a(u_1*v)+b(u_2*v)$
- 正定性 $u*u\geq 0$ 且 $u*u=0$ iff $u=0$
- 兩個向量內積為0則稱之正交(Orthogonal)
### Norm Space
- 定義了長度的向量空間
- Definition
- 給定F上的線性空間V，內積空間額外規範了一種長度(norm)
- $\|av\| = |a|\cdot\|v\|$
- 三角不等式 $\|u+v\|\leq \|u\|+\|v\|$
- 正定 $\|v\|\geq 0$ 且 $\|v\|=0$ iff $v=0$
- 內積定義了一個很自然的norm: $\|v\|:=\sqrt{v*v}$

### 基底
- 一些向量$\{v_1,v_2...,v_n\}$的線性組合即每個向量若干倍係數積之和：
- $a_1v_1+a_2v_2...a_nv_n$
- 在定義散歛性的情況也可以把這個定義擴充到無窮級數
- 一些向量的線性組合的蒐集稱之為這些向量的展成(Span)：
- $Span\{v_1,v_2,...v_n\}=\{a_1v_1+a_2v_2...a_nv_n: a_i\in F\}$
- 線性組合$a_1v_1+a_2v_2...a_nv_n=0$的係數組合如果只出現在$a_i$全零(平凡解)那麼我們說$\{v_1,v_2...,v_n\}$是線性獨立的，否則他們是線性相依的
- 如果線性空間V的一組基底(Basis)是一向量集S=$\{v_1,v_2...,v_n\}$滿足
- $Span(S)=V$
- $S$線性獨立
- 如果空間中有兩組有限基底，那麼這兩組基底大小相同，我們稱它是線性空間的維度(dimension)
- 用詞上，若B為正交，我們稱之正交基底(Orthogonal Basis)，若B為正交且單範(長度是1)，我們稱之標準正交基底(Orthonormal Basis)
### Gram Schmidt 正交化
- 考慮在內積空間下有一組有限基底$B = \{b_1,b_2,b_3,...,b_n\}$
- Gram Schmidt給出了一套方法獲得$Span(B)$上的一組正交基底
- 考慮我們已經取得了$S_k = Span\{b_1,b_2,...,b_{k-1}\}$底下的正交基底
- 我們接著能夠取$b_k$
- $b_k = u_k+v_k$, $u_k\in S_k$, $v_k\in S_k^\perp$
- 其中$u_k = \sum_{i=1}^{k-1}\frac{b_k\cdot v_i}{v_i\cdot v_i}v_i$
- $v_k$就是我們下一個正交基底裡頭向量
- 最後會得到$\{v_1,v_2,...,v_n\}$就是我們的正交基底
### 線性轉換(Linear Transform)
- 給定兩個線性空間$V_1, V_2$之間的線性變換$L:V_1→V_2$滿足
- $L(av_1+bv_2)=aL(v_1)+bL(v_2)$
- 類似地，$V_2$中0向量的pre-image我們稱做Kernel
- $Ker(L) = \{v\in V_1:L(v)=0\}$
- 線性轉換也是一個加法上的homomorphism，這兩個涵義所指涉的Kernel是同一個集合
- 考慮$V_1$是有限維度的，那麼一個線性映射值域的維度必然不超過定義域的維度
- 我們稱$\dim L(V_1)$是這個轉換的秩(rank)，記做$Rank(L)$
- $\dim V_1 = Rank(L) + \dim Ker(L)$

- 我們稱兩個線性空間是同構的當且僅當它們之間有一個bijective的線性轉換
- 這代表這兩個空間的結構是相同的，我們可以藉由研究其中一個了解另一個的性質
- 並且，兩個有限維且維度相等的線性空間是同構的
### 矩陣意義下的線性轉換
承接上面，考慮$L:V_1→V_2$是一個線性轉換
- 有限維度空間之間的轉換可以寫成矩陣
- 給定$B_1=\{b_1,b_2,...,b_n\}, B_2=\{b'_1,b'_2,...,b'_m\}$分別為$V_1,V_2$空間的有限基底
- 那麼任何$u\in V_1, v\in V_2$可以寫成
- $u = u_1b_1+u_2b_2+...u_kb_n$
- $v = v_1b'_1+v_2b'_2+...v_kb'_m$
- 抽出係數構成矩陣我們得到
- $u' = \begin{pmatrix}u_1 & u_2 & ... & u_n \end{pmatrix}^T$
- $v' = \begin{pmatrix}v_1 & v_2 & ... & v_m \end{pmatrix}^T$
- 任何的線性轉換可以表達成係數矩陣上的矩陣乘法
- $v' = A_{m\times n}u'$
- 矩陣A可以透過若干個資料點求解還原
- 我們也可以掌握基底之間的係數關係藉以還原矩陣A
- 考慮$b_i\mapsto_L \sum_{j=1}^m a^i_j\cdot b'_j$
- 那麼 $A = (a^i_j)_{m\times n}$
- 上標代表row index，下標代表col index
- 考慮矩陣$A$存在的前題下
- 我們特稱$Ker(A)=Null(A)=\{v:Av=0\}$為$A$的Null Space
- 此外$Null(A^T)$我們稱做$A$的Left Null Space，根據作者習慣語意不同，null space可能指涉不同的意思，但要注意這兩個null space並不保證是相同的
- Null space的維度我們稱做nullity
- 將矩陣$A$的行向量$C=\{c_1,c_2,...,c_n\}$蒐集起來
- 我們稱$Span(C)=Col(A)$為A的column space
- 同理，矩陣$A$的列向量$R=\{r_1,r_2,...,r_m\}$蒐集起來
- 我們稱$Span(R)=Row(A)$為A的row space
- 矩陣$A$的行空間與列空間是相同維度的，正好等於$A$的rank
- $Rank(A)=\dim R(A)=\dim C(A)$
- 要確認行空間或列空間的維度只要透過Gaussian Elimination即可達成
- 前面所述的維度關係在矩陣上我們特稱Rank-Nullity Theorem
- $n = Rank(A_{m\times n}) + \dim Null(A)$
### 特徵(Eigen)
- 考慮線性變換$L:V→V$，它的特徵向量$v\in V$與特徵值$\lambda\in F$ 滿足
- $v\mapsto_L \lambda\cdot v$
- $v\neq 0$
- 特徵向量可以理解為經過映射後方向不變的非零向量
- 蒐集相同特徵值$\lambda$的所有特徵向量與零向量，會構成一個子空間$S$
- 我們稱做特徵子空間
- 這個子空間的image包含於自己：$L(S)\subset S$
- 因此它是一個不變子空間(上面是不變子空間的定義)
- 不變子空間底下$L:S→S$也構成一個縮減的線性映射
- 特徵子空間的維度我們稱做對應特徵值的幾何重數
- 特別地，$Ker(L)$也是一個特徵值為0的特徵子空間
- 考慮方陣$A_{n\times n}$
- 它的所有特徵值就是$\det(A-\lambda\cdot I)$的根
- 從根與係數的關係可以發現特徵值之和即是方陣對角線之和(若有重根則直接累加)
- 我們特稱為$A$的跡(trace)，記為$tr(A)$
- 對應某個特徵值的重根個數則稱作該特徵值的代數重數
- 找出特徵值$\lambda$後，透過高斯消去法找出$Null(A-\lambda\cdot I)$即是對應特徵值的特徵子空間
### Normal Matrix(正規陣)
- 一個正規陣(Normal Matrix)$N$代表
- $N^*N = NN^*$
- 一個酉陣(Uniary Matrix) $U$代表它的共軛轉置$U^*$構成他的反陣
- $UU^*=U^*U=I$
- 一個厄米矩陣(Hermitian Matrix)$A$是一個共軛對稱的方陣
- $A^*=A$
- 顯然，酉陣與厄米陣都是正規的
- 相似性
- 方陣$A, B$是相似的代表
- 存在某個可逆陣$M$, $A = M^{-1} B M$
- 我們稱兩個相似方陣是酉相似(unitarily similar)如果對應的矩陣$M$是個酉陣
- 一般來說，我們稱實參數的酉陣為正交陣，隨文意和作者習慣不同，正交陣可能指涉為酉陣
- 酉陣可以理解為行向量們(或列向量們)單範正交的方陣
### 譜分解(Spectral Decomposition)
- 考慮一個方陣$A_{n\times n}$，假設恰好有n個線性獨立的特徵值(幾何重數為n)
- $v_i \mapsto\lambda_iv_i$
- 那麼將它蒐集起來可以得到
- $\begin{pmatrix}v_1 & v_2 & ... & v_n \end{pmatrix}\mapsto
\begin{pmatrix}\lambda_1v_1 & \lambda_2v_2 & ... & \lambda_nv_n \end{pmatrix}$
- 令$V = \begin{pmatrix}v_1 & v_2 & ... & v_n \end{pmatrix}$
- $AV = V\Sigma$
- 其中$\Sigma =\
\begin{pmatrix}\lambda_1 & 0 & ... & 0 \\
0 & \lambda_2 & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & \lambda_n\\
\end{pmatrix}$
- 因此有$A = V\Sigma V^{-1}$
- 我們稱之$A$的特徵分解，或譜分解(Spectral Decomposition)
- 求出譜分解的過程，我們稱之對角化(Diagonalization)
- 如果$V$是一個酉陣，那麼我們稱之酉對角化
- 從譜分解可以看出$\det A = \det\Sigma = \prod_{i=1}^n\lambda_i$
- 另外，譜分解給出一個方陣冪的良好形式
- $A^k=V\Sigma^kV^{-1}$
- 其中$\Sigma^k =\
\begin{pmatrix}\lambda_1^k & 0 & ... & 0 \\
0 & \lambda_2^k & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & \lambda_n^k\\
\end{pmatrix}$

### Schur Decomposition
- 任何一個方陣$A$酉相似於一個上三角陣$T$
- $A = U^*TU$，其中$U$是酉陣
- 考慮方陣$A_{n\times n}$
- 考慮某個特徵值的特徵子空間$V_\lambda$與補空間$V_\lambda^\perp$
- 令$B_1, B_2$為個別的標準基底
- 對於$v\in V_\lambda^\perp$
- $Av = v_1+v_2, v_1\in V_\lambda, v_2\in V_\lambda^\perp$
- 定義映射$L:V/V_\lambda→V/V_\lambda$, where $v+V_\lambda\mapsto Av+V_\lambda$
- 容易證明$V/V_\lambda$構成一個線性空間而$L$構成一個線性映射
- 可以遞迴地考慮這個映射的某個特徵子空間與補空間
- 因此$A \begin{pmatrix}B_1 & B_2 \end{pmatrix} = \begin{pmatrix}B_1 & B_2 \end{pmatrix} \begin{pmatrix}\lambda\cdot I & M_1 \\ 0 & M_2 \end{pmatrix}$
- 由遞迴條件可以知道，$M_2$也可以是一個上三角陣，由此得到Schur分解
- 另外可以看出三角陣$T$的對角線即為$A$的特徵值
### Spectural Theorem(譜定理)
- 任何一個方陣$N$是正規的當且僅當可以酉對角化
- $N = U^*\Lambda U$
- 其中$U$是酉陣，$\Lambda$是對角陣
- 考慮正規陣$N$的Schur分解
- $A = U^*\Lambda U$，其中$U$是酉陣，$T$是上三角陣
- 那麼$U^*T^*TU=A^*A=AA^* = U^*TT^*U$
- 因此有$T^*T=TT^*$，$T$為對角陣
- 若能酉對角化，則方陣顯然正規
### 消滅多項式
- 消滅多項式
- 一個方陣$A$的消滅多項式$p(x)$是以此方陣為零點的多項式
- $p(A) = 0$
- Cayley Hamilton Theorem
- 任何方陣$A$的特徵方程$p(\lambda) = \det(A-\lambda\cdot I)$是$A$的消滅多項式
- 考慮Schur分解$A = Q^*TQ$
- 那麼$p(A) = p(Q^*TQ) = Q^*p(T)Q$
- 又$p(T) = c\cdot(T-\lambda_1\cdot I)\cdot(T-\lambda_2\cdot I)...\cdot(T-\lambda_n\cdot I)$
- 其中$T-\lambda_i\cdot I$是一個上三角陣，且第i個對角元是0
- 不難證明$p(T)=0$因此$p(A)=0$
- 最小多項式
- 方陣$A$的最小多項式被定義為degree最小，領導係數為1的消滅多項式
- 可以證明這樣的多項式是唯一的
- 任何消滅多項式都可以被最小多項式除盡
- 因此最小多項式必為特徵多項式的因式
### Jordan Canonical Form
- 任何一個複參數方陣$A_{n\times n}$相似於一個分塊對角陣$J$
- $A = M J M^{-1}$
- $J = \begin{pmatrix}J_1 & 0 & ... & 0 \\
0 & J_2 & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & J_k\\
\end{pmatrix}$ 是一個分塊對角陣
- 其中 $J_i = \begin{pmatrix}\lambda_i & 1 & 0 & ... & 0 \\
0 & \lambda_i & 1 & ... & 0 \\
0 & 0 & \lambda_i & ... & 0\\
... & ... & ... & ... & ...\\
0 & 0 & 0 & ... & \lambda_i\\
\end{pmatrix}$
- 其中$\lambda_i$是方陣$A$的特徵值
- 容易證明每個Jordan分塊都只有一個特徵向量
- 因為每個分塊可以寫成$J_i = \lambda_i\cdot I+N$
- $N$是冪零陣(Nilpotent Matrix)，對角線上一格皆為1其他為0
- 某個特徵值的幾何重數由對應特徵值的Jordan分塊塊數所決定，而代數重數則由對角線出現次數所決定
- 因此任何特徵值的幾何重數不大於代數重數
- 解方陣$A_{n\times n}$的Jordan Form
- 考慮特徵多項式$det(A-\lambda\cdot I) = c\cdot(\lambda-\lambda_1)^{e_1}\cdot(\lambda-\lambda_2)^{e_2}...(\lambda-\lambda_k)^{e_k}$
- 假設對於特徵值$\lambda_i$有某個特徵向量$v$
- 令$M_k = Null(A-\lambda_i)^k$
- 考慮最小多項式$m(\lambda)=(\lambda-\lambda_1)^{m_1}\cdot(\lambda-\lambda_2)^{m_2}...(\lambda-\lambda_k)^{m_k}$
- 找出一個$v_{r}\in M_{r}$但$v\not\in M_{r-1}, r\leq m_i$
- 令$v_j=(A-\lambda_i I)v_{j+1}$ for $j<m_i$
- 並且滿足$v_1=v$
- 那麼$v_j\in M_j, v_j\not\in M_{j-1}$
- 於是有$A \begin{pmatrix}v_1 & v_2 & ... & v_r\end{pmatrix}
= \begin{pmatrix}v_1 & v_2 & ... & v_r\end{pmatrix} \begin{pmatrix}\lambda_i & 1 & 0 & ... & 0 \\
0 & \lambda_i & 1 & ... & 0 \\
0 & 0 & \lambda_i & ... & 0\\
... & ... & ... & ... & ...\\
0 & 0 & 0 & ... & \lambda_i\\
\end{pmatrix}$
- 考慮每一個特徵值所產生的向量最後會有如下形式$AV = VJ$, 其中$V$可逆
- 即有$A = VJV^{-1}$
### 矩陣冪、矩陣指數
- 考慮方陣$A_{n\times n}$
- 定義方陣指數
- $e^A = \sum_{k\geq0}\frac{A^k}{k!}$
- 若可以對角化
- $A = V^{-1}\Sigma V$
- 則如前所述，方陣冪可以有良好形式$A^k = V^{-1}\Sigma^k V$
- 方陣指數亦有良好形式
- $e^A = V^{-1}e^\Sigma V$
- 其中$e^A =
\begin{pmatrix}e^{\lambda_1} & 0 & ... & 0 \\
0 & e^{\lambda_2} & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & e^{\lambda_n}\\
\end{pmatrix}$
- 若不能對角化
- 考慮Jordan Form $A = MJM^{-1}$
- 類似地，$A^m = M J^m M^{-1}$
- 其中$J^m = \begin{pmatrix}J_1^m & 0 & ... & 0 \\
0 & J_2^m & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & J_k^m\\
\end{pmatrix}$
- 又$J_i = \lambda_i\cdot I + N$
- $J_i^m = \sum_{j=0}^m C(m,j)\lambda_i^{m-j}N^j$
- 而對於$N_{r\times r}$ 有 $N^r=0$故級數只有有限項
- 類似地，方陣指數：$e^A = Me^JM^{-1}$
- 其中$e^J = \begin{pmatrix}e^{J_1} & 0 & ... & 0 \\
0 & e^{J_2} & ... & 0 \\
... & ... & ... & ...\\
0 & 0 & ... & e^{J_k}\\
\end{pmatrix}$
- $e^{J_i} = e^{\lambda_i\cdot I + N} = e^{\lambda_i}e^N$
- 其中，利用泰勒泰勒級數展開$e^N$只有有限項
### 常係數線性差分方程
- 考慮如下形式的方程
- $\sum_{i=0}^kc_i\cdot A[n-i] = B[n]$
- 其中$c_i, B[n],A[0..k-1]$已知，我們想要求解$A[n]$的通式或任意項
- 首先考慮線性映射$S:C^{\aleph_0}\rightarrow C^{\aleph_0}$
- $A[n]\mapsto_S A[n-1]$
- 我們知道$\lambda^n$是一個特徵向量，特徵值為$\lambda^{-1}$
- 定義線性映射$L$
- $A[n]\mapsto_L \sum_{i=0}^kc_i\cdot S^i\{A[n]\}$
- 考慮$S$的特徵向量$v\mapsto_S \lambda v$
- 那麼$v$也是$L$的一個特徵向量，特徵值為
- $\sum_{i=0}^kc_i\cdot \lambda^{-i}$
- 我們可以改寫方程如下
- $L\{A[n]\} = B[n]$
- 由於$L$構成加法群的homomorphism，所以解空間是如下形式
- $v+Ker(L)$
- 其中$Lv = B[n]$
- v稱為方程的特解，一般需要各種不同技巧求解之，此地暫時不贅述
- 今考慮$B[n] = 0$
- 則解空間為$Ker(L)$
- 也就是我們要找出特徵值為0的特徵子空間
- 先求解特徵值為0的形式
- 考慮$\lambda^n$有特徵值$\sum_{i=0}^kc_i\cdot \lambda^{-i}$
- 令特徵值為0，我們得到下式，稱之特徵方程
- $\sum_{i=0}^kc_i\cdot \lambda^{k-i}=0$
- 解出特徵值後，再還原得到特徵向量，經由線性組合即可得到通式
- 我們也可以寫成矩陣形式
- $\begin{pmatrix}
A[n]\\A[n-1]\\...\\A[n-k+1]
\end{pmatrix} = \begin{pmatrix}
-c_1&-c_2&...&-c_{n-k}\\&&&0\\&I&&...\\&&&0
\end{pmatrix} \begin{pmatrix}
A[n-1]\\A[n-2]\\...\\A[n-k]
\end{pmatrix}$
- 此問題演變成一個方陣冪的問題
- 利用快速冪在$k^3\log n$內求出指定項
- 抑或是對此矩陣求譜分解或Jordan Form
- 此外利用消滅多項式，如Cayley Hamilton定理所給出的特徵多項式
- 解出$f(x) = x^n \mod p(x)$
- 其中$p(x) = \det(A-x\cdot I)$
- $f(A) = A^n$
- 此法可以在$k^2 \log n$求出指定項
- 搭配下面講到的快速傅立葉轉換能夠在$k \log k \log n$解出指定項
### 正定性(Positive Definite)
- 一個方陣$A_{n\times n}$是正定的當且僅當
- 對於所有$v\neq 0$都有$v^*Av>0$
- 若僅有$v^*Av\geq 0$則稱之半正定
- 一個正定陣的定義有許多種等價的定義，我們從這個定義出發
- 正定陣等價於如下形式的方陣$A = B^*B$ 其中$B$可逆
- 對於此形式的方陣
- $x^*Ax = x^*B^*Bx = \|Bx\|$
- 又因為$B$可逆，對於所有$x\neq 0$有$Bx\neq 0$
- 因此有$\|Bx\|>0$
- 對於正定陣$A$
- 考慮酉對角化$A = U^*\Lambda U$
- 其中$\Lambda$主對角元均大於零
- 令$B = U^*\Lambda^{\frac{1}{2}}U$
- 顯然我們有$A = B^*B$
- 並且$B$顯然可逆
- 類似地，半正定陣等價於$A = B^*B$形式的方陣
- 正定陣等價於所有特徵值為正實數的厄米陣(Hermitian Matrix)
- 考慮正定陣$A_{n\times n}$
- 考慮任何特徵向量$v$有$Av=\lambda v$
- 那麼$v^*Av=\lambda v^*v$
- 因此有$\lambda >0$
- 並且這樣的方陣必定是個厄米陣
- 首先考慮$(x+y)^*A(x+y)= (x^*Ax+y^*Ay)+(x^*Ay+y^*Ax)$
- 因為$(x^*Ax+y^*Ay)\in R$所以$f(x,y)=(x^*Ay+y^*Ax)\in R$
- 考慮$f(e_j,e_k) = a_{jk}+a_{kj}\in R$
- 因此$Im\{a_{jk}\}=-Im\{a_{kj}\}$
- 以及$f(e_j,i\cdot e_k)=i\cdot (a_{jk}-a_{kj})\in R$
- 因此$Re\{a_{jk}\}=Re\{a_{kj}\}$
- 由於$j, k$選取可以任意，故$A^*=A$
- 考慮特徵值均大於零的酉陣$B_{n\times n}$
- 根據譜定理，考慮酉對角化$B=U^*\Lambda U$
- 由於$\Lambda$是對角陣，且特徵值皆為正實數
- 令$\lambda_i = \Lambda_{i,i}$
- 由假設可知$\lambda_i >0$
- 於是對於任意$x\in F^n$
- $x^* Bx = (Ux)^*\Lambda(Ux) = y^*\Lambda y = \sum_{i=1}^n\lambda_i \bar{y_i}y_i>0$
- 類似地，半正定陣等價於所有特徵值為非負實數的厄米陣
- 從這個正定陣的定義可以看出，正定陣規範了一個自然的內積
- $x\cdot y = x^*Ay$
- 這個內積底下的正交性我們特稱共軛(Conjugate)
- 高斯消元時，正定陣的pivot皆正
- 這代表不需要列交換就可以完成高斯消元
- 因此紀錄高斯消元的步驟可以得到方陣$A$的拆解
- $A = LU$其中$L$是下三角陣，$U$是上三角陣
- 我們稱作LU分解
- 將兩個三角陣的對角元normalize可以得到一個LDU分解
- $A=LDU$, $L,U$是兩個三角陣，$D$是對角陣
- 因為消元pivot都是正的所以D的主對角軸每一項都是正的
- 在LU主對角軸被normalize成1的意義下LDU的D如果對角項無零元那麼分解是唯一的
### Cholesky Decomposition
- 任何一個正定陣$A_{n\times n}$存在拆解 $A = L L^*$
- 其中$L$是下三角陣
- 我們稱之Cholesky分解
- 首先考慮LDU拆解$A = LDU$
- 根據正定性，$A$是個厄米陣$A^*=A$
- 所以有$A = U^*DL^*$
- 這也構成了一個LDU分解，因為$U^*, L^*$分別符合兩個三角陣的形式
- 因為LDU分解是唯一的，所以$U^*=L, L^*=U$
- 我們因此有$A = LDL^*$
- 因為$D$對角元皆正所以可以拆解出方根
- $D = D^{\frac{1}{2}}D^{\frac{1}{2}}$
- 所以有$A = (LD^{\frac{1}{2}})(LD^{\frac{1}{2}})^*$
- 其中$LD^{\frac{1}{2}}$構成一個下三角陣
- 由此得到$A$的Cholesky分解
- 解稀疏線性系統
- 考慮$Ax = b$, $A$正定
- 那麼先求$Cholesky$分解$A = LL^*$
- 考慮$a_{ij} = \sum_{k=1}^{\min(i,j)} l_{ik}l_{jk}$
- 對於$i=j$, $a_{ii} = \sum_{k=1}^{i} l_{ik}^2$
- 因此有$l_{ii} = \sqrt{a_{ii}-\sum_{k=1}^{i-1} l_{ik}^2}$
- 對於$i>j,$ $a_{ij} = \sum_{k=1}^{j} l_{ik}l_{jk}$
- 因此有$l_{ij}=\frac{1}{l_{jj}}\cdot (a_{ij}-\sum_{k=1}^{j-1} l_{ik}l_{jk})$
- 如果有稀疏性，可以在$O(n\cdot e)$內解完
- 其中$e$是方陣的非零項數
- 然後利用回帶法解出答案$LL^* x = b$
- 總複雜度$O(n^2+ne)$

### Conjugate Gradient Method
- 同樣考慮稀疏線性系統$A_{n\times n}x = b$
- 複雜度 $m\cdot(n+e)$
- m是迭代次數，到m=n時保證收斂
- e是矩陣非零項數
- 不同於Cholesky的是，共軛梯度法是一個迭代算法，不一定要全部算完，每次迭代後數值會逐步收斂
- 概念上，找出一組$A$所定義的內積的共軛基底(利用Gram Schmidt)，然後每次迭代找出一個基底向量的係數
- 詳細過程與證明有點複雜，因此我先寫在紙上再貼上來，有興趣的同學歡迎找我討論
### Polynomial Interpolation
- 給定資料點$x_i\mapsto_f y_i$ for $1\leq i\leq N$
- 那麼存在唯一一個degree不超過N-1的多項式通過這些點
- Lagrange Interpolation給出一個簡單的形式
- $p(x) = \sum_{i=1}^N(y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j})$
- 另外我們定義均差(Divided Difference)
- $f[x] = f(x)$
- $f[a_1,a_2,...,a_k] = \frac{f[a_1,a_2,...,a_{k-1}]-f[a_2,a_3,...a_k]}{a_1-a_k}$
- 可以利用建表DP算出均差的表
- 建立在均差之上，Newton Interpolation給出一個簡單的形式
- $f(x) = \sum_{i=1}^{N} f[x_1,x_2,...,x_i](x-x_1)(x-x_2)...(x-x_{i-1})$
### Polynomial Modular
- 給定多項式$f,g$, $\deg f\geq \deg g$
- 我們有$f(x)=q(x)g(x)+r(x)$, $\deg q\leq\deg f-\deg g$
- 定意多項式反轉$p^R(x) = x^{\deg p}f(\frac{1}{x})$
- 我們有$f^R(x)=(q(x)g(x)+r(x))^R = q^R(x)g^R(x)+x^{\deg f-\deg g +1}r^R(x)$
- $f^R(x)=q^R(x)g^R(x) \mod x^{\deg f-\deg g+1}$
- 因此$q^R(x)=f^R(x)g^{-R}(x)\mod x^{\deg f-\deg g+1}$
- 這代表經過項的反轉後，多項式取模問題演變成一個多項式求逆問題
### Polynomial Inverse
- 對於$f(x)g(x)=1\mod x^n$與$f(x)h(x)=1\mod x^m, m=\lceil\frac{n}{2}\rceil$
- $g(x)-h(x)=0\mod x^m$
- $(g-h)^2=g^2-2gh+h^2=0\mod x^n$
- $g=2h-fh^2=h(2-fh)\mod x^n$
- 因此多項式求逆問題可以由多項式乘法遞迴求出

## 傅立葉(離散系列)
### 離散時間傅立葉級數(Discrete Time Fourier Series)
- 考慮以整區間$Z_n$為循環節的離散複值週期函數空間$S$
- 定義內積運算為$<f,g>=\frac{1}{N}\sum_{n=0}^{N-1}{f[n]\overline{g[n]}}$
- 集合$B=\{e^{j\Omega_0kn}:k\in Z_N\}, \Omega_0=\frac{2\pi}{N}$顯然構成一組正交基底，並且為了方便，這個內積運算前面所帶有的1/N常數保證B是單範的
### 離散傅立葉轉換(Discrete Fourier Transform)
- 離散時間離散頻率(建立在DTFS上)
- 特別注意用詞上，離散傅立葉轉換(DFT)和離散時間傅立葉轉換(DTFT)指涉不同的意思，後者是離散時間連續頻率的轉換
- 另外，根據時間、頻率的離散、連續性，這類轉換有四種版本，此地只介紹其中一種
- 集合B是一個基底，代表空間內任意函數都可表示為它的線性組合
- $\forall f\in S,\exists f'\in S: f=\sum_{n=0}^{N-1}f'[k]\cdot e^{j\Omega_0kn}$
- 尋找出線性組合的係數函數$f'[k]$的方法，我們稱之為傅立葉轉換
- 根據正交性，利用內積(投影)的方式找出係數
- 又因為基底的單範性，所以取完內積後不必再除掉，指定向量的長度，如果自己寫DFT的基底沒有單範性記得最後要除掉一個係數
- $f'[k]=<f,e^{j\Omega_0kn}> = \frac{1}{N}\sum_{n=0}^{N-1}f[n]\cdot e^{-j\Omega_0kn}$
- 整理得到DFT和逆DFT如下
- $f'[k]= \frac{1}{N}\sum_{n=0}^{N-1}f[n]\cdot e^{-j\Omega_0kn}$
- $f[n]=\sum_{n=0}^{N-1}f'[k]\cdot e^{j\Omega_0kn}$
- 係數函數$f'[k]$稱作$f[n]$的頻譜，是DFT頻域上的函數，$f[n]$則是DFT時域上的函數
- 他們在諸多方面呈現對偶(dual)的特性
- 許多在一個domain上困難的事情，在另一個domain卻相對簡單，例如微分、積分、捲積
- DFT是個線性映射
- DFT的取樣(補充)
- 一般來說，理解一個周期性連續函數$g$的方式可以透過等間距的取樣
- $f[n] = g(c+\frac{n}{Nf_0})$, for $n\in Z_N$
- 有物理意義的頻率只有$\lceil\frac{N}{2}\rceil$個，即$0,f_0,2f_0,...(\lceil\frac{N}{2}\rceil-1)f_0$
- 特別注意$kf_0$與$(N-k)f_0$的頻率是相同的(但有相位上的差別)
- 取樣定理
- 由上可知頻譜的寬度(頻寬)受到取樣頻率$Nf_0$影響，最多只能到取樣頻的一半
- 頻譜的解析度
- 頻譜的解析度受到取樣時間窗$T=1/f_0$的影響，最小可分辨頻率$f_0$我們稱做基頻
- 傅立葉轉換的解析度在各個頻率都一樣(和小波轉換不同的是，小波轉換在低頻解析度較高)
### 快速傅立葉轉換(Cooley Tukey radix 2)
- 考慮DFT，且$N=2^m$：
- $F_N\{f[n]\}$
$=\frac{1}{N}\sum_{n=0}^{N-1}f[n]\cdot e^{-j\Omega_0kn}$
$=\frac{1}{N}\sum_{n=0}^{\frac{N}{2}-1}(f[2n]\cdot e^{-j2\Omega_0kn}+f[2n+1]\cdot e^{-j2\Omega_0kn}\cdot e^{-j\Omega_0k})$
$=\frac{1}{N}\sum_{n=0}^{\frac{N}{2}-1}f[2n]\cdot e^{-j2\Omega_0kn}+\frac{1}{N}\sum_{n=0}^{\frac{N}{2}-1}f[2n+1]\cdot e^{-j2\Omega_0kn}\cdot e^{-j\Omega_0k}$
$=\frac{1}{2}\cdot F_{N/2}\{f[2n]\}+\frac{e^{-j\Omega_0k}}{2}\cdot F_{N/2}\{f[2n+1]\}$
- 複雜度$T(N) = 2T(N/2)+O(N) = N\cdot log(N)$
- 同理，考慮逆變換
- $F_N^{-1}\{f'[k]\} = F_{N/2}^{-1}\{f'[2k]\}+F_{N/2}^{-1}\{f'[2k+1]\}\cdot e^{j\Omega_0k}$
- 複雜度大抵相同
- 實作Cooley Tukey的時候，如何奇偶項拆解？
- 另外開一條陣列
- 位元反轉
### 捲積(Convolution)
- 定義循環捲積(Circular Convolution)：
- $(a*_cb)[n] = \sum_{k=0}^{N-1} a[k]b[n-k]$
- 定義線性捲積(Linear Convolution)：
- $(a*_lb)[n] = \sum_{k\in Z} a[k]b[n-k]$
- 通常對於周期性序列，我們會採用循環捲積，而對於脈衝序列，我們會採用線性捲積，主要是取決於級數的散歛性
- Convolution Theorem：
- 對於DFT，頻域的乘法等同於時域的(循環)捲積；反之亦然
- 考慮$a,b→_F a',b'$那麼$a*_cb→_Fa'\cdot b'$且$a\cdot b→_Fa'*_c b'$
- 可理解為DFT保留了卷積和乘法的運算特性，在轉換後將之對調
- 快速捲積
- 上面的性質告訴我們一個自然的，快速捲積的算法
- 利用DFT轉換到頻域後做乘法再轉換回時域
- 特別注意用DFT算的捲積是循環捲積
- 若我們想要解線性捲積，則先將線性捲積轉換為循環捲積(補零)，再做循環捲積
- 例子： 大數乘法、多項式相乘皆可視為捲積
## 數論
整數論主要在研究整數的行為，有解析數論和代數數論兩個分支，這裡我們僅介紹賽場上相對常用且容易的主題，有興趣的同學可以另外研讀相關書籍
### 數論轉換(Number Theoretic Transform)
- DFT的進一步推廣
- Ring R中的一個N次主單位根(Principal n'th Root of unity)$a$滿足
- $a^N=1$
- $\sum_{n=0}^{N-1}a^{nk}=0$, for $1\leq k<n$
- 若R是個整環(Field也是一種整環)，那麼任何N次本原根(primitive n'th root of unity)都會是N次主單位根
- $a^N=1$
- $a^k\neq 0$, for $1\leq k<n$
- 特別地對於質數$p$，若$N$整除$\phi(p)=p-1$
- 考慮模p的原根$g$
- $g^{\frac{\phi(p)}{N}}$就會是個N次單位本原根
- 給定主N次單位根，可用類似形式定義轉換與反轉換，相關性質容易證明
- $f'[k]=\sum_{n=0}^{N-1}f[n]\cdot a^{nk}$
- $f[n]=\frac{1}{N}\sum_{k=0}^{N-1}f'[k]\cdot a^{-nk}$
- $\frac{1}{N}$代表乘法逆元，若逆元不存在則逆轉換不存在

### 中國剩餘定理(Chinese Remainder Theorem)
- 給定同餘方程組
- $x\equiv a_i\mod m_i$, for $1\leq i\leq N$
- $m_i$兩兩互質
- 那麼此方程組等價於
- $x\equiv\sum_{i=1}^{N}a_iM_i(M_i^{-1}\mod m_i)$
- 其中$M=\prod_{i=1}^{N}m_i, M_i=\frac{M}{m_i}$
- 這代表若m,n互質，則$Z_{mn}^\times \cong Z_m^\times\times Z_n^\times$
- 考慮質因數拆解$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}$
- 那麼$Z_n^\times \cong Z_{p_1^{e_1}}^\times\times Z_{p_2^{e_2}}^\times\times Z_{p_3^{e_3}}^\times\times...\times Z_{p_k^{e_k}}^\times$
- 因此得到一個$\phi(n)$的計算方法
- 考慮$n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$為質因數拆解
- 那麼$\phi(n)=\phi(p_1^{e_1})\phi(p_2^{e_2})...\phi(p_k^{e_k})$
- $\phi(p^k) = p^k-p^{k-1}$
- 可以發現中國剩餘定理的解形式非常類似於Lagrange Interpolation

### 原根(Primitive Root)
- Definition
- $Z_n^\times$的生成元(如果存在)
- 當且僅當n是$2,4,p^k,2p^k$, p是奇質數，$Z_n^\times$是cyclic的
- 找$Z_n$的原根
- 必須先有$\phi(n)$的分解(通常是n與分解一起產生)
- 若給定質因數分解$\phi(n)=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_k^{e_k}$
- 那麼根據lagrange theorem任何一個$a\in Z_n^\times$的order是$p_1^{e'_1}p_2^{e'_2}p_3^{e'_3}...p_k^{e'_k}$且$e'_i\leq e_i$
- 所有的$e_i=e'_i$當且僅當$a$是一個generator
- 不存在某個$p_i$使得$a^{\frac{\phi(n)}{p_i}}=1$當且僅當所有的$e_i=e'_i$
- 因此，前式能夠做為判斷$a$是個generator的充要條件
- 不斷隨機生成$a\in Z_n^\times$的候選，然後檢查它是否是個generator

### Miller Rabin
- 對數時間判定質數
- $Z_p^\times$單位平方根只有$\pm1$
- 若 $x^2=1$ 則 $x=\pm 1$
- 考慮$\phi(p) = p-1 = s\cdot 2^r$, $s$ 為奇數
- 因此對於任意 $a=b^s$, $b\in Z_p^\times$
- $a, a^2, a^{2^2}, ..., a^{2^r}$必有如下其中一種形式
- $b_1, b_2, ...b_k,-1,1,1,1,...,1$
- $1,1,1,...,1$
- 對於任何一個整數 $n-1=s\cdot 2^r$
- 隨機挑選許多$a=b^s$, $b\in Z_n$
- 這樣的$b$我們稱做一個liar
- 檢驗以下至少其中一個條件被滿足
- $a=1$
- $a^{2^i}=-1$, for some $1\leq i\leq r$
- 如果檢驗失敗就是合數
- 檢驗成功仍有可能會是合數
- 我們稱做偽素數
- 但在多次檢驗後偽素數出現的機率會變得很少
- 針對32, 64 bit範圍已經有人找出能夠完全覆蓋的liar：
- 實作場合仍要小心運算溢位的問題
- $2^{32}$以下：$\{2, 7, 61\}$
- $2^{64}$以下：$\{2,325,9375,28178,450775,9780504,1795265022\}$
### Birthday Problem
- 考慮一個有限值域的hash function $h:D→Z_n$
- 今隨機揀選一些元素，若要產生碰撞的機率達到$\frac{1}{2}$ (或其他指定值)
- 則選的元素各數$\tilde{O}(\sqrt{n})$
- 考慮泰勒級數$e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+...$
- for small $x$: $e^x\approx 1+x$
- $r$個hash不發生碰撞的機率$P(r)$滿足
- $P(r)=1\cdot (1-\frac{1}{n})\cdot (1-\frac{2}{n})...(1-\frac{r-1}{n})$
$\approx e^0\cdot e^{-\frac{1}{n}}\cdot e^{-\frac{1}{n}}... e^{-\frac{r-1}{n}}$
$= e^{-\frac{r(r-1)}{2n}}$
$\approx e^{-\frac{r^2}{2n}}$
- 因此 $r$ 只要$\tilde{O}(\sqrt{n})$就能夠有高機率碰撞
### Pollard's Rho (For factoring)
- 因數分解
- 考慮$N=n\cdot m$, 若 $x\equiv y \mod n$那麼$n|\gcd(x-y,N)$
- 利用生日攻擊的方式，決定一個偽隨機序列$a_0, a_1, a_2...$
- 後項都由前項得到$a_{i+1}=h(a_i)$
- 注意$h$必須要是一個$\mod n$ 的homomorphism
- 通常$h(m)$可以選擇一個二次多項式
- 序列大約在長度延伸到$\sqrt{n}$ 階時，會發生$\mod{n}$的碰撞
- 利用Floyd's Algorithm檢測碰撞(環)
- 選定$x=a_i, y=a_{2i+1}$
- 若有環，則$x,y$會在一圈內碰撞(兩個都進入到圈後開始算)
- 若$N$最小的質因數為$p$則此算法複雜度為$\tilde O(\sqrt{p})$
- 又$p=O(\sqrt{n})$所以複雜度有$\tilde O(n^{\frac{1}{4}})$
- 足夠處理64 bit的場合，但200~300bit以上等密碼學場合不適用

### Discrete Logarithm
給定$a,b\in G$，對$a^i=b$求出最小非負的$i$記做$\log_ab$
### Shank's Algorithm (Baby Step Giant Step)
- 利用分塊爆搜解離散對數
- 考慮$\|a\|=n$是有限階的，求解$log_ab$(若存在)
- 考慮$<a>=\{a,a^2,...a^n\}$
- 定義步寬$m = \lceil\sqrt{n}\rceil$
- 找出$\{a^{mi}:i\in Z_m\}\cap\{b\cdot a^{-i}:i\in Z_m\}$
- 容易證明交集非空
- 因此有$b\cdot a^{-i} = a^{mj}$移項可得$b=a^{i+mj}$
- 複雜度$\sqrt{n}$
### Pi Count
給定整數$n$，算出小於等於$n$的質數個數，記為$\pi(n)$

### Meissel Lehmer Algorithm
- 求解pi count, 複雜度$n^{\frac{2}{3}}$，一秒約可處理$n\leq 10^{11}$
- 首先定義序列$p_i$為前$i$小的質數，如$p_1=2$
- 定義$\phi(m,n):=\|\{a\leq m : \forall 1\leq i\leq n,p_i\nmid a \}\|$
- 代表不大於$m$且不被前$n$個質數整除的數字個數
- 定義$P_k(m,n):=\|\{q_1q_2...q_k\leq m:\exists j>n,q_i=p_j\}\|$
- 代表不大於m，且所有質因數大於$p_n$的數字個數
- 若 $\sqrt[3]{m}\leq y\leq\sqrt{m}$
- 令$n=\pi(y)$
- 顯然$P_k(m,n)=0$ for $k\geq 3$
- 因為$p_{n+1}>y\geq \sqrt[3]{m}$
- $\phi(m,n) = \sum_{k\geq0}P_k(m,n)$
$= P_0(m,n)+P_1(m,n)+P_2(m,n)$
$=1+\pi(m)-n+P_2(m,n)$
- 移項得到$\pi(m)=\phi(m,n)+n-1-P_2(m,n)$
- 根據定義容易證明以下兩項
- 求解$\phi(m,n)$
- $\phi(m,0)=\lfloor m\rfloor$
- $\phi(m,n)=\phi(m,n-1)-\phi(\frac{m}{p_n},n-1)$
- 求解$P_2(m,n) = \sum_{p_n<p\leq\sqrt{m}}(\pi(\frac{m}{p})-\pi(p)+1)$
# 簡單der數學題
- 打星星的代表vjudge不支援該oj，有興趣還是可以寫寫看
- BZOJ 1004 (Burnside's) (裸)(*)
http://www.lydsy.com/JudgeOnline/problem.php?id=1004

- BZOJ 4162: (Cayley Hamilton Theorem)(*)

- CodeVS 4939: (Euler's Function) (裸)(*)
http://codevs.cn/problem/4939/

- 2017 ICPC Jakarta pK (Group + CRT) (*)
https://training.ia-toki.org/problemsets/101/problems/546/

- Formosa OJ 146: (CRT) (裸) (*)
https://oj.nctu.me/problems/146/

- ZOJ a007: (Miller Rabin) (裸)(*)
https://zerojudge.tw/ShowProblem?problemid=a007

- HDU 1402:
- POJ 2417:
- POJ 1811:
- HDU 5901
- CF 665F:
- HDU 5446:
- POJ 2409:
- HDU 5080:
- POJ 2891:
- HDU 5391:
- POJ 2118:
- POJ 1284: