# Help understanding Replacement theorem Friedberg

• Jan 26th 2013, 10: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 $V$ be a vector space that is generated by a set $G$ containing exactly $n$ vectors, and let $L$ be a linearly independent subset of $V$ containing exactly vectors. Then $m\leq n$ and there exists a subset $H$ of $G$ containing exactly $n-m$ vectors such that $L \cup H$ generates $V$

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

Inductive step

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

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

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

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

Edit: Is it beacause the induction hypothesis gives us $m\leq n$ and and since $L$ has an extra vector means that they cannot be equal?
• Jan 26th 2013, 11: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

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

we have

$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, 12:04 PM
gordo151091
Re: Help understanding Replacement theorem Friedberg
Thanks, I over looked n-m=0