# 列空間、零解空間、及其基底

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, row_space_matrix, 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_R$ and $\beta_K$ be the standard bases of $\operatorname{Row}(A)$ and $\operatorname{ker}(A)$, respectively.
We have known that
1. $\operatorname{Row}(A) = \operatorname{span}(\beta_R)$.
2. $\operatorname{ker}(A) = \operatorname{span}(\beta_K)$.

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

Let $V$ be a subspace in $\mathbb{R}^n$ spanned by a finite set of vectors $S$.
Then we may find a basis of $V^\perp$ as follows.
1. Write the matrix $A$ whose rows are the vectors in the basis.
3. Calculate $\beta_K$ and it is a basis of $V^\perp$.

## Side stories
- basis of the orthogonal complement
- basis of a hyperplane

## Experiments

##### Exercise 1

執行下方程式碼。
令 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 為 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 最簡階梯形式矩陣。
令 $S = \{ {\bf r}_1, \ldots, {\bf r}_3 \}$ 為 $A$ 的各列向量﹐
而 $S' = \{ {\bf r}'_1, \ldots, {\bf r}'_3 \}$ 為 $R$ 的各列向量。

### code
set_random_seed(0)
print_ans = false
m,n,r = 3,5,2
A = random_good_matrix(m,n,r)
AI = A.augment(identity_matrix(m), subdivide=True)
RB = AI.rref()
B = RB[:,n:]

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

if print_ans:
    for i in range(m):
        print( "r'%s = "%(i+1) + " + ".join("%s u%s"%(B[i,k], k+1) for k in range(m)) )

藉由 `seed = 0` 得到

$$\left[\begin{array}{c|c} A & I \end{array}\right] = \left[\begin{array}{ccccc|ccc} 1 & -3 & 18 & 5 & -14 & 1 & 0 & 0\\3 & -8 & 49 & 15 & -39 & 0 & 1 & 0\\-8 & 20 & -124 & -40 & 100 & 0 & 0 & 1\end{array}\right].
$$

且

$$\left[\begin{array}{c|c} R & B \end{array}\right] = \left[\begin{array}{ccccc|ccc} 1 & 0 & 3 & 5 & -5 & 0 & -5 & -2\\0 & 1 & -5 & 0 & 3 & 0 & -2 & -3/4\\0 & 0 & 0 & 0 & 0 & 1 & -1 & -1/4\end{array}\right].
$$

##### Exercise 1(a)

將 $S'$ 中的每一個向量寫成 $S$ 的線性組合。

**Answer:**

${\bf r}_1' = 0{\bf r}_1 - 5{\bf r}_2 - 2{\bf r}_3$
${\bf r}_2' = 0{\bf r}_1 - 2{\bf r}_2 - 3/4{\bf r}_3$
${\bf r}_3' = 1{\bf r}_1 - 1{\bf r}_2 - 1/4{\bf r}_3$

##### Exercise 1(b)

令 $B$ 的第一列為 $(b_1, \ldots, b_3)$。
說明如果要把 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 的第一列寫成 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 各列的線性組合﹐
使用係數 $b_1, \ldots, b_3$ 是唯一的辦法。
更一般來說﹐說明 $BA = R$。

（提示：令 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 的各列為 ${\bf w}'_1, \ldots, {\bf w}'_3$、
而 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 的各列為 ${\bf w}_1, \ldots, {\bf w}_3$。
解 $x_1{\bf w}_1 + x_2{\bf w}_2 + x_3{\bf w}_3 = {\bf w}'_1$。
只要觀察這個方程式每個向量的最後幾項就好。）

**Answer:**

令 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 的各列為 ${\bf w}'_1, \ldots, {\bf w}'_3$，
且 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 的各列為 ${\bf w}_1, \ldots, {\bf w}_3$。
以上述矩陣為例，解 $x_1{\bf w}_1 + x_2{\bf w}_2 + x_3{\bf w}_3 = {\bf w}'_1$，
可得
$x_1 = b_1 = 0,x_2 = b_2 = -5,x_3 = b_3 = -2.$
這是因為$\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I \end{array}\right]$ 最簡階梯形式矩陣，
則 $A$ 和 $I$ 分別經由相同列運算得到 $R$ 和 $B$，
所以 $B$ 為此列運算之基本矩陣，
即 $BA = R$。
此時，$x_1,x_2,x_3$ 僅有唯一解 $b_1,b_2,b_3$，
使得 $b_1{\bf w}_1 + b_2{\bf w}_2 + b_3{\bf w}_3 = {\bf w}'_1$。

##### Exercise 1(c)

若 $A$ 是一個 $n\times n$ 矩陣。
而 $\left[\begin{array}{c|c} A & I_n \end{array}\right]$ 的最簡階梯形式矩陣是 $\left[\begin{array}{c|c} I_n & B \end{array}\right]$。
藉由上一小題的結果（再次）證明
若 $B$ 是 $n\times n$ 矩陣使得 $AB = I_n$﹐
則 $BA = I_n$。

**Answer 1:**

:::warning

- [x] 只證明到 $n=2$ 的部份
- [x] 題目可能沒寫清楚，但目標是證明
$AB = I_n$ $\Rightarrow$
$\left[\begin{array}{c|c} A & I_n \end{array}\right]$ 的最簡階梯形式矩陣是 $\left[\begin{array}{c|c} I_n & B \end{array}\right]$ $\Rightarrow$
$BA = I$
這題寫這樣就好：參考 [113-5](https://hackmd.io/X8UkX1_aRs6G2_LMmtBT3Q#Exercise-5)。
- [x] 所以將 $\left[\begin{array}{c|c} A & I_n\end{array}\right]$ 右乘 $B$ 進行相同列運算可得到 $\left[\begin{array}{c|c} I_n & B \end{array}\right]$ 。 --> 所以得知 $\left[\begin{array}{c|c} A & I_n\end{array}\right]$ 的最簡階梯形式為 $\left[\begin{array}{c|c} I_n & B \end{array}\right]$。
:::

令 $B$ 為 $n\times n$ 矩陣表示為
$$B = \begin{bmatrix}
| & ~ & | \\
\bb_1 & \cdots & \bb_n \\
| & ~ & | \\
\end{bmatrix}$$
並把 $AB=I_n$ 看成
$$A\begin{bmatrix}
| & ~ & | \\
\bb_1 & \cdots & \bb_n \\
| & ~ & | \\
\end{bmatrix}=\begin{bmatrix}
| & ~ & | \\
{\bf e}_1 & \cdots & {\bf e}_n \\
| & ~ & | \\
\end{bmatrix},
$$
也就是對任何 $i = 1,\ldots, n$ 都有 $A\bb_i = \be_i$。

所以得知 $\left[\begin{array}{c|c} A & I_n\end{array}\right]$ 的最簡階梯形式為 $\left[\begin{array}{c|c} I_n & B \end{array}\right]$。

再由上一小題的結果得知因為$\left[\begin{array}{c|c} I_n & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I_n \end{array}\right]$ 最簡階梯形式矩陣，

所以 $BA = I_n$。

因此若 $B$ 是 $n\times n$ 矩陣使得 $AB = I_n$﹐則 $BA = I_n$。

## Exercises

##### Exercise 2

執行以下程式碼。
其中 $R$ 是 $A$ 的最簡階梯形式矩陣。

### code
set_random_seed(0)
print_ans = False
m,n,r = 4,5,2
A = random_good_matrix(m,n,r)
R = A.rref()

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

if print_ans:
    print("A basis of the row space can be the set of rows of")
    show(row_space_matrix(A))
    print("A basis of the kernel can be the set of columns of")
    show(kernel_matrix(A))

藉由 `seed = 0` 得到
$$A =\begin{bmatrix}
1 & -3 & 18 & 5 & -14 \\
3 & -8 & 49 & 15 & -39 \\
-5 & 12 & -75 & -25 & 61\\2 & -4 & 26 & 10 &-22
\end{bmatrix}
$$
以及
$$R = \begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0
\end{bmatrix}.
$$
##### Exercise 2(a)

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

:::warning

- [x] $\beta_R$=\{$A$中對應的$\operatorname{pivots}$的列向量\} --> $\beta_R$ 為 $R$ 中的非零列向量所形成的集合
- [x] 中英數空格, see [風格指引](https://sagelabtw.github.io/LA-Tea/style.html)
- [x] 把那些數學式用 `aligned` 排好, see [風格指引](https://sagelabtw.github.io/LA-Tea/style.html
- [x] 下標不要粗體
:::

**Answer:**

令 $$
A = \begin{bmatrix} - & {\bf u}_1 & - \\
~ & \vdots & ~ \\ - & {\bf u}_m & - \\
\end{bmatrix}
$$

$$
R = \begin{bmatrix} - & {\bf r}_1 & - \\
~ & \vdots & ~ \\ - & {\bf r}_m & - \\
\end{bmatrix}
$$

已知 $\operatorname{Row}(A) = \operatorname{span}(\beta_R)$，$\beta_R$ 為 $R$ 中的非零列向量所形成的集合。

所以 $\beta_R = \{\br_1$,$\br_2\}$。

其中：
$$\begin{aligned}
\\&{\bf u}_1= {\bf r}_1-3{\bf r}_2
\\&{\bf u}_2=3{\bf r}_1-8{\bf r}_2\\
&{\bf u}_3=-5{\bf r}_1+12{\bf r}_2\\
&{\bf u}_4=2{\bf r}_1-4{\bf r}_2
\end{aligned}
$$
由運算得知 $A$ 中的所有列向量皆可由 ${\bf r}_1$,${\bf r}_2$ 組成。且我們可以從最簡階梯式知道 ${\bf r}_1$ , ${\bf r}_2$ 無法互相寫成彼此的線性組合，故 $\beta_R$ 為線性獨立。

所以 $\beta_R$ 為 $\operatorname{Row}(A)$ 的一組基底。

##### Exercise 2(b)

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

:::warning

- [x] 我已經不知道要說什麼了... $A$ 是 $4\times 5$，你的 $\ker(A)$ 應該是一群維度 $5$ 的向量集合
- [x] 然後你的 $R$ 是心情好就 $5\times 3$，然後想換就把它換成 $3\times 3$？
- [x] 中英數空格
- [x] columns --> 行
- [x] $ker$ --> $\ker$
- [x] 令 $R$ 的行為 ${X_1,X_2,...,X_5}$, 自由變數為 $X_3$,$X_4$,$X_5$ --> 由於 $R$ 上的自由變數為 $3$, $4$, $5$，我們可以將其中一個設為 $1$，其它的設為 $0$，來求出 $\beta_K$ 中的三個向量。因此 $\beta_K$ 為
$$\begin{bmatrix}
-3 & -5 & 5\\
5 & 0 & -3\\
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{bmatrix}
$$
中行向量所形成的集合。
:::

**Answer:**

由於 $R$ 上的自由變數為 $3$, $4$, $5$，我們可以將其中一個設為 $1$，其它的設為 $0$，來求出 $\beta_K$ 中的三個向量。

因此 $\beta_K$ 為

$$\begin{bmatrix}
-3 & -5 & 5\\
5 & 0 & -3\\
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{bmatrix}
$$
中行向量所形成的集合。

##### Exercise 3

令
$$A = \begin{bmatrix}
1 & -1 & 0 \\
1 & 0 & 1 \\
0 & 1 & -1 \\
\end{bmatrix}
$$
且 $S = \{{\bf r}_1,\ldots,{\bf r}_3\}$ 為其各列向量。
令 $V = \operatorname{span}(S)$，
求 $V^\perp$ 的一組基底。

:::warning

- [x] 用 LaTeX 打好你的數學式
- [x] 你的 $\beta_K$ 是錯的
:::

**Answer:**

因為 $S=\{{\bf r}_1,\ldots ,{\bf r}_3\}$， $V =\operatorname{span}\{{\bf 𝐫}_1,\ldots,{\bf 𝐫}_3\} = \operatorname{Row}(A)$。

所以 $V^\perp = \operatorname{Row}(A)^\perp = \ker(A)$，

所以 $\beta_K$ 為 $V^\perp$ 的基底。

$A$ 的最簡階梯型為

$$R =\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{bmatrix}.
$$

因為 $A$ 沒有自由變數，所以 $V^\perp$ 的基底 $\beta_K$ 為空集合。

##### Exercise 4

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

:::warning

- [x] 個人喜好：rref 不用進數學式
- [x] 粗體不要包含下標，比如說：${\bf u_3}$ --> $\bu_3$
- [x] 但是這題不是要你舉例，是要你說明對任何的 $A$ 來說 $\beta_R$ 都是獨立的。zero forcing 的部份要看上一小節，或是你可以像下一題說明 $\beta_R$ 中有 $I$。

經由上述的例子可以發現，在經過最簡階梯型後，對應到軸（pivotz）的那些行必定只有一個 $1$ 且其它項為 $0$。
如果 $R$ 中有 $r$ 個非零列，則它有 $r$ 個軸。
當軸產生的時候，使得每一列無法透過其他的列經過加減運算後得出相同的向量。換個方式想，在經過最簡階梯型的運算後，任何可以經由其他列加減組合而成的列，都會被還原成最初始、最簡單的列向量，則可知當 $\operatorname{Row}(R)$ 產生 $\beta_R$ 時，每個列是獨立的。
:::

**Answer:**
先看一個例子。

設 $A = \begin{bmatrix}
1 & 1 & 5 & 7 \\
-2& 1 &-6 &-9 \\
-1& 6 &-1 &-2
\end{bmatrix}.$

其中，${\bf u}_1=(1,1,5,7)$、${\bf u}_2=(-2,1,-6,9)$、${\bf u}_3=(-1,6,-1,-2)$。

觀察其最簡階梯型為

$R = \begin{bmatrix}
1 & 1 & 5 & 7 \\
0 & 3 & 4 & 5 \\
0 & 0 & 0 & 0
\end{bmatrix}.$

在 $\operatorname{Row}(A)$ 到 $\operatorname{Row}(R)$ 中，最簡階梯型的過程會使 $\operatorname{Row}(A)$ 的列變成獨立的。
而 ${\bf u}_3={\bf u}_1+{\bf u}_2$，卻在經過最簡階梯型後會變成 ${\bf 0}$ 向量，由此可見最簡階梯型會使原本的${\bf u}_1,{\bf u}_2,{\bf u}_3$變成線性獨立的列，又或者是 ${\bf 0}$ 列。

因為
$$\begin{bmatrix} - & {\bf u}_1 & -\\ - & {\bf u}_2 & -\\ - & {\bf u}_3 & -\\
\end{bmatrix},
$$
經由最簡階梯型形成
$$\begin{bmatrix} - & {\bf v}_1 & -\\ - & {\bf v}_2 & -\\ - & {\bf 0 } & -\\
\end{bmatrix}.
$$

此時 ${\bf v}_1$ 和 ${\bf v}_2$ 線性獨立
所以當 $c_1{\bf v}_1+c_2{\bf v}_2=0$ 時 $c_1=c_2=0$。

經由上述的例子可以發現，在經過最簡階梯型後，對應到軸（pivots）的那些行必定只有一個 $1$ 且其它項為 $0$。好比: \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}
如果 $R$ 中有 $r$ 個非零列，則它有 $r$ 個軸。
當軸產生的時候，使得每一列無法透過其他的列經過加減運算後得出相同的向量。換個方式想，在經過最簡階梯型的運算後，任何可以經由其他列加減組合而成的列，都會被還原成最初始、最簡單的列向量，則可知當 $\operatorname{Row}(R)$ 產生 $\beta_R$ 時，每個列是獨立的。

得 $\beta_R$ 是線性獨立的。

##### Exercise 5

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

:::warning

- [x] 由於 $ker(A)$ 向量中的自由變數是由$I_n$組成 --> 由於
$$
\begin{bmatrix}
| & ~ & | \\
\bh_1 & \cdots & \bh_n \\
| & ~ & | \\
\end{bmatrix}
$$
中包含一個子矩陣 $I_n$
- [x] 標點
- [x] rref 不要進數學
- [x] 下標不要粗體
:::

**Answer:**

當我們觀察 $A$ 的最簡階梯型 $R$ 時，會發現在轉變的過程中產生了領導變數和自由變數。
而為了求出 $\ker(A)$ 的解，
我們會找出自由變數{${x_1,...,x_n}$}，以 $I_n$ 帶入 $R$ 矩陣求出領導變數的值。
將產生:

$\ker(A)=$$\begin{bmatrix}| \\ {\bf h}_1 \\ | \end{bmatrix}$,...,$\begin{bmatrix}| \\ {\bf h}_n \\ | \end{bmatrix}$,

由於矩陣 $$\begin{bmatrix} | & & |\\ {\bf h}_1 & ... & {\bf h}_n\\ | & & |\\
\end{bmatrix}$$中包還一個子矩陣 $I_n$，
所以 $c_1{\bf h}_1+...+c_n{\bf h}_n=0$。

得 $\beta_k$ 是線性獨立的。

##### Exercise 6

令 $A$ 為一 $m \times n$ 矩陣。
若 $E$ 是一個 $m\times m$ 可逆矩陣且 $B = EA$。

##### Exercise 6(a)

證明 $\operatorname{Row}(A) = \operatorname{Row}(B)$。
（提示：可以把 $E$ 拆成基本矩陣當做列運算。
另一個方法是說明 $B$ 的每一列都可以 $A$ 的各列的線性組合，而且反之亦然。）

**[由林柏仰同學提供]**
若令
$$
A = \begin{bmatrix}
- & \br_1 & - \\
~ & \vdots & \\
- & \br_m & -
\end{bmatrix} 。
$$
$$
E = \begin{bmatrix}
e_{11} & \ldots & e_{1m} \\
\vdots & ~ & \vdots \\
e_{m1} & \ldots & e_{mm}
\end{bmatrix}。
$$
則因 $B = EA$ ，故 $B$ 可表示成
$$
B = \begin{bmatrix}
e_{11}\br_1 + e_{12}\br_2 + ... + e_{1m}\br_m \\
\vdots \\
e_{m1}\br_1 + e_{m2}\br_2 + ... + e_{mm}\br_m
\end{bmatrix}。
$$
可觀察到，$B$ 的每個列向量都是 $A$ 的所有列向量的線性組合。
換句話說， $\Row(A)\subseteq\Row(B)$ 。
同時，由於 $E$ 可逆，故 $B=EA$ 也可寫成 $E^{-1}B=A$。
故也可以同樣論證證明 $\Row(A)\supseteq\Row(B)$ 。
因為 $\Row(A)\subseteq\Row(B)$ 且 $\Row(A)\supseteq\Row(B)$ ，故 $\Row(A) = \Row(B)$ 。

##### Exercise 6(b)

證明以下敘述等價：
1. $A$ 的各列集合線性獨立。
2. $B$ 的各列集合線性獨立。
（提示：證明 $\operatorname{Col}(A)^\perp = \{{\bf 0}\}$ 和 $\operatorname{Col}(B)^\perp = \{{\bf 0}\}$ 等價。）

**[由林柏仰同學提供]**
若 $A$ 的列向量線性獨立，則 $A\trans$ 的行向量也為線性獨立。
若 $\bx = (x_1,\ldots,x_m)\in\ker(A\trans)$ ，則 $\bx$ 滿足 $A\trans\bx = \bzero$ 。
將此等式以矩陣乘法表示
$$
\bzero = A\trans\bx = \begin{bmatrix}
| & ~ & | \\
\br_1 & \ldots & \br_m \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
x_1 \\
\vdots \\
x_m
\end{bmatrix} =
x_1\br_1 + \cdots + x_m\br_m.
$$
矩陣 $A\trans$ 的行向量線性獨立的意思是：
只有當 $x_1 = x_2 = \cdots = x_m = 0$，才會滿足 $x_1\br_1 + x_2\br_2 + \ldots + x_m\br_m = \bzero$。
而 $\ker(A\trans) = \{\bzero\}$ 的意思是：
只有 $\bx = \bzero$，才會滿足 $A\trans\bx = \bzero$。
因此，「$A$ 的列集合線性獨立」和「$\ker(A\trans) = \{\bzero\}$」等價。

若 $\bx'\in\ker(B\trans)$，則 $B\trans\bx' = \bzero$。
因為 $B=EA$，故 $B\trans = (EA)\trans = A\trans E\trans$。
則 $\ker(B\trans)$ 中的向量 $\bx^{'}$ 也會滿足 $A\trans E\trans\bx' = {\bf 0}$ 。
由於 $\ker(A\trans) = \{\bzero\}$，我們知道 $E\trans\bx' = \bzero$。
又因 $E^{-1}$ 存在，且 $(E\trans)^{-1} = (E^{-1})\trans$，故 $(E\trans)^{-1}$ 也存在。
因此由 $E\trans\bx' = \bzero$ 可以推得 $\bx' = (E\trans)^{-1}\bzero = \bzero$。
所以得到結論 $\ker(B\trans) = \{{\bf 0}\}$；
換句話說，$B\trans$ 的行向量也就是 $B$ 的列向量為線性獨立。

而我們也可假設 $B$ 的列向量為線性獨立，並依同樣的過程求出 $A$ 的列向量也為線性獨立。
故 $A$ 的列向量為線性獨立等價於 $B$ 的列向量為線性獨立。

##### Exercise 6(c)

總結來說，
證明若 $A$ 的各列集合是 $\operatorname{Row}(A)$ 的一組基底，
則 $B$ 的各列集合也是 $\operatorname{Row}(A)$ 的一組基底。

:::warning

- [x] 自由變數設成多少不會改變 $\beta_R$
- [x] 所以 $EA = A$ <--- 為什麼
- [x] 這題要用 6(a), 6(b)
:::

**Answer:**
$\{\ba_1,\ldots,\ba_m\}$ 為 $A$ 的列向量，
$\{\bb_1,\ldots,\bb_m\}$ 為 $B$ 的列向量，

若 $\{\ba_1,\ldots,\ba_m\}$ 為 $\Row(A)$ 的基底，
則 $\vspan\{\ba_1,\ldots,\ba_m\}$ 等於 $\Row(A)$ 且線性獨立。
根據 6(a)，可以知道 $\Row(A) = \Row(B)$，
又根據 6(b)，可以知道 $\{\bb_1,\ldots,\bb_m\}$ 線性獨立，
由此可知 $B$ 的各列集合也是 $\Row(A)$ 的一組基底。

由於 $E$ 可逆，$A = E^{-1}B$。
所以類似的證明可以得到反向證的證明。

:::info
8/14題有錯，請想清楚每一步在做什麼

目前分數 4.5/5
:::