維度、擴充與縮限法則

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

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

Main idea

An important consequence of the basis exchange lemma is:
If \(V\) has a finite basis \(\beta\), then every linearly independent set \(\alpha\) in \(V\) is finite and \(|\alpha|\leq |\beta|\).
Suppose \(V\) has two finite bases \(\alpha\) and \(\beta\).
Then we have \(|\beta|\leq |\alpha|\) and \(|\alpha|\leq|\beta|\), so \(|\alpha| = |\beta|\).
Therefore, if \(V\) has a finite basis, then every basis of \(V\) has the same size.
We define the dimension of \(V\) as the size of a basis of \(V\), denoted as \(\dim(V)\).

Starting with a linearly independent set, one may keep adding vectors not in the span until it becomes a basis.
The only unfortunate case is the unintuitive possibilty when adding new vectors never reaches to a spanning set but results in a linearly independent set of infinitely many vectors.
However, the basis exchange lemma excludes this possibility!

Expanding lemma

Let \(V\) be a subspace contained in another subspace \(U\).
Suppose \(U\) is has a finite basis.
Let \(\alpha\) be a linearly independent set in \(V\).
Then there is a finite basis \(\beta\) of \(V\) with \(\alpha\subseteq\beta\).
In particular, every subspace in \(\mathbb{R}^n\) has a finite basis.

On the other hand, one may start with a spanning set and keep removing redundant vectors.
(We have seen this before, but let's formally write it down as below.)

Shrinking lemma

Let \(V = \operatorname{span}(S)\) be a subspace and \(S\) a finite set of vectors.
Then there is a basis \(\beta\) of \(V\) with \(\beta\subseteq S\)

Side stories

  • common subspaces
  • intersection and sum of two subspaces

Experiments

Exercise 1

執行下方程式碼。
令 \(S = \{ {\bf u}_1, \ldots, {\bf u}_5 \}\) 為 \(A\) 的各行向量
且 \(V = \operatorname{span}(S)\)。
已知 \({\bf a}\in V\)、
\(R\) 為 \(A\) 的最簡階梯形式矩陣、
\(\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]\) 為 \(\left[\begin{array}{c|c} {\bf a} & A \end{array}\right]\) 的最簡階梯形式矩陣。

### code
set_random_seed(0)
print_ans = False
m,n,r = 4,5,3
A, R, A_pivots = random_good_matrix(m,n,r, return_answer=True)
a = A * vector(random_int_list(5))
aA = matrix(a).transpose().augment(A, subdivide=True)
aR = aA.rref()
aA_pivots = find_pivots(aR)

print("A =")
show(A)
print("a =", a)
print("R =")
show(R)
print("[ e1 | R' ] =")
show(aR)

if print_ans:
    print("{ a, " + ", ".join("u%i"%(i) for i in aA_pivots[1:]) + " } is a basis of V containing a.")
    print("{ " + ", ".join("u%i"%(i+1) for i in A_pivots) + " } is a basis of V contained in S.")
Exercise 1(a)

求一組 \(V\) 的基底 \(\beta\) 且 \({\bf a}\in \beta\)。

  • \(\ba\)=(-177,701,3324,-6482) –> \(\ba =(-177,701,3324,-6482)\)
  • 所以 \(\beta\) 相當於 \(\left[\begin{array}{c|c} {\bf a} & A \end{array}\right]\) 對應到軸的向量所組成。
    \[ \beta = \begin{bmatrix} -177 & 1 & -3\\ 701 & -4 & 13\\ 3324 & -19&61\\ -6482 & 37&-119 \end{bmatrix}. \] –>
    所以 \(\beta\) 可以取為 \[ \begin{bmatrix} -177 & 1 & -3\\ 701 & -4 & 13\\ 3324 & -19&61\\ -6482 & 37&-119 \end{bmatrix} \] 的行向量，其中第一行為 \(\ba\)。

當 set_random_seed(0) 時，會有以下數字 \[ A = \begin{bmatrix} 1 & -3 & 3 & 18 & 29 \\ -4 & 13&-8&-77&-109 \\ -19&61&-40&-362&-520 \\ 37&-119&-78&706&1014 \\ \end{bmatrix}. \] \(\ba =(-177,701,3324,-6482)\) \[ R=\begin{bmatrix} 1&0&0&3&5 \\ 0&1&0&-5&-5 \\ 0&0&1&0&3 \\ 0&0&0&0&0 \\ \end{bmatrix}. \] \[\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]= \left[\begin{array}{c|ccccc} 1 & 0 & 0 & \frac{-1}{11} & 0 & \frac{-3}{-11} \\ 0 & 1 & 0 & -3 & 3 & -4 \\ 0 & 0 & 1 & \frac{37}{11} & -5 & \frac{56}{11} \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}\right]. \] 其中 \(\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]\) 為 \(\left[\begin{array}{c|c} {\bf a} & A \end{array}\right]\) 的最簡階梯形式矩陣。
而我們發現 \(\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]\) 的前三行對應到軸，
因此我們可知 \(\left[\begin{array}{c|c} {\bf a} & A \end{array}\right]\) 剛好也對應到軸。
所以 \(\beta\) 可以取為 \[ \begin{bmatrix} -177 & 1 & -3\\ 701 & -4 & 13\\ 3324 & -19&61\\ -6482 & 37&-119 \end{bmatrix} \] 的行向量，其中第一行為 \(\ba\)。

Exercise 1(b)

求一組 \(V\) 的基底 \(\beta\) 且 \(\beta\subseteq S\)。

\(Ans:\)
若將 \(A\) 進行列運算得到其最簡階梯形的矩陣 \(R\) 。
\[ R=\begin{bmatrix} 1&0&0&3&5 \\ 0&1&0&-5&-5 \\ 0&0&1&0&3 \\ 0&0&0&0&0 \\ \end{bmatrix}. \] 由此矩陣可知 \(R\) 的前三行為軸，換句話說， \(A\) 的前三行也為軸。
故若令 \(\beta\) 為 \(A\) 的前三行向量， \(\beta\) 為 \(\Col(A)\) 的基底。
而 \(A\) 的各行向量為 \(S\) 中的向量，換句話說 \(\beta\) 也是 \(V\) 的基底，且 \(\beta\subseteq S\)。

Exercises

Exercise 2(a)

求
\[V = \operatorname{span}\left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 1 \\ 4 \\ 9 \end{bmatrix} \right\} \]
的維度。

  • 由矩陣 \(R\) 可以得到 \(A\) 的軸 \(pivot=3\)， –> 由矩陣 \(R\) 可以得到 \(A\) 的軸數為 \(3\)，
  • \(dim\) –> \(\dim\)

\(Ans:\)

令 \(A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}\)

將 \(A\) 經列運算後得到 \(A\) 的最簡階梯型矩陣 \(R = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix}.\)

由矩陣 \(R\) 可以得到 \(A\) 的軸數為 \(3\)，

故 \(V\) 的維度 \(\dim(V)=3\)。

Exercise 2(b)

求
\[V = \operatorname{span}\left\{ \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \right\} \]
的維度。

  • 最簡階梯形式 –> 階梯形式（你們的 \(R\) 沒有消到最簡）
  • \(dim\) –> \(\dim\)

\(Ans:\)
令
\[A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 2 & 1 & 1 \end{bmatrix}\]

將 \(A\) 經過列運算後可得 \(A\) 的最簡階梯形式為
\[R =\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}\]

由矩陣 \(R\) 可得 \(A\) 有兩個軸，

故 \(V\) 的維度 \(\dim(V)=2\)。

Exercise 2©

令 \[A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} \] 求
\[V = \{ {\bf x}\in\mathbb{R}^4 : A{\bf x} = {\bf 0}\} \]
的維度。

  • 這題是問 \(\ker(A)\) 的維度
  • 由矩陣 \(R\) 得知矩陣 \(A\) 軸的個數 \(pivot = 2\)， –> 由矩陣 \(R\) 得知矩陣 \(A\) 軸的個數為 \(2\)，
  • 故維度 \(\dim(V) = 2\)。 –> 故維度 \(\dim(V) = \dim(\ker(A)) = ...\)，也就是自由變數的個數。

\(Ans:\)
將矩陣 \(A\) 化簡為最簡階梯形式，得：
\[R = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix}. \] 由矩陣 \(R\) 得知矩陣 \(A\) 軸的個數為 \(2\)，
故維度 \(\dim(V) = \dim(\ker(A)) = 4 - 2 = 2\)，也就是自由變數的個數。

Exercise 2(d)

令 \[A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 1 \\ \end{bmatrix}.\] 求
\[V = \{ {\bf x}\in\mathbb{R}^4 : A{\bf x} = {\bf 0}\} \]
的維度。

  • 照上一題改

\(Ans:\)
將 \(A\) 矩陣化簡為最簡階梯式
\[R = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 &0 & 0 \\ \end{bmatrix}. \]

\(R\) 的軸數為 \(2\)，
因此 \(A\) 矩陣的維度 \(\dim(A)=2\)。
故維度 \(\dim(V) = \dim(\ker(A)) = 4 - 2 = 2\)，也就是自由變數的個數。

Exercise 3

令 \(U = \{ {\bf x} = (x,y,z,w)\in\mathbb{R}^4 : x + y + z + w = 0 \}\) 且
\(V = \{ {\bf x} = (x,y,z,w)\in\mathbb{R}^4 : x + y + 2z + 2w = 0 \}\)。
求出 \({\bf u}_1, \ldots, {\bf u}_4\) 使得
\(\{ {\bf u}_1,{\bf u}_2 \}\) 是 \(U\cap V\) 的一組基底、
\(\{ {\bf u}_1,{\bf u}_2,{\bf u}_3 \}\) 是 \(U\) 的一組基底、
\(\{ {\bf u}_1,{\bf u}_2,{\bf u}_4 \}\) 是 \(V\) 的一組基底。

  • \(u_1\), \(u_2\) –> \(\bu_1\), \(\bu_2\)（其它向量也要粗體）
  • \(\bu_3\) 和 \(\bu_4\) 的找法沒有很明確說明為什麼 \(\{\bu_1,\bu_2,\bu_3\}\) 是 \(U\) 的一組基底。建議以下的寫法：

空間 \(U\) 可以看成是矩陣 \(\begin{bmatrix} 1 & 1 & 1 \end{bmatrix}\) 的核。經過計算 \(\beta_K\) 可以知道 \(U = \Col(A_U)\)，其中 \[A_U =\begin{bmatrix} -1&-1&-1 \\ 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix}. \]
將增廣矩陣
\[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_U \end{array}\right] \] 化簡為最簡階梯形式
\[ \left[\begin{array}{cc|c} ? & ? & ? \end{array}\right] \] 並知道 \(\{\bu_1,\bu_2,\bu_3\}\) 為 \[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_U \end{array}\right] = \Col(A_U) = U \] 的一組基底，其中 \(\bu_3\) 為 \(A_U\) 的第 ? 行。

\(Ans：\)
由定義可知 \(U\cap V\) 包含了所有滿足 \[ \begin{cases} x&+ y&+ z&+ w&= 0,\\ x&+ y&+ 2z&+ 2w&= 0. \end{cases} \] 的向量 \(\bx = (x,y,z,w)\)。
將方程式化簡可得 \[ \begin{cases} x&+ y& & &= 0,\\ & & z&+ w&= 0. \end{cases} \] 令 \(y = a, w = b\) ， \(a,b\in\mathbb{Z}\)，
則
\[\begin{bmatrix} x \\ y \\ z \\ w \end{bmatrix}= \begin{bmatrix} -a \\ a \\ -b \\ b \end{bmatrix}= \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix}a + \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \end{bmatrix}b. \] 取 \(\bu_1 =\begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix}\), \(\bu_2 =\begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \end{bmatrix}，\) 得 \(\{ {\bf u}_1,{\bf u}_2 \}\) 是 \(U\cap V\) 的一組基底。

空間 \(U\) 可以看成是矩陣 \(\begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}\) 的核。
經過計算 \(\beta_K\) 可以知道 \(U = \Col(A_U)\)，其中 \[A_U =\begin{bmatrix} -1&-1&-1 \\ 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix}. \]
將增廣矩陣
\[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_U \end{array}\right] \] 化簡為最簡階梯形式
\[ \left[\begin{array}{cc|ccc} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \] 並知道 \(\{\bu_1,\bu_2,\bu_3\}\) 為 \[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_U \end{array}\right] = \Col(A_U) = U \] 的一組基底，其中 \(\bu_3\) 為 \(A_U\) 的第 2 行。

空間 \(V\) 可以看成是矩陣 \(\begin{bmatrix} 1 & 1 & 2 & 2 \end{bmatrix}\) 的核。
經過計算 \(\beta_K\) 可以知道 \(V = \Col(A_V)\)，其中
\[A_V =\begin{bmatrix} -1&-2&-2 \\ 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix}. \]
將增廣矩陣
\[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_V \end{array}\right] \] 化簡為最簡階梯形式
\[ \left[\begin{array}{cc|ccc} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \] 並知道 \(\{\bu_1,\bu_2,\bu_4\}\) 為 \[ \left[\begin{array}{cc|c} \bu_1 & \bu_2 & A_V \end{array}\right] = \Col(A_V) = V \] 的一組基底，其中 \(\bu_4\) 為 \(A_V\) 的第 \(2\) 行。

Exercise 4

令
\[A = \begin{bmatrix} 1 & 2 \\ 1 & 2 \\ 2 & 1 \\ 2 & 1 \\ \end{bmatrix}, B = \begin{bmatrix} 1 & 2 \\ 2 & 1 \\ 1 & 2 \\ 2 & 1 \\ \end{bmatrix}. \]
求 \(\operatorname{span}(\operatorname{Col}(A) \cup \operatorname{Col}(B))\) 的一組基底。

  • 向量粗體
  • 由矩陣 \(C'\) 的軸位於 \(x_1,x_2,x_3\) 得知 –> 由矩陣 \(C'\) 的軸位於 \(1, 2, 3\) 得知
  • \[\beta_C = \begin{bmatrix} 1 & 2 & 1 \\ 1 & 2 & 2 \\ 2 & 1 & 1 \\ 2 & 1 & 2 \end{bmatrix}. \] –> \[\beta_C = \left\{ \begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix}, \begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \\ 2 \end{bmatrix} \right\}. \]

\(Ans:\)
令
\[\bu_1 = \begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix}、 \bu_2 = \begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \end{bmatrix}、 \bu_3 = \begin{bmatrix} 1 \\ 2 \\ 1 \\ 2 \end{bmatrix}、 \bu_4 = \begin{bmatrix} 2 \\ 1 \\ 2 \\ 1 \end{bmatrix}, \]
則 \(\operatorname{span}(\operatorname{Col}(A) \cup \operatorname{Col}(B))\) = \(\operatorname{span}(\{ {\bf u}_1 , {\bf u}_2 , {\bf u}_3, {\bf u}_4\})\)，
令矩陣
\[C = \begin{bmatrix} 1 & 2 & 1 & 2\\ 1 & 2 & 2 & 1\\ 2 & 1 & 1 & 2\\ 2 & 1 & 2 & 1 \end{bmatrix}.\] 將其化簡為最簡階梯形式為
\[C' = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 0 \end{bmatrix}.\]
由矩陣 \(C'\) 的軸位於 \(1, 2, 3\) 得知，
\(\operatorname{span}(\operatorname{Col}(A) \cup \operatorname{Col}(B))\) 的一組基底可為
\[\beta_C = \left\{ \begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix}, \begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \\ 2 \end{bmatrix} \right\}. \]

Exercise 5

證明 expanding lemma。

  • 取 \(\beta'\) 與 \(\beta\) 交集之集合 \(S\)，
    得 \(\{ {\bf \alpha} , {\bf S} \} = \{ {\bf \beta'} \}\)， –> 且 \(\alpha\subseteq\beta'\)。

\(Ans:\)
已知集合 \(V\) 存在一組 \(\beta\) 為有限基底。
令 \(\alpha\) 為線性獨立的集合，
根據基底交換法則，
若將 \(\beta\) 中部分向量集合用 \(\alpha\) 取代得到 \(\beta'\)，
則 \(\beta'\) 仍為集合 \(V\) 的一組有限基底，
且 \(\alpha\subseteq\beta'\)。
故 expanding lemma 得證。

Exercise 6

利用 expanding lemma 證明所有 \(\mathbb{R}^n\) 中的子空間都有一組有限個數的基底。

令 \(V\) 為一 \(\mathbb{R}^n\) 中的子空間。
若 \(\alpha\) 為 \(V\) 中的一線性獨立集，
則 \(\alpha\) 同時也是 ??? 的一線性獨立集。
根據 expanding lemma，\(\alpha\) 可以擴展成一組 \(\mathbb{R}^n\) 的基底，其大小為 \(n\)，因此 \(\alpha\) 的個數有限。
由於這個論證對所有 \(V\) 中的獨立集都對，所以 \(V\) 中的獨立集個數都是有限個，且個數不超過 ?。

取一個 \(V\) 中個數最多的獨立集 \(\beta\)。
若 \(V \neq \vspan(\beta)\)，則存在 \(\bv\) 落在 ??? 中。
因此 \(\beta \cup \{\bv\}\) 是 \(V\) 中一個更大的獨立集，這和 \(\beta\) 的個數最多的假設相矛盾。
所以 ???。
也就是 ??? 為 \(V\) 的一組基底。

\(Ans:\)

令 \(V\) 為一 \(\mathbb{R}^n\) 中的子空間。
若 \(\alpha\) 為 \(V\) 中的一線性獨立集，
則 \(\alpha\) 同時也是 \(\mathbb{R}^n\) 的一線性獨立集。
根據 expanding lemma，\(\alpha\) 可以擴展成一組 \(\mathbb{R}^n\) 的基底，其大小為 \(n\)，因此 \(\alpha\) 的個數有限。
由於這個論證對所有 \(V\) 中的獨立集都對，所以 \(V\) 中的獨立集個數都是有限個，且個數不超過 \(n\)。

取一個 \(V\) 中個數最多的獨立集 \(\beta\)。
若 \(V \neq \vspan(\beta)\)，則存在 \(\bv\) 落在 \(V \setminus \vspan(\beta)\) 中。
因此 \(\beta \cup \{\bv\}\) 是 \(V\) 中一個更大的獨立集，這和 \(\beta\) 的個數最多的假設相矛盾。
所以 \(V = \vspan(\beta)\)。
也就是 \(\beta\) 為 \(V\) 的一組基底。

目前分數： 5.5 分

Select a repo