# Help understanding Replacement theorem Friedberg

• Jan 26th 2013, 09:47 AM
gordo151091
Help understanding Replacement theorem Friedberg
Hello everyone, im having trouble understanding the Replacement Theorem proof outline in Friedberg Linear Algebra 4th pg 45.

Theorem 1.10 (Replacement Theorem)

Let $\displaystyle V$ be a vector space that is generated by a set $\displaystyle G$ containing exactly $\displaystyle n$ vectors, and let $\displaystyle L$ be a linearly independent subset of $\displaystyle V$ containing exactly vectors. Then $\displaystyle m\leq n$ and there exists a subset $\displaystyle H$ of $\displaystyle G$ containing exactly $\displaystyle n-m$ vectors such that $\displaystyle L \cup H$ generates $\displaystyle V$

The proof is by induction on $\displaystyle m$, I skipped the base case$\displaystyle m=0$.

Inductive step

Let $\displaystyle L = \{v_{1},...,v_{m+1}\}$, be a linearly independent subset of $\displaystyle V$ consisting of $\displaystyle m+1$ vectors. Then $\displaystyle \{v_{1},...,v_{m}\}$is linearly independent, and so we may apply the induction hypothesis to conclude that $\displaystyle m\leq n$ and that theres is a subset $\displaystyle \{u_{1},...,v_{m-n}\}$ of $\displaystyle G$such that $\displaystyle \{v_{1},...,v_{m}\} \cup \{u_{1},...,v_{m-n}\}$ generates$\displaystyle V$. Thus there exist scalars $\displaystyle a_{1},..,a_{m},b_{1},...,b_{n-m}$ such that $\displaystyle a_{1}v_{1}+...+a_{m}v_{m}+b_{1}u_{1}+...+b_{n-m}u_{n-m}=v_{m+1}$.

Note that $\displaystyle n-m>0$, lest $\displaystyle v_{m+1}$ be a linear combination of $\displaystyle \{v_{1},...,v_{m}\}$ which contradicts the assumption that L is linearly independent.

I am having trouble understanding why does $\displaystyle n-m>0$.

Could someone give me a hint so I can understand. Thanks!

Edit: Is it beacause the induction hypothesis gives us $\displaystyle m\leq n$ and and since $\displaystyle L$ has an extra vector means that they cannot be equal?
• Jan 26th 2013, 10:34 AM
emakarov
Re: Help understanding Replacement theorem Friedberg
Since m <= n, the only choices are m < n and m = n. If m = n, then from

$\displaystyle a_{1}v_{1}+...+a_{m}v_{m}+b_{1}u_{1}+...+b_{n-m}u_{n-m}=v_{m+1}$

we have

$\displaystyle a_{1}v_{1}+...+a_{m}v_{m}=v_{m+1}$

i.e., L is not linearly independent, contrary to the assumption.
• Jan 26th 2013, 11:04 AM
gordo151091
Re: Help understanding Replacement theorem Friedberg
Thanks, I over looked n-m=0