維度、擴充與縮限法則

# 維度、擴充與縮限法則 ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png) 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 %} ```python 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]$ 的最簡階梯形式矩陣。 ```python ### 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$。 :::warning - [x] $\ba$=(-177,701,3324,-6482) --> $\ba =(-177,701,3324,-6482)$ - [x] 所以 $\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\} $$ 的維度。 :::warning - [x] 由矩陣 $R$ 可以得到 $A$ 的軸 $pivot=3$， --> 由矩陣 $R$ 可以得到 $A$ 的軸數為 $3$， - [x] $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\} $$ 的維度。 :::warning - [x] 最簡階梯形式 --> 階梯形式（你們的 $R$ 沒有消到最簡） - [x] $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(c) 令 $$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}\} $$ 的維度。 :::warning - [x] 這題是問 $\ker(A)$ 的維度 - [x] 由矩陣 $R$ 得知矩陣 $A$ 軸的個數 $pivot = 2$， --> 由矩陣 $R$ 得知矩陣 $A$ 軸的個數為 $2$， - [x] 故維度 $\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}\} $$ 的維度。 :::warning - [ ] 照上一題改 ::: $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$ 的一組基底。 :::warning - [x] $u_1$, $u_2$ --> $\bu_1$, $\bu_2$（其它向量也要粗體） - [x] $\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))$ 的一組基底。  :::warning - [x] 向量粗體 - [x] 由矩陣 $C'$ 的軸位於 $x_1,x_2,x_3$ 得知 --> 由矩陣 $C'$ 的軸位於 $1, 2, 3$ 得知 - [x] $$\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。  :::warning - [x] 取 $\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$ 中的子空間都有一組有限個數的基底。 :::warning 令 $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$ 的一組基底。 :::success 目前分數： 5.5 分 :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.