Every linearly independent set of a finitely generated vector space has at most the same number of vectors as its spanning set

up:: Finitely Generated Vector Space

Let be a Vector Space, with Spanning Set . Let be a Linearly Independent set. We seek to prove that .

We seek to prove that, by adequate arrangements, exchanges of vectors of with vectors from still make the new set a spanning set, since each vector removed can be seen as the linear combination of the remainder of the vectors (thus, “no information is lost”).

Proof by Induction: removing a vector from and adding a vector from still makes their union a spanning set.

• : is Linearly Dependent and spans . Since A set is linearly dependent iff there is a vector which is a linear combination of previous vectors, then we can rearrange the new set and remove some vector from such that this union still spans ─ say, removing ¹ ─ yielding .
• : Suppose that is still a spanning set, after having swapped vectors from for vectors from (provided adequate arrangements). Since it spans , then we have that, in particular,

Note that we must have some different than , since else it would make linearly independent² ─ let it be . Then we have

Thus, is in the span of . As a consequence, this new set will still span (since it contains all vectors which, per hypothesis, span ).

At the end, we’ll have the set which spans . Note that, if , we’d run out of spanning vectors and would be forced to remove vectors from themselves ─ which would make it Linearly Dependent, contradiction.

Thus we must have that .

Corollaries

• All Hamel bases have the same number of elements (in a finitely generated vector space)
• Sets larger than a finitely generated space’s bases are linearly dependent
• Any linearly independent set can be extended to a Hamel basis

---

References

• linear algebra - Prove that cardinality of linearly independent set is less than or equal to spanning set - Mathematics Stack Exchange
• linear algebra - The length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors. - Mathematics Stack Exchange

Footnotes

1. This works since will be substituted by the span of the remaining vectors ─ and, thus, this new set will still span the entire set, just with instead of with . ↩

2. And we have that A set is linearly independent iff all its finite subsets are also L.I.. ↩