# 維度、擴充與縮限法則

Dimension, expanding and shrinking lemmas

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

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 = \vspan(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 = \{ \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]$ 的最簡階梯形式矩陣。

<!-- eng start -->
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]$.
<!-- eng end -->

### 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("R =")
show(R)
print("a =", a)
print("") 
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.")

The result from the code above:

---
#### Exercise 1(a)

求一組 $V$ 的基底 $\beta$ 且 $\ba\in \beta$。

<!-- eng start -->
Find a basis $\beta$ of $V$ such that $\ba\in\beta$.
<!-- eng end -->
:::info
Based on the result from the code, we found that the first three columns of $\left[\begin{array}{c|c} {\bf e}_1 & R' \end{array}\right]$ correspond to the pivots.

Hence, we know that $\left[\begin{array}{c|c} {\bf a} & A \end{array}\right]$ also correspond to the pivots.

Then $\beta$ can be
$$
\begin{bmatrix}
-177 & 1 & -3\\
701 & -4 & 13\\
3324 & -19&61\\
-6482 & 37&-119
\end{bmatrix}=\{\ba,\bu_1,\bu_2\},
$$
which is a basis of $V$ such that $\ba \in \beta$.
:::

#### Exercise 1(b)

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

<!-- eng start -->
Find a basis $\beta$ of $V$ such that $\beta\subseteq S$.
<!-- eng end -->
:::info
Based on the result from the code, we can take $\beta$ be the first three columns of $A$.

Thus, $\beta=\{\bu_1,\bu_2,\bu_3\}$ is a basis of $\Col(A)$, and $S$ is the columns of $A$.

In other words, $\beta$ is also a basis of $V$ such that $\beta \subseteq S$.
:::

:::spoiler
1 周、伶、湯; 2a 伶; 2b 盧; 2c 周; 2d 湯
:::

## Exercises

#### Exercise 2(a)

求

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

的維度。

<!-- eng start -->
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\}.
$$
<!-- eng end -->

#### Exercise 2(a) [Answer]

Let $A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}$.

<!-- Suppose $R$ is the reduced echelon form of $A$. -->

Then we get its reduced echelon form
$R = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}.$

Hence, we know $\dim(V)=3$.

---
#### Exercise 2(b)

求

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

的維度。

<!-- eng start -->
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\}
$$
<!-- eng end -->

**[由鄭宗祐提供]**
**Answer**
Let $A$ be the matrix $\begin{bmatrix}1&1&1\\1&2&2\\2&1&1\end{bmatrix}$. Then its rref is $\begin{bmatrix}1&0&0\\0&1&1\\0&0&0\end{bmatrix}.$
Since the matrix has two pivots, we can know $\dim(V)=2.$

#### Exercise 2\(c\)

令

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
\end{bmatrix}
$$

求

$$
V = \{ \bx\in\mathbb{R}^4 : A\bx = \bzero\}
$$

的維度。

<!-- eng start -->

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\}.
$$
<!-- eng end -->

#### Exercise 2\(c\) [Answer]

By calculation,$$A = \left[\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 \\
\end{array}\right].
$$
Because the number of free variables is two, thus the dimension of $V$ is $2$.

---

#### Exercise 2(d)

令

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

的維度。

<!-- eng start -->
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\}.
$$
<!-- eng end -->

#### Exercise 2(d) [Answer]
:::info
We may compute the reduced echelon form $R$ of $A$ as
$$R = \begin{bmatrix}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0&0&0&0 \\
\end{bmatrix}.
$$

After the computation, we have

$$
V =\ker(A)= \vspan
\left\{
\begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix},
\begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \end{bmatrix}
\right\}.
$$
Therefore, we can get $\dim(V)=2$ .
:::

---

#### Exercise 3

令 $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$ 的一組基底。

<!-- eng start -->
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$.
<!-- eng end -->

#### 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}.
$$

求 $\vspan(\Col(A) \cup \Col(B))$ 的一組基底。

<!-- eng start -->
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))$.
<!-- eng end -->

#### Exercise 5

證明 expanding lemma。

<!-- eng start -->
Prove the expanding lemma.
<!-- eng end -->

#### Exercise 6

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

<!-- eng start -->
Use the expanding lemma to prove that every subspace of $\mathbb{R}^n$ has a basis consisting of finite number of vectors.
<!-- eng end -->

:::info

collaboration: 2
3 problems: 3
done: 2a, 2c, 2d

moderator: 1
quality control: 1
:::