# 數學
## 95

> $trace(A^{T}A) = trace(AA^{T}) = \sum_{j=1} (A^{T}A)_{jj} = \sum_{j=1} \sum_{i=1}(A)_{ij} * (A)_{ij} = \sum_{j=1} \sum_{i=1}(A)_{ij}^2 = \sum_{i=1} \sigma_i^2$ ($A^{T}A$的奇異值平方和)
> 要找和奇異值的關係用SVD分解：$trace(A^{T}A) = trace(\sum^T \sum) = \sum_{i=1} \sigma_i^2$
> 要找和特徵值的關係用Schur分解：$trace(A^{T}A) = trace(UT^*U^*UTU^*) = trace(T^*T) = \sum_{j=1} \sum_{i=1}(T_{ij})^2 = \sum_{i=1}(T_{ii})^2 + \sum_{i=1, j>i}(T_{ij})^2$
> $= \sum_{i=1} \lambda_i^2 + \sum_{i=1, j>i}(T_{ij})^2 >= \sum_{i=1} \lambda_i^2$
> 等號成立於A為正規矩陣的時候
> https://ccjou.wordpress.com/2010/05/10/矩陣模/
> https://ccjou.wordpress.com/2013/10/30/矩陣跡數與特徵值和奇異值的關係/

## 96
> 要硬爆也是可以只是比較慢
> 重點是變數變換：$I = (I+A)(I+A)^{-1}$

> generating function method
> 解題步驟：
> 令$A(x) = a_0 + a_1*x^1 + a_2*x^2 + ...$
> 找出最低次方為$A_{n}$的遞迴式： $A_{n+2} = 3A_{n+1} + 2A_{n}$
> 乘上最高次方：$x^{n+2}$
> 解$A(x)$



## 97
> Householder 除了鏡射之外，**長度伸縮**的概念（看特徵值）
> 

> $(c, d) = (-1, n-1)$
> if $v^{T}u = -1$, then eigenvalue of $v^{T}u$ is $-1, 0, 0, 0,...$(n-1個 0)
> $u^{T}v$ 的 eigenvalue 為：$ is $-1, 0, 0, 0,...$(n-1個 0)
> $I + u^{T}v$ 的 eigenvalue 為：$ is $0, 1, 1, 1,...$(n-1個 1)
> $Nullity(I + u^{T}v) = dim(ker(I + u^{T}v)) = dim(ker((I + u^{T}v) - 0*I)) = 1$
> $rank(I + u^{T}v) = n - 1$
> 也可以由 $N(I + u^{T}v) = span(u)$ 得出$rank(I + u^{T}v) = n - 1$
> 因為$(I + u^{T}v)*x = 0, x = -(v^{T}x)*u, x \in span(u)$
> 
> https://ccjou.wordpress.com/2010/02/02/特殊矩陣-十：基本矩陣/

> 
> https://ccjou.wordpress.com/2012/06/27/伴隨矩陣/
> 計算伴隨矩陣是用餘因子，當原本矩陣有兩列相同，做這列的餘因子會是ㄧ樣的，而其他
列的餘因子都會是0（因為有兩列相同），所以做出來的adj(A)會是rank1。
> 當超過兩列相同，餘因子就會都是0，rank(adj(A)) = 0
> 證明：
> 等式：$A * adj(A) = det(A) * I$
> 若 $A$可逆，$adj(A) = A^{-1} * det(A) * I$，$adj(A^{-1}) = (A^{-1})^{-1} * det(A^{-1}) * I = A * 1/det(A)$
> 若 $A$不可逆：$A * adj(A) = 0$ 代表 $adj(A)$的行空間屬於 $A$的零空間
> 故 $rank(adj(A)) = dim(C(adj(A))) <= dim(N(A))$
> 由定義計算，分為2 case：
> 1. $rank(A) = n - 1 -> rank(adj(A)) = 1$
> 2. $rank(A) < n - 1 -> rank(adj(A)) = 0$

> 
>https://ccjou.wordpress.com/2009/10/21/%e4%ba%8c%e6%ac%a1%e5%9e%8b%e8%88%87%e6%ad%a3%e5%ae%9a%e7%9f%a9%e9%99%a3/
https://ccjou.wordpress.com/2010/03/16/hermitian-%E7%9F%A9%E9%99%A3%E7%89%B9%E5%BE%B5%E5%80%BC%E7%9A%84%E8%AE%8A%E5%8C%96%E7%95%8C%E5%AE%9A/

> 
> 
>
https://ccjou.wordpress.com/2013/06/14/%e5%bb%a3%e7%be%a9%e7%89%b9%e5%be%b5%e5%80%bc%e5%95%8f%e9%a1%8c/

* 9, 10題的key idea都是變數變換，使得我們最後只需要解一個Rayleigh 商即可

> Boolean algebra is a lattice, which is **bounded**, **distributed**, **complemented**.
> 有交換律！
> ---
> 
> ---
> 

> 先證 單位元素，再證反元素，最後是封閉性
> 結合、交換是遺傳
> ---
> 
> 
> ---
> 
> 

>

>

## 98
* 旋轉矩陣
> https://ccjou.wordpress.com/2014/04/29/三維空間的旋轉矩陣/
> https://ccjou.wordpress.com/2015/08/19/高階旋轉矩陣/
> https://ccjou.wordpress.com/2015/08/12/旋轉與鏡射/

> 

> https://ccjou.wordpress.com/2009/10/23/特殊矩陣七：循環矩陣/
> 
> 

> CDE
> 

> A,B: 環--> +:封結單反交，X: 封結，X 對 + 有分配律
> C選項，環的定義，要求 x 對 + 要有分配律！
> D選項，holds only for boolean algebra
> E選項，這是一個定理
> 

> 
> D選項：
> 
> 注意是Cn+1，C0 = 1
> 
> E選項：非線性遞迴（混沌）並非都有解

> 如果A選項是正確的，那麼兩圖是否同構的問題即有充分條件，不再是NP問題了
> 
> 
> E選項：
> 
> 

## 99
* $rank(A^TA) = rank(A)$
> Gramian 矩陣： https://ccjou.wordpress.com/2011/03/07/特殊矩陣-14：gramian-矩陣/

> HouseHolder --> **純量**
> 

> 可用暴力，不過
> 
> https://ccjou.wordpress.com/2009/08/26/cayley-hamilton-定理/

> https://ccjou.wordpress.com/2011/01/19/利用循環子空間計算特徵多項式/
> https://ccjou.wordpress.com/2012/12/05/限定算子的特徵值與特徵向量-上/
> https://ccjou.wordpress.com/2012/12/07/不使用行列式的特徵值和特徵向量算法-上/
> https://ccjou.wordpress.com/2012/12/26/最小多項式的計算方法/
> 
> 
> 
> 參考觀念：
> 

> 三對角矩陣特徵值公式：https://ccjou.files.wordpress.com/2010/02/powsol-feb-15-10.pdf
> 此例：$b = 3, a = 2, c = 2$
> $\lambda_i = b + 2a \sqrt{c/a} * cos(i\pi/(n+1))$
> $= 3 + 2*2*cos(i\pi/(5+1)), i = 1,2,3,4,5$
> 在 i = 1時$cos(\pi/(5+1))= \sqrt3 / 2$有最大值 = $3 + 2\sqrt3$

> 也可以解遞迴
> 遞迴由小到大或是由大到小都可以，重點是式子要寫清楚，不要計算錯誤
> 
> 
>
> 
> 

> 
> 
> E選項：
> 

> D選項：
> 指數生成函數 $e^x = \sum^{\infty}_{i=0}x^{i}/i!$
> $e^{-x} = \sum^{\infty}_{i=0}(-x)^{i}/i!$
> $(e^x + e^{-x}) / 2= \sum^{\infty}_{i=0}(x)^{i} + (-x)^{i})/i! = 1 + x^2/2! + x^4/4! ...$
> $(e^x - e^{-x}) / 2= \sum^{\infty}_{i=0}(x)^{i} - (-x)^{i})/i! = 1 + x^3/3! + x^5/5! ...$
>
>

> B選項：BFS後collapse parent connection, 形成 connected component
> 


---

## 100

> 除了硬幹，也可以用下式求解
> $trace(A^2) = \sum\lambda^2$
> https://ccjou.wordpress.com/2013/10/30/矩陣跡數與特徵值和奇異值的關係/

> key: rank1 matrix
> https://ccjou.wordpress.com/2010/02/02/特殊矩陣-十：基本矩陣/
> https://ccjou.wordpress.com/2009/09/14/特殊矩陣-四：householder-矩陣/
> https://ccjou.wordpress.com/2009/03/14/ab-和-ba-有何關係/
> 

>
>

>
>

> 

## 101

> 觀察，題目給$A$的特徵方程式，要求$A^{2}$的特徵方程式，決定利用特徵多項式的根與係數關係
> 設$A$特徵值：$a, b, c$
> 得 $a + b + c = 1, ab + bc + ca = 3, abc = 2$
> 欲求$a^{2} + b^{2} + c^{2}, a^{2}b^{2} + b^{2}c^{2} + c^{2}a^{2}, a^{2}b^{2}c^{2}$
> $(a + b + c)^{2} = a^{2} + b^{2} + c^{2} + 2(ab + bc + ca) = 1$
> --> $a^{2} + b^{2} + c^{2} = -5$
> --> $a^{2}b^{2}c^{2} = 2^2 = 4$
> 令$a^{2}b^{2} + b^{2}c^{2} + c^{2}a^{2} = Y$
> 可建構出 $det(xI - A^2) = x^3 + 5x^2 + Yx - 4$
> $x$代 $1$可得$det(I - A^2) = det(I + A) * det(I - A) = ((-1)^3 * -7 )* 1 = 7 = 2 + Y$
> $Y = 5$
> $det(xI - A^2) = x^3 + 5x^2 + 5x - 4$
> 這題要注意係數正負的關係，注意首項的係數是正（正負正負正負...）or負（負正負正負正...）
> https://ccjou.wordpress.com/2010/01/12/特徵多項式蘊藏的訊息/
> 
> 

> 可用不變子空間求解特徵根（和台大99年第九題一樣），也像下方詳解那樣用行列式去算。
> 行列式求解的關鍵：需要 k 個特徵根乘積和，就在主對角線上任選k個element，刪掉其所在的行與列，求剩下的行列式值，最後sum起來，即為所求。
>
>

> https://ccjou.wordpress.com/2010/02/22/特殊矩陣-11：三對角矩陣/
> 三對角矩陣，特徵值公式：https://ccjou.files.wordpress.com/2010/02/powsol-feb-15-10.pdf
> 
> 
> 
> 
> 

> 
> 環的 **有限** 子集必可找到加法單位元素，也就可以找到加法反元素，所以為子環

## 102
> 

> 

> 
> 

> 
> 

>

> 
> https://ccjou.wordpress.com/2010/01/12/特徵多項式蘊藏的訊息/
> 計算行列式時可針對$\lambda$所在的列去做拆分（餘因子），拆成$\lambda$和0，如此一來可清楚看出要求次方的係數是由哪些餘因子構成。
> 重要觀察：要找$X^k$的係數，就在對角線上選 $C(n, k)$個主對角線element，然後劃掉相關行、列，剩下的取方陣四角元素做行列式，再sum起來，及為所求。

> 

> TTTFF
> 注意C選項，因為矩陣size: nxn，所以AB具有相同的非零特徵值之外，連零特徵值的個數都相同

## 103

> $4^{2^{m}}$

> 求和算子：==$1/1-x$==
> 
> 

> 

> C小題：
> Ans: 28
> 實矩陣佈於$R^n$時，維度是n
> 複矩陣佈於$C^n$時，維度是n
> 複矩陣佈於$R^n$時，維度是2n
> 實矩陣佈於$C^n$時，不為vector space，反例：$i(1,0)$
> https://ccjou.wordpress.com/2013/09/23/複數的矩陣表示/
> D小題：
> 

## 104
> 
> 

> 
> 

> 觀念：線性泛涵與對偶空間 https://ccjou.wordpress.com/2011/06/13/線性泛函與對偶空間/
> 
> 

>
> 
>

## 105
> Ans: DE
> C選項：orthogonal set 可以包含0向量，orthornormal不行（因為0向量非單位向量）

> Ans: D
> C選項False
> 反例：$3x + 4y = 3, (x1,x2) = (1, 0), (x3, x4) = (0, 3/4)$
> but $(x1,x2) + (x3, x4) = (1, 3/4)$，帶入 $3x + 4y = 6$ 不等於 $min(\alpha i) = 3$

> https://ccjou.wordpress.com/2009/07/29/特殊矩陣-一：冪零矩陣/
> 冪零矩陣 的特徵值都是 0
> 
> $(I + N)(I - N + N^2 - N^3 + ... + N^k) = I - N^k = I$
> $(I + N)^{-1}=(I - N + N^2 - N^3 + ... + N^k)$

> 利用 $||<x,y>|| = 1$
> 得 $x^2/4+ y^2 /9 = 1$

> Ans = $6*2^n - 2 - n$
>

>

## 106

> 當行獨立時（列獨立取轉置）$A^{+} = (A^T A)^{-1} A^T$
> 行獨立代表$(A^T A)^{-1}$可逆，所以$A^{+} = (A^T A)^{-1} A^T$
> 行不獨立時，$rank(A) = rank(A^{T}A) < n$，不可逆，正規方程式有無限多解，要用SVD才可以求出$A^{+}$
> 這題用$A^{+} = U\Sigma^{+} V^T$硬幹會發現$A^T A$的特徵分解醜到爆，算不出來

https://ccjou.wordpress.com/2013/07/03/moore-penrose-偽逆矩陣/
https://ccjou.wordpress.com/2014/02/11/矩陣的四個基本子空間的正交投影矩陣/

> 
> key: 直線 $y' = (y/x) x'$ 的基底是 $(x, y)$

> $\vec{v} = (\pm1/\sqrt{3}, \pm1/\sqrt{3})$
> 考點：主軸定理，二次型的應用
> https://ccjou.wordpress.com/2010/09/16/cholesky-分解/
> 
> $f(x,y) = \begin{bmatrix} y1\\y2 \end{bmatrix} ^{T}\begin{bmatrix} 1&-1\\-1&4 \end{bmatrix}\begin{bmatrix} x1\\x2 \end{bmatrix}$
> \
> 又$\begin{bmatrix} 1&-1\\-1&4 \end{bmatrix}$為正定矩陣
> \
> 做$LDL^{T}$分解
> \
> $\begin{bmatrix} 1&-1\\-1&4 \end{bmatrix} = \begin{bmatrix} 1&0\\-1&1 \end{bmatrix} \begin{bmatrix} 1&-1\\0&3 \end{bmatrix} = \begin{bmatrix} 1&0\\-1&1 \end{bmatrix} \begin{bmatrix} 1&0\\0&3 \end{bmatrix} \begin{bmatrix} 1&-1\\0&1 \end{bmatrix} = \begin{bmatrix} 1&0\\-1&\sqrt{3} \end{bmatrix} \begin{bmatrix} 1&0\\0&1 \end{bmatrix} \begin{bmatrix} 1&-1\\0&\sqrt{3} \end{bmatrix}$
>\
>$f(x,y) = \begin{bmatrix} y1\\y2 \end{bmatrix} ^{T}\begin{bmatrix} 1&0\\-1&\sqrt{3} \end{bmatrix} \begin{bmatrix} 1&0\\0&1 \end{bmatrix} \begin{bmatrix} 1&-1\\0&\sqrt{3} \end{bmatrix}\begin{bmatrix} x1\\x2 \end{bmatrix}$
>\
>又 $f(u,v) = \begin{bmatrix} t1\\t2 \end{bmatrix} ^{T} \begin{bmatrix} 1&0\\0&1 \end{bmatrix} \begin{bmatrix} s1\\s2 \end{bmatrix}$
>\
>又$\begin{bmatrix} s1\\s2 \end{bmatrix}為\begin{bmatrix} x1\\x2 \end{bmatrix}$ 以 ${u, v}$ 為基底的座標
>\
>$\begin{bmatrix} x1\\x2 \end{bmatrix}$ 是以 ${x, y} (R^2的standard basis)$為基底的座標，所以$\begin{bmatrix} 1&-1\\0&\sqrt{3}\end{bmatrix}$ 就是從基底${u, v}$轉到 standard basis的 Transition matrix. 求其轉置即是 從standard basis轉到 ${u, v}$ basis的 Transition matrix。
>\
>$\begin{bmatrix} 1&-1\\0&\sqrt{3}\end{bmatrix}^{-1} = \begin{bmatrix} 1&1/\sqrt{3}\\0&1/\sqrt{3} \end{bmatrix} = \begin{bmatrix} u1&v1 \\u2&v2\end{bmatrix}$
> \
> 得解$\vec{v} = \begin{bmatrix} v1\\v2 \end{bmatrix} = (1/\sqrt{3}, 1/\sqrt{3})$(負的解發生在$LDL^{T}$分解時D取負)
>
> 

> Bipartite or two colorable（a graph is bipartite if and only if there is no odd length cycle)

## 107
> 解題步驟：先寫出$A{n}$，然後開始微分（積分），起始項都是 n = 0。

> 
> 

> https://ccjou.wordpress.com/2011/05/19/正交補集與投影定理/
## 108

> 利用進出公式：${n\choose m} = n/m * {n-1\choose m-1}$
> ${2n\choose n+1} + {2n\choose n} = {2n+1\choose n+1} = {2n+1\choose n}$
> ${2n+1\choose n} * 2 * (n+1)/(n+1) = {2n+2\choose n+1}$

> $A = 2n, B = n+1$
> https://ccjou.wordpress.com/2013/10/02/二項式係數公式/
> 
> 

> ACE
> 
> question: 任何vector space都有基底？有限？無限？
> https://ccjou.wordpress.com/2010/06/15/基底與維度-常見問答集/
> 任何有限維向量空間都有基底，（{0}的基底為空集合，維度為0）
> https://ccjou.wordpress.com/2016/02/24/無限維向量空間的基底/
>根據選擇公理，任何無限維向量空間，存在一個Hamel基底

> All
> 
> question: $N(A) 和 N(A^{-1})$的關係？相同？在什麼狀況下相同？

> ABCE
> 
> A選項：若是由jordan 分塊（廣義特徵空間）構成的直和，則不可對角化，但是有jordan form
> B選項：正規算子的性質，$N(A) = N(A^{*})$(可由乒乓協議 $x^{*}(Ay) = (A^{*}x)^{*}y$證明）, 平移之後還是正規算子，所以$N(A - \lambda * I) = N(A^{*} - \lambda * I)$，所以對於特徵值$\lambda$而言，具有相同的特徵向量
> 或者也可由下圖中觀念來證明有相同的特徵向量
> 
> C選項：我認為解答錯了，任何特徵多項式必定可以因式分解(只是根可能不是整數而已)
> https://ccjou.wordpress.com/2010/01/12/特徵多項式蘊藏的訊息/
> https://ccjou.wordpress.com/2010/11/10/jordan-形式大解讀-上/
>https://ccjou.wordpress.com/2009/07/22/從實數域到複數域/
>https://ccjou.wordpress.com/2010/01/05/特殊矩陣-九：-hermitian-矩陣/
>https://ccjou.wordpress.com/2009/10/01/特殊矩陣-六：正定矩陣/
>https://ccjou.wordpress.com/2009/08/12/特殊矩陣-二：正規矩陣/
>https://ccjou.wordpress.com/2012/10/19/實對稱矩陣特徵值變化界定的典型問題/
>https://ccjou.wordpress.com/2010/03/16/hermitian-矩陣特徵值的變化界定/

> 
> 
> https://ccjou.wordpress.com/2011/06/13/線性泛函與對偶空間/
> https://ccjou.wordpress.com/2011/04/08/線性變換集合構成向量空間/ㄋ
> 
> 

* Note: 計算高階矩陣的inverse時，可以先對每一列做除法，降低計算難度，反正計算$[A|I] -> [I|A^{-1}]$三種列基本運算都可以用。
> https://ccjou.wordpress.com/2012/10/04/三階逆矩陣公式/

## 109
* 計算虛反矩陣要點：
> 看$A^{T} or A$ 誰的$A^{T}A$ size比較小，就用誰計算SVD分解
> 在計算SVD分解時，若上ㄧ步有取轉置$B = A^{T}$來計算，要時刻保持注意，注意$U, V$兩個矩陣，以及他們的他們的size，若特徵向量不夠，要再去相對的子空間生出來。
---

## 109 台大電信丙

## 106 & 108 台大電信丙
> TRUE
> proof:
> $<v,v_i> = <w, vi>, i = 1, 2,...,n$
> $<v,v_i> - <w, vi> = 0, i = 1, 2,...,n$
> $<v-w, vi> = 0, i = 1, 2,...,n$
> $S$ 是 $R_n$的基底
> 所以$v-w = 0$, $v = w$

> TRUE
> 實對稱矩陣性質
> proof:
> $Ax = \lambda x$
> $x^{T}Ax = \lambda x^{T}x = \lambda ||x||^{2}$
> 因為$x^{T}Ax \in R$，所以$\lambda ||x||^{2}\in R$ ，又$||x||^{2}\in R$，所以$\lambda \in R$

> A沒有半正定！如果是半正定此題就是True
> False:
> 反例：
> $A = \begin{bmatrix} 0&0&1\\0&0&0\\1&0&0\end{bmatrix}$
>
> $v = \begin{bmatrix} 1&0&0 \end{bmatrix}$

> 半正定才可以保證特徵值 >= 0，才可以把A開根號(對角矩陣主對角線元素都 >= 0)


> 正交補空間性質

> 解的種類