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

Column space, left kernel, and their bases

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

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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 $\Col(A)$ and $\ker(A\trans)$, respectively.
We have known that
1. $\Col(A) = \vspan(\beta_C)$.
2. $\ker(A\trans) = \vspan(\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 = \vspan(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 $\bb$ 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 $\bb$ 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\trans A)^{-1}A\trans \bb$.

## Side stories
- projection
- basis with preferred vector

## Experiments

##### Exercise 1

執行下方程式碼。
令 $R$ 為 $A$ 最簡階梯形式矩陣。
令 $S= \{ \bu_1, \ldots, \bu_5 \}$ 為 $A$ 的各行向量且 $V = \vspan(S)$。

<!-- eng start -->
Run the code below. Let $R$ be the reduced echelon form of $A$. Let $S= \{ \bu_1, \ldots, \bu_5 \}$ be the columns of $A$ and $V = \vspan(S)$.
<!-- eng end -->

### 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$ 的一組基底。

<!-- eng start -->
Find a basis of $V$.
<!-- eng end -->

:::warning

- [x] we know $\bu_1$, $\bu_2$, the vectors corresponding to the pivots, are independent (boldface, and add explanation)
- [x] $\bu_3$, $\bu_4$, $\bu_5$ might not be dependent --- think about why.
- [x] Add a period in the end.
:::

**Answer**
Run the code above, we can get
$$
A = \begin{bmatrix}
1 & -3 & 18 & 5 & -14\\
3 & -8 & 49 & 15 & -39\\
-8 & 20 & -124 & -40 & 100\\
\end{bmatrix}
$$
Let $R$ be the row reduced echelon form of $A$.
$$
R = \begin{bmatrix}
1 & 0 & 3 & 5 & -5\\
0 & 1 & -5 & 0 & 3\\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
$$
Let $S= \{ \bu_1, \ldots, \bu_5 \}$ be the columns of $A$ and $V = \vspan(S)$.
According to reduced echelon form of $A$, we know $\bu_1$,$\bu_2$, the vectors corresponding to the pivots, are linealy independent because the only coefficients $c_1, c_2\in\mathbb{R}$ satisfying$c_1\bu_1$ + $c_2\bu_2$ = $\bzero$
is $c_1 = c_2 = 0$.

Let $\beta_C$ be the standard bases of $\Col(A)$.
$\beta_C$ is the basis of $V$.
So the basis of $V$ can be the set of columns of

$$
\begin{pmatrix}
1 & -3\\
3 & -8\\
-8 & 20\\
\end{pmatrix}.
$$

##### Exercise 1(b)

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

<!-- eng start -->
For any vector in $S$ but not in your basis in the previous problem, write it as a linear combination of the basis.
<!-- eng end -->

:::warning

- [x] Make vectors boldface.
- [x] Put equations into the math mode `$...$`.
:::

**Answer**

$$
\bu_3 = \begin{bmatrix}
3 \\
-5 \\
0 \\
\end{bmatrix},
\bu_4 = \begin{bmatrix}
5 \\
0 \\
0 \\
\end{bmatrix},
\bu_5 = \begin{bmatrix}
-5 \\
3 \\
0 \\
\end{bmatrix}
$$

$$
\bu_3 = 3\bu_1 - 5\bu_2\\
\bu_4 = 5\bu_1 \\
\bu_5 = -5\bu_1 + 3\bu_2
$$

## Exercises

##### Exercise 2

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

<!-- eng start -->
Run the code below. Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be the reduced echelon form $\left[\begin{array}{c|c} A & I \end{array}\right]$.
<!-- eng end -->

### 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)

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

<!-- eng start -->

Find a basis of $\Col(A)$.
<!-- eng end -->

:::warning

- [x] Revise according to the comments in 1(a).
:::

**Answer**

$$
A=\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]
\xrightarrow{\text{rref}}
R = \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{4}{5}\\
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]$$

Let $S= \{ \bu_1, \ldots, \bu_5 \}$ be the columns of $A$ and $V = \vspan(S)$.
According to reduced echelon form of $A$,
we know $\bu_1$,$\bu_2$ are independent, the vectors corresponding to the pivots,
and the only solution of equation
$c_1\bu_1$ + $c_2\bu_2$ = $\bzero$, where $c_1, c_2\in\mathbb{R}$ is coefficients $c_1=c_2=0.$

So one of the basis of $V$ can be the set of columns of
$$\vspan\left\{
\begin{bmatrix}
1 \\
3 \\
-5 \\
2 \\
\end{bmatrix},
\begin{bmatrix}
-3\\
-8\\
12\\
-4\\
\end{bmatrix}
\right\}.
$$

##### Exercise 2(b)

求出 $\ker(A\trans)$ 的一組基底。

<!-- eng start -->
Find a basis of $\ker(A\trans)$.
<!-- eng end -->

:::warning

Nice work! :thumbsup:

However, please add some explanations about how you find the two vectors ($\bh_1$, $\bh_2$) for $\ker(A\trans)$.

- [x] $span$ --> $\vspan$
- [x] basic --> basis
:::

**Answer**

Since $A$ is a $4\times 5$ matrix , $A\trans$ is a $5\times 4$ matrix.

$$
A\trans=\begin{bmatrix}
1 & 3 & -5 & 2 \\
-3 & -8 & 12 & -4 \\
18 & 49 & -75 & 26 \\
5 & 15 & -25 & 10 \\
-14 & -39 &61 &-22 \\
\end{bmatrix}
\xrightarrow{\text{rref}}
R = \begin{bmatrix}
1 & 0 & 4 & -4 \\
0 & 1 &-3 & 2 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}
$$

Then we may find the standard basis of $\ker(A\trans)$ as

$$
\left\{
\begin{bmatrix}
-4\\
3\\
1\\
0
\end{bmatrix},
\begin{bmatrix}
4\\
-2\\
0\\
1\\
\end{bmatrix}\right\}
.
$$

##### 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 = \{ \bu_1, \ldots, \bu_5 \}$ 為 $A$ 的各行向量。
集合 $S$ 有 $\binom{5}{4} = 5$ 個大小為 $4$ 的子集。
把這些子集分類﹐哪些是行空間的基底？哪些不是？

<!-- eng start -->
Let

$$
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}
$$

and $S = \{ \bu_1, \ldots, \bu_5 \}$ the columns of $A$. The set $S$ contains $\binom{5}{4} = 5$ subsets of size $3$. For each of them, determine if it is a basis of $\Col(A)$ or not.
<!-- eng end -->

:::warning

- [x] $\bu_1,\bu_5$ is independent --> $\bu_1,\bu_5$ cannot be a linear combination of other vectors
- [x] A set must have the symbol $\{ ... \}$.
- [x] We only need to get $2$ basis from $\bu_2,\bu_3,\bu_4$ we can get all three of them --> We only need to pick two vectors from $\{\bu_2, \bu_3, \bu_4\}$ to form an independent set.
- [x] is a basis --> are bases
- [x] But --> , but
- [x] isn't --> aren't

:::

$Ans:$
$\bu_1=\begin{bmatrix}
1 \\
-1\\
0 \\
0 \\
0 \\
\end{bmatrix}$ ,
$\bu_2=\begin{bmatrix}
0 \\
1 \\
-1\\
0 \\
0 \\
\end{bmatrix}$,
$\bu_3=\begin{bmatrix}
0 \\
1 \\
0 \\
-1\\
0 \\
\end{bmatrix}$,
$\bu_4=\begin{bmatrix}
0 \\
0 \\
1 \\
-1\\
0 \\
\end{bmatrix}$ ,
$\bu_5=\begin{bmatrix}
0 \\
0 \\
0 \\
1\\
-1 \\
\end{bmatrix}$

We can observe that $\bu_4=\bu_3-\bu_2$, and $\bu_1,\bu_5$ cannot be a linear combination of other vectors (the first entry is only from $\bu_1$ and the last entry is only from $\bu_5$).
We only need to pick two vectors from $\{\bu_2, \bu_3, \bu_4\}$ to form an independent set.
So we can know that $\{\bu_1,\bu_2,\bu_3,\bu_5\}$, $\{\bu_1,\bu_2,\bu_4,\bu_5\}$, $\{\bu_1,\bu_3,\bu_4,\bu_5\}$ are bases of $\Col(A)$
but $\{\bu_2,\bu_3,\bu_4,\bu_5\}$, $\{\bu_1,\bu_2,\bu_3,\bu_4\}$ aren't.

##### Exercise 4

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

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

<!-- eng start -->
Let $A$ be a matrix and $R$ its reduced echelon form. Let $A_p$ be the submatrix of $A$ induced on the columns corresponding to the pivots of $R$. Let $R_p$ be the submatrix of $R$ induced on the columns of its pivots. (Therefore, the columns of $A_p$ form $\beta_C$.)

Show that $\ker(R_p) = \{ \bzero \}$ and $\ker(A_p) = \{ \bzero \}$. Use these facts to prove that $\beta_C$ is linearly independent.
<!-- eng end -->

##### Exercise 5

若 $S = \{ \bu_1, \ldots, \bu_k \}$ 為一群 $\mathbb{R}^n$ 中的向量。
在某些比較簡單的狀況下﹐我們可以用以下的過程來說明 $S$ 是一個線性獨立集。

1. 令 $S' = S$。
2. 若 $j = 1,\ldots, n$ 中有一個足標﹐使得 $S'$ 中的每個向量的第 $j$ 項都是零﹐除了 $\bu_i$ 的第 $j$ 項不是零﹐則把 $\bu_i$ 從 $S'$ 中拿掉。
3. 重覆步驟 2﹐如果最後可以把所有向量都拿掉的話﹐則 $S$ 是一個線性獨立集。

這個方法稱作 **zero forcing** 。

<!-- eng start -->
Let $S = \{ \bu_1, \ldots, \bu_k \}$ be some vectors in $\mathbb{R}^n$. In some special cases, we may use the following process to show that $S$ is linearly independent.

1. Let $S' = S$.
2. If for some $j = 1,\ldots, n$, every vector in $S'$ has its $j$-th entry zero except for one vector $\bu_i$ with its $j$-th entry nonzero, then remove $\bu_i$ from $S'$.
3. Repeat Step 2. If there is a way to remove all vectors, then $S$ is a linearly independent set.

This process is called **zero forcing** .
<!-- eng end -->

##### 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}
$$

的列向量集合是線性獨立的。

<!-- eng start -->
Use zero forcing to show that the rows of

$$
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}
$$

form a linearly independent set.
<!-- eng end -->

##### Exercise 5(b)

說明

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
\end{bmatrix}
$$

的列向量集合是線性獨立的﹐
但 zero forcing 的方法並不適用。

<!-- eng start -->
Verify that the rows of

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
\end{bmatrix}
$$

form a linearly independent set, but zero forcing fails to show the independence.
<!-- eng end -->

:::warning

You did not explain why the zero forcing technique does not apply --- you may present your answer at the comprehension meeing.

Do you mean the set of ==row== vectors?

- [x] A --> $A$
:::

**Answer**
Let $S = \{ {\bf u}_1, {\bf u}_2, {\bf u}_3 \}$ be three vectors in $\mathbb{R}^n$.
$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 6 \\
\end{bmatrix}
\xrightarrow{\text{rref}}
R = \begin{bmatrix}
1 & 0 & 0 & 6 \\
0 & 1 & 0 & -11 \\
0 & 0 & 1 & 6 \\
\end{bmatrix}
$$
Because ${\bf u}_1,{\bf u}_2,{\bf u}_3$ cannot be written as linear combinations of each other, the set of row vectors of $A$ is linearly independent.

##### Exercise 6

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

<!-- eng start -->
Use zero forcing to show that $\beta_L$ is linearly independent.
<!-- eng end -->

##### 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 = \{ \bu_1, \ldots, \bu_5 \}$ 為 $A$ 的各行向量。
令 $A'$ 是把 $A$ 中第一行和第四行互換所得的矩陣。
因此 $\Col(A) = \Col(A')$。
計算 $A$ 和 $A'$ 各自算出來的 $\beta_C$。
它們一樣嗎？

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

<!-- eng start -->
Let

$$
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}
$$

and $S = \{ \bu_1, \ldots, \bu_5 \}$ the columns of $A$. Let $A'$ be the matrix obtained from $A$ by switching the first column and the fourth column. Thus, $\Col(A) = \Col(A')$. Find the $\beta_C$ for $A$ and for $A'$, respectively. Are they the same?

This example shows that if we wish a column to be selected into the basis of the column space, then we may put it as the first column and then run the Gaussian elimination.
<!-- eng end -->

:::info
collaboration: 1
4 problems: 4

bonus: 1 (nice answer from 2(b))

moderator: 1
quality control: 1
:::