# 基底交換法則

Basis exchange lemma

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\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

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 = \{ \bb_1, \ldots, \bb_d \}$ be a basis of a subspace $V$.
Let $\ba$ be a nonzero vector in $V$.
Then there is a vector $\bb\in\beta$ such that $\beta\cup\{\ba\}\setminus\{\bb\}$ is again a basis of $V$.
Moreover, if $\ba = c_1\bb_1 + \cdots + c_d\bb_d$, then $\bb$ can be chosen as any $\bb_i$ with $c_i\neq 0$.

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

Let $\beta = \{ \bb_1, \ldots, \bb_d \}$ be a basis of a subspace $V$.
Let $\alpha$ be a linearly independent set of (possibly infinitely many) vectors in $V$.
Then $|\alpha| \leq |\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

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

<!-- eng start -->
Run the code below. Suppose $\ba\in\Col(B)$. Let $\bb_1, \ldots, \bb_3$ be the columns of $B$. Let $R$ be the reduced echelon form of $B$ and $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ the reduced echelon form of $\left[\begin{array}{c|c} \ba & B \end{array}\right]$.
<!-- eng end -->

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

By running the code above, we obtain that
$$
\left[\begin{array}{c|c} \ba & B \end{array}\right]
= \left[\begin{array}{c|cc} \
-4 & 1 & 3 & 5 \\
19 &-5 &-14 &-30\\
-57 & 15 & 42 & 91\\
-183&48&135 & 289
\end{array}\right],
$$
$$
R = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0
\end{bmatrix},
$$
and
$$
\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]
= \left[\begin{array}{c|cc} \
1 & 0 & -1 & 0 \\
0 & 1 & -1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0
\end{array}\right].
$$

##### Exercise 1(a)

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

<!-- eng start -->
Determine if $R$ and $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ have the same number of pivots. Equivalently, do the $\beta_C$ for $B$ and the $\beta_C$ for $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ have the same size?

:::success
Good. You may think about why this is true :shrug: .
:::

:::warning

However, your $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ and $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ should have four columns.
:::

##### Exercise 1(a) - answer here

From the code we know that<!-- eng end -->
$$
\ba = ( {-4}，{19}，{-57}，{-183}) ,
$$
$$
\ B = \begin{bmatrix}
1 & 3 & 5 \\
-5 &-14 &-30\\
15 & 42 & 91\\
48 &135 & 289
\end{bmatrix}
$$
and

$$\ R = \begin{bmatrix}
1 & 3 & 5 \\
0 & 1 &-5 \\
0 & 0 & 1 \\
0 & 0 & 0
\end{bmatrix},
$$
so $R$ have $3$ pivots.

We can get

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

and

$$
\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]
= \left[\begin{array}{c|cc} \
1 & 0 & -1 & 0 \\
0 & 1 & -1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0
\end{array}\right],
$$

so $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ have $3$ pivots.

So we can know that $R$ and $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ have the same number of pivots.

##### Exercise 1(b)

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

<!-- eng start -->
Find the $\beta_C$ for $B$ and the $\beta_C$ for $\left[\begin{array}{c|c} \ba & B \end{array}\right]$.
<!-- eng end -->

:::warning

Grammar:

- [x] "therefore" is not a conjunction, so it should be "Sentence ... . Therefore, ..." or "Sentence ..., so ... ."
:::

##### Exercise 1(b) - answer here

By $B$ 's reduced echelon form $R$, we can know that, the pivots are on $1,2,3$ , so we can know that
$$\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\}.
$$
By $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 's reduced echelon form $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ , we can know that, the pivots are on $1,2,4$ , because of that we can know that
$$\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)

把 $\ba$ 表示成 $B$ 的各行向量的線性組合。
<!-- eng start -->
Write $\ba$ as a linear combination of the columns of $B$.
<!-- eng end -->

:::warning

Math:

Instead of the direct calculation, can you read the relation $\ba + \bb_1 + \bb_2 = \bzero$ from $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$?

Writing:

- [x] Your answer is not complete.

Typesetting:

- [x] Use boldface for vectors.
:::

##### Exercise 1(c) - answer here

By running the code above, we obtain that

$$
\ba = ( {-4}，{19}，{-57}，{-183}) ,
$$
$$
\ B = \begin{bmatrix}
1 & 3 & 5 \\
-5 &-14 &-30\\
15 & 42 & 91\\
48 &135 & 289
\end{bmatrix}.
$$
We set $\bb_1$, $\bb_2$, $\bb_3$ as the columns of $B$.
$$
\bb_1 = ( {1}，{-5}，{15}，{48})
, $$

$$
\bb_2 =( {3}，{-14}，{42}，{135})
, $$

$$
\bb_3 = ( {5}，{-30}，{91}，{289})
.
$$

If $\ba$ is a linear combination of $\bb_1$, $\bb_2$ and $\bb_3$, the equation $c_1\bb_1 + c_2\bb_2 + c_3\bb_3 ＝ \bzero$ will be hold. ($c_1,c_2,c_3\in\mathbb{R}$)

By calculation, we can get that
$c_1 = c_2 = -1$,
$c_3 = 0$, so we know that $\ba$ is a linear combination of $\bb_1$ and $\bb_2$,

$$
\ba = -\bb_1-\bb_2.
$$

We see this question in the other way.
We calculate the matrix $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ and we can get the reduced echelon form $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$.
According to the property of linear combination and Gaussian elimination, if the vector $\ba$ and the matrix $B$ has the reduced echelon form, it means $\ba$ can be combinated by the columns of $B$.

##### Exercise 1(d)

用程式計算看看對於哪些 $i = 1,\ldots, 5$﹐
$\beta\cup\{\ba\}\setminus\{\bb_i\}$ 是 $\Col(B)$ 的基底。

<!-- eng start -->
Use computer if necessary, check if $\beta\cup\{\ba\}\setminus\{\bb_i\}$ is a basis of $\Col(B)$ for each $i = 1, \ldots, 5$.
<!-- eng end -->

:::warning

Writing:

- [x] Check missing period.
:::

##### Exercise 1(d) - answer here
From the answer to 1(c), we know that $\ba = -\bb_1 - \bb_2$.
So $\beta\cup\{{\bf a}\}\setminus\{{\bf b}_1\}, \beta\cup\{{\bf a}\}\setminus\{{\bf b}_2\}$ is the basis of $\operatorname{Col}(B)$,
And $\beta\cup\{{\bf a}\}\setminus\{{\bf b}_3\}$ is not the base of $\operatorname{Col}(B)$.

## Exercises

##### Exercise 2

若 $\beta = \{ \bb_1, \bb_2, \bb_3 \}$ 是子空間 $V$ 的一組基底。
已知 $\ba = 4\bb_2 + 5\bb_3$。
令 $\beta_1 = \beta \cup \{\ba\} \setminus \{ \bb_3 \}$。

<!-- eng start -->
Let $\beta = \{ \bb_1, \bb_2, \bb_3 \}$ be a basis of the subspace $V$. Suppose $\ba = 4\bb_2 + 5\bb_3$. Let $\beta_1 = \beta \cup \{\ba\} \setminus \{ \bb_3 \}$.
<!-- eng end -->

##### Exercise 2(a)

將 $\bb_3$ 寫成 $\beta_1$ 的線性組合﹐
並說明 $\vspan(\beta) = \vspan(\beta_1) = V$。

<!-- eng start -->
Write $\bb_3$ as a linear combination of $\beta_1$. Then explain why $\vspan(\beta) = \vspan(\beta_1) = V$.
<!-- eng end -->

:::warning

:thumbsup: Nice answer!

Grammar:

- [x] Due to ..., ~~so~~ ... .
:::

##### Exercise 2(a) - answer here

Due to $\ba\in V$, $\vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = V$.
By ${\bf a} = 4{\bf b}_2 + 5{\bf b}_3$, we get ${{\bf b}_3 = \frac{1}{5}\ba - \frac{4}{5}{\bf b}_2} \in \vspan\{\ba,\bb_2\}$.
So we know that,
$$
\vspan(\beta_1) = \vspan(\{\ba,\bb_1,\bb_2,\bb_3\}) = \vspan(\beta) = V.
$$
##### Exercise 2(b)

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

<!-- eng start -->
Show that $\beta_1$ is linearly independent, so it is a basis of $V$.
<!-- eng end -->

:::warning

Beautiful answer :heart: .

Grammar:

- [x] Let ... .
- [x] We knew that ... . --> By substituting $\ba = 4\bb_2 + 5\bb_3$, we have $c_1... = \bzero$.
:::

##### Exercise 2(b) - answer here

Let $c_1\bb_1 + c_2\bb_2 + c_3\ba = \bzero$. By substituting ${\bf a} = 4{\bf b}_2 + 5{\bf b}_3$, we have $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$.
Because of the independence of $\beta$,
$c_1 = c_2 + 4c_3 = 5c_3 = 0$,
and we get $c_1 = c_2 = c_3 = 0$.
Thus $\beta_1$ is independent.

##### Exercise 3

對任一矩陣 $A$ 而言，
若 $\bu_1, \ldots, \bu_n$ 為 $A$ 的向行向量、
且 $R$ 為 $A$ 的最簡階梯形式，
則已知以下敘述等價：

1. $i$ is a pivot of $R$.
2. $\bu_i\notin \vspan(\{\bu_1,\ldots,\bu_{i-1}\})$.

對以下小題，
令 $\beta = \{\bb_1,\ldots,\bb_n\}$ 為子空間 $V$ 的一組基底
而 $B$ 為一矩陣其行向量為 $\beta$ 的向量。

<!-- eng start -->
Let $A$ be a matrix and $\bu_1, \ldots, \bu_n$ its columns. Let $R$ be the reduced echelon form of $A$. It is known that the following are equivalent:

1. $i$ is a pivot of $R$.
2. $\bu_i\notin \vspan(\{\bu_1,\ldots,\bu_{i-1}\})$.

For the following problems, let $V$ be a subspace, $\beta = \{\bb_1,\ldots,\bb_n\}$ its basis, and $B$ the matrix whose columns are vectors in $\beta$.
<!-- eng end -->

##### Exercise 3(a)

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

<!-- eng start -->
Let $\ba\in V$ be a nonzero vector and caculate the $\beta_C$ of $\left[\begin{array}{c|c} \ba & B \end{array}\right]$. Explain why $\ba$ must be in $\beta_C$. Therefore, $\beta_C$ is a basis of $V$ containing $\ba$.
<!-- eng end -->

:::success
Nice answers for 3(a) and 3(b).
:::

:::warning

Math error:

"Independent" is an adjective for a set, so the sentence "$\ba$ is not independent with $\bb_1, \ldots, \bb_n$" does not really make sense mathematically.

Typesetting:

- [x] $Col$ --> $\Col$
:::

##### Exercise 3(a) - answer here

According to the questions, let $\beta$ be a basis of $V$ and $B$ be the matrix, like

$$
B = \begin{bmatrix}
| & ~ & | \\
\bb_1 & \cdots & \bb_n \\
| & ~ & | \\
\end{bmatrix}.
$$

And we set $\ba$ is a vector in $V$.

We will find that because $\ba$ is a vector in $V$, it means $\ba$ is a linear combination of $c_1\bb_1+ \ldots+ c_n\bb_n$.

Because of that, we know that

$$
\Col(B) = \Col(\left[\begin{array}{c|c} \ba & B \end{array}\right]).
$$

After calculating by Gaussian elimination, we get the reduced echelon form of $B$ is $R$,
the reduced echelon form of $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ is $R'$.

Because $\ba$ is a linear combination of $c_1\bb_1+ \ldots+ c_n\bb_n$, according to Gaussian elimination, the pivots of $R'$ has to contain vector $\ba$. And also, $\ba$ must be in $\beta_C$.

Due to $\Col(B) = \Col(\left[\begin{array}{c|c} \ba & B \end{array}\right])$ and $\ba$ must be in $\beta_C$, we can understand $\beta_C$ is a basis of $V$ containing $\ba$.

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

<!-- eng start -->
Let $\alpha$ be a finite set of vectors in $V$ such that $\alpha$ is linearly independent. Let $A$ be the matrix whose columns are vectors in $\alpha$ and calculate the $\beta_C$ of $\left[\begin{array}{c|c} A & B \end{array}\right]$. Explain why $\alpha\subseteq\beta_C$. Therefore, $\beta_C$ is a basis of $V$ containing $\alpha$.
<!-- eng end -->

##### Exercise 3(b) - answer here

The exercise 3(b) is a extension of the exercise 3(a).

In the exercise 3(a), we only exchange one vector, but in the exercise 3(b) we are exchange a finite set of vectors in $V$ into the matrix.

We set $\alpha$ be a finite set of vectors in $V$ such that $\alpha$ is linearly independent. Because $\alpha$ is linearly independent, it means $\alpha$ can't be combined by $\bb_1, \ldots, \bb_n$.

Let $A$ be the matrix whose columns are vectors in $\alpha$.

After calculating the matrix $\left[\begin{array}{c|c} A & B \end{array}\right]$ by Gaussian elimination, we can get the $\beta_C$ of $\left[\begin{array}{c|c} A & B \end{array}\right]$.

Because of Gaussian elimination, we will see that $\beta_C$ is reduced by the matrix $A$.
The columns of the matrix $A$ are vector in $\alpha$, $\beta_C$ is reduced by the matrix $A$, so $\alpha\subseteq\beta_C$ .
$\alpha$ will be the new pivots of the reduced echlon form of $\left[\begin{array}{c|c} A & B \end{array}\right]$.

Because $\alpha$ is a finite set of vectors in $V$, $\beta_C$ is also in $V$.

After the above discussion, we can find that $\beta_C$ is a basis of $V$ containing $\alpha$.

##### Exercise 4

證明 basis exchange lemma (vector form)。

<!-- eng start -->
Prove the basis exchange lemma (vector form).
<!-- eng end -->

:::warning

Need more explanations for the two claims. Let's discuss this tomorrow.
:::

##### Exercise 4 - answer here

Since $\beta$ is a basis of $V$ and $\ba\in V$, $\ba$ can be written as the linear combination
$$\ba = c_1\bb_1 + \cdots + c_d\bb_d
$$
of $\beta$.
Since $\ba\neq\bzero$, at least one of $c_i$ is nonzero.
Without loss of generality, we may assume $c_d\neq 0$.
Let $\beta_1 = \beta \cup \{\ba\} \setminus \{\bb_d\}$.

:::warning

- [x] Complete the blank in $\bb_d = ...$
:::

**Claim: $\vspan(\beta_1) = V$**
Because $\ba$ is the linear combination of $\beta$,

$$
V = \vspan(\beta) = \vspan(\beta \cup \{\ba\}).
$$

Since $\bb_d =\frac 1 {c_d}\ba-\frac {c_1} {c_d}\bb_1-...-\frac {c_{d-1}} {c_d}\bb_{d-1}$ is also a linear combination of $\beta_1 = \{\ba, \bb_1,\ldots,\bb_{d-1}\}$, we know

$$
V = \vspan(\beta \cup \{\ba\}) = \vspan(\beta_1).
$$

:::warning

- [x] Make zero vector as $\bzero$.
- [x] is independent --> is independent, we know
- [x] $k_a=k_2= ...$ --> Therefore, $k_a=k_2= ...$. Also, add a period in the end of this sentence.
- [x] So $\beta=\{\bb_1,\ldots,\bb_d\}$ --> So $\beta=\{\bb_1,\ldots,\bb_d\}$ is independent.
:::

**Claim: $\beta_1$ is linearly independent**
Suppose $k_a\ba+k_1\bb_1+...+k_{d-1}\bb_{d-1}=\bzero$.
Since $\ba=c_1\bb_1+c_2\bb_2+...+c_d\bb_d$, with $c_d \not=0$, we get $k_a(c_1\bb_1+c_2\bb_2+...+c_d\bb_d)+k_1\bb_1+...+k_{d-1}\bb_{d-1}=\bzero$
$(k_ac_1+k_1)\bb_1+(k_ac_2+k_2)\bb_2+...+(k_ac_{d-1}+k_{d-1})\bb_{d-1}+k_ac_d\bb_d=\bzero$.
Since $\beta$ is independent, we know $\begin{cases} k_ac_1+k_1=0 \\ k_ac_2+k_2=0 \\ ... \\ k_ac_d=0\end{cases}$, with $c_d\not=0$.
Therefore, $k_a=k_2=k_3=...=k_{d-1}=0$.
So $\beta=\{\bb_1,\ldots,\bb_d\}$ is independent.

##### Exercise 5

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

<!-- eng start -->
Use the basis exchange lemma (vector form) to prove the basis exchange lemma (set form).
<!-- eng end -->

Sample:
If $\alpha = \emptyset$, then there is nothing to prove.
Suppose $\alpha \neq \emptyset$.
Pick an element $\ba\in\alpha$ and let $\alpha'_1 = \{\ba\}$.
By the basis exchange lemma (vector form), $\beta_1 = \beta \cup \alpha \setminus \beta'_1$ with $\beta'_1 = \{\bb\}$ for some $\bb\in\beta$.

Continue the following process for $i = 2, \ldots, d$.
If $\alpha'_{i-1} = \alpha$, then we are done.
Otherwise, pick an element $\ba\in\alpha\setminus\alpha'$ and let $\alpha'_i = \alpha'_{i-1} \cup \{\ba\}$.
Since $\beta_{i-1}$ is a basis, ...
...
By the basis exchange lemma (vector form), $\beta_i = \beta \cup \alpha \setminus \beta'_i$ with $\beta'_i = \beta'_{i-1} \cup \{\bb\}$ for some $\bb\in\beta\setminus\beta'_{i-1}$.

Suppose the process finished at $i = d$.
Then $\beta_d$ is composed of some $d$ vectors in $\alpha$.
Since $\beta_d$ is a basis, $\alpha\setminus\beta_d$ is empty for otherwise $\alpha$ is not linearly independent.
Therefore, necessarily $|\alpha|\leq|\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|$.

:::warning

Let's discuss this tomorrow.

Writing:

I don't understand the meaning of innumerable?

Grammar:

- [x] Let ... be ... .
:::

##### Exercise 5 - answer here

Let $\beta = \{\bb_1,\ldots,\bb_n\}$ is a set of bases in $V$.
Let $\alpha$ be a set of linearly independent vectors in $V$. It may be innumerable.
Let $\alpha' = \{\bb_1,\ldots,\bb_k\}$ are the $k$ vectors in $\alpha$, and $\alpha'$ will also be an independent set.
Because $\alpha\subseteq\ V$, So all vectors in $\alpha$ can be written as linear combinations of $\beta$.
Therefore, all vectors in $\alpha'$ can be written as linear combinations of $\beta$.

At this time, according to the basis exchange rule of the vector version, we can find a vector $\bb1$ in $\beta$, and $\bb1$ satisfies that when $\ba1$ is written as a linear combination of $\beta$, the coefficient of $\bb1$ is not 0.
Therefore, we can exchange $\ba1$ and $\bb1$ to form a new basis $\beta_1$, and $\beta_1 = (\beta\cup\{\ba_1\})\setminus\{\bb_1\}$.
Repeat the above actions until the vectors in $\alpha'$ have been swapped in.
In this process, because $\alpha'$ is an independent set, any vector $\ba_i$ in $\alpha'$ cannot be represented by $\alpha'\setminus\{\ba_i\}$.
So we can find a vector in $\beta$ to swap out in every exchange.
And if all vectors exchanged in $\beta$ are regarded as a set $\beta'$, we will get $\beta_k =(\beta\cup\alpha')\setminus\beta'$ as a basis finally.

:::info

collaboration: 1
4 problems: 4

- done: 2(a), 2(b), 3(a), 3(b)

extra:

- pending: 4, 5

moderator: 1
quality control: 1
:::