An important result in linear algebra, one of those niggly little theorems that helps you prove things that should be patently obvious. Basically it says that you can exchange an element of a basis for a linear combination of it and the rest of the basis, and still have a basis. More formally:

Lemma: (Steinitz) If V is a vector space with basis B = {b1,...,bn} and v ∈ V such that v = λibi with λ1 ≠ 0, then {v, b2,...,bn} is a basis of V.

Proof: Let C = {v, b2,...,bn}. We now have B ∪ {v} = C ∪ {b1} spans V. As b1 ∈ <C>, we get C spans V. If μv + μjbj = 0 (j ≠ 1), then μλ1b1 + (μj + λjμ)bj = 0. Since B is a basis and λ1 ≠ 0, we can see that μ = μj = 0. Therefore C is a linearly independent spanning set and hence a basis for V.

While not important on its own, this lemma has an astonishing number of useful corollaries, such as the following:

  • If B is a basis and C is a linearly independent set, then |B| ≥ |C| and there is a basis D with C ⊆ D and |B ∩ (D\C)| = |B| - |C|
  • If V is a finite dimensional vector space and L ⊆ V is linearly independent, then V has a basis containing L
  • If V is a finite dimensional vector space and B and C are bases of V, then |B| = |C| = dim(V)
  • If V is finite dimensional, S ⊆ V is linearly independent and |S| = dim(V), then S is a basis of V
  • If V is finite dimensional, S ⊆ V spans V and |S| = dim(V), then S is a basis of V
  • If U is a subspace of a finite dimensional vector space V, then U is finite dimensional and dim(U) ≤ dim(V) with equality iff U = V

For those who are seeing lots of little squares, this symbol (∈) is "is an element of" and this symbol (⊆) is "is a subset of or is equal to"