Basis exchange lemma
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
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:
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.
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$.
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|$.
執行下方程式碼。
己知 $\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]$ 的最簡階梯形式矩陣。
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]$.
### 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.")
判斷 $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$ 其包含的向量個數是否一樣?
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?
計算 $B$ 和 $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 各算得出來的 $\beta_C$。
Find the $\beta_C$ for $B$ and the $\beta_C$ for $\left[\begin{array}{c|c} \ba & B \end{array}\right]$.
把 $\ba$ 表示成 $B$ 的各行向量的線性組合。
Write $\ba$ as a linear combination of the columns of $B$.
用程式計算看看對於哪些 $i = 1,\ldots, 5$﹐
$\beta\cup\{\ba\}\setminus\{\bb_i\}$ 是 $\Col(B)$ 的基底。
Use computer if necessary, check if $\beta\cup\{\ba\}\setminus\{\bb_i\}$ is a basis of $\Col(B)$ for each $i = 1, \ldots, 5$.
若 $\beta = \{ \bb_1, \bb_2, \bb_3 \}$ 是子空間 $V$ 的一組基底。
已知 $\ba = 4\bb_2 + 5\bb_3$。
令 $\beta_1 = \beta \cup \{\ba\} \setminus \{ \bb_3 \}$。
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 \}$.
將 $\bb_3$ 寫成 $\beta_1$ 的線性組合﹐
並說明 $\vspan(\beta) = \vspan(\beta_1) = V$。
Write $\bb_3$ as a linear combination of $\beta_1$. Then explain why $\vspan(\beta) = \vspan(\beta_1) = V$.
證明 $\beta_1$ 線性獨立﹐因此它是 $V$ 的一組基底。
Show that $\beta_1$ is linearly independent, so it is a basis of $V$.
對任一矩陣 $A$ 而言,
若 $\bu_1, \ldots, \bu_n$ 為 $A$ 的向行向量、
且 $R$ 為 $A$ 的最簡階梯形式,
則已知以下敘述等價:
對以下小題,
令 $\beta = \{\bb_1,\ldots,\bb_n\}$ 為子空間 $V$ 的一組基底
而 $B$ 為一矩陣其行向量為 $\beta$ 的向量。
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:
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$.
令 $\ba\in V$ 是一個非零向量
並計算 $\left[\begin{array}{c|c} \ba & B \end{array}\right]$ 的 $\beta_C$。
說明 $\ba$ 一定會落在 $\beta_C$ 裡﹐
因此 $\beta_C$ 是 $V$ 的一組基底並且包含 $\ba$。
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$.
令 $\alpha$ 是一群 $V$ 中有限個數的向量且線性獨立﹐
且 $A$ 為一矩陣其各行向量為 $\alpha$ 中的向量。
並計算 $\left[\begin{array}{c|c} A & B \end{array}\right]$ 的 $\beta_C$。
說明 $\alpha\subseteq\beta_C$ 裡﹐
因此 $\beta_C$ 是 $V$ 的一組基底並且包含 $\alpha$。
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]$ 的 $\beta_C$. Explain why $\alpha\subseteq\beta_C$. Therefore, $\beta_C$ is a basis of $V$ containing $\alpha$.
Sample:
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\}$.
Claim: $\vspan(\beta_1) = V$
...
Claim: $\vspan(\beta_1)$ is linearly independent
...
利用 basis exchange lemma (vector form) 證明 basis exchange lemma (set form)。
Use the basis exchange lemma (vector form) to prove the basis exchange lemma (set form).
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|$.