# Null space 的通靈算法
以下假設 $A$ 是一個矩陣，$R$ 是 $A$ 的 rref，$x$ 是向量。
## 先備知識
1. $Ax=0$ 跟 $Rx=0$ 有一樣的解。
2. 矩陣乘向量就是把矩陣的 columns 作 linear combination，係數就是那個向量。e.g. $$\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = x \begin{bmatrix}a\\c\end{bmatrix}+y\begin{bmatrix}b\\d\end{bmatrix}$$

## 用眼睛算 null space
如果是 full rank 那當然沒有 null space。如果不是，就會有 $x\neq 0$ 使得 $Rx=0$。$Rx=0$ 表示 $R$ 裡面有一些 columns 可以線性組合成 $0$，係數就是 $x$ 。

一個非常神奇的觀察是，雖然列運算會改變column space，但是不會改變 columns 之間的關係。所以這組使得 $R$ 的 columns 組合成 $0$ 的係數也可以讓 $A$ 對應的 columns 組合成 $0$。原因就是因為 $Rx=0$ 跟 $Ax=0$ 有一樣的解。

把 rref 求出來之後，每一個 non pivot column 裡面的數字，就是它被 pivot columns 組合的係數，每一組這樣的係數都對應到一個 basis 的向量。

下面給出一個例子，這個例子是抄[線代啟示錄：零空間的快捷算法](<https://ccjou.wordpress.com/2013/12/27/%E9%9B%B6%E7%A9%BA%E9%96%93%E7%9A%84%E5%BF%AB%E6%8D%B7%E7%AE%97%E6%B3%95/>)的。

以下我們用 $R_i$ 表示 $R$ 的第 $i$ 行。
$$R=\begin{bmatrix}
1&4&0&1&-3&0\\
0{}& 0{}& 1{}& -1{}& 2{}& 0\\
0{}& 0{}& 0{}& 0{}& 0{}& 1\\
0{}& 0{}& 0{}& 0{}& 0{}& 0
\end{bmatrix}$$
因為第二行是第一行乘 4 ，很明顯可以看出 $(-4)$ 倍的第一行加 $1$ 倍的第二行可以組合成 $0$，i.e. $R_2=4R_1$，which implies that $-4R_1+R_2=0$ ，所以 $$
\begin{bmatrix}-4\\1\\0\\0\\0\\0\end{bmatrix}
$$ 一定是基底的一個向量。

再來是第四行，它可以被第一跟第三行組合出來，係數是 $(1,-1)$，我們有 $-R_1+R_3+R_4=0$ ，所以下一個基底的向量是

$$
\begin{bmatrix}-1\\0\\1\\1\\0\\0\end{bmatrix}
.$$

最後一個 non pivot column 是第五行，明顯地我們有 $3R_1-2R_3+R_5=0$，所以最後一個基底的向量是
$$
\begin{bmatrix}3\\0\\-2\\0\\1\\0\end{bmatrix}
.$$
如此你就可以在辛苦的求出 rref 之後馬上寫出 null space 了 ><

## 還可以做什麼用

假設你現在有一坨線性獨立的向量，給你另一個向量，你可以用這個方法超快算出 linear combination 的係數。

比如 $S=\{(1,1),(1,-1)\}$，要求 $S$ 組合出 $(2,4)$ 的係數，考慮
$$\begin{bmatrix}1&1&2\\ 1&-1&4 \end{bmatrix}\to \begin{bmatrix} 1&0&3\\0&1&-1\end{bmatrix}$$
由此可得 3rd column 可以被 3 倍的 1st column 跟 $-1$ 倍的 2nd column 組合出來，所以我們有
$$(2,4) = 3 (1,1) - (1,-1)$$

###### tags: `LA`