# Thread: Help understanding Replacement theorem Friedberg

1. ## 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?

2. ## 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.

3. ## Re: Help understanding Replacement theorem Friedberg

Thanks, I over looked n-m=0

,

,

,

,

,

,

,

,

,

,

# replacement theorem explained

Click on a term to search for related topics.