[선형대수학] 기저 대체 정리 (Replacement Theorem)

$\underline{Thm}$ (Replacement Theorem)

Let $G, L$ be subset of a vector space $V$ such that $\vert G \vert =n \in \mathbb{N}_{0}, span(G)=V, \vert L \vert =m \in \mathbb{N}_{0}$ and $L$ is linear independent, where $\mathbb{N}_{0}=\mathbb{N} \cup \{ 0 \}$.

Then $n \geq m$, and $\exists H \subset G$ with $\vert H \vert=n-m$ such that $span(H \cup  L) =V$.

 

$\underline{Proof}$

We prove by induction on $m \geq 0$.

$(m=0)$

In this case, $L=\phi$.

$n \geq 0=m$, and letting $H=G$, we have $\vert H \vert=n=n-0=n-m$ and $span(H \cup L)=span(G)=V$.

 

$(Induction\;hypothesis)$

Assume that the statement holds for some integer $m \geq 0$.

$(m+1\;case)$

We now show that the statement holds for $m+1$ under the induction hypothesis.

So, let $G$ be as in the statement, and let $L= \{v_{1}, \cdots, v_{m+1} \}$ be a linear independent subset of $V$.

Then $\{ v_{1}, \cdots, v_{m} \}$ is linear independent. By induction hypothesis, we have $n \geq m$ and $\exists \{ u_{1}, \cdots, u_{n-m} \} \subset G$ such that $span(\{ u_{1}, \cdots, u_{n-m}, v_{1}, \cdots, v_{m} \}) = V$.

 

Since $v_{m+1} \in V$, $\exists a_{1}, \cdots, a_{m}, b_{1}, \cdots, b_{n-m} \in \mathbb{F}$ such that $v_{m+1}=a_{1}v_{1}+\cdots+a_{m}v_{m}+b_{1}u_{1}+\cdots+b_{n-m}u_{n-m}\; \cdots \; (\ast)$.

If $n=m$, then $v_{m+1}=a_{1}v_{1}+\cdots+a_{m}v_{m}$, so that $\{v_{1},\cdots,v_{m},v_{m+1} \}$ is linearly dependent, a contradiction.

So, $n>m$; that is $n \geq m+1$.

If $b_{1}=\cdots=b_{n-m}=0$, we also arrive at a contradiction as above. So, interchanging some indices if necessary, we can have $b_{1} \neq 0$.

Using $(\ast)$, we get $u_{1}=(-b_{1}^{-1}a_{1})v_{1}+ \cdots +(-b_{a}^{-1}a_{m})v_{m}b_{1}^{-1}v_{m+1}+(-b_{1}^{-1}b_{2})u_{2}+ \cdots +(-b_{1}^{-1}b_{n-m})u_{n-m}$.

This implies $V=span(\{ u_{1},\cdots,u_{n-m},v_{1},\cdots,v_{m} \}) \subset span(\{u_{2}, \cdots, u_{n-m},v_{1},\cdots,v_{m},v_{m+1} \}) \subset V$.

Let $H=\{u_{2}, \cdots, u_{n-m} \} \subset G$; then $\vert H \vert = n -(m+1)$ ans $span(H \cup L)=V$.

Therefore, the statement holds for $m+1$. The theorem is now proved by induction.

---

$\underline{Coro}$

Let $V$ be a vector space having a basis $\beta$ with $\vert \beta \vert = n \in \mathbb{N}_{0}$.

If $\gamma$ is any basis for $V$, then $\vert \gamma \vert = n$.

 

$\underline{Proof}$

Let $\gamma$ be any basis for $V$.

If $\vert \gamma \vert = \infty$, we can choose a $\gamma^{'} \subset \gamma$ with $\vert gamma \vert = n+1$.

Note $\gamma^{'}$ is also linear independent.

Since $span(\beta)=V$, the replacement theorem implies $\vert \gamma^{'} \vert =n+1 \leq n= \vert \beta \vert$, a contradiction.

So, $\vert \gamma \vert=m \in \mathbb{N}_{0}$. Since $span(\beta)=V$ & $\gamma$ is linear independent, by the theorem, we get $m \leq n$.

Interchanging their roles in applying the theorem, we get $n \leq m$.