# 數學
## 99
> 
> 先化簡成 RREF，才可以看出行向量之間的線性組合關係，非pivot的行，從上往下看，依序是各個pivot行的組成係數
> \
> $\begin{bmatrix} 1&0&1&0&1\\0&1&1&0&-2\\0&0&0&1&1\\0&0&0&0&0 \end{bmatrix}$
> \
> 上方矩陣是U的 rref，因此可看出第五行向量就是由 $1*a1 + (-2)*a2 + 1*a4$ 所組成

> 非方陣
> 

## 100
* 定義：
> a system is consistent if has at least one solution
> a system is inconsistent if it has no solution

> Ans: ACE
> E選項:
> $(A*(A+B)^{-1}*B)*(A^{-1} + B^{-1}) = A*(A+B)^{-1}* (BA^{-1} + I)$
> $= A*(A+B)^{-1}*(A+B)*A^{-1} = I$
> $(A^{-1} + B^{-1})*(A*(A+B)^{-1}*B) = I$ 同理
> 延伸概念：https://ccjou.wordpress.com/2009/12/04/矩陣和之行列式-上/

> BD
> A選項概念：
> https://ccjou.wordpress.com/2009/05/08/利用分塊矩陣證明-detabdet-adet-b/
> https://ccjou.wordpress.com/2010/12/01/行列式的運算公式與性質/

> ADE
> A:
> 向量空間十公設
> 加法：封結單反交
> 乘法：封結單
> 純量積對向量分配律：$\alpha * (u + v) =\alpha * u + \alpha *v$
> 純量積對純量分配律：$(\alpha + \beta)* u =\alpha * u + \beta *u$

> B: 加法單位元素不存在
> D選項：兩子空間維度相加可以超過原向量空間，是他們的**連集**的維度不行
> E: 同維即同構

> BCE
> E選項：因為row space of C is a subspace of B(由A的列向量對B做linear combination)，所以若A之row vectors are linearly dependent, then row vectors of C are linearly dependent.

> (A)CE
> A選項：不一定？不知道B採用的基底是不是同一個
> B選項：no，only if不成立（if $L(v_1), L(v_2), ..., L(v_k)$ 線性相依，則$v_1, v_2, ..., v_k$不一定線性相依，例如$L(x) = 0$)
> 觀念如下：
> L必定保相依，1-on-1則保獨立，onto則保生成
> C選項：Transition matrix是不同basis之間的對應關係，basis線性獨立，所以Transition matrix必是nonsingular，注意這裡是用nonsingular這個詞，因為invertable只能用在方陣。而matrix representation of 一個不 1-on-1 的linear tranformation可以是singular。
> D選項：similar --> same trace，反過來不成立
> E選項：$\begin{bmatrix} 2&1\\3&2 \end{bmatrix}$ = $[T]uu$
$[T]vv = [I]vs[I]su[T]uu[I]sv[I]us$
---
> ACD
> A選項：$P^{-1}AP = D = \begin{bmatrix} 0&0&0\\0&1&0\\0&0&3 \end{bmatrix}, rank(A) = rank(D) = 2$
> D選項：$2v + 3w + u$投影到$C(A)$就是$2v + 3w$，所以誤差就是$||u||^{2}$

> CD
> https://ccjou.files.wordpress.com/2009/12/powsol-dec-7-09.pdf
> https://ccjou.wordpress.com/2016/01/04/ab-與-ba-的關係：特徵空間篇/
> 
> $xy^{T}$ 和 $y^{T}x$ 有相同的非零特徵值
> $y^{T}x$特徵值：$y^{T}x$
> $xy^{T}$特徵值：$y^{T}x, 0, 0, 0, ...$
> rank 1 matrix $A = xy^{T}$, $Ax = xy^{T}x = (y^{T}x) x$，特徵值為$y^{T}x$，特徵向量為$x$，$y^{T}x$有可能為0，例如$x = (0,1,0), y = (1,0,0)$，取$xi\in y^{\perp}$，則$Axi = x(y^{T}xi) = x*0 = 0$，特徵值為$0$，特徵向量為$xi$
> $A^{T}A = yx^{T}xy^{T} = x^{T}xyy^{T}$
> $A^{T}Ay = yx^{T}xy^{T}y = (x^{T}x)y(y^{T}y) = (y^{T}y)(x^{T}x)y$，奇異值為$||x||||y||$
> $y$為$vi$，SVD中 $ui = Avi / \sigma i = Ay/||x||||y|| = xy^{T}y / ||x||||y|| = x||y|| / ||x||||y|| = x / ||x||$

> 循環群的運算
> [a c d --> [a c d
> d a c] --> c d a]
> 以第一行為例：(a, d) --> (d, c) --> (a, c)

> TFTTT
> (2): V - E + r = 2只能用在只有一個connected components
> 若有多個則是 V - E + r = 1 + k, k是#connected components
> V - E + r = 2k - (k-1) = 1 + k
> k-1個重複算的infinite region
> 
> 

## 101

> Ans: BC
> 觀念：$R(A^{T}) N(A)$互為正交補空間
> A選項：$rank(A) = 1$，所以b可能是無解或是無限多解
> B選項：$(1,1,0), (1,0,0)$屬於$N(A^{T}A) = N(A)$，取其正交補空間基底$(0,0,1)$屬於 $R(A^{T})$，故$(0,0,5)$有解
> C選項：因為誤差即為$(0,2,2)$到$N(A)$，（$N(A)$為$R(A^{T})$之正交補空間），用$(1,1,0), (1,0,0)$為基底計算投影矩陣，再將$(0,2,2)$投影，算長度，即為4。
> 若要$(0,2,2)$對基底向量分別投影這個方法，基底向量必須是經過Grand-Smith process後出來的**正交基底**！
> D選項：$dim(N(A)) = dim(N(A^{T}A)) = 2,rank(A) = 1$
> E選項：可三列都一樣，$rank(A) = 1$

> Ans: ACE
> 觀念：
> 列運算不影響行空間向量的線性組合關係
> 行運算不影響列空間向量的線性組合關係（可對上句取轉置做證明）
> C選項：列運算後，$C(A)$和$C(U)$不一定會相同，是在這個例子中因為基底向量一樣所以才相同（保持不變的只有行向量之間的線性組合關係）
>（由 U可知，A的行向量中1, 3行為線性獨立基底向量，而 U中也是1, 3行為基底）
> https://ccjou.wordpress.com/2010/12/24/左乘還是右乘，這就是問題所在/
> https://ccjou.wordpress.com/2011/01/10/基本矩陣的幾何意義/

> Ans: BD
> 觀念：行運算，跟上面那題類似觀念。行運算不影響列空間向量的線性組合關係，但是列空間可能會改變，rref也不同，kernel space也可能跟著改變。但是Column space不會改變，Range 自然也不會改變。
> https://ccjou.wordpress.com/2011/01/10/基本矩陣的幾何意義/

> Ans: BCDE
> 觀念：可逆矩陣代表滿秩，故b一定在A的行空間中，有唯一解
> Cramer's rule只有當A可逆才可以用，必為唯一解
> https://ccjou.wordpress.com/2009/10/28/從線性變換解釋最小平方近似/
> https://ccjou.wordpress.com/2009/04/01/由簡約列梯形式判斷線性方程解的結構/
> https://ccjou.wordpress.com/2010/11/08/圖說矩陣基本子空間與線性方程解的結構/
> https://ccjou.wordpress.com/2009/11/10/克拉瑪公式的證明/

> 

> 

> 

> 

> 
> 

## 102
> Ans:ABC
> 行基本矩陣不為基本矩陣，僅是為多個列基本矩陣的乘積

> Ans:ABDE
> C選項: 反例：$\begin{bmatrix} -1&0\\0&-2 \end{bmatrix}$
> 奇異值是特徵值開根號，會有正負的差異
> D選項：true, 見下圖。延伸：$A^{T}A$的特徵值和 $A$原本的特徵值 的關係是什麼？
> https://ccjou.wordpress.com/2013/10/30/矩陣跡數與特徵值和奇異值的關係/
> 
> E選項：
> $x^{T}AA^{T}x= ||A^{T}x||^{2}$
> 因為$A$ is full row rank --> $A^{T}$ is full column rank
> $A^{T}x$ 對於任何非0向量x(正定的定義）都不等於0
> $x^{T}AA^{T}x > 0$
> $AA^{T}$為正定矩陣

> Ans: CE
> CE選項: https://ccjou.wordpress.com/2009/09/14/特殊矩陣-四：householder-矩陣
> **重點在於Houshholder like的矩陣要運用 Xtranspose X以及正交補空間等等，內積為0的性質去解題**
> (D): minimal 2-norm的解會在$C(A^{T})$，也就是在$span(y)$，$x\notin span(y)$，所以D選項錯誤


> Ans: BCE
> (D):
> 觀念：秩的退化
> $rank(AB) = rank(B) - dim(N(A)\cap C(B)) <= rank(B)$
對上式取轉至可得 $rank(AB) <= rank(A)$
故 $rank(AB) <= \min(rank(A), rank(B))$
又$dim(N(A)\cap C(B)) <= dim(N(A)) = n - rank(A)$
$rank(AB) = rank(B) - dim(N(A)\cap C(B)) >= rank(B) - n + rank(A)$
綜合以上：**$rank(A) + rank(B) - n <= rank(AB) <= \min(rank(A), rank(B))$**
https://ccjou.wordpress.com/2010/01/14/破解矩陣秩的等式與不等式證明/
(E):見下圖，因為有同樣的$X^{+}$解，所以$AX^{+}$必定是相同的(投射到$C(A)$)，代表$b = c$。

> 由SVD分解可知 $A^{+}$ 和 $A^{T}$的四大子空間都相同，差別只在伸縮倍率上
> $x^{+} = A^{+}b = A^{+}c$
> $A^{+}(b-c) = 0$
> $(b-c) \in N(A^{+})$
$N(A^{+}) = N(A^{T})$
$b-c$ 若$\in N(A^{T})$ 就是答案
https://ccjou.wordpress.com/2012/07/06/偽逆矩陣與轉置矩陣的二三事/

> Ans: BE
(A): $10 \choose 3$ $* 2^7 * 3^3$
>
> (B): $x1 + x2 = 16$ 的非負整數解 --> ${2 +16 - 1 \choose 16} = 17$
(D):
亂序的遞迴：
$D_n = (n-1) (D_{n-1} + D_{n-2})$
$D1 = 0$
$D2 = 1$

> Ans: AB
(B): 由外而內
(C ):2的2的2的...k次方 = 1024沒有正數解
像是2的2的k次方-->4的k次方 = 1024
(D): 111無對應值

## 103
* 解極小範數解，可假設解$x^{+}$為$A^{T}x$，再帶入等式$Ax^{+} = p$。因為極小範數解位在$C(A^{T})$當中
---
> (a) : asymmetric, 因為transitive + irreflexive 代表asymmetric(假設 (a,b)存在，因為(b,b)不存在，所以(b,a)不存在)。第二個答案為irreflexive，因為asymmetric代表irreflexive。
(b): 
(c ): s長度 < t長度
(d):一樣長的時候

## 104
(1) <
(2) = 因為C++ program terminate與否，都是valid C++ program, 而valid C++ program is countable
* 注意：當沒有公因數的時候，congruence要乘上乘法反元素，才可以消去

## 105
> $[I]$from u to v，代表將u的基底用v的基底來描述
$[w]$用v基底表示 = ($[I]$from u to v) x $[w]$用u基底表示 （只是座標改變而已）（在同一個vector space）
若是不同vector space間的linear transformation 則寫成
$[T(w)]$用v基底表示 = ($[T]$from u to v) x $[w]$用u基底表示
所以此題：u1 = 4 v1 + 2 v2, u2 = 1 v1 + 1 v2

> True, $dim(Pn) = n + 1$
$ker(T) = span(1), dim(ker(T)) = 1$
$rank(T) = (n + 1) - 1 = n$

> 口訣：由外而內

## 106
> * T(n) = 7T(n/2) + n^2 --> O(n^2.78)

> a. False, 函數可以多對ㄧ
b. False, 么正矩陣的特徵值的絕對值為1
c. True
d. True
e. False, 可逆和可對角化沒關係
f. True
g. False
h. False
i. True, A是正規矩陣，且A和其轉置本來就具有相同的特徵值，是A若為正規矩陣，則A和其伴隨算子 A*之特徵值會差一個bar，特徵向量相同
## 107

## 108

## 109

> (b)
> vertex a: indegree = 1, outdegree = 2
> vertex e: indegree = 4, outdegree = 3
> 


---
> 觀念：外積 https://www.youtube.com/watch?v=BaM7OCEm3G0
> https://ccjou.wordpress.com/2014/04/29/三維空間的旋轉矩陣/