---
disqus: ierosodin
---

# Highlights of Linear Algebra

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `Linear Algebra` `學習筆記`

## Ｍultiply a matrix by a vector

### Column space

矩陣乘以一個向量，可以有兩個思考方式：
* By rows
* ${{\left[
\begin{array}{ccc}
2 & 1 & 3 \\
3 & 1 & 4 \\
5 & 7 & 12 \\
\end{array}
\right]}{\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
\end{array}
\right]} = {\left[
\begin{array}{c}
2x_1 + x_2 + 3x_3 \\
3x_1 + x_2 + 4x_3 \\
5x_1 + 7x_2 + 12x_3 \\
\end{array}
\right]}}$
* $x$ 對 $A$ 的每一列進行 dot product。
* By columns
* ${{\left[
\begin{array}{ccc}
2 & 1 & 3 \\
3 & 1 & 4 \\
5 & 7 & 12 \\
\end{array}
\right]}{\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
\end{array}
\right]} = x_1{\left[
\begin{array}{c}
2 \\
3 \\
5 \\
\end{array}
\right]} + x_2{\left[
\begin{array}{c}
1 \\
1 \\
7 \\
\end{array}
\right]} + x_3{\left[
\begin{array}{c}
3 \\
4 \\
12 \\
\end{array}
\right]}}$
* 可以想像 $x_1, x_2$ 是一個參數，來對 $A$ 的兩個 column 進行 linear combination。
* 也可以將 $Ax$ 表示成，$A$ 中的第 $k$ 行與 $x$ 中的第 $k$ 列進行矩陣乘法，並取 $k = 1 \sim n$ 的運算結果和 (sum of outer product)。
* 因此今天我們有無限多個 $x$，並且可以透過 $Ax$ 得到無限多的向量，這些向量就組成了 column space，這裡我們記作 $C(A)$。
* 以一個 3x3 的矩陣，可能可以得到一個 R3 的空間，或者小於 R3，以上面這個例子，我們得到的是一個平面的空間。
* 可以很直覺的發現，col(3) 其實可以由 col(1) + col(2) 所組成，因此實際獨立的 column 只有兩個。
* 我們稱一個矩陣的獨立 column 個數為這個矩陣的 rank，也可以解釋為，$C(A)$ 的 dimension，以上面這個例子，其 $C(A)$ 的 dim 為 2。
* 這些獨立的 column 可以形成這個 column space 的一組 basis。
* 互相獨立，並且可以 span 出整個 column space。

### Rank

當一個 $m \times m$ 的矩陣其 rank 為 r 時，則可以 factorize 成 $CR$，其中 $C, R^T$ 皆為 $m \times r$ 的矩陣，且其 column 互相獨立(rank = r)。
* ${{\left[
\begin{array}{ccc}
2 & 1 & 3 \\
3 & 1 & 4 \\
5 & 7 & 12 \\
\end{array}
\right]} = {\left[
\begin{array}{cc}
2 & 1 \\
3 & 1 \\
5 & 7 \\
\end{array}
\right]} {\left[
\begin{array}{ccc}
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{array}
\right]}}$
* 對於 R 中的每一個 column，我們可以解釋成，$A$ 中的每一個 column 是如何以 C 這組 basis 來進行 linear combination。

### Row Space

除了 column space，我們也定義 row space = $C(A^T)$，並且：
* ==The rank of column space is equal to the rank of row space, whether if it is a square matrix.==
* 首先，我們知道 row rank 就是 row space 的 dimension，要找到獨立的 row 有兩種方法：
1. 像找 independent column 一樣，將 $A$ 進行轉置後，找出 $A^T$ 中獨立的 column，$C(A^T)$ 即為 row space。
2. 你可以相信，${\left[
\begin{array}{ccc}
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{array}
\right]}$ 會是 row space 的一組 basis。
* 首先要確認是否可以透過這組 row，來 linear combine 出 $A$ 中的所有 row。
* 很明顯，$C$ 的每一個 row 即為組成 $A$ 中每個 row 的參數，例如：
${\left[
\begin{array}{ccc}
2 & 1 & 3 \\
\end{array}
\right]}$ 可以透過 ${\left[
\begin{array}{cc}
2 & 1 \\
\end{array}
\right]\left[
\begin{array}{ccc}
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{array}
\right]}$ 來得到。
* 接著是，這組 row 必須彼此互相獨立，這也很明顯，因為 $R$ 是由 $I$ 與非 0 的 vector 所組成的。
* 這也解釋了為何 $A$ 的 column's rank 會與 row's rank 相等。
* $R$ 稱為 ==the row reduced echelon form of the matrix==

## Ｍultiply a matrix by a matrix

矩陣乘以一個矩陣 $CR$，同樣可以有兩個思考方式：
* Result from inner product
* $CR$ 可以透過對 $C$ 中每一個 row 與 $R$ 中每一個 column 進行 dot product 來得到結果。
* Sum of rank-1 matrices
* 對 $C$ 中的 column 與 $R$ 中的 row 進行 outer product，在進行加總。
* ${\left[
\begin{array}{ccc}
c_1 & c_2 & c_3 \\
\end{array}
\right]} {\left[
\begin{array}{c}
r_1^T \\
r_2^T \\
r_3^T \\
\end{array}
\right]} = c_1r_1^T + c_2r_2^T + c_3b_r^T$
* $CR = \sum_{k=1}c_k \times r_k^T$

對於一個 $m \times n$ 矩陣乘以 $n \times p$ 矩陣，第一種方法需要進行 $n \times (m \times p)$ 次的乘法，而第二種方法為 $(m \times p) \times n$。運算量其實是一樣的，只是透過不同的方式進行。

## The ranks of $AB$ and $A + B$

1. $\text{rank of }AB \leq \text{rank of }A, B$
* proof:
$\begin{split} &C(AB) \subseteq C(A) \Rightarrow r(AB) \leq r(A) \\
&C(B^TA^T) \subseteq C(B^T) \Rightarrow r(B^TA^T) = r(AB) \leq r(B^T) = r(B)\end{split}$
> $A$ 的 column space 做任何線性轉換後還是會在 C(A) 中
>
2. $\text{rank of }A + B \leq \text{rank of }A + \text{rank of }B$
* proof:
$C(A+B) \subseteq C(A) + C(B) \Rightarrow r(A+B) \leq r(A) + r(B)$
> $A + B$ 的所有 column 必由 $C(A)$ 與 $C(B)$ 透過線性組合產生
3. $\text{rank of }A^TA = \text{rank of }AA^T = \text{rank of }A = \text{rank of }A^T$
* proof:
$N(A^TA) = N(A) \Rightarrow C(AA^T) = C(A^T)$
$N(AA^T) = N(A^T) \Rightarrow C(A^TA) = C(A)$
> 任何線性矩陣乘上 $A$，其 Null space 不會變
> $Ax = 0 \Rightarrow A^TAx = 0$
> 反之，$A^TAy = 0 \Rightarrow y^TA^TAy = 0 \Rightarrow ||Ay|| = 0 \Rightarrow Ay = 0$
4. If $A$ is $m\times r$ and $B$ is $r\times n$ - both with rank r, then $AB$ also has rank r.
* proof:
By 3, $A^TA$ and $BB^T$ have rank r, and both are invertible matrices
$\Rightarrow \text{rank of }A^TABB^T = r$
By 1, $\text{rank of }A^TABB^T \leq \text{rank of }AB$
$\Rightarrow r \leq \text{rank of }AB \leq \text{rank of }A = r$
$\Rightarrow \text{rank of }AB = r$
> 如果 $r\times r$ 矩陣 $A$ 的 rank 為 r，則 $A$ 為可逆矩陣。因為rank = r 代表 $Ax = 0$ 有唯一零解，然而不可逆矩陣，其 $Ax = 0$ 有無窮多組解，$N(A) > 0$，矛盾
> 若 $AA^T$ 與 $BB^T$ 皆為可逆，則 $A^TABB^T$ 為可逆
> 若為可逆矩陣，則 rank = r

## Factorization

* $A = LU$
* elimination
* $A = QR$
* $Q$ column is orthogonal (or maybe orthonormal)
* $Q^TQ = I$
* Gram-Schmidt
* $R$ is upper triangular
* $S = Q\Lambda Q^T$
* Symmetric matrices
* $QQ^T = Q^TQ = I$
* $\Lambda$ is a diagonal eigenvalue matrix
* $Q$ has the eiganvectors in the columns
* 不是每個對稱矩陣都有足夠的 eigenvectors
* $\begin{split}S &= {\left[
\begin{array}{ccc}
q_1 & ... & q_n\\
\end{array}
\right]} {\left[
\begin{array}{ccc}
\lambda_1 \\
& ... \\
& & \lambda_n \\
\end{array}
\right]} {\left[
\begin{array}{c}
q_1^T \\
... \\
q_n^T \\
\end{array}
\right]} \\
&= {\left[
\begin{array}{ccc}
\lambda_1q_1 & ... & \lambda_nq_n\\
\end{array}
\right]} {\left[
\begin{array}{c}
q_1^T \\
... \\
q_n^T \\
\end{array}
\right]} \\
&= \text{sum of rank-1 matrices} \\
&= \lambda_1q_1q_1^T + ... + \lambda_nq_nq_n^T\end{split}$
* > 題外話，當我們將 $S$ 乘上 $q_1$，可以得到 $Sq_1 = \lambda_1q_1q_1^Tq_1 = \lambda_1q_1$
* $A = X\Lambda X^{-1}$
* $A = U\Sigma V^T$
* SVD
* 每個矩陣都能進行 SVD 分解

### LU

* 一般的 LU 分解：
* ${\left[
\begin{array}{cc}
2 & 3 \\
4 & 7 \\
\end{array}
\right]} = L{\left[
\begin{array}{cc}
2 & 3 \\
0 & 1 \\
\end{array}
\right]} \Rightarrow L = {\left[
\begin{array}{cc}
1 & 0 \\
2 & 1 \\
\end{array}
\right]}$
* 讓我們重新看 LU 的分解，如果今天將 2x2 的矩陣拆解成兩個 rank-1 matrices：
* ${\left[
\begin{array}{cc}
2 & 3 \\
4 & 7 \\
\end{array}
\right]} = {\left[
\begin{array}{cc}
2 & 3 \\
4 & ? \\
\end{array}
\right]} + {\left[
\begin{array}{cc}
0 & 0 \\
0 & ? \\
\end{array}
\right]} = {\left[
\begin{array}{cc}
2 & 3 \\
4 & 6 \\
\end{array}
\right]} + {\left[
\begin{array}{cc}
0 & 0 \\
0 & 1 \\
\end{array}
\right]}$
* 回想前面說的，每個矩陣乘法都能拆解成 sum of rank-1 matrices
* ${\left[
\begin{array}{cc}
2 & 3 \\
4 & 6 \\
\end{array}
\right]} + {\left[
\begin{array}{cc}
0 & 0 \\
0 & 1 \\
\end{array}
\right]} = {\left[
\begin{array}{c}
1 \\
2 \\
\end{array}
\right]} {\left[
\begin{array}{cc}
2 & 3 \\
\end{array}
\right]} + {\left[
\begin{array}{c}
0 \\
1 \\
\end{array}
\right]} {\left[
\begin{array}{cc}
0 & 1 \\
\end{array}
\right]} = {\left[
\begin{array}{c}
l_1 \\
\end{array}
\right]} {\left[
\begin{array}{cc}
u_1 \\
\end{array}
\right]} + {\left[
\begin{array}{c}
l_2 \\
\end{array}
\right]} {\left[
\begin{array}{c}
u_2 \\
\end{array}
\right]}$
* 每個 LU 分解都能透過這種方法得到：
* $A = {\left[
\begin{array}{c}
1\times pivot\ row_1 \\
l_{21}\times pivot\ row_1 \\
l_{31}\times pivot\ row_1 \\
l_{41}\times pivot\ row_1 \\
\end{array}
\right]} + {\left[
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & x & x & x \\
0 & x & x & x \\
0 & x & x & x \\
\end{array}
\right]} = A^{'}_1 + A^{'}_2$
* $A^{'}_1 = {\left[
\begin{array}{c}
1 \\
l_{21} \\
l_{31} \\
l_{41} \\
\end{array}
\right]}{\left[
\begin{array}{c}
row_1 \\
\end{array}
\right]} = l_1u_1^T$
* $A^{'}_2 = {\left[
\begin{array}{c}
0\times pivot\ row_2 \\
1\times pivot\ row_2 \\
l_{32}\times pivot\ row_2 \\
l_{42}\times pivot\ row_2 \\
\end{array}
\right]} + {\left[
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & x & x \\
0 & 0 & x & x \\
\end{array}
\right]} = A^{''}_2 + A^{'}_3$
* ...
* $A = l_1u_1^T + l_2u_2^T + l_3u_3^T + l_4u_4^T = LU$

## 4 Fundamental Subspaces

$A$ 是一個 $m\times n$ 的矩陣 (rank r)

* Column space $C(A)$, dim = r
* Row space $C(A^T)$, dim = r
* Null space $N(A)$, dim = n - r
* Null space $N(A^T)$, dim = m - r

### Null space

* a set of solutions to $Ax = 0$
* space 有一個基本性質：我可以對這個 space 中的向量做基本的線性運算，ex：加法，並且其結果仍然在這個 space 之中
* 我們將 $C(A^T)$ 與 $N(A)$ 放在一起，因為它們的維度都是 $R^n$，同樣的 $C(A)$ 與 $N(A^T)$ 放在一起
* 
* 先看 $C(A^T)$ 與 $N(A)$：
* 可以想像，今天有 r 個互相獨立的等式，並且有 n 個未知數，很明顯的，我們可以得到 n - r 組互相獨立的答案
* 接下來我們觀察為什麼要將這兩個 space 畫成垂直？下面舉一個 $m\times n$, r=1 的例子
* $A = {\left[
\begin{array}{ccc}
1 & 2 & 4 \\
2 & 4 & 8 \\
\end{array}
\right]}$
* $C(A^T) = {\left[
\begin{array}{c}
1 \\
2 \\
4 \\
\end{array}
\right]}$
* $Ax = 0 \Rightarrow N(A) = {\left[
\begin{array}{cc}
0 & 4 \\
-2 & 0 \\
1 & -1 \\
\end{array}
\right]}$
* 可以發現這兩個 space 是呈現 orthogonal 的關係！這是必然的，因為 $N(A)$ 是 $Ax = 0$ 的解，因此 $A$ 主中的每個 row 乘上 $N(A)$ 都會是 0
* 同理，$C(A)$ 與 $N(A^T)$ 也是呈現 orthogonal 的關係

## Orthogonal Matrix

* Tall thin matrices
* $Q$ with orthonormal columns
* $Q^TQ = I$
* 任何向量乘上 $Q$ 並不會改變其長度
* ${||Qx||}^2 = {(Qx)^TQx} = x^TQ^TQx = {||x||}^2$
* Orthogonal matrices
* 如果一個 tall thin matrix 又是 square matrix，則稱為 orthogonal matrix
* 對於一個 $n\times n$ 的 orthogonal matrix，$Q^TQ = QQ^T = I$
* 因此其 column 與 row 皆為 $R^n$ 的 orthonormal basis
* Projection matrices
* 透過投影矩陣 $P$ 將向量 $b$ 投影在空間 $A$ 上，其投影向量為 $p$
* $p$ 為 $C(A)$ 透過線性組成產生，$p = Ax$
* Normal equations:
* $A^T(b - p) = 0 \\
\Rightarrow A^T(b - Ax) = 0 \\
\Rightarrow x = {(A^TA)}^{-1}A^Tb \\
\Rightarrow p = A{(A^TA)}^{-1}A^Tb \\
\Rightarrow P = A{(A^TA)}^{-1}A^T$
* 若是投影到 line $a$
* $P = \frac{aa^T}{a^Ta}$
* 若是投影到 $Q$ orthogonal matrix
* $P = Q{(Q^TQ)}^{-1}Q^T = QQ^T$
* $QQ^T$ 為一種投影矩陣
* $p = QQ^Tb = {\left[
\begin{array}{cc}
q_1 & q_2 \\
\end{array}
\right]} {\left[
\begin{array}{c}
q_1^T \\
q_2^T \\
\end{array}
\right]} b = (q_1^Tb)q_1 + (q_2^Tb)q_2$
* 也就是說，透過 $QQ^T$ 投影，相當於個別投影到 C(Q) 的每個互相獨立的 colomn 後，再取向量和。
* Example of orthogonal matrices
* Rotation matrix: ${\left[
\begin{array}{cc}
cos\theta & -sin\theta \\
sin\theta & cos\theta \\
\end{array}
\right]}$
* Reflection matrix: ${\left[
\begin{array}{cc}
cos\theta & sin\theta \\
sin\theta & -cos\theta \\
\end{array}
\right]}$
* Householder reflection matrix: $H = H - 2uu^T, where ||u|| = 1$
* $H$ is a symmetric, orthogonal matrix
* $H$ mirrors any vector $w$ along the direction that is perpendicular to $u$