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

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

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\) 的一組基底。

答:
執行程式碼後得 \[ 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)\) 的一組基底。

答:
\(\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\) 的子集。
把這些子集分類﹐哪些是行空間的基底？哪些不是？

答:
將 \(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\) 是線性獨立的。

答:
令 \(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} \] 的列向量集合是線性獨立的。

答:
令 \(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 的方法並不適用。

答:
令 \(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\) 是線性獨立的。

答:
假設 \({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\)。
它們一樣嗎？

答:
令 \(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\)一樣。

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