# 四大基礎子空間

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

## Main idea

Recall that if $V$ is a subspace in $\mathbb{R}^n$, then its orthogonal complement is
$$V^\perp = \{{\bf w}\in\mathbb{R}^n : \langle{\bf w},{\bf v}\rangle = 0 \text{ for all }{\bf v}\in V\}.$$

Suppose $V = \operatorname{span}(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 ${\bf b}$ can be written as a unique representation
$${\bf b} = {\bf w} + {\bf h}
$$
such that ${\bf w}\in V$ and ${\bf h}\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 $\operatorname{Row}(A)$ and $\operatorname{ker}(A)$ are subspaces in $\mathbb{R}^n$ and they are the orthogonal complement of each other.

Let $\beta_R = \{{\bf r}_1,\ldots,{\bf r}_r\}$ be the set of nonzero rows in $R$.
Then $\operatorname{Row}(A) = \operatorname{span}(\beta_R)$.

Let $\beta_K = \{{\bf h}_1, \ldots, {\bf h}_{n-r}\}$ be the set of homogeneous solutions solved by setting one free variable as $1$ and others as $0$.
Then $\operatorname{ker}(A) = \operatorname{span}(\beta_K)$.

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

Let $\beta_C = \{ {\bf u}_1,\ldots, {\bf u}_r \}$ be the set of columns of $A$ corresponding to the pivots of $R$.
Then $\operatorname{Col}(A) = \operatorname{span}(\beta_C)$.

Let $\beta_L = \{ {\bf b}_1,\ldots,{\bf b}_{m-r} \}$ be the last $m-r$ rows in $B$.
Then $\operatorname{ker}(A^\top) = \operatorname{span} (\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]$ 的最簡階梯形式矩陣。

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

Ans:
When`seed = 0`, the number given by the question is
$$
\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].
$$

The set $\beta_R$ is the set of nonzero rows in $R$,
so that $\operatorname{span}(\beta_R) = \operatorname{Row}(A)$.
Hence,
$\beta_R$ is composed of the rows of
$$\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3
\end{bmatrix}.
$$

Hence,
the number of pivots is $r = 2$.

##### Exercise 1(b)

求 $\beta_K$。

:::warning

- [x] 純量不要粗體 $\bx_1$ --> $x_1$
- [x] $\beta_K$ = columns of --> $\beta_K$ is composed of the columns of
- [x] 最後一個矩陣後加句點
:::

Ans:
Let $A{\bf x} = {\bf 0}$
$$
\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\ 0 & 1 & -5 & 0 & 3 \\0 & 0 & 0 & 0 & 0 \end{bmatrix}\begin{bmatrix}{x_1}\\{x_2}\\{x_3}\\{x_4}\\{x_5}\end{bmatrix} = \begin{bmatrix} 0\\0\\0\\0\\0\end{bmatrix}.
$$
Let ${x_3} = i$, ${x_4} = j$, ${x_5} = k$,
$$
{\bf x}_k = \begin{bmatrix}{x_1}\\{x_2}\\{x_3}\\{x_4}\\{x_5}\end{bmatrix} = \begin{bmatrix} - 3i - 5j +5k\\5i - 3k\\i\\j\\k\end{bmatrix} = i \begin{bmatrix} 3\\5\\1\\0\\0\end{bmatrix} + j \begin{bmatrix}- 5\\0\\0\\1\\0\end{bmatrix}+ k \begin{bmatrix}- 5\\- 3\\0\\0\\1\end{bmatrix}.
$$
so $\beta_K$ is composed of the columns of
$$
\begin{bmatrix}
-3 & -5 & 5 \\
5 & 0 & -3 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}.
$$

##### Exercise 1(c)

求 $\beta_C$。

:::warning

- [x] , hence --> . Hence （hence 不是連接詞）
- [x] $\beta_C$ = columns of --> $\beta_C$ is composed of the columns of
:::

Ans:
The set $\beta_C$ is the set of columns of $A$ corresponding to the pivots of $R$.
Hence $\beta_C$ is composed of the columns of
$$\begin{bmatrix}
1 & -3 \\
3 & -8 \\
-8 & 20
\end{bmatrix}.
$$

##### Exercise 1(d)

求 $\beta_L$。

:::warning

- [x] $\beta_L$ = rows of --> $\beta_L$ is composed of the rows of
:::

Ans:
The $\beta_L$ is the last $m-r$ row in $B$,
which is last (3-2) = 1 row in $B$,
so $\beta_L$ is composed of the rows of
\begin{bmatrix}
1 & -1 & -1/4\\
\end{bmatrix}
## Exercises

##### Exercise 2

執行以下程式碼。
令 $S = \{ {\bf r}_1, {\bf r}_2, {\bf r}_3 \}$ 為矩陣 $A$ 的各列向量
且 $V = \operatorname{span}(S)$。
求 $T$ 使得 $V^\perp = \operatorname{span}(T)$。

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

:::warning

- [x] The basis of $V^\perp$ are special solutions to $Ax = 0$, and those independent solutions are columns of $T$. --> And we know that $\vspan(\beta_K) = \ker(A) = V^\perp$.
- [x] reduced echelon form --> the reduced echelon form
- [x] and the special solutions to $Rx = 0$ --> and the solutions to $R\bx = \bzero$
- [x] through setting one of --> Through setting one of
- [x] we get all of the special solutions, --> we get the solutions in $\beta_K$ as
- [x] Therefore $T$ should be ... matrix. --> Therefore, setting $T = \beta_K$ is enough.
:::

Ans:
That $V$ is the row space of $A$ implies that the orthogonal complement of $V$, i.e., $V^\perp$ is the nullspace (kernel) of $A$. And we know that $\vspan(\beta_K) = \ker(A) = V^\perp$.
First of all, we reduce $A$ to the reduced echelon form,

$$
\left[\begin{array}{c} R \end{array}\right] =
\left[\begin{array}{ccccc}
1 & 0 & 3 & 5 & -5\\
0 & 1 & -5 & 0 & 3\\
0 & 0 & 0 & 0 & 0\\
\end{array}\right]
$$

the nonzero rows of $R$ span $V$, and the solutions to $R\bx = \bzero$ span the nullspace of $A$.
Through setting one of the free variable to $1$ and the others to $0$, we get all the independent solutions in $\beta_K$ as,

$$
\left[\begin{array}{c}
-3\\
5\\
1\\
0\\
0\\
\end{array}\right] ,
\left[\begin{array}{c}
-5\\
0\\
0\\
1\\
0\\
\end{array}\right] ,
\left[\begin{array}{c}
5\\
-3\\
0\\
0\\
1\\
\end{array}\right]
$$

Therefore, setting $T$ = $\beta_K$ is enough.

##### Exercise 3

執行以下程式碼。
令 $S = \{ {\bf u}_1, {\bf u}_2 \}$ 為矩陣 $A$ 的各行向量
且 $V = \operatorname{span}(S)$。
求 ${\bf b}$ 在 $V$ 上的投影。

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

:::warning

- [x] $b$ --> $\bb$, $p$ --> $\bp$
- [x] 中英數之間空格 [S01](https://sagelabtw.github.io/LA-Tea/style.html)
- [x] 中文字不要丟到數學模式裡
- [x] $span$ --> $\vspan$
- [x] $s$ --> $S$
- [x] $A$ 不用粗體
- [x] 下一題有類似的狀況
:::

**Ans:**

以下為運行程式碼後得到的數據：

$A=\begin{bmatrix}１&3\\5&16\\10&33\\-20&-63\\15&48\end{bmatrix}$、$\bb=(4,-4,-3,2,4)。$

令 $S= \{ {\bf u}_1,\ \bu_2 \}$ 為矩陣A的各行向量，
因此 ${\bf u}_1=(1,5,10,-20,15)$、${\bf u}_2=(3,16,33,-63,68)$。
且令 $V=\vspan(S)$、$\bp$ 為向量 $\bb$ 於 $\vspan(S)$ 上的投影。

由公式可知
$$\begin{aligned}
{\bf p} &= A(A^\top A)^{-1}A^\top \bb, \\
\end{aligned}
$$
且由 $A$ 便可得 $A^\top$
$$\begin{aligned}
A^\top =\begin{bmatrix}1&5&10&-20&15\\3&16&33&-63&48\end{bmatrix}。
\end{aligned}
$$
經過計算可得 $A^\top A$
$$\begin{aligned}A^\top A=\begin{bmatrix}751&2393\\2393&7627\end{bmatrix}。
\end{aligned}
$$
取 $A^\top A$ 的反矩陣

$$\begin{aligned}(A^\top A)^{-1}=\begin{bmatrix}\frac{{7627}}{{1428}}&\frac{{-2393}}{{1428}}\\\frac{{ -2393}}{{1428}}&\frac{{ 751}}{{1428}}\end{bmatrix}。
\end{aligned}
$$

將 $\bb$ 寫成矩陣形式可得
$$\begin{aligned} \bb=\begin{bmatrix}4\\-4\\-3\\2\\4\end{bmatrix}。
\end{aligned}$$
將 $(A^\top A)^{-1}、A^\top、\bb$ 的值帶入公式可得
$$\begin{aligned}
{\bf p} &= \begin{bmatrix}１&3\\5&16\\10&33\\-20&-63\\15&48\end{bmatrix}\begin{bmatrix}\frac{{\bf 7627}}{{1428}}&\frac{{\bf -2393}}{{1428}}\\\frac{{\bf -2393}}{{1428}}&\frac{{\bf 751}}{{1428}}\end{bmatrix}\begin{bmatrix}1&5&10&-20&15\\3&16&33&-63&48\end{bmatrix}\begin{bmatrix}4\\-4\\-3\\2\\4\end{bmatrix}。
\end{aligned}
$$

將計算的結果寫成向量便可得 $\bp=(\frac{{3}}{{17}},\frac{{-1}}{{4}},\frac{{-111}}{{68}},\frac{{-9}}{{68}},\frac{{-3}}{{4}})。$

##### Exercise 4

執行以下程式碼。
令 $S = \{ {\bf u}_1, {\bf u}_2, {\bf u}_3 \}$ 為矩陣 $A$ 的各行向量
且 $V = \operatorname{span}(S)$。
求 ${\bf b}$ 在 $V$ 上的投影。
（如果你發覺 $A^\top A$ 不可逆的話﹐
記得把一些不重要的向量拿掉。
只要生成出來是 $V$﹐
不一定要把全部向量放進去。）

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

:::warning

- [x] $取$ --> 改令 （因為 $A$ 己經用過了）
:::

**Ans:**

以下為運行程式碼後得到的數據：

$A=\begin{bmatrix}1&-5&-22\\-5&26&115\\-15&78&345\\-17&89&394\\17&-89&-394\end{bmatrix}$、$\bb=(-3,2,4,-4,-1)。$

令 $S= \{ \bu_1,\ \bu_2,\ \bu_3 \}$ 為矩陣 $A$ 的各行向量,

因此 $\bu_1=(1,-5,-15,-17,17)$、${\bf u}_2=(-5,26,78,89,-89)$、$\bu_3=(-22,115,345,394,-394)。$

且只取 $\bu_1、\bu_2$ 作 $S= \{ \bu_1,\ \bu_2 \}$

令 $V=\vspan(s)、\bp$ 為向量 $\bb$ 於 $\vspan(S)$ 上的投影。

改令
$$\begin{aligned}
A &= \begin{bmatrix}1&-5\\-5&26\\-15&78\\-17&89\\17&-89\end{bmatrix}。
\end{aligned}
$$
由公式可知
$$\begin{aligned}
{\bf p} &= A(A^\top A)^{-1}A^\top \bb, \\
\end{aligned}
$$
且由 $A$ 可得 $A^\top$
$$\begin{aligned}
A^\top &= \begin{bmatrix}1&-5&-15&-17&17\\-5&26&78&89&-89\end{bmatrix}。
\end{aligned}
$$
經過計算可得 $A^\top A$
$$\begin{aligned}A^\top A=\begin{bmatrix}829&-4331\\-4331&22627\end{bmatrix}。
\end{aligned}
$$
取 $A^\top A$ 的反矩陣
$$\begin{aligned}(A^\top A)^{-1}=\begin{bmatrix}\frac{{22627}}{{222}}&\frac{{4331}}{{222}}\\\frac{{ 4331}}{{222}}&\frac{{ 829}}{{222}}\end{bmatrix}。
\end{aligned}
$$
將 $\bb$ 寫成矩陣形式可得
$$\begin{aligned} \bb=\begin{bmatrix}-3\\2\\4\\-4\\-1\end{bmatrix}。
\end{aligned}$$
將 $(A^\top A)^{-1}、A^\top、\bb$ 的值帶入公式可得
$$\begin{aligned}
{\bf p} &= \begin{bmatrix}1&-5\\-5&26\\-15&78\\-17&89\\17&-89\end{bmatrix}\begin{bmatrix}\frac{{22627}}{{222}}&\frac{{4331}}{{222}}\\\frac{{ 4331}}{{222}}&\frac{{ 829}}{{222}}\end{bmatrix}\begin{bmatrix}1&-5&-15&-17&17\\-5&26&78&89&-89\end{bmatrix}\begin{bmatrix}-3\\2\\4\\-4\\-1\end{bmatrix}
\end{aligned}.
$$

將計算的過程寫成向量便可得 $\bp=(\frac{{-92}}{{37}},\frac{{163}}{{111}},\frac{{163}}{{37}},\frac{{-176}}{{111}},\frac{{176}}{{111}})$。

##### Exercise 5

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

以下我們說明為什麼 $\operatorname{ker}(A) = \operatorname{span}(\beta_K)$。

##### Exercise 5(a)

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

:::warning

因為 $R$ 是 $A$ 的最簡階梯形式，又 $R'$ 由 $R$ 的非零列所組成，所以 $\ker(A) = \ker(R) = \ker(R')$。

若 $(\bv_1, \bv_2)$ 在 $\ker(R')$ 裡，則 $\bv_1 + Y\bv_2 = \bzero$。因此 $\bv_1 = ???$，得知所有 $\ker(R')$ 裡的解都是 $...$ 的形式。
:::

**Ans:**
因為 $R$ 是 $A$ 的最簡階梯形式，又 $R'$ 由 $R$ 的非零列所組成，所以 $\ker(A) = \ker(R) = \ker(R')$。

且由
$$\begin{aligned}
R'\begin{bmatrix}\bv_1\\\bv_2\end{bmatrix} = I_r \bv_1 + Y \bv_2 = \bv_1 +Y \bv_2 = \bzero,
\end{aligned}$$

可得
$$\begin{aligned}
\bv_1 = -Y \bv2
\end{aligned}
$$

得知所有 $\ker(R')$ 裡的解都是 $(-Y\bv_2, \bv_2)$ 的形式。

##### Exercise 5(b)

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

說明 $H{\bf v}_2 = (-Y{\bf v}_2, {\bf v}_2)$、
因此 $\operatorname{ker}(A) = \operatorname{Col}(H) = \operatorname{span}(\beta_K)$。

:::warning
- [x] Multiply the matrices $H{\bf v_2}$ in row picture <-- 這句我不懂
- [x] ${\bf e_i}$ --> $\be_i$
- [x] Let ${\bf e_i}$ be the $i$th column of $I_{n-r}$, then for each ${\bf e_i}$, $H{\bf e_i}$ is a special solution to $R'{\bf x} = 0$, which is also the one to $R{\bf x} = 0$ and $A{\bf x} = 0$. <-- 這段不用，改為 By Exercise 5(a),
$$
\ker(A) = \{(-Y\bv_2, \bv_2): \bv_2\in\mathbb{R}^{n-r}\} = \{H\bv_2: \bv_2\in\mathbb{R}^{n-r}\} = \Col(H).
$$
- [x] All of the special solution can span $\operatorname{ker}(A)$ since all of {\bf e_i} are basis vectors in $\mathbb{R}^{n-r}$. --> Since the columns of $H$ are the vectors in $\beta_K$, $\Col(H) = \vspan(\beta_K)$.
:::

Ans:

Since each entry of $H{\bf v_2}$ is the inner product of each row of $H$ and ${\bf v_2}$, so $H{\bf v_2} = \begin{bmatrix} -Y{\bf v_2} \\ I_{n-r}{\bf v_2} \end{bmatrix} = (-Y{\bf v_2}, {\bf v_2})$.

Exercise 5(a),
$$
\ker(A) = \{(-Y\bv_2, \bv_2): \bv_2\in\mathbb{R}^{n-r}\} = \{H\bv_2: \bv_2\in\mathbb{R}^{n-r}\} = \Col(H).
$$

<!--
Let $\be_i$ be the $i$th column of $I_{n-r}$, then for each ${\bf e_i}$, $H{\bf e_i}$ is a special solution to $R'{\bf x} = 0$, which is also the one to $R{\bf x} = 0$ and $A{\bf x} = 0$.
-->

Since the columns of $H$ are the vectors in $\beta_K$, $\Col(H) = \vspan(\beta_K)$.

##### Exercise 5(c)

藉由 $H^\top$ 和 $R'$ 的形式的相似性﹐
說明 $\operatorname{ker}(H^\top) = \operatorname{Col}(R'^\top)$。

:::warning
- [x] Let ... . Then ... .
- [x] 向量粗體
:::

Ans:
Observe that
$$
H\trans = \begin{bmatrix}
-Y\trans & I_{n-r}
\end{bmatrix}
\text{ and }
R'\trans = \begin{bmatrix}
I_r \\ Y\trans
\end{bmatrix}.
$$
Let $\bv$ be any vector in $\mathbb{R}^{r}$. Then $R'^\top \bv = \begin{bmatrix} I_{r}\bv\\ Y^\top \bv \end{bmatrix}$.

By multipling $H^\top$ and $R'^\top {\bf v}$, we can see that

$$
H^\top R'^\top {\bf v} = \begin{bmatrix} -Y^\top I_{r}{\bf v} + I_{n-r}Y^\top {\bf v} \end{bmatrix} = \begin{bmatrix} -Y^\top {\bf v} + Y^\top {\bf v} \end{bmatrix} = {\bf 0}.
$$

For each ${\bf v}$, $R'^\top {\bf v}$ is a solution to $H^\top {\bf x} = \bzero$, which implies that $\operatorname{ker}(H^\top) \supseteq \operatorname{Col}(R'^\top)$.

Besides, let $\be_i$ be the $i$th column of $I_r$, and all of $R'^\top {e_i}$ are special solutions to $H^\top \bx = 0$.

Therefore, $\operatorname{ker}(H^\top) = \operatorname{span}(\{{R'^\top \be_i: i \in \mathbb{R}^r}\}) = \operatorname{Col}(R'^\top)$.

(end-of-proof)

##### Exercise 5(d)

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

**[由廖緯程同學提供]**
$Ans:$
令 $S = \{ \bu_1 , \ldots , \bu_m \ : \bu_i \in \mathbb{R}^n \}$，$A$ 為一 $m \times n$ 的矩陣，且
$$
A = \begin{bmatrix}- & {\bf u}_1 & - \\
~ & \vdots & ~ \\ - & {\bf u}_m & - \\
\end{bmatrix}.
$$
$V = \vspan(S) = \Row(A) = \Row(R)$，
根據5(b)，$V^\perp = \Row(A)^\perp = \ker(A) = \Col(H) = \Row(H\trans)$，
根據5(c)，$(V^\perp)^\perp = \Row(H\trans)^\perp = \ker(H\trans) = \Col(R'\trans) = \Row(R') = \Row(R) = V$。

##### Exercise 6

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

##### Exercise 6(a)

令 $\beta_K = \{{\bf h}_1,\ldots,{\bf h}_{n-r}\}$。
令 $j$ 為 $R$ 的第 $i$ 個軸。
藉由 $A{\bf h}_i = {\bf 0}$ 來說明 ${\bf u}_j\in\operatorname{span}(\beta_C)$、
並證明 $\operatorname{Col}(A) = \operatorname{span}(\beta_C)$。

:::warning

- [x] 你們的證明是對的，但是其實沒用到 $\bh$。（不過沒關係）
- [x] As a result, non-pivot column ${\bf u}_k$, which is corresponding column to ${\bf r}_k$, is also a linear combination of $\{{\bf e}_1,\ldots,{\bf e}_i\}$. --> Consequently, since $\br_k$ is a linear combination of $\{\be_1,\ldots, \be_i\}$, which are the columns to the left of $\br_k$ in $R$, $\bu_k$ is also a linear combination of the columns to the left of $\bu_k$ in $A$.
- [x] 第二段用到的 $\bh$ 是多餘的。可以整段刪掉，留下 The solutions of the homogeneous equations $A{\bf x} = 0$ and $R{\bf x} = 0$ are the same. 當做下一段的開頭就好
:::

**Ans:**
Observe that ${\bf r}_j$ is the $i$-th pivot column of $R$, that is, ${\bf e}_i$.
Let ${\bf r}_k$ be the $k$-th non-pivot column of $R$ where there are $i$ pivot columns to the left of ${\bf r}_k$ in $R$.
So ${\bf r}_k$ is a linear combination of $\{{\bf e}_1,\ldots,{\bf e}_i\}$.

The solutions of the homogeneous equations $A{\bf x} = 0$ and $R{\bf x} = 0$ are the same.
Consequently, since $\br_k$ is a linear combination of $\{\be_1,\ldots, \be_i\}$, which are the columns to the left of $\br_k$ in $R$, $\bu_k$ is also a linear combination of the columns to the left of $\bu_k$ in $A$.
So the pivot columns of $A$ span the column space of $A$,
that is, $\operatorname{Col}(A) = \operatorname{span}(\beta_C)$.

##### Exercise 6(b)

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

:::warning

- [x] $\hat{R}$ are the pivot columns of $R$,
hence are the standard vectors $\{{\bf e}_1,\ldots,{\bf e}_r\}$ that are linearly independent in $R_m$. --> Since $\hat{R}$ consists of the pivot columns of $R$, the columns of $\hat{R}$ are the standard vectors $\{{\bf e}_1,\ldots,{\bf e}_r\}$, which is linearly independent in $\mathbb{R}_m$.
:::

**Ans:**
Since $\hat{R}$ consists of the pivot columns of $R$, the columns of $\hat{R}$ are the standard vectors $\{{\bf e}_1,\ldots,{\bf e}_r\}$, which is linearly independent in $\mathbb{R}_m$.
Then, $\{{\bf 0}\}$ is the only solution of $\hat{R}{\bf x} = 0$.
Hence, $\operatorname{ker}(\hat{R}) = \{{\bf 0}\}$ and then $\operatorname{ker}(\hat{A}) = \{{\bf 0}\}$.

##### Exercise 6(c)

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

令 ${\bf e}_1,\ldots,{\bf e}_n$ 為 $I_n$ 中的行向量。
觀察到
$$\left[\begin{array}{c|c} A & I_m \end{array}\right] \begin{bmatrix} {\bf e}_i \\ -{\bf u}_i \end{bmatrix} = {\bf 0}.
$$
利用這個性質推得 $R{\bf e}_i = B{\bf u}_i$ 並說明 ${\bf u}_i$ 和 $\beta_L$ 中的各向量垂直。

**[由廖緯程同學提供]**
$Ans:$
因為 $\left[
\begin{array}{c|c}
A & I_m
\end{array}
\right]
\begin{bmatrix}
\be_i\\
-\bu_i\\
\end{bmatrix}
= {\bf 0}$，所以

$$\begin{bmatrix}
\be_i\\
-\bu_i\\
\end{bmatrix} \in \ker(\left[
\begin{array}{c|c}
A & I_m
\end{array}
\right]) = \ker(\left[
\begin{array}{c|c}
R & B
\end{array}
\right])，
$$

再由 $\ker$ 的定義得 $\left[
\begin{array}{c|c}
R & B
\end{array}
\right]
\begin{bmatrix}
\be_i\\
-\bu_i\\
\end{bmatrix}
= R\be_i - B\bu_i = {\bf 0}，$ 即 $R\be_i = B\bu_i。$
令 $B$ 的第 $i$ 個列向量為 $\bb_i$。
我們可以把 $i$ 從 $1$ 到 $n$ 合在一起，

$$
R
\begin{bmatrix}
| & & |\\
\be_1 & \ldots & \be_n\\
| & & |
\end{bmatrix} = R = \begin{bmatrix} - & {\bf b}_1 & - \\
~ & \vdots & ~ \\ - & {\bf b}_m & - \\
\end{bmatrix}
\begin{bmatrix}
| & & |\\
\bu_1 & \ldots & \bu_n\\
| & & |
\end{bmatrix}，
$$

把 $R$ 的最後 $m-r$ 列取出來看，會有

$$
\begin{bmatrix} - & {\bf 0} & -\\
& \vdots & \\ - & {\bf 0} & -
\end{bmatrix} =
\begin{bmatrix} - & \bb_{r+1} & -\\
& \vdots & \\ - & \bb_m & -
\end{bmatrix}
\begin{bmatrix}
| & & |\\
\bu_1 & \ldots & \bu_n\\
| & & |
\end{bmatrix}，
$$

可以看出對於所有的 $j=r+1,\ldots,m$，$i=1,\ldots,n$ 有 $\langle \bb_j,\bu_i \rangle = 0$，
根據 $\beta_L$ 的定義，$\beta_L = \{ \bb_{r+1},\ldots,\bb_m \}$。
所以 ${\bf u}_i$ 和 $\beta_L$ 中的各向量垂直。

##### Exercise 6(d)

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

因為 $\operatorname{Col}(A)^\perp = \operatorname{ker}(A^\top)$﹐
所以 $\operatorname{ker}(A^\top) = \operatorname{span}(\beta_L)$。

:::warning

- [x] 因為 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I_m \end{array}\right]$ 的 reduced echelon form，所以 ${\bf v}^\top$ 落在 $\left[\begin{array}{c|c}A & I_m\end{array}\right]$ 上，且 ${\bf v}^\top$ 落在$\left[\begin{array}{c|c}R&B\end{array}\right]$ 上。
-->
因為 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I_m \end{array}\right]$ 的 最簡階梯形式，且 $\bv\trans$ 落在 $\left[\begin{array}{c|c}A & I_m\end{array}\right]$ 的列空間上，所以 ${\bf v}^\top$ 也落在$\left[\begin{array}{c|c}R&B\end{array}\right]$ 的列空間上。
- [x] 加上：由於 $\bv\trans$ 的前半段皆為零，後半段為 $\bb\trans$，則 $\bb\trans$ 會由 $\beta_L$ 生成。
:::

**Ans:**
令 ${\bf b}\in\operatorname{Col}(A)^\perp$ 則 ${\bf b}^\top A = {\bf 0}$。
考慮 ${\bf v}^\top = {\bf b}^\top \left[\begin{array}{c|c} A & I_m \end{array}\right] =
\left[\begin{array}{c|c} {\bf 0}^\top & {\bf b}^\top\end{array}\right]$。
因為 $\left[\begin{array}{c|c} R & B \end{array}\right]$ 是 $\left[\begin{array}{c|c} A & I_m \end{array}\right]$ 的 最簡階梯形式，且 $\bv\trans$ 落在 $\left[\begin{array}{c|c}A & I_m\end{array}\right]$ 的列空間上，所以 ${\bf v}^\top$ 也落在$\left[\begin{array}{c|c}R&B\end{array}\right]$ 的列空間上。
由於 $\bv\trans$ 的前半段皆為零，後半段為 $\bb\trans$，則 $\bb\trans$ 會由 $\beta_L$ 生成。，且 ${\bf v}^\top$ 落在$\left[\begin{array}{c|c}R&B\end{array}\right]$ 上。
所以$\operatorname{Col}(A)^\perp = {\bf b} =\operatorname{ker}(A^\top)$﹐

所以 $\operatorname{ker}(A^\top) = \operatorname{span}(\beta_L)$。
所以 ${\bf b}\in\operatorname{span}(\beta_L)$

##### Exercise 6(e)

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

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

**[由廖緯程同學提供]**
$Ans:$
令 $\bb \in \ker(A\trans)^\perp$，根據定義，對於所有的 $\bx \in \ker(A\trans)$，$\langle \bb,\bx \rangle = 0$。
因為 $\beta_L \subseteq \ker(A\trans)$，所以 $\beta_L$ 中所有元素與 $\bb$ 內積都等於 $0$，即 $B$ 的最後 $m-r$ 列與 $\bb$ 內積也都等於 $0$。
因此 $B \bb$ 的最後 $m-r$ 項都是 $0$。

因為 $R$ 的最後 $m-r$ 列都是 $0$，$R\bv$ 的最後 $m-r$ 列也都是 $0$。
所以我們可以把，求一個 $\bv \in \mathbb{R}^n$ 使得
$$
\left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} {\bf v} \\ {\bf b} \end{bmatrix} = {\bf 0}
$$
改寫成，求一個 $\bv \in \mathbb{R}^n$ 使得
$$
\left[\begin{array}{c|c} R' & B' \end{array}\right] \begin{bmatrix} {\bf v} \\ {\bf b} \end{bmatrix} = {\bf 0}.
$$
其中 $R',B'$ 是 $R,B$ 的前 $r$ 列。
考慮
$$
R'\bv=\bu
$$
是否有解，其中 $\bu = -B'\bb$，因為 $R'$ 沒有非零列而且是RREF，所以 $\Col(R') = \mathbb{R}^r$。
自然的，$\bu \in \mathbb{R}^r = \Col(R')$，所以存在一個 $\bv \in \mathbb{R}^n$ 使得
$$
R'\bv=\bu
$$
有解，即
$$
R\bv + B\bb = \left[\begin{array}{c|c} R & B \end{array}\right] \begin{bmatrix} {\bf v} \\ {\bf b} \end{bmatrix} = {\bf 0}
$$
因為 $B$ 是基本矩陣的乘積，所以一定有反矩陣，同時在左邊乘 $B^{-1}$ 得
$$
A\bv + \bb = {\bf 0}
$$
寫成
$$
A(-\bv) = \bb
$$
可以得到 $\bb \in \Col(A)$，等價於 $\operatorname{ker}(A^\top)^\perp \subseteq \operatorname{Col}(A)$。
最後可以得證 $\operatorname{ker}(A^\top)^\perp = \operatorname{Col}(A)$。

##### Exercise 7

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

##### Exercise 7(a)

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

:::success
這裡好像沒什麼要解釋的，看過就好！
:::

##### Exercise 7(b)

說明 $A^\top A$ 可逆。
同時驗證
$$\begin{aligned}
{\bf w} &= A(A^\top A)^{-1}A^\top {\bf b}, \\
{\bf h} &= {\bf b} - {\bf w}
\end{aligned}
$$
符合我們要的條件。

:::warning
- [x] $A$ 不一定是方陣，所以不見得可以算行列式值。這部份只要叫 105-2 就好。比如說：根據 105-2，因為 ... ，所以 ... 可逆。
- [x] $Col(A)$ --> $\Col(A)$, $ker(A)$ --> $\ker(A)$
- [x] 向量粗體
- [x] 而依照題目的假設 <-- 那段是在解釋為什麼 $\bw$ 和 $\bh$ 要取成這樣。但題目是要你驗證 $\bw \in V = \Col(A)$ 及 $\bh \in V^\perp = \ker(A\trans)$，所以請在這段之後加上：因為 ... ，所以 $\bw \in V = \Col(A)$。而因為 ... ，所以 $\bh \in V^\perp = \ker(A\trans)$。
:::

根據 105-2，因為 $\ker(A)=0$，所以 $A^\top A$可逆。

因為 ${\bf w}= A(A^\top A)^{-1}A^\top {\bf b}$
如同 ${\bf A}$ 乘上一個向量﹐
所以${\bf w}\in \Col(A)。$

根據計算，
得出
$$A^\top {\bf h} = A^\top {\bf b} - A^\top {\bf w} = A^\top {\bf b} -A^\top(A(A^\top A)^{-1}A^\top
{\bf b}) = A\trans\bb - A\trans\bb = \bzero,
$$
所以 ${\bf h} = \ker(A^\top)$。

##### Exercise 7(c)

證明 ${\bf b}$ 寫成 ${\bf w} + {\bf h}$ 的方法唯一。
也就是說﹐如果 ${\bf b} = {\bf w}_1 + {\bf h}_1 = {\bf w}_2 + {\bf h}_2$
使得 ${\bf h}_1,{\bf h}_2\in V$ 且 ${\bf w}_1,{\bf w}_2\in V^\perp$﹐
則 ${\bf h}_1 = {\bf h}_2$ 且 ${\bf w}_1 = {\bf w}_2$。

:::warning

- [x] 向量粗體
- [x] 因為是假設有 $\bw$ 和 $\bh$ 滿足某些條件，所以這裡沒辦法用上面的公式

參考以下的框架：

若有兩組 $\bh_1,\bh_2\in V$ 及 $\bw_1,\bw_2\in V^\perp$ 使得 $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$。
則 $\bw_1 - \bw_2 = ...$。
由於 $...\in V$ 且 $...\in V^\perp$，
加上 $V\cap V^\perp = \{\bzero\}$，
所以 $...$。
:::

若有兩組 $\bh_1,\bh_2\in V$ 及 $\bw_1,\bw_2\in V^\perp$ 使得 $\bb = \bw_1 + \bh_1 = \bw_2 + \bh_2$。
則 $\bw_1 - \bw_2 = \bh_2 - \bh_1$。
由於 $\bh_1,\bh_2\in V$ 且 $\bw_1,\bw_2\in V^\perp$，
加上 $V\cap V^\perp = \{\bzero\}$，
所以 $\bw_1 - \bw_2 =0$ 且 $\bh_1 - \bh_2 = 0$。
則${\bf h}_1 = {\bf h}_2$ 且 ${\bf w}_1 = {\bf w}_2$。

<!--
${\bf b} ={\bf w}+{\bf h}$ 我們可以改寫為 ${\bf h} ={\bf b}-{\bf w}$
根據前面的證明 ${\bf w}$ 帶入式子
${\bf h} = bIn-A(A^\top A)^{-1} A^\top b$
提出$b$ 使得$\bb = \bb(In-A(A^\top A)^{-1} A^\top)$
而根據這個式子，我們發現只需要確定$\bb、\bh、\bw$的其中一個向量唯一，
則${\bf b} ={\bf w}+{\bf h}={\bf w}_1+{\bf h}_1$ , ${\bf w}={\bf w}_1$ , ${\bf h}={\bf h}_1$即成立。

而 $V$ 為 $span(S)$ 所張出的平面且 ${\bf w}\in V$ 和 ${\bf h}\in V^\perp$，
我們發現 $w$ 為 $b$ 投影在 $V$ 平面之向量，
而根據同一向量所投影到的同一平面之向量為唯一，
得到 $b$ 寫成 $w+h$ 的方法為唯一。
-->

:::info
目前分數 5/5
:::