基底交換法則

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

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.")

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\)。

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©

把 \({\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© 的答案，我們可知 \(\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\)。

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

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}\)。

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'\) 為一基底。