0

The Replacement Theorem says two things about a finite subset S with n elements which spans a vector space V and another finite subset L of m linearly independent elements taken from V:

  • Firstly that we can find a subset S' of S, containing$\ n - m$ elements, such that $\ S' ∪ L$ also spans V. A very nice induction proof helped me understand this: essentially replacing each element in S with elements in L, one-by-one, all the while proving that the resulting set still spanned V. Eventually she arrives at the final case, where all m elements of L have been moved into S.
  • Secondly, that $\ m ≤ n$. I just can't seem to see why. Another clip even mentioned something about L needing to strictly have fewer elements than the spanning set S.

Why can't the number of elements m of the linearly independent set be larger than the number of elements n in the spanning set, and should m even by strictly$\ < n$?

iWebb
  • 17

1 Answers1

0

If a set is linearly independent in a finite-dimensional space (by which I mean, has a finite spanning set), then we may always extend it to a spanning set. How? Well, let $A = \lbrace v_1, \ldots, v_m \rbrace$ be L.I. and $B = \lbrace w_1, \ldots, w_n \rbrace$ be spanning. What we do is take elements of $B$, one by one, and check to see if they belong to the span of $A$. Once we find a vector not in the span, we add it to $A$ and repeat the process. Each time we do this, we maintain linear independence, but by construction, every element of $B$ is either in the set, or is a linear cominbation of the other vectors. Hence, the set spans all of $B$, and hence is spanning and linearly independent.

On the other hand, if a (finite) set is spanning, we can reduce it to linear independence. You can take it step-by-step: check first if $w_1 = 0$. If not, keep it, otherwise throw it out. Then check $w_2$ to see if it's in the span of $w_1$. If not, keep it, otherwise throw it out. Then check if $w_3 \in \operatorname{span}\lbrace w_1, w_2 \rbrace$, etc. Throwing out vectors in this way provably preserves span (since nothing you threw out contributes anything but a combination of what came before), but at the end, none of the vectors are linear combinations of each other, and hence are linearly independent.

So now, if we have a linearly independent set that's strictly larger than a spanning set, this means the linearly independent set can be extended to basis that's strictly larger than any basis the spanning set can be reduced to. By replacing elements from the larger basis with elements of the smaller basis, it's simple to get to a contradiction.

Theo Bendit
  • 50,900
  • Great, and intutive explanation. Thank you @TheoBendit.

    Firstly, as the replacement theorem only talks about extending the L.I. set so it spans, I guess the first paragraph deals with this (your second paragraph deals with the $\ m ≤ n $ part). However, I notice that in the first paragraph, you don't simply extend the L.I. set to a spanning set, you ensure L.I. of the ever-extending set, and thus that the end result is a basis. Am I right that you've gone above and beyond the replacement theorem (possibly you did this in order to be able to explain $\ m ≤ n $ to me).

     – iWebb Dec 02 '17 at 14:26
  • In part 2, you also create a basis.

    So, my question is, aren't you using the fact that all bases have the same number of elements to prove that m cannot be$\ > n$?

     – iWebb Dec 02 '17 at 14:26
  • Yes, I'm going beyond the single theorem to explain intuitively why we can do these things, and thus derive facts like all linearly independent sets are smaller than spanning sets, and all bases are of the same size. If I'm retreading any old ground of which you are already familiar and convinced, please feel free to substitute with your own understanding! – Theo Bendit Dec 02 '17 at 14:41
  • Ah, I see.

    So the first paragraph and the second paragaph both describe one-directional process:

    The first shows us that we can always extend a L.I. set to become a spanning set (if it's not already a spanning set, i.e. a basis), BUT can't go in the opposite direction (remove elements) as then we definitely won't span.

    Similarly, the second paragraph says we can reduce a spanning set to linear independence (if it's not already L.I., i.e. a basis), BUT can't go the other way as we already span and so definitely won't achieve L.I. by adding more vectors from V.

     – iWebb Dec 02 '17 at 15:47
  • So whilst we might not need to do anything to our spanning set (it might already be LI, i.e. a basis) or to our LI set (it might already span, i.e. a basis), if we do need to do anything it will be to reduce the spanning set or to extend the LI set, and hence either m = n (i.e. a basis already), or m < n. – iWebb Dec 02 '17 at 15:53