state and proof replacement theorem
Answers
The proof in the book says to start with m=0. In that case L=∅, the empty set.
Okay, and I hope you realize that this also proves the inequality m≤n for the base case.
Let's assume this theorem is true for some integer m ≥ 0.
Let L = v1,v2,....vm+1 and define it as a linearly independent subset of V consisting of m+1 vectors.
So we're going to use induction on m to prove the theorem. Also, it should be L={v1,…,vm+1}.
Since any subset of a linearly independent set is linearly independent as well (S1⊆S2⊆V), then {v1,v2,....vm} is linearly independent also.
That's correct. I'll call this set L′.
It then says to use the induction hypothesis to say that m≤n. Well, ok, but that seems sort of pulled out of nowhere to me. The next step is to say that there is therefore another subset, {u1,u2,....unm} of G s.t. {v1,v2,....vm} ∪ {u1,u2,....un−m} generates V.
It isn't pulled out of nowhere because it follows from the induction hypothesis. As we have assumed it for some m≥0, we can apply the theorem to {v1,…,vm} which gives us the inequality m≤n and the set H′={u1,…,un−m}⊂G such that L′∪H′ generates V.
That being the case there are scalars a1,a2,....am and b1,b2,....bn−m which you can multiply by the vectors vi and ui. You can then add th two sets of vectors, yielding
a1v1+a2v2+...+amvm+b1u1+b2u2+...bn−mun−m=vm+1(*)
We can do this as L′∪H′ generates V.
At this point I am not sure I understand things. Because we are assuming n-m>0 -- otherwise vm+1 is linearly dependent. But then it says not only is n>m but n>m+1, and that is where I am losing the plot to get to the next step.
What follows is this:
Note that n−m>0, lest vm+1 is a linear combination of v1,…,vm which by Theorem 1.7 (pg 39) contradicts the assumption that L is linearly independent.
Do you understand why it must be n−m>0? Well if we had n−m=0 then H′=∅ and this would mean that (*) is only composed of vectors of L′ and therefore, L′∪{vm+1}=L would be linearly dependent as vm+1∈span(L′), but that would be a contradiction.
Hence n>m; that is, n≥m+1.
Why? Because another way of expressing n>m, as n and m are integers, is n≥m+1. That's all there is to it.
Moreover, some bi, say b1 is nonzero, for otherwise we obtain the same contradiction. Solving (*) for u1 gives
u1=(−b−11a1)v1+⋯+(−b−11am)vm+(−b1)vm+1+(−b−11b2)u2+⋯+(−b−11bn−m)un−m
Of course. If bi were all zero in (*) it would again only be composed of vectors of L′ and we know that that can't be the case for the same reason as above.
Let H={u2,…,un−m}. Then u1∈span(L∪H) and because v1,…,vm,u2,…,un−m are clearly in span(L∪H), it follows that
L′∪H′={v1,…,vm,u1,…,un−m}⊆span(L∪H).
This should be clear.
Because L′∪H′ generates V, Theorem 1.5 (pg 30) implies that span(L∪H) generators V.
To see why you can apply Theorem 1.5 you must remember that if S⊆V then span(S) is a subspace of V and therefore, by Theorem 1.5, if W⊆span(S) then span(W)⊆span(S). So we have that V=span(L′∪H′)⊆span(L∪H) and since obviously, span(L∪H)⊆V we have span(L∪H)=V.
Since H is a subset of G which contains (n−m)−1=n−(m+1) vectors the theorem is true for m+1. This completes the induction.
This should be clear.
Hope this helps!