---
# System prepended metadata

title: Highlights of Linear Algebra
tags: [學習筆記, Linear Algebra]

---

---
disqus: ierosodin
---

# Highlights of Linear Algebra

> Organization contact [name= [ierosodin](ierosodin@gmail.com)]
###### 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)$ 放在一起
 * ![](https://i.imgur.com/8znei24.png)
 * 先看 $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$