# 行空間、左零解空間、及其基底

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

from lingeo import random_good_matrix, column_space_matrix, left_kernel_matrix

## Main idea

You are recommended to read the section _Four fundamental subspaces_ first, where you will find the definition of $\beta_R$, $\beta_K$, $\beta_C$, $\beta_L$.

Let $A$ be a matrix.
Let $\beta_C$ and $\beta_L$ be the standard bases of $\operatorname{Col}(A)$ and $\operatorname{ker}(A^\top)$, respectively.
We have known that
1. $\operatorname{Col}(A) = \operatorname{span}(\beta_C)$.
2. $\operatorname{ker}(A^\top) = \operatorname{span}(\beta_L)$.

In fact, both $\beta_C$ and $\beta_L$ are linearly independent.
Therefore, it is fine that we call them the standard bases.

When $S$ is a finite set of vectors and $V = \operatorname{span}(S)$, we may find a basis of $V$ as follows.
1. Write the matrix $A$ whose columns are the vectors in $S$ (in any order).
2. Let $R$ be the reduced echelon form of $A$ and find the pivots of $R$.
3. Let $\beta_C$ be the columns of $A$ that corresponds to the pivots.

Thus, $\beta_C$ is a basis of $V$.

Let ${\bf b}$ be a vector in $\mathbb{R}^n$.
Let $V$ be a subspace in $\mathbb{R}^n$ spanned by a finite set of vectors $S$.
Then we may find the projection of ${\bf b}$ onto $V$ as follows.
1. Find a basis of $V$.
2. Write the matrix $A$ whose columns are the vectors in the basis.
3. The projection is $A(A^\top A)^{-1}A^\top {\bf b}$.

## Side stories
- projection
- basis with preferred vector

## Experiments

##### Exercise 1

執行下方程式碼。
令 $R$ 為 $A$ 最簡階梯形式矩陣。
令 $S= \{ {\bf u}_1, \ldots, {\bf u}_5 \}$ 為 $A$ 的各行向量且 $V = \operatorname{span}(S)$。

**[原筆記的程式碼有更新，請使用以下的程試碼]**

### code
### code
set_random_seed(0)
print_ans = False
m,n,r = 3,5,2
A, R, pivots = random_good_matrix(m,n,r, return_answer=True)
C = column_space_matrix(A)

print("A =")
show(A)
print("R =")
show(R)

if print_ans:
    print("A basis of V can be the set of columns of")
    show(C)
    free = [i for i in range(n) if i not in pivots]
    for f in free:
        print("u%s = "%(f+1) + " + ".join("%s u%s"%(R[j,f], pivots[j]+1) for j in range(r)) )

##### Exercise 1(a)

求 $V$ 的一組基底。

:::warning

- [x] 粗體不要包含下標，像是 ${\bf u_1}$ --> $\bu_1$ <-- 檢查全部
- [x] 而 $\bu_1$ 和 $\bu_4$ 是同樣的向量 --> 而 $\bu_1$ 和 $\bu_4$ 是平行的向量
:::

答:
執行程式碼後得
$$
A = \begin{bmatrix}
1 & -3 & 18 & 5 & -14 \\
3 & -8 & 49 & 15 & -39 \\
-8 & 20 & -124 & -40 & 100
\end{bmatrix}
$$
將 $A$ 進行列運算後得矩陣 $R$
$$R = \begin{bmatrix}
1 & 0 & 3 & 5 & -5\\
0 & 1 & -5 & 0 & 3\\
0 & 0 & 0 & 0& 0\\
\end{bmatrix}
$$
若令 $S'= \{ \bv_1, \ldots, \bv_5 \}$ 為 $R$ 的各行向量，則可透過運算得知
$$\bv_3 = 3\bv_1 - 5\bv_2, \bv_4 = 5\bv_1, \bv_5 = -5\bv_1 + 3\bv_2,
$$
因此得知 $A$ 的各行關係為
$${\bf u}_3 = 3{\bf u}_1 - 5{\bf u}_2 , {\bf u}_4 = 5{\bf u}_1 , {\bf u}_5 = {5\bf -u}_1 + 3{\bf u}_2.
$$
而 $\bu_1$ 和 $\bu_4$ 是平行的向量，則忽略掉 $\bu_4$ 後， $\bu_1$ 和 $\bu_2$ 可表示 $V$ 內的所有向量而 $\bu_1,\bu_2$ 無法被其他向量所表示。
換句話說， $\bu_1,\bu_2$ 為 $V$ 的一組基底。

##### Exercise 1(b)

把每個 $S$ 中不在基底裡的向量
寫成基底的線性組合。

答:
${\bf u}_3 = 3{\bf u}_1 - 5{\bf u}_2 , {\bf u}_4 = 5{\bf u}_1 , {\bf u}_5 = -5{\bf u}_1 + 3{\bf u}_2$。

## Exercises

##### Exercise 2

執行以下程式碼。
其中 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 的最簡階梯形式矩陣。

### code
set_random_seed(0)
print_ans = False
m,n,r = 4,5,2
A = random_good_matrix(m,n,r)
AI = A.augment(identity_matrix(m), subdivide=True)
RB = AI.rref()

print("[ A | I ] =")
show(AI)
print("[ R | B ] =")
show(RB)

if print_ans:
    print("A basis of the column space can be the set of columns of")
    show(column_space_matrix(A))
    print("A basis of the left kernel can be the set of rows of")
    show(left_kernel_matrix(A))

##### Exercise 2(a)

求出 $\operatorname{Col}(A)$ 的一組基底。

答:
執行程式碼後得
$$
\left[\begin{array}{c|c} A & I \end{array}\right]= \left[\begin{array}{ccccc|cccc}
1 & -3 & 18 & 5 & -14 & 1 & 0 & 0 & 0 \\
3 & -8 & 49 & 15 & -39 & 0 & 1 & 0 & 0 \\
-5 & 12 & -75 & -25 & 61 & 0 & 0 & 1 & 0 \\
2 & -4 & 26 & 10 & -22 & 0 & 0 & 0 & 1 \\
\end{array}\right]
$$
將 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 進行列運算後得 $\left[\begin{array}{c|c} R & B \end{array}\right]$
$$
\left[\begin{array}{c|c} R & B \end{array}\right] = \left[\begin{array}{ccccc|cccc}
1 & 0 & 3 & 5 & -5 & 0 & 0 & 1 & 3 \\
0 & 1 & -5 & 0 & 3 & 0 & 0 & \frac{1}{2} & \frac{5}{4} \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & \frac{1}{2} & \frac{3}{4} \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
\end{array}\right]
$$
若令 $S= \{ {\bf u}_1, \ldots, {\bf u}_5 \}$ 為 $A$ 的各行向量，則可透過運算得知 ${\bf u}_3 = {\bf 3u}_1 - {\bf 5u}_2 , {\bf u}_4 = {\bf 5u}_1 , {\bf u}_5 = {\bf -5u}_1 + {\bf 3u}_2$。
而 $\bu_1$ 和 $\bu_4$ 是平行的向量，則忽略掉 $\bu_4$ 後， $\bu_1$ 和 $\bu_2$ 可表示 $A$ 內的所有向量而 $\bu_1,\bu_2$ 無法被其他向量所表示。
換句話說， $$\begin{bmatrix}
1 & -3 \\
3 & -8 \\
-5 & 12 \\
2 & -4 \\
\end{bmatrix}$$ 為 $\Col(A)$ 的一組基底。

##### Exercise 2(b)

求出 $\operatorname{ker}(A^\top)$ 的一組基底。

:::warning

- [x] 為 $\operatorname{ker}(A^\top)$ 的一組基底 --> 的兩列組成 $\operatorname{ker}(A^\top)$ 的一組基底
:::

答:
$\operatorname{ker}(A^\top)$ 的基底為 $B$ 中的最後 $m-r$ 列，故 $\operatorname{ker}(A^\top)$ 為 $B$ 中的最後兩列，得
$$\begin{bmatrix}
1 & 0 & \frac{1}{2} & \frac{3}{4} \\
0 & 1 & 1 & 1 \\
\end{bmatrix}$$
的兩列組成 $\operatorname{ker}(A^\top)$ 的一組基底。

##### Exercise 3

令
$$A = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
-1 & 1 & 1 & 0 & 0 \\
0 & -1 & 0 & 1 & 0 \\
0 & 0 & -1 & -1 & 1 \\
0 & 0 & 0 & 0 & -1 \\
\end{bmatrix}
$$
而 $S = \{ {\bf u}_1, \ldots, {\bf u}_5 \}$ 為 $A$ 的各行向量。
集合 $S$ 有 $\binom{5}{3} = 10$ 個大小為 $3$ 的子集。
把這些子集分類﹐哪些是行空間的基底？哪些不是？

:::info
題目出錯，應該是問 $\binom{5}{4}$ 個大小為 $4$ 的子集。
不過就現行題目來說，你們答得沒錯~
:::

答:
將 $A$ 進行列運算可得 $R$
$$R = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & -1 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
$$
${\bf u}_4 = {\bf u}_3 - {\bf u}_2$。
${\bf u}_1$, ${\bf u}_2$, ${\bf u}_3$, ${\bf u}_5$ 可表示 $A$ 內的所有行向量。
換句話說，${\bf u}_1$, ${\bf u}_2$, ${\bf u}_3$, ${\bf u}_5$ 為 $\Col(A)$ 的基底。
所以在 $S$ 中大小為 $3$ 的子集沒有行空間的基底。
而$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 1 \\
0 & -1 & 0 \\
0 & 0 & -1 \\
0 & 0 & 0 \\
\end{bmatrix}
$$
$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & -1 & 1 \\
0 & 0 & -1 \\
0 & 0 & 0 \\
\end{bmatrix}
$$$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & 0 & 1 \\
0 & -1 & -1 \\
0 & 0 & 0 \\
\end{bmatrix}
$$$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & 0 & 0 \\
0 & -1 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$$$\begin{bmatrix}
1 & 0 & 0 \\
-1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$$$\begin{bmatrix}
0 & 0 & 0 \\
1 & 1 & 0 \\
-1 & 0 & 1 \\
0 & -1 & -1 \\
0 & 0 & 0 \\
\end{bmatrix}
$$$$\begin{bmatrix}
0 & 0 & 0 \\
1 & 1 & 0 \\
-1 & 0 & 0 \\
0 & -1 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$$$\begin{bmatrix}
0 & 0 & 0 \\
1 & 0 & 0 \\
-1 & 1 & 0 \\
0 & -1 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$$$\begin{bmatrix}
0 & 0 & 0 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & -1 & 1 \\
0 & 0 & -1 \\
\end{bmatrix}
$$
皆不是行向量的基底。

##### Exercise 4

令 $A$ 為一矩陣而 $R$ 為其最簡階梯形式矩陣。
考慮 $R$ 的軸﹐
令 $A_p$ 為 $A$ 中對應到軸的那些行所組成的矩陣、
令 $R_p$ 為 $R$ 中對應到軸的那些行所組成的矩陣。
（所以 $A_p$ 的各行向量就是 $\beta_C$。）

依序證明 $\operatorname{ker}(R_p) = \{ {\bf 0} \}$ 以及 $\operatorname{ker}(A_p) = \{ {\bf 0} \}$﹐
最後得到 $\beta_C$ 是線性獨立的。

:::warning
不須要改，但
因 $A_p,R_p$ 分別為從 $A,R$ 中擷取特定行所形成的矩陣，故若對 $A_p$ 進行列運算可得到 $R_p$。
這句話只有在取軸上的行的時候才會對。

比如說
$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 2 & 2 \\
1 & 1 & 3 & 3 \\
\end{bmatrix}
\xrightarrow{\text{rref}}
R = \begin{bmatrix}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}
$$
你會發現 $A$ 的三四行做出來的 rref 並不是 $R$ 的三四行。

- [x] 最後一段：${\bf u_1, u_2,...,u_k}$ --> $\bu_1, \bu_2,\ldots,\bu_k$
:::

:::success
這題寫得很完整喔！
Good job!
:::

答:
令 $A$ 為一 $m\times n$ 的矩陣而 $R$ 為其最簡階梯形式矩陣。
若將 $A$ 的每一列表示成向量 $\{\br_1,\ldots,\br_m\}$。
則因 $R$ 為 $A$ 進行列運算得來，故 $R$ 的每一列皆可表示成 $c_1\br_1 + c_2\br_2 + ... + c_m\br_m$ 的形式。
因此將 $R$ 和 $\ker(A)$ 中的所有向量相乘皆會得到 ${\bf 0}$。
換句話說， $\ker(A)\in\ker(R)$ ，而以同樣方式也可證明 $\ker(R)\in\ker(A)$ ，故 $\ker(A) = \ker(R)$ 。

而今令 $A_p$ 為 $A$ 中對應到軸的那些行所組成的矩陣、$R_p$ 為 $R$ 中對應到軸的那些行所組成的矩陣。
因 $A_p,R_p$ 分別為從 $A,R$ 中擷取特定行所形成的矩陣，故若對 $A_p$ 進行列運算可得到 $R_p$。
由上方結論我們可知 $\ker(A_p) = \ker(R_p)$ 。
因 $R_p$ 為從 $R$ 中擷取出對應到軸的那些行所形成的矩陣，故 $R_p$ 的每一行都只有一個位置是非零的，且每一行非零的項皆不同，其餘皆為零。
若 $R_p$ 為一 $m\times k$ 的矩陣。
則此時假設一向量 $\bx = (x_1,x_2,...,x_k)$ 且 $\bx\in\ker(R_p)$ 。
我們會發現只有當 $x_1 = x_2 = ... = x_k = 0$ 時，此向量才會在 $\ker(R_p)$ 裡面。
換句話說 $\ker(A_p) = \ker(R_p) = \{ {\bf 0} \}$。

而由於 $A_p$ 中的各行向量為 $A$ 中對應到軸的向量，故 $A_p$ 相當於 $\beta_C$ 。
今若 $\beta_C$ 不是線性獨立，則可將 $A_p$ 的各行依序看成向量 ${\bu_1,\bu_2,...,\bu_k}$ 且其中至少有一個向量可寫成其餘向量各自乘以一純量的形式。
若以 $u_1$ 為例: $\bu_1 = a_2\bu_2 + a_3\bu_3 + ... + a_k\bu_k$。
這表示 $1\bu_1 - a_2\bu_2 - a_3\bu_3 - ... - a_k\bu_k = {\bf 0}$。
換句話說 $(1,-a_2,-a_3,...,-a_k)\in\ker(A_p)$ ，但此與我們先前的結論 $\ker(A_p) = \{ {\bf 0} \}$ 相違背。
因此我們可知 $\beta_C$ 為線性獨立。

##### Exercise 5

若 $S = \{ {\bf u}_1, \ldots, {\bf u}_k \}$ 為一群 $\mathbb{R}^n$ 中的向量。
在某些比較簡單的狀況下﹐我們可以用以下的過程來說明 $S$ 是一個線性獨立集。
1. 令 $S' = S$。
2. 若 $j = 1,\ldots, n$ 中有一個足標﹐使得 $S'$ 中的每個向量的第 $j$ 項都是零﹐除了 ${\bf u}_i$ 的第 $j$ 項不是零﹐則把 ${\bf u}_i$ 從 $S'$ 中拿掉。
3. 重覆步驟 2﹐如果最後可以把所有向量都拿掉的話﹐則 $S$ 是一個線性獨立集。

這個方法稱作 zero forcing。

##### Exercise 5(a)

利用 zero forcing 的方法﹐
說明
$$ A = \begin{bmatrix}
1 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 \\
\end{bmatrix}
$$
的列向量集合是線性獨立的。

:::success
Nice work!
不過 $A$ 不用粗體
:::

答:
令 $S = \{ {\bf r}_1, {\bf r}_2, {\bf r}_3, {\bf r}_4\}$ 為矩陣 $A$ 的各列向量。
利用 zero forcing 可以先後將 ${\bf r}_3,{\bf r}_2,{\bf r}_4,{\bf r}_1$ 拿掉，可以得到 $0{\bf u}_1+0{\bf u}_2+0{\bf u}_3+0{\bf u}_4={\bf 0}$。
可以發現符合線性獨立的定義，係數都是0，因此得證 ${A}$ 的列向量集合是線性獨立。
##### Exercise 5(b)

說明
$$ A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
\end{bmatrix}
$$
的列向量集合是線性獨立的﹐
但 zero forcing 的方法並不適用。

:::warning

- [x] 矩陣不用粗體
:::

答:
令 $S = \{ {\bf r}_1, {\bf r}_2, {\bf r}_3 \}$ 為矩陣 $A$ 的各列向量。
${A}$ 的最簡階梯式 $${R} = \begin{bmatrix}
1 & 0 & 0 & 6 \\
0 & 1 & 0 & -11 \\
0 & 0 & 1 & 6 \\
\end{bmatrix}，$$我們可以從最簡階梯式知道 ${\bf r}_1,{\bf r}_2,{\bf r}_3$ 無法寫成彼此的線性組合，因此 ${A}$ 的列向量集合是線性獨立的。

但如果使用 zero forcing 方法求證 ${A}$ 是否線性獨立，將 ${A}$ 使用 zero forcing 後，發現無法找到可以拿掉的向量，無法證明線性獨立。

##### Exercise 6

利用 zero forcing 的方法來說明 $\beta_L$ 是線性獨立的。

:::warning

- [x] 一樣，矩陣不用粗體
- [x] $\vspan(I)$ --> $\Col(I_m)$ 因為 $\vspan$ 裡要是一群向量，而不是一群矩陣
:::

答:
假設 ${A}$ 是一個 $m\times n$ 的矩陣，${I}$ 是一個 $m\times m$ 的基本矩陣，而 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 為 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 的最簡階梯型的矩陣。

因為此時 $I$ 為一 $m\times m$ 的基本矩陣，故若將 $I_m$ 中的每一行依序看成向量 ${\bf i}_1, {\bf i}_2, \ldots, {\bf i}_m$ ，這些向量中任一向量都無法寫成其餘向量各乘以一純量相加的樣式。
因此，$\Col(I)$ 可以張出 $\mathbb{R}^m$。
而因 $\Col(I)\subseteq\Col([A|I])$ ，故此時若將 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 寫成最簡階梯型矩陣 $\left[\begin{array}{c|c} R & B \end{array}\right]$ ， $\left[\begin{array}{c|c} R & B \end{array}\right]$ 總共會有 $m$ 個軸。
則此時若有 $h$ 個軸位於 $R$ 的位置，將會有 $m-h$ 個軸位於 $B$ 上。
而 $\beta_L$ 為 $B$ 中對應到 $R$ 中所有非零列之下的列，且 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 為最簡階梯型矩陣，故 $\beta_L$ 中有 $m-h$ 個軸。

假設 $\operatorname{span}(\beta_L) = \{ {\bf b}_1,{\bf b}_2, \ldots, {\bf b}_{m-h} \}$ ，因此可以使用 zero forcing 依序拿掉 ${\beta_L}$ 的各向量，得到 $0{\bf b}_1+0{\bf b}_2+\ldots+0{\bf b}_{m-h}={\bf 0}$，符合線性獨立定義，證明 ${\beta_L}$ 線性獨立。

##### Exercise 7

令
$$A = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
-1 & 1 & 1 & 0 & 0 \\
0 & -1 & 0 & 1 & 0 \\
0 & 0 & -1 & -1 & 1 \\
0 & 0 & 0 & 0 & -1 \\
\end{bmatrix}$$
而 $S = \{ {\bf u}_1, \ldots, {\bf u}_5 \}$ 為 $A$ 的各行向量。
令 $A'$ 是把 $A$ 中第一列和第三列互換所得的矩陣。
因此 。
計算 $A$ 和 $A'$ 各自算出來的 $\beta_C$。
它們一樣嗎？

:::warning

抱歉又是我寫錯... 應該是第一行和第四行互換。
就結論來說，如果拿 $A$ 去做列運算的話，
取得的基底 $\beta_C = \{\bu_1, \bu_2, \bu_3, \bu_5\}$。
然而在把第一行和第四行互換以後，
得到的 $A'$ 再去做列運算，
會得到另外一組基底 $\beta_C = \{\bu_1, \bu_2, \bu_4, \bu_5\}$。
因此取 $\beta_C$ 的這個做法對排在愈左邊的行向量優先加入基底中。
:::

答:
令 $R$ 為矩陣 $A$ 的最簡階梯形式矩陣。
經高斯消去法，我們可以得到
$$R = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & -1 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}。$$
另一方面，
我們也可令 $R'$ 為矩陣 $A'$ 的最簡階梯形式矩陣。
得知
$$R' = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & -1 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}。$$
由此我們可以知道，兩者的基底皆為向量 $(1,-1,0,0,0)，(0,1,-1,0,0)，(0,1,0,-1,0)，(0,0,0,1,-1)$，
故 $A$ 和 $A'$ 各自算出來的 $\beta_C$一樣。

（這個例子說明如果想把確保某一個非零向量有被選到基底中﹐
只要把它放在第一行再做高斯消去法就好。）

:::info

目前分數 6.5/5
:::