Dimension, expanding and shrinking lemmas
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
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!
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.)
Let $V = \vspan(S)$ be a subspace and $S$ a finite set of vectors.
Then there is a basis $\beta$ of $V$ with $\beta\subseteq S$
執行下方程式碼。
令 $S = \{ \bu_1, \ldots, \bu_5 \}$ 為 $A$ 的各行向量
且 $V = \vspan(S)$。
已知 $\ba\in V$、
$R$ 為 $A$ 的最簡階梯形式矩陣、
$\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ 為 $\left[\begin{array}{c|c} \ba & A \end{array}\right]$ 的最簡階梯形式矩陣。
Run the code below. Let $S = \{ \bu_1, \ldots, \bu_5 \}$ be the columns of $A$ and $V = \vspan(S)$. Suppose $\ba\in V$. Suppose $R$ is the reduced echelon form of $A$ and $\left[\begin{array}{c|c} \be_1 & R' \end{array}\right]$ is the reduced echelon form of $\left[\begin{array}{c|c} \ba & 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.")
求一組 $V$ 的基底 $\beta$ 且 $\ba\in \beta$。
Find a basis $\beta$ of $V$ such that $\ba\in\beta$.
求一組 $V$ 的基底 $\beta$ 且 $\beta\subseteq S$。
Find a basis $\beta$ of $V$ such that $\beta\subseteq S$.
求
$$ V = \vspan\left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 1 \\ 4 \\ 9 \end{bmatrix} \right\} $$的維度。
Find the dimension of
$$ V = \vspan\left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 1 \\ 4 \\ 9 \end{bmatrix} \right\}. $$求
$$ V = \vspan\left\{ \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \right\} $$的維度。
Find the dimension of
$$ V = \vspan\left\{ \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \right\} $$令
$$ A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} $$求
$$ V = \{ \bx\in\mathbb{R}^4 : A\bx = \bzero\} $$的維度。
Let
$$ A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix}. $$Find the dimension of
$$ V = \{ \bx\in\mathbb{R}^4 : A\bx = \bzero\}. $$令
$$ A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 1 \\ \end{bmatrix} $$求
$$ V = \{ \bx\in\mathbb{R}^4 : A\bx = \bzero\} $$的維度。
Let
$$ A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 1 \\ \end{bmatrix}. $$Find the dimension of
$$ V = \{ \bx\in\mathbb{R}^4 : A\bx = \bzero\}. $$令 $U = \{ \bx = (x,y,z,w)\in\mathbb{R}^4 : x + y + z + w = 0 \}$ 且
$V = \{ \bx = (x,y,z,w)\in\mathbb{R}^4 : x + y + 2z + 2w = 0 \}$。
求出 $\bu_1, \ldots, \bu_3$ 使得
$\{ \bu_1,\bu_2 \}$ 是 $U\cap V$ 的一組基底、
$\{ \bu_1,\bu_2,\bu_3 \}$ 是 $U$ 的一組基底、
$\{ \bu_1,\bu_2,\bu_4 \}$ 是 $V$ 的一組基底。
Let $U = \{ \bx = (x,y,z,w)\in\mathbb{R}^4 : x + y + z + w = 0 \}$ and $V = \{ \bx = (x,y,z,w)\in\mathbb{R}^4 : x + y + 2z + 2w = 0 \}$. Find $\bu_1, \ldots, \bu_3$ such that $\{ \bu_1,\bu_2 \}$ is a basis of $U\cap V$, $\{ \bu_1,\bu_2,\bu_3 \}$ is a basis of $U$, and $\{ \bu_1,\bu_2,\bu_4 \}$ is a basis of $V$.
令
$$ 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}. $$求 $\vspan(\Col(A) \cup \Col(B))$ 的一組基底。
Let
$$ 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}. $$Find a basis of $\vspan(\Col(A) \cup \Col(B))$.
利用 expanding lemma 證明所有 $\mathbb{R}^n$ 中的子空間都有一組有限個數的基底。
Use the expanding lemma to prove that every subspace of $\mathbb{R}^n$ has a basis consisting of finite number of vectors.