# 四大基礎子空間

Four fundamental subspaces

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, random_int_list

## Main idea

Recall that if $V$ is a subspace in $\mathbb{R}^n$, then its orthogonal complement is
$$V^\perp = \{\bw\in\mathbb{R}^n : \inp{\bw}{\bv} = 0 \text{ for all }\bv\in V\}.$$

Suppose $V = \vspan(S)$ for some finite set $S$.
(We will show in the next chapter that in fact every subspace in $\mathbb{R}^n$ can be generated by a finite set.)
Then every matrix $\bb$ can be written as a unique representation
$$\bb = \bw + \bh$$
such that $\bw\in V$ and $\bh\in V^\perp$.
Also, $(V^\perp)^\perp = V$.

Let $A$ be an $m\times n$ matrix.
Let $R$ be the reduced echelon form of $A$ and $r$ the number of its pivots.
Consider the augmented matrix $\left[\begin{array}{c|c} A & I_m \end{array}\right]$.
Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be its reduced echelon form.

Then $\Row(A)$ and $\ker(A)$ are subspaces in $\mathbb{R}^n$ and they are the orthogonal complement of each other.

Let $\beta_R = \{\br_1,\ldots,\br_r\}$ be the set of nonzero rows in $R$.
Then $\Row(A) = \vspan(\beta_R)$.

Let $\beta_K = \{\bh_1, \ldots, \bh_{n-r}\}$ be the set of homogeneous solutions solved by setting one free variable as $1$ and others as $0$.
Then $\ker(A) = \vspan(\beta_K)$.

On the other hand, $\Col(A)$ and $\ker(A\trans)$ are subspaces in $\mathbb{R}^m$ and they are the orthogonal complement of each other.
The subspace $\ker(A\trans)$ is called the **left kernel** of $A$.

Let $\beta_C = \{ \bu_1,\ldots, \bu_r \}$ be the set of columns of $A$ corresponding to the pivots of $R$.
Then $\Col(A) = \vspan(\beta_C)$.

Let $\beta_L = \{ \bb_1,\ldots,\bb_{m-r} \}$ be the last $m-r$ rows in $B$.
Then $\ker(A\trans) = \vspan(\beta_L)$.

We call each of $\beta_R$, $\beta_K$, $\beta_C$, $\beta_L$ the **standard basis** of the corresponding subspace.
(We have not yet mentioned what is a basis, so you may view them as standard generating sets of the corresponding subspaces.
But we will prove they are really a basis in the future.)

## Side stories
- generator of $V^\perp$

## Experiments

##### Exercise 1

執行下方程式碼。
矩陣 $\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 of $\left[\begin{array}{c|c} A & I \end{array}\right]$.
<!-- 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)

AI = A.augment(identity_matrix(3), subdivide=True)
RB = AI.rref()
B = RB[:,n:]
print("[ A | I ] =")
show(AI)
print("[ R | B ] =")
show(RB)

if print_ans:
    Rp = R[:r,:] ### r x n
    H = zero_matrix(Rp.base_ring(), n, n-r) ### n x (n-r)
    free = [i for i in range(n) if i not in pivots]
    H[pivots] = -Rp[:, free]
    H[free] = identity_matrix(n-r)
    C = A[:, pivots] ### m x r
    Bp = B[r:,:] ### (m-r) x m
    print("beta R = rows of")
    show(Rp)
    print("beta K = columns of")
    show(H)
    print("beta C = columns of")
    show(C)
    print("beta L = rows of")
    show(Bp)

##### Exercise 1(a)

求 $\beta_R$。

<!-- eng start -->
Find $\beta_R$.
<!-- eng end -->

##### Exercise 1(b)

求 $\beta_K$。

<!-- eng start -->
Find $\beta_K$.
<!-- eng end -->

##### Exercise 1(c)

求 $\beta_C$。

<!-- eng start -->
Find $\beta_C$.
<!-- eng end -->

##### Exercise 1(d)

求 $\beta_L$。

<!-- eng start -->
Find $\beta_L$.
<!-- eng end -->

## Exercises

##### Exercise 2

執行以下程式碼。
令 $S = \{ \br_1, \br_2, \br_3 \}$ 為矩陣 $A$ 的各列向量
且 $V = \vspan(S)$。
求 $T$ 使得 $V^\perp = \vspan(T)$。

<!-- eng start -->
Run the code below. Let $S = \{ \br_1, \br_2, \br_3 \}$ be the columns of $A$ and $V = \vspan(S)$. Find $T$ such that $V^\perp = \vspan(T)$.
<!-- 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)
print("A =")
show(A)

if print_ans:
    H = zero_matrix(R.base_ring(), n, n-r)
    free = [i for i in range(n) if i not in pivots]
    H[pivots,:] = R[:r,free]
    H[free,:] = identity_matrix(n-r)
    print("T = the set of columns of")
    show(H)

##### Exercise 3

執行以下程式碼。
令 $S = \{ \bu_1, \bu_2 \}$ 為矩陣 $A$ 的各行向量
且 $V = \vspan(S)$。
求 $\bb$ 在 $V$ 上的投影。

<!-- eng start -->
Run the code below. Let $S = \{ \bu_1, \bu_2 \}$ be the columns of $A$ and $V = \vspan(S)$. Find the projection of $\bb$ onto $V$.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
A = random_good_matrix(5,2,2)
print("A =")
show(A)

b = vector(random_int_list(5))
print("b =", b)

if print_ans:
    ATAinv = (A.transpose() * A).inverse()
    w = A * ATAinv * A.transpose() * b
    print("projection =", w)

##### Exercise 4

執行以下程式碼。
令 $S = \{ \bu_1, \bu_2, \bu_3 \}$ 為矩陣 $A$ 的各行向量
且 $V = \vspan(S)$。
求 $\bb$ 在 $V$ 上的投影。
（如果你發覺 $A\trans A$ 不可逆的話﹐
記得把一些不重要的向量拿掉。
只要生成出來是 $V$，
不一定要把全部向量放進去。）

<!-- eng start -->
Run the code below. Let $S = \{ \bu_1, \bu_2, \bu_3 \}$ be the columns of $A$ and $V = \vspan(S)$. Find the projection of $\bb$ onto $V$. (If you found that $A\trans A$ is not invertible, then you might consider removing some redundant columns. After all, all we care about is $V$ but not the vectors.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
A = random_good_matrix(5,3,2)
print("A =")
show(A)

b = vector(random_int_list(5))
print("b =", b)

if print_ans:
    Ap = A[:,pivots]
    ATAinv = (Ap.transpose() * Ap).inverse()
    w = Ap * ATAinv * Ap.transpose() * b
    print("projection =", w)

##### Exercise 5

令 $A$ 為一 $m\times n$ 矩陣。
我們知道高斯消去法不會影響列空間，
因此自然地 $\Row(A) = \vspan(\beta_R)$。

以下我們說明為什麼 $\ker(A) = \vspan(\beta_K)$。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix. We know that row operations does not change the row space, so $\Row(A) = \vspan(\beta_R)$.

Here we study why $\ker(A) = \vspan(\beta_K)$.
<!-- eng end -->

##### Exercise 5(a)

令 $R$ 為 $A$ 的最簡階梯形式矩陣。
我們把領導變數拉到左邊、自由變數拉到右邊
（最後求完解以後再把變數順序拉回來就好），
因此我們可以假設 $R$ 的非零列長得像 $R' = \begin{bmatrix} I_r & Y \end{bmatrix}$。
我們把每個 $\mathbb{R}^n$ 的向量都寫成 $(\bv_1, \bv_2)$ 使得 $\bv_1\in\mathbb{R}^r$ 而 $\bv_2\in\mathbb{R}^{n-r}$。
說明

$$
\ker(A) = \ker(R') = \{(-Y\bv_2, \bv_2): \bv_2\in\mathbb{R}^{n-r}\}.
$$

<!-- eng start -->
Let $R$ be the reduced echelon form of $A$. For convenience, we assume all leading variables are on the left while all the free variables are on the right. (We may change the order of the variables again once we have solved the system.) Therefore, we may assume the nonzero rows of $R$ has the form $R' = \begin{bmatrix} I_r & Y \end{bmatrix}$. Let us consider every vector in $\mathbb{R}^n$ as $(\bv_1, \bv_2)$, where $\bv_1\in\mathbb{R}^r$ and $\bv_2\in\mathbb{R}^{n-r}$. Show that

$$
\ker(A) = \ker(R') = \{(-Y\bv_2, \bv_2): \bv_2\in\mathbb{R}^{n-r}\}.
$$
<!-- eng end -->

##### Exercise 5(b)

令 $H$ 為一 $n\times (n-r)$ 的矩陣﹐
其各行向量是由 $\beta_K$ 中的向量組成。
觀察到 $H = \begin{bmatrix} -Y \\ I_{n-r} \end{bmatrix}$。

說明 $H\bv_2 = (-Y\bv_2, \bv_2)$、
因此 $\ker(A) = \Col(H) = \vspan(\beta_K)$。

<!-- eng start -->
Let $H$ be the $n\times (n-r)$ matrix whose columns are vectors in $\beta_K$. Observe that $H = \begin{bmatrix} -Y \\ I_{n-r} \end{bmatrix}$.

Show that $H\bv_2 = (-Y\bv_2, \bv_2)$. Therefore, $\ker(A) = \Col(H) = \vspan(\beta_K)$。
<!-- eng end -->

##### Exercise 5(c)

藉由 $H\trans$ 和 $R'$ 的形式的相似性，
說明 $\ker(H\trans) = \Col(R'\trans)$。

<!-- eng start -->
Based on the similarity of the structures of $H\trans$ and $R'$, show that $\ker(H\trans) = \Col(R'\trans)$.
<!-- eng end -->

##### Exercise 5(d)

若 $S\subseteq\mathbb{R}^n$ 是一群有限個數的向量而 $V = \vspan(S)$。
證明 $(V^\perp)^\perp = V$。

<!-- eng start -->
Suppose $S\subseteq\mathbb{R}^n$ is a finite set of vectors and $V = \vspan(S)$. Show that $(V^\perp)^\perp = V$.
<!-- eng end -->

##### Exercise 6

令 $A$ 為一 $m\times n$ 矩陣。
令 $\bu_1,\ldots,\bu_n$ 為 $A$ 的各行向量。
接下來我們說明 $\Col(A) = \vspan(\beta_C)$ 及 $\ker(A\trans) = \vspan(\beta_L)$。
令 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 為 $\left[\begin{array}{c|c} A & I_m \end{array}\right]$ 的最簡階梯形式矩陣。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix. Let $\bu_1,\ldots,\bu_n$ be the columns of $A$. We will show that $\Col(A) = \vspan(\beta_C)$ and $\ker(A\trans) = \vspan(\beta_L)$. Let $\left[\begin{array}{c|c} R & B \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A & I_m \end{array}\right]$.
<!-- eng end -->

##### Exercise 6(a)

令 $\beta_K = \{\bh_1,\ldots,\bh_{n-r}\}$。
令 $j$ 為 $R$ 的第 $i$ 個軸。
藉由 $A\bh_i = \bzero$ 來說明 $\bu_j\in\vspan(\beta_C)$、
並證明 $\Col(A) = \vspan(\beta_C)$。

<!-- eng start -->
Let $\beta_K = \{\bh_1,\ldots,\bh_{n-r}\}$. Let $j$ be the $i$-th pivot of $R$. Use the fact that $A\bh_i = \bzero$ to show that $\bu_j\in\vspan(\beta_C)$ and $\Col(A) = \vspan(\beta_C)$.
<!-- eng end -->

##### Exercise 6(b)

令 $\hat{R}$ 為 $R$ 中對應到軸的那幾個行向量所組成的 $m\times r$ 矩陣。
令 $\hat{A}$ 為 $A$ 中對應到 $R$ 的軸的那幾個行向量所組成的 $m\times r$ 矩陣。
藉由 $\ker(\hat{R}) = \{\bzero\}$ 來說明 $\ker(\hat{A}) = \{\bzero\}$。

<!-- eng start -->
Let $\hat{R}$ be the $m\times r$ submatrix of $R$ induced on the columns corresponding to the pivots. Let $\hat{A}$ be the $m\times r$ submatrix of $A$ induced on the columns corresponding to the pivots of $R$. Use the fact that $\ker(\hat{R}) = \{\bzero\}$ to show that $\ker(\hat{A}) = \{\bzero\}$.
<!-- eng end -->

##### Exercise 6(c)

接著我們說明 $\beta_C$ 和 $\beta_L$ 中的向量互相垂直。

令 $\be_1,\ldots,\be_n$ 為 $I_n$ 中的行向量。
觀察到

$$
\left[\begin{array}{c|c} A & I_m \end{array}\right] \begin{bmatrix} \be_i \\ -\bu_i \end{bmatrix} = \bzero.
$$

利用這個性質推得 $R\be_i = B\bu_i$ 並說明 $\bu_i$ 和 $\beta_L$ 中的各向量垂直。

<!-- eng start -->
Now we show that any vector in $\beta_C$ is orthogonal to any vector in $\beta_L$.

Let $\be_1,\ldots,\be_n$ be the columns of $I_n$. Observe that

$$
\left[\begin{array}{c|c} A & I_m \end{array}\right] \begin{bmatrix} \be_i \\ -\bu_i \end{bmatrix} = \bzero.
$$

Use this fact to show that $R\be_i = B\bu_i$ and that $\bu_i$ is orthogonal to any vector in $\beta_L$.
<!-- eng end -->

##### Exercise 6(d)

由前一題我們已知 $\Col(A)^\perp \supseteq \vspan(\beta_L)$。
接著我們證明 $\Col(A)^\perp \subseteq \vspan(\beta_L)$。
令 $\bb\in\Col(A)^\perp$ 則 $\bb\trans A = \bzero$。
考慮 $\bv\trans = \bb\trans \left[\begin{array}{c|c} A & I_m \end{array}\right] =
\left[\begin{array}{c|c} \bzero\trans & \bb\trans\end{array}\right]$。
說明 $\bv\trans$ 也落在 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 的列空間中﹐進而說明 $\bb\in\vspan(\beta_L)$。

因為 $\Col(A)^\perp = \ker(A\trans)$﹐
所以 $\ker(A\trans) = \vspan(\beta_L)$。

<!-- eng start -->
By the previous problem, we know that $\Col(A)^\perp \supseteq \vspan(\beta_L)$. Now we show that $\Col(A)^\perp \subseteq \vspan(\beta_L)$. Let $\bb\in\Col(A)^\perp$ 則 $\bb\trans A = \bzero$. Consider $\bv\trans = \bb\trans \left[\begin{array}{c|c} A & I_m \end{array}\right] =
\left[\begin{array}{c|c} \bzero\trans & \bb\trans\end{array}\right]$. Show that $\bv\trans$ is in the row space of $\left[\begin{array}{c|c} R & B \end{array}\right]$. Therefore, $\bb\in\vspan(\beta_L)$.

Since $\Col(A)^\perp = \ker(A\trans)$, we know $\ker(A\trans) = \vspan(\beta_L)$.
<!-- eng end -->

##### Exercise 6(e)

其實我們也可以證明 $\ker(A\trans)^\perp = \Col(A)$。
如此一來可以再次說明 $(V^\perp)^\perp = V$。

因為我已知 $\ker(A\trans)^\perp \supseteq \Col(A)$。
接著我們證明 $\ker(A\trans)^\perp \subseteq \Col(A)$。
令 $\bb\in\ker(A\trans)^\perp$ 因此 $B\bb$ 的最後 $m-r$ 項都是 $0$。
說明存在 $\bv\in\mathbb{R}^n$ 使得
$$
\left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} \bv \\ \bb \end{bmatrix} = \bzero.
$$
因此 $A\bv + I_m\bb = \bzero$﹐得到 $\bb\in\Col(A)$。

<!-- eng start -->
In fact, we may prove that $\ker(A\trans)^\perp = \Col(A)$. This provides an alternative proof to $(V^\perp)^\perp = V$.

Since we already know that $\ker(A\trans)^\perp \supseteq \Col(A)$, it is enough to show that $\ker(A\trans)^\perp \subseteq \Col(A)$. Let $\bb\in\ker(A\trans)^\perp$. Thus, the last $m-r$ entries of $B\bb$ are zero. Show that there is a vector $\bv\in\mathbb{R}^n$ such that

$$
\left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} \bv \\ \bb \end{bmatrix} = \bzero.
$$

Therefore, $A\bv + I_m\bb = \bzero$﹐得到 $\bb\in\Col(A)$.
<!-- eng end -->

##### Exercise 7

若 $S\subseteq\mathbb{R}^n$ 是一群有限個數的向量而 $V = \vspan(S)$。
依照以下步驟證明：
任何向量 $\bb\in\mathbb{R}^n$ 都可以寫成 $\bb = \bw + \bh$
使得 $\bw\in V$ 且 $\bh\in V^\perp$。

<!-- eng start -->
Suppose $S\subseteq\mathbb{R}^n$ is a finite set of vectors and $V = \vspan(S)$. Use the given instructions to show that: Any vector $\bb\in\mathbb{R}^n$ can be written as $\bb = \bw + \bh$ such that $\bw\in V$ and $\bh\in V^\perp$.
<!-- eng end -->

##### Exercise 7(a)

令 $A_S$ 為一矩陣其各行向量由 $S$ 的各向量組成﹐
並算出其 $\beta_C$。
令 $A$ 為 $A_S$ 中只留 $\beta_C$ 中向量的子矩陣。
由前一題我們知道 $\Col(A_S) = \Col(A) = V$
且 $\ker(A) = \{\bzero\}$。

<!-- eng start -->
Let $A_S$ be the matrix whose columns are vectors in $S$. Find the $\beta_C$ of $A_S$. Let $A$ be the submatrix of $A_S$ composed of vectors in $\beta_C$. By the previous problem, we know $\Col(A_S) = \Col(A) = V$ and $\ker(A) = \{\bzero\}$.
<!-- eng end -->

##### Exercise 7(b)

說明 $A\trans A$ 可逆。
同時驗證

$$
\begin{aligned}
\bw &= A(A\trans A)^{-1}A\trans \bb, \\
\bh &= \bb - \bw
\end{aligned}
$$

符合我們要的條件。

<!-- eng start -->
Explain why $A\trans A$ is invertible. Also, verify that

$$
\begin{aligned}
\bw &= A(A\trans A)^{-1}A\trans \bb, \\
\bh &= \bb - \bw
\end{aligned}
$$

satisfy the desired properties.
<!-- eng end -->

##### Exercise 7(c)

證明 $\bb$ 寫成 $\bw + \bh$ 的方法唯一。
也就是說﹐如果 $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$
使得 $\bh_1,\bh_2\in V$ 且 $\bw_1,\bw_2\in V^\perp$﹐
則 $\bh_1 = \bh_2$ 且 $\bw_1 = \bw_2$。

<!-- eng start -->
Show that the decomposition $\bb = \bw + \bh$ is unique. That is, if $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$ such that $\bh_1,\bh_2\in V$ and $\bw_1,\bw_2\in V^\perp$, then $\bh_1 = \bh_2$ 且 $\bw_1 = \bw_2$.
<!-- eng end -->