---
tags: Linear Algebra, NCTU OCW, 莊重
---

# Lecture 6

## 1.6 Bases (基底) and Dimension (維度)

### Theorem 1.7

$S\subset V,~ S\text{ L.I.},~ v\in\left(V\setminus S\right)\\
\implies \left( \left(S\cup\{v\}\right)\text{ L.D.} \iff v\in\text{Span}\left(S\right) \right)$

### Theorem 1.10

__Replacement Theorem__

Let $V=\text{Span}(G)$, $\lVert G\rVert=n$.
Suppose $L\subset V$, $L \text{ L.I.}$, and $\lVert L\rVert=m$, then we have the followings:
1. $m\leq n$
2. $\exists H\subset V,~ \lVert H\rVert=(n-m),~\text{s.t. Span}\left(L\cup H\right)=V$
That is, $G$ could be replaced with other $n$ vectors, with $m$ of which are $\text{L.I.}$
- (this is why it's called replacement theorem)
- $\text{L.I.}$ sets are very important in any vector space...

__proof__:
(*using mathmatical induction on $m$*)
supp. $m=0$, that is, $L=\phi$; by definition it's linearly independent.
1 and 2 both clearly hold, if we choose $H=G$.
Suppose for any $\lVert L\rVert=m$, 1 and 2 both hold;
Suppose further that we find $\lVert L\rVert=m+1$ is $\text{L.I.}$, we want 1 and 2 still hold.
Let $L=\big\{l_1,l_2,\cdots,l_{m+1}\big\}$
Let $L^{'}=\big\{l_1,l_2,\cdots,l_{m}\big\}$; notice $L^{'}$ must be $\text{L.I.}$ since $L^{'} \subset L$
1. from our induction hypothesis, there exists $H^{'}=\big\{h_1,\cdots,h_{n-m}\big\}$ s.t. $\text{Span}\left(L^{'}\cup H^{'}\right)=V$; notice $m\leq n$
Suppose, hoping to find contradiction, $n=m$, which makes our $\lVert L \rVert = n+1$ and violates our proposition
$\implies H^{'}=\phi\implies \text{Span}\left(L\right)=V\\
\implies l_{m+1}\in\text{Span}\left(L^{'}\right)\implies L\text{ L.D.}$
which is a contradiction to that $L$ is linearly independent
hence $n>m$, 1 holds.
2. from induction hypothesis, that $\text{Span} \left(L^{'}\cup H^{'}\right)=V$, we have $l_{m+1}=\left(\sum\limits_{i=1}^{n}{\left(a_il_i\right)}\right)+\left(\sum\limits_{i=1}^{n-m}{\left(b_ih_i\right)}\right)$
We want to find $H$ such that $\text{Span}(L\cup H)=V$
Intuitively, we may want to derive $H$ from $H^{'}$...
Claim: there exists $b_j\neq {0}$
- if not, $l_{m+1}=\left(\sum\limits_{i=1}^{n}{\left(a_il_i\right)}\right)$, which is against the prerequisite that $L$ is linearly independent

WLOG let be $b_1\neq 0$
$\implies h_1=
\frac{\left(\sum\limits_{i=1}^{n}{\left(-a_il_i\right)}\right)+\left(\sum\limits_{i=2}^{n-m}{\left(-b_ih_i\right)}\right)+\left(l_{m+1}\right)}{b_1}$
Hence, we could choose $H=\big\{h_2,h_3,\cdots,h_{n-m}\big\}=H^{'}\setminus \{h_1\}$
, satisfying the proposition that there exists $H$ such that $\text{Span}\left(L\cup H\right)=V$ and $\lVert H\rVert=\left(n-m-1\right)$<div style="text-align: right">$\square$</div>

### Basis

intuition: not more, not less, a subset of vectors $B$ shall be representive of vector space $V$

#### Definition

Let $B\subset V$, where $V$ is a vector space, then $B$ is called $\text{Basis}$ of $V$ if the followings hold:
1. $B$ is a $\text{L.I.}$ set
2. $\text{Span}\left(B\right)=V$

Intuitively, it's saying...
1 $\rightarrow$ 不多
2 $\rightarrow$ 不少

notice we don't limit on the size of $B$ here, till now.

##### Example

- $V=\mathbb{R}^2,~ B=\{(1,0),(0,1)\}$
- $V=\mathbb{R}^2,~ B^{'}=\{(1,0),(1,1)\}$
- 二維平面若不平行的兩個向量即為線性獨立集合
- $V=M_{2\times 3}\left(\mathbb{R}\right),~ B=\\
\Big\{
\left(\begin{array}{ccc}1 & 0 & 0 \\ 0 & 0 & 0\end{array}\right),
\left(\begin{array}{ccc}0 & 0 & 0 \\ 1 & 0 & 0\end{array}\right),\\
\left(\begin{array}{ccc}0 & 1 & 0 \\ 0 & 0 & 0\end{array}\right),
\left(\begin{array}{ccc}0 & 0 & 0 \\ 0 & 1 & 0\end{array}\right),\\
\left(\begin{array}{ccc}0 & 0 & 1 \\ 0 & 0 & 0\end{array}\right),
\left(\begin{array}{ccc}0 & 0 & 0 \\ 0 & 0 & 1\end{array}\right),
\Big\}$
- (__Definition__) $V=\{\vec{0}\}\implies B=\phi\text{ is a basis of }V,\\
\text{ that is, }V\text{ have dimension of zero.}$
- $V=P_2(\mathbb{R})$
$B=\big\{1,x,x^2\big\}$ is a basis of $V$
$B^{'}=\big\{1,x+1,2x^2\big\}$ is a basis of $V$
- $V=P(\mathbb{R})=\big\{\text{polynomials with real coefficients}\big\}$
turns out there is no finite basis.
$B=\big\{1,x,x^2,x^3,\cdots\big\}$?
- 2 is easier to prove; a trivial one even.
__proof__:
$\forall f\in V=P(\mathbb{R})\\
\implies f(x)=a_nx^n+\cdots+a_1x+a_0\\
\implies f\in\text{Span}(B)$
$\text{Q.E.D.}$
- Does 1 hold? is $B$ linearly independent?
claim: $B$ is linearly independent, that is,
there's only the trivial way s.t. a finite set of distinct vectors sums to $\vec{0}$
__proof__:
supp. $\beta$ is a finite set of vectors s.t. $\beta\subset B$
since $\beta$ is finite, there exists some $k$ s.t. the highest order is exactly $k$
$\implies$ any linear combination on $\beta$ is a polynomial with degree at most $k$
since $P_k\left(\mathbb{R}\right)$ is the zero function $\iff$ all the coefficients are the real number zero
($k\text{-degree polynomial}$ have no more than $k$ real roots if not all coefficients are zero)
hence $B$ is linearly independet.
$\text{Q.E.D.}$
Notice we here actually showed that any finite set can't be basis, and there exist one basis which we just found; it's a *infinite-dimensioned* space.

### Theorem 1.8

$B\text{ is a basis of }V,~ B=\{u_1,u_2,\cdots,u_n\}\\
\iff \forall v\in V,~ \exists! \Big\{a_i ~|~ i\in\{1,2,\cdots,n\}\Big\} , \text{ s.t. }v=\sum\limits_{i=1}^{n}{\left(a_iu_i\right)}$

__remark__:
notice this is a theorem of *equivalent* conditions

__proof__:
($\rightarrow$)
supp. there's $\{a_i\}$ and $\{b_i\}$ not all the same s.t. $v=\sum\limits_{i=1}^{n}{\left(a_iu_i\right)}=\sum\limits_{i=1}^{n}{\left(b_iu_i\right)}$
by moving terms, and that *anti element of operator $+$ is just multiplying it by scalar $(-1)$*, we have:
$\sum\limits_{i=1}^{n}{\left(\left(a_i-b_i\right)u_i\right)}=\vec{0}$
which is against the assumption that $B$ is a basis, which is linear independent.
($\leftarrow$)
apparently we have $\text{Span}(B)=V$
and since all $0$ is apparently a method to have $\vec{0}$, which is unique, we know $B$ is also linearly independent.
We conclude $B$ is indeed a basis.
$\text{Q.E.D.}$

observation:
a basis is s.t. it's a proper-sized set that represents the vector space:
all elements in the vector space could be uniquely identified with the basis, with proper coefficients.
That is, all finite dimension vector space, or all vector spaces that have finite basis, is similar to some extent, in that we could use the coefficients as coordinates:
$V\cong F^n$

### Theorem 1.9

Let $V=\text{Span}(G),~ \lVert G\rVert<\infty\\
\implies V \text{ has a finite basis}$

__remark__:

Theorem 1.9 ensures existence of a basis...

__proof__:
1. $V=\{\vec{0}_V\}\implies B=\phi$
2. $V\neq \{\vec{0}\}$
$\exists u_1\neq \vec{0}$
notice $\{u_1\}$ is linearly independent
$\implies \exists\{u_1,\cdots,u_n\}=B$ s.t.
- $B$ is linearly independent
- for any $v\in\left(V\setminus B\right)$, $\left(B\cup \{v\}\right)$ is linearly dependent.

claim: $B$ is a basis
we already have $B$ linearly independent;
we only need $\text{Span}(B)=V$.
using Theorem 1.7, for any $v\in V$, either $v\in\left(V\setminus B\right)$ or $v\in B$, we have $v\in \text{Span}(B)$;
we conclude that $\text{Span}(B)=V$;
$B$ is indeed a basis.
$\text{Q.E.D.}$

(existence of $B$ is guaranteed by theorem 1.10, since $\lVert G\rVert=n$ is finite.)
(a rather easy way to explicitly construct $B$ is to choose vectors from within $G$.)

### Dimension

intuition: $\text{dim}(V)\overset{\Delta}{=}\lVert\text{Basis of }V\rVert$

recall: supp. $V$ vectors space, a subset of $B\subset V$ is s.t. $B$ is proper-sized and represents $V$, called basis of $V$, that is, $\text{Span}(B)=V$ (不多) and $B\text{ is L.I.}$ (不少)
*representation*: since, by theorem 1.8, any $v\in V$ have only one set of scalars s.t. their linear combination on $B$ is $v$.

#### Definition

1. Let $B$ be a basis of $V$, with $\lVert B\rVert\leq\infty$, then we say $\text{dim}\left(V\right)\overset{\Delta}{=}\lVert B\rVert$, and we say $V$ is finite dimentional.
2. If $V$ is not finite dimensional, then $V$ is infinite dimensional.

##### Example

- $V=\mathbb{R}^2$
$B=\big\{(1,0),(0,1)\big\}$
$B^{'}=\big\{(1,1),(-2,1)\big\}$

Question: Basis is not unique in general; can a vector space have distinct basis s.t. they don't agree on the number of them?
*Is such definition __well-defined__*?
(luckily, we have handy-dandy theorem 1.10; check for yourself.)

#### Corollary

1. - Let $V=\text{Span}(G),~ \lVert G\rVert = n$, if $L$ is linearly independent, $L\subset V$,
then $\lVert L\rVert\leq n$
- different from theorem 1.10, where we choose a *finite* linearly independent set $L$ and argue its size limitation, here we choose any subset of $V$ and claim limitation on its size.
- proof:
supp. $L=\infty$, $\exists I\subset L\text{ s.t. }\lVert I\rVert=(n+1)$
via theorem 1.10, we have $n\geq \left(n+1\right)$ (!!!!)
which is contradiction; we conclude that $\lVert L\rVert$ must be finite.
Which brings us back to the situation of theorem 1.10.
- Let $B$ and $C$ be finite basis of $V$, then $\lVert B\rVert = \lVert C\lVert$
- proof:
let $G=B$, apply theorem 1.10, we have $\lVert C\rVert\leq \lVert B\rVert$.
similarly, let $G=C$, apply theorem 1.10, we have $\lVert B\rVert\leq \lVert C\rVert$
we conclude that they must agree on their size. $\text{Q.E.D.}$
2. suppose $\text{dim}(V)=n< \infty$
- $\text{Span}(G)=V\implies \lVert G\rVert\geq n$
moreover, if $\lVert G\rVert=n$, then $G$ is also basis of $V$
(基底是最小的spanning set)
- proof:
supp. $\lVert G\rVert=\infty$, done.
supp. $\lVert G\rVert=m$, notice there exists basis $B$ of $V$ with $\lVert B\rVert=n$
apply theorem 1.10, we know $m\geq n$, done.
supp. $\lVert G\rVert=n$, is $G$ indeed a basis?
check linear independence...
supp. $G$ is linear dependent; there exists some $G^{'}\subset G$ s.t. $\lVert G^{'}\rVert=m<n$ and $\text{Span}\left( G^{'}\right)=V$
apply the first sub corollary of corollary 1, we achieved a $\bot$
We conclude that $G$ must be linearly independent if $\lVert G\rVert=n$. $G$ is basis.
- $L \text{ L.I.} ,~ L \subseteq V \implies \lVert L \rVert\leq n$
moreover, $\lVert L\rVert=n \implies L\text{ is a basis of }V$
(基底是最大的線性獨立子集合)
- proof:
from first sub corollary of corollary 1, since there exists $B$ basis of $V$ and $\lVert B\rVert=n$, we know any $\text{L.I.}$ set must have its size not more than $n$.
we want $\text{Span}(L)=V$ when $\lVert L\rVert=n$...
apply second part of theorem 1.10; notice $H=\phi$, that is, $\text{Span}(L)=V$
$\text{Q.E.D.}$

#### Example

- suppose $\text{dim}(V)=n<\infty$, $W$ subspace of $V$
then we have the following:
1. $\text{dim}(W)\leq\text{dim}(V)$
- proof: a trivial result of first part of theorem 1.10
2. $\text{dim}(W)=\text{dim}(V)\implies W=V$
- proof: a trivial result of second part of theorem 1.10
- suppose $V=\{\vec{0}\}$, then $\text{dim}(V)=0$
- $\mathbb{R}^3$ have dimension 3
examples of basis include $\big\{\left(1,0,0\right),\left(0,1,0\right),\left(0,0,1\right),\big\}$
- $M_{2\times 3}\left(\mathbb{R}\right)$ have dimension 6
- $P_n\left(\mathbb{R}\right)$ have dimension $\left(n+1\right)$
- $P\left(\mathbb{R}\right)$ is *infinite-dimensioned*
- proof: *left as exercise*
- $V=\mathbb{C}$, $F=\mathbb{R}$, notice $V$ is vector space on $F$
then $V$ is __2-dimensioned__.
- $V=\mathbb{C}$, $F=\mathbb{C}$, notice $V$ is vector space on $F$
then $V$ is __1-dimensioned__: any set consisting of single non-zero complex number is a basis
since the field we chose is larger.
- $B=\{u,v\}$ be basis of $V$
prove that $\big\{\left(u+v\right),\left(u-v\right)\big\}$ is also a basis
- we only need to prove one of linear independence and spanning $V$
- notice that by corollary 2, we only need to prove linear independence.
since they agree on size.
- notice that by corollary 1, we only need to prove it spans the set $V$,
since they agree on size.
- both property are easy to prove, hence the proposition holds.
- (__Lagrange Polynomial__)
consider $P_n(F)$, $c_0,c_1,\cdots,c_n$ be distinct numbers
define $f_i\left(x\right)=\prod\limits_{j\in\big\{k~ \big\vert~ k\in\left(\mathbb\{N\}\cup\{0\}\right),~ k\neq i\big\}}{\left(\frac{x-c_j}{c_i-c_j}\right)}$
$\implies \Big\{f_0,f_1,f_2,\cdots,f_n\Big\}$ is a basis of $P_n\left(\mathbb{R}\right)$
- remark: they are all $n\text{-degreed polynomial}$
- since $\big\lVert \big\{ f_i\left(x\right) ~\big\vert~ i\in\mathbb{N}\cup\{0\},~ i\leq n\big\} \big\rVert=n+1$
similar to previous examples, we need to prove only one of the following:
- $\text{Span}\left(\big\{ f_i\left(x\right) ~\big\vert~ i\in\mathbb{N}\cup\{0\},~ i\leq n\big\}\right)=V$
- $\big\{ f_i\left(x\right) ~\big\vert~ i\in\mathbb{N}\cup\{0\},~ i\leq n\big\}$ is linearly independent

### Homework

- section 1.6
- 1
- 2
- a
- 3
- a
- 5
- 10
- a
- 13
- 14
- 21
- 22
- 30
- 31
- existence of basis?
- related to [axiom of choice](https://math.stackexchange.com/questions/1615363/proving-that-basis-always-exists-and-is-not-unique "existence of basis \"for every\" vector space")
- existence of basis of suspace $B$ of vector space $V$
where we already know that $\text{dim}\left(V\right)=n\in\mathbb{N}$?

### Question

- Why Theorem 1.10 is stated in such a *weird* form? Given a $V=\text{Span}(S)$, $\lVert S \rVert = n$, and suppose we found a finite $\text{L.I.}$ set $\lVert L \rVert = m$, and suddenly we have $m\leq n$...
- It's as such so that the theorem itself is pretty minimal.
Notice, though, the induction part: since if $L\text{ L.I.}$ and $L^{'} \subset L$, we have $L^{'}\text{ L.I.}$, we only check for the case when $\lVert L\rVert$ is just at the boundary, $n$.