# 基底交換法則

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_int_list, random_good_matrix, find_pivots

## Main idea

It is attempting to define the _dimension_ of a subspace as the number of vectors in one of its basis.
The following two sections considers the following questions:
1. Do different bases of a subspace contain the same number of vectors?
2. Can $\mathbb{R}^n$ contain a linearly independent set of infinitely many vectors?

It turns out intuition wins!
The answer is YES to 1 and NO to 2, and we will walk through these theoretical foundations of the dimension.

##### Basis exchange lemma (vector form)

Let $\beta = \{ {\bf b}_1, \ldots, {\bf b}_d \}$ be a basis of a subspace $V$.
Let ${\bf a}$ be a nonzero vector in $V$.
Then there is a vector ${\bf b}\in\beta$ such that $\beta\cup\{{\bf a}\}\setminus\{{\bf b}\}$ is again a basis of $V$.
Moreover, if ${\bf a} = c_1{\bf b}_1 + \cdots + c_d{\bf b}_d$, then ${\bf b}$ can be chosen as any ${\bf b}_i$ with $c_i\neq 0$.

##### Basis exchange lemma (set form)

Let $\beta = \{ {\bf b}_1, \ldots, {\bf b}_d \}$ be a basis of a subspace $V$.
Let $\alpha$ be a linearly independent set of (possibly infinitely many) vectors in $V$.
Then $|\alpha|<|\beta|$ and there is a subset $\beta'\subseteq\beta$ such that $\beta\cup\alpha\setminus\beta'$ is again a basis of $V$ and $|\beta'| = |\alpha|$.

## Side stories
- algorithm for exchanging the basis

## Experiments

##### Exercise 1

執行下方程式碼。
己知 ${\bf a}\in\operatorname{Col}(B)$。
令 ${\bf b}_1,\ldots,{\bf b}_3$ 為 $B$ 的各行向量。
令 $R$ 為 $B$ 的最簡階梯形式矩陣、
$\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]$ 為 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 的最簡階梯形式矩陣。

### code
set_random_seed(0)
print_ans = False
m,n,r = 4,3,3
B = random_good_matrix(m,n,r)
R = B.rref()
v = random_int_list(3, r=1)
a = B * vector(v)
aB = matrix(a).transpose().augment(B, subdivide=True)
eRp = aB.rref()
pivots = find_pivots(eRp)

print("[ a | B ] =")
show(aB)
print("R =")
show(R)
print("[ e1 | R' ] =")
show(eRp)

if print_ans:
    print("Number of pivots for R and [ e1 | R' ] are %s; they are the same."%len(pivots))
    print("The betaC for B is { b1, ..., b3 }.")
    print("The betaC for [ a | B ] is { a, " + ", ".join("b%s"%i for i in pivots[1:]) + " }.")
    print("a = " + " + ".join("%s u%s"%(v[i], i+1) for i in range(n)) )
    for i in range(n):
        if i in pivots:
            print("{ a, " + ", ".join("b%s"%(j+1) for j in range(n) if j != i) + " } is a basis.")
        else:
            print("{ a, " + ", ".join("b%s"%(j+1) for j in range(n) if j != i) + " } is not a basis.")

:::warning

- [x] 把你們的 `seed` 和題目的數字紀錄下來
:::

##### Exercise 1(a)

判斷 $R$ 和 $\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]$ 的軸數量是否一樣？
也就是 $B$ 和 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 所得出來的 $\beta_C$ 其包含的向量個數是否一樣？

***Ans:***
令`set_random_seed(0)`，
可得
$$R = \begin{bmatrix}
1 & 0 & 0 \\ 0 & 1 & 0 \\
0 & 0 & 1 \\ 0 & 0 & 0 \\\end{bmatrix}, \left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right] = \left[\begin{array}{c|ccc}
1 & 0 & -1 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\\end{array}\right],
$$
$$\left[\begin{array}{c|c} \ba & B \end{array}\right] = \left[\begin{array}{c|ccc}
-4 & 1 & 3 & 5 \\ 19 & -5 & -14 & -30 \\ -57 & 15 & 42 & 91 \\ -183 & 48 & 135 & 289 \\\end{array}\right].
$$
$R$ 的軸數量為 $3$，
$\left[\begin{array}{c|c}
{\bf e}_1 & R' \end{array}\right]$ 的軸數量也為 $3$，
因此 $R$ 和 $\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]$ 的軸數量一樣。

##### Exercise 1(b)

計算 $B$ 和 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 各算得出來的 $\beta_C$。

:::warning

- [x] pivot=1,2,3 --> 軸在 $1,2,3$ 的位置
- [x] $\beta_C$ = \begin{bmatrix}
1 \\ -5 \\ 15 \\ 48 \end{bmatrix}，\begin{bmatrix}
3 \\ -14 \\ 42 \\ 135 \\ \end{bmatrix}，\begin{bmatrix}
5 \\ -30 \\ 91 \\ 289 \\
\end{bmatrix}。
-->
$$\beta_C = \left\{\begin{bmatrix}
1 \\ -5 \\ 15 \\ 48 \end{bmatrix}, \begin{bmatrix}
3 \\ -14 \\ 42 \\ 135 \\ \end{bmatrix}, \begin{bmatrix}
5 \\ -30 \\ 91 \\ 289 \\
\end{bmatrix}\right\}.
$$
- [x] 後面改法一樣
:::

***Ans:***
由 $B$ 的最簡階梯形式矩陣 $R$ 可以得知，軸在 $1,2,3$ 的位置，因此可以得知
其
$$\beta_C = \left\{\begin{bmatrix}
1 \\ -5 \\ 15 \\ 48 \end{bmatrix}, \begin{bmatrix}
3 \\ -14 \\ 42 \\ 135 \\ \end{bmatrix}, \begin{bmatrix}
5 \\ -30 \\ 91 \\ 289 \\
\end{bmatrix}\right\}.
$$
由 $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 的最簡階梯形式矩陣 $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ 可以得知，軸在 $1,2,4$ 的位置上，因此可以得知
其
$$\beta_C = \left\{\begin{bmatrix}
-4 \\ 19 \\ -57 \\ -183 \end{bmatrix}, \begin{bmatrix}
1 \\ -5 \\ 15 \\ 48 \\ \end{bmatrix}, \begin{bmatrix}
5 \\ -30 \\ 91 \\ 289 \\
\end{bmatrix}\right\}.
$$

##### Exercise 1(c)

把 ${\bf a}$ 表示成 $B$ 的各行向量的線性組合。

***Ans:***
設 $c_1\bb_1 + c_2\bb_2 + c_3\bb_3 = \ba，c_1,c_2,c_3\in R$
則
$$
\begin{aligned}
c_1 + 3c_2 + 5c_3 &= -4, \\
-5c_1 - 14c_2 - 30c_3 &= 19, \\
15c_1 + 4c_2 + 9c_3 &= -57, \\
48c_1 + 135c_2 + 289c_3 &= -183.
\end{aligned}
$$

因此可得 $c_1=-1,c_2=-1,c_3=0$。

另解
**[由林柏仰同學提供]**
把 $\ba$ 表示成 $B$ 的各行向量的線性組合。

執行程式碼後得到

$$
\left[\begin{array}{c|c} \ba & B \end{array}\right] = \left[\begin{array}{c|ccc}
-4 & 1 & 3 & 5 \\ 19 & -5 & -14 & -30 \\ -57 & 15 & 42 & 91 \\ -183 & 48 & 135 & 289 \\
\end{array}\right] 。
$$

以及 $\left[\begin{array}{c|c}
\ba & B
\end{array}\right]$ 的最簡階梯型 $\left[\begin{array}{c|c}
e_1 & R'
\end{array}\right]$

$$
\left[\begin{array}{c|c} e_1 & R' \end{array}\right] =
\left[\begin{array}{c|ccc}
1 & 0 & -1 & 0 \\
0 & 1 & -1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
\end{array}\right] 。
$$

而因為 $\left[\begin{array}{c|c} e_1 & R' \end{array}\right]$ 的行向量間的關係和 $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 的行向量間的關係相同。
換句話說，若令 $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 的行向量依序為 $\{\ba,\bu_1,\bu_2,\bu_3\}$ ，並令 $\left[\begin{array}{c|c} e_1 & R' \end{array}\right]$ 的行向量依序為 $\{\br_1,\br_2,\br_3,\br_4\}$。
則若 $\br_1$ 可寫成 $\br_1 = c_2\br_2 + c_3\br_3 + c_4\br_4$ ，則 $\ba$ 也可寫成 $c_2\bu_2 + c_3\bu_3 + c_4\bu_4$。
而觀察 $\left[\begin{array}{c|c} e_1 & R' \end{array}\right]$ 會發現， $\br_1 = -1\br_2 - 1\br_3$ 。
故 $\ba$ 也可寫成 $\ba = -1\bu_2 - 1\bu_3$。

##### Exercise 1(d)

用程式計算看看對於哪些 $i = 1,\ldots, 3$﹐
$\beta\cup\{{\bf a}\}\setminus\{{\bf b}_i\}$ 是 $\operatorname{Col}(B)$ 的基底。

***Ans:***
根據 1(c) 的答案，我們可知 $\ba = -1\bb_1 - 1\bb_2$ ，
因此可得 $\beta\cup\{{\bf a}\}\setminus\{{\bf b}_1\}，\beta\cup\{{\bf a}\}\setminus\{{\bf b}_2\}$ 為 $\operatorname{Col}(B)$ 的基底，
而 $\beta\cup\{{\bf a}\}\setminus\{{\bf b}_3\}$ 不是 $\operatorname{Col}(B)$ 的基底。

## Exercises

##### Exercise 2

若 $\beta = \{ {\bf b}_1, {\bf b}_2, {\bf b}_3 \}$ 是子空間 $V$ 的一組基底。
已知 ${\bf a} = 4{\bf b}_2 + 5{\bf b}_3$。
令 $\beta_1 = \beta \cup \{{\bf a}\} \setminus \{ {\bf b}_3 \}$。

##### Exercise 2(a)

將 ${\bf b}_3$ 寫成 $\beta_1$ 的線性組合﹐
並說明 $\vspan(\beta) = \vspan(\beta_1) = V$。

:::warning

- [x] 令 ${\bf a}\in V$ 是一個非零向量 <-- 這句可以刪掉，要是 $\ba = \bzero$ 怎辦
- [x] 前面加：由於 $\ba\in V$，所以 $\vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = V$。
- [x] 中英數空格
- [x] 向量粗體
- [x] 可知${\bf \beta_1} = {\bf \beta} = V$ -->
可知
$$
\vspan(\beta_1) = \vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = \vspan(\beta) = V.
$$
:::

***Ans***

由於 $\ba\in V$，所以 $\vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = V$。
由 ${\bf a} = 4{\bf b}_2 + 5{\bf b}_3$ 得 ${{\bf b}_3 = \frac{1}{5}\ba - \frac{4}{5}{\bf b}_2} \in \vspan\{\ba,\bb_2\}$。
可知
$$
\vspan(\beta_1) = \vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = \vspan(\beta) = V.
$$

##### Exercise 2(b)

證明 $\beta_1$ 線性獨立﹐因此它是 $V$ 的一組基底。

:::warning

- [x] 純量不用粗體
- [ ] 這個答案只是把定義寫一遍，並沒有解釋為什麼。

設 $c_1\bb_1 + c_2\bb_2 + c_3\ba = \bzero$
則 ???。
由於 $\beta$ 獨立。
所以 ???。
因此 $\beta_1$ 獨立。
:::

***Ans***

設 $c_1\bb_1 + c_2\bb_2 + c_3\ba = \bzero$﹐
已知 ${\bf a} = 4{\bf b}_2 + 5{\bf b}_3$ 代入原式
使得 $c_1\bb_1 + c_2\bb_2 + c_3(4{\bf b}_2 + 5{\bf b}_3)$ ＝ $c_1\bb_1 + (c_2+4 c_3)\bb_2 + 5c_3\bb_3 ＝ \bzero$。
由於 $\beta$ 獨立。
所以 $c_1 = c_2 + 4c_3 = 5c_3 = 0$
並得到 $c_1 = c_2 = c_3 = 0$。
因此 $\beta_1$ 獨立。

##### Exercise 3

令 $\beta = \{{\bf b}_1,\ldots,{\bf b}_n\}$ 為子空間 $V$ 的一組基底
而 $B$ 為一矩陣其行向量為 $\beta$ 的向量。
令 $R$ 為 $B$ 的最簡階梯形式矩陣。
若 $i$ 為 $R$ 的一個軸﹐
則表示在 $R$ 上第 $i$ 行比前面幾行多了一列非零的元素﹐
因此我們有以下等價敘述：
1. $i$ is a pivot of $R$.
2. ${\bf b}_i\notin \operatorname{span}(\{{\bf b}_1,\ldots,{\bf b}_{i-1}\})$.

##### Exercise 3(a)

令 ${\bf a}\in V$ 是一個非零向量
並計算 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 的 $\beta_C$。
說明 ${\bf a}$ 一定會落在 $\beta_C$ 裡﹐
因此 $\beta_C$ 是 $V$ 的一組基底並且包含 ${\bf a}$。

:::warning

- [x] 因此 $\beta_C$ 是 $V$ 的一組基底並且包含 ${\bf a}$。 <-- 這句就是要證明的。

因為 $\ba\neq\bzero$，所以 $\ba\notin\vspan(\emptyset)$。
根據題目的說明，$\ba$ 會對應到 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 的 $\beta_C$ 的軸，所以一定會被選在 $\beta_C$ 裡。

由於 $\beta_C$ 是 $\Col(\left[\begin{array}{c|c} {\bf a} & B \end{array}\right])$ 的基底。
又 $\ba\in V$，所以 ???。
因此 ??? 是 ??? 的一組基底。
:::

***Ans***

因為 $\ba\neq\bzero$，所以 $\ba\notin\vspan(\emptyset)$。
且根據題目的說明，$\ba$ 會對應到 $\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]$ 的 $\beta_C$ 的軸，所以一定會被選在 $\beta_C$ 裡。

由於 $\beta_C$ 是 $\Col(\left[\begin{array}{c|c} {\bf a} & B \end{array}\right])$ 的基底，又 $\ba\in V$，
所以 $\Col(\left[\begin{array}{c|c} {\bf a} & B \end{array}\right]) = V$。
因此 $\beta_C$ 是 $V$ 的一組基底。

##### Exercise 3(b)

令 $\alpha$ 是一群 $V$ 中有限個數的向量且線性獨立﹐
且 $A$ 為一矩陣其各行向量為 $\alpha$ 中的向量。
並計算 $\left[\begin{array}{c|c} A & B \end{array}\right]$ 的 $\beta_C$。
說明 $\alpha\subseteq\beta_C$ 裡﹐
因此 $\beta_C$ 是 $V$ 的一組基底並且包含 $\alpha$。

**[由林柏仰同學提供]**
答:

若 $\alpha$ 為 $V$ 中一群有限個數的向量且線性獨立。
且 $A$ 為一個行向量為 $\alpha$ 中的向量的矩陣。
則我們可得知 $\alpha$ 相當於 $A$ 行向量的基底。

觀察 $\left[\begin{array}{c|c} A & B \end{array}\right]$ ，我們會發現由於 $A$ 的行向量為一群線性獨立的向量。
故若將 $\left[\begin{array}{c|c} A & B \end{array}\right]$ 進行列運算已得到其最簡階梯型的矩陣 $\left[\begin{array}{c|c} R_A & R_B \end{array}\right]$ ，我們會發現 $R_A$ 中的每一行都會對應到軸。
換句話說， $\left[\begin{array}{c|c} A & B \end{array}\right]$ 行向量的基底 $\beta_C$ 必定包含 $A$ 的行向量，也就是 $\alpha$ 。
因此 $\alpha\subseteq\beta_C$ 。
因為 $B$ 的行向量 $\beta$ 為 $V$ 的一組基底，故 $\Col(B) = \vspan(\beta) = V$
且 $\alpha$ 為 $V$ 中的一群有限個數且線性獨立的向量，故 $\vspan(\alpha)\subseteq\vspan(\beta)$ 。
同時 $\Col(A)\subseteq\Col(B)$ 為顯而易見的。
因此我們也可推斷出 $\vspan(\beta_C) = \Col([A|B]) = \Col(B) = V$ 。
換句話說， $\beta_C$ 為 $\vspan(\beta_C)$ 也就是 $V$ 的一組基底。

##### Exercise 4

證明 basis exchange lemma (vector form)。

**[由林柏仰同學提供]**
答:

令 $\beta = \{\bu_1,\bu_2,\ldots,\bu_k\}$ 為 $V$ 中的一組基底。
並令 $\ba$ 為一向量且 $\ba$ 滿足 $\ba\in V$
並且 $\ba$ 可寫成 $\ba = c_1\bu_1 + c_2\bu_2 + \ldots + c_k\bu_k$ 的形式。

若令 $\beta' = \{\ba,\bu_1,\bu_2,\ldots,\bu_k\}$ 。
我們會發現 $d_a\ba + d_1\bu_1 + d_2\bu_2 + \ldots + d_k\bu_k = \bzero$ 此等式有 $d_a = d_1 = \ldots = d_k = 0$ 以外的解的。
(只需令 $d_1 = -d_ac_1, d_2 = -d_ac_2, \ldots, d_k = -d_ac_k$ 即可。)
故 $\beta'$ 不為線性獨立。
且因 $\ba$ 為 $\beta$ 中的向量所寫出來的線性組合，故在 $\beta$ 中加入 $\ba$ 不會改變所張出的子空間。
換句話說， $V = \vspan(\beta) = \vspan(\beta')$

而若令 $\beta''$ 相當於 $\beta'$ 去掉 $\bu_1$ 。
事實上在 $\beta'$ 中拿掉 $\beta$ 中的任一向量形成 $\beta''$，接下來的動作與結果(證明 $\beta''$ 為一基底)都會類似，而在此以去掉 $\bu_1$ 做說明。
此時 $e_a\ba + e_2\bu_2 + \ldots + e_k\bu_k = \bzero$ 只有當 $e_a = e_2 = \ldots = e_k = 0$ 才會有解。
因為此等式相當於 $e_a\bu_1 + (e_ac_2 + e_2)\bu_2 + (e_ac_3 + e_3)\bu_3 + \ldots + (e_ac_k + e_k)\bu_k = 0$ 。
因 $\beta$ 為線性獨立，故所有係數皆須等於 $0$ 才會有解，相當於上述成立。
故 $\beta''$ 為線性獨立。
此時因為 $\bu_1$ 可被 $\{\ba,\bu_2\,\bu_3,\ldots,\bu_k\}$ 做出來，故去掉 $\bu_1$ 不會影響所張出的子空間。
換句話說， $V = \vspan(\beta') = \vspan(\beta'')$ 。

##### Exercise 5

利用 basis exchange lemma (vector form) 證明 basis exchange lemma (set form)。

**[由林柏仰同學提供]**
答:

令 $\beta = \{\bb_1,\bb_2,\ldots,\bb_d\}$ 為 $V$ 中的一組基底。
令 $\alpha$ 為 $V$ 中一群線性獨立的向量，這些向量可能有無窮多個 。
令 $\alpha' = \{\ba_1,\ba_2,\ldots,\ba_k\}$ 為 $\alpha$ 中的 $k$ 個向量，且 $\alpha'$ 也會是獨立集。
因為 $\alpha\subseteq V$ ，故 $\alpha$ 中的所有向量都可以寫成 $\beta$ 的線性組合。
因此 $\alpha'$ 裡的向量都可以寫成 $\beta$ 的線性組合。

此時依據向量版的基底交換法則，我們可在 $\beta$ 中找到一向量 $\bb_1$ ，並且 $\bb_1$ 滿足在 $\ba_1$ 寫成 $\beta$ 的線性組合時， $\bb_1$ 的係數不為 $0$ 。
故我們可將 $\ba_1$ 和 $\bb_1$ 交換並形成新的一基底 $\beta_1$ ，且 $\beta_1 = (\beta\cup\{\ba_1\})\setminus\{\bb_1\}$ 。
接下來，我們可以重複以上動作直到 $\alpha'$ 中的向量都被交換進去。
而在這個過程中，因為 $\alpha'$ 為獨立集，故 $\alpha'$ 中的任一向量 $\ba_i$ 都不能用 $\alpha'\setminus\{\ba_i\}$ 表示出來。
故我們在每次交換中都可以在 $\beta$ 中找到一向量交換出去。
而若將 $\beta$ 中被交換出去的所有向量看成一集合 $\beta'$ 。
最後我們會得到 $\beta_k =(\beta\cup\alpha')\setminus\beta'$ 為一基底。

:::info
數學不完整：1c, 1d, 2a, 2b, 3a, 3b, 4, 5

目前分數：4/5
:::