We prove the exchange theorem to show well-definedness of the term "dimension" later.
In this article we will discuss the exchange lemma and Steinitz's exchange theorem. These state how a given basis of a vector space can be converted into another one by cleverly replacing some of the old basis vectors with new vector space elements. This is especially useful when you want to construct a basis that contains certain previously fixed vectors. Another consequence of the replacement theorem is the fact that linearly independent sets have a lower or equal cardinality than bases. This result is essential for the definition of the dimension of a vector space. We first prove the exchange lemma and then Steinitz's theorem.
Theorem (Exchange lemma)
Let be a vector space over a field and a Basis of . Further, let which can be written as a linear combination , where . If such that , then is also a Basis of .
Proof (Exchange lemma)
Let be the set where has been replaced by . We need to prove that is a basis, as well. For this, we show that is a generator of and linearly independent.
Proof step: is a generator
We know with and . According to the above assumption, and therefore it has an inverse in .
Thus we may transform:
Because is a basis of , we may find for every vector some scalars , such that . We now plug in the above result for and obtain:
So the vector has been represented as a linear combination of and is indeed a generator of .
Proof step: is linearly independent
Let , such that . We replace by its representation as a linear combination of the basis elements and obtain:
Since is linearly independent, we have that and for all .
From and we have .
But this also implies for all .
Hence, is linearly independent which finishes the proof.
The converse of the exchange lemma also holds true (without proof, here):
Let be a vector space over a field and be a basis of . Further, let with the linear combination , where . If such that is also a basis of , then we already have that .
Next, we prove a slight modification of the exchange lemma. It shows that the lemma is "almost always" applicable. We only assume that the new basis vector is not the zero vector:
Theorem (Exchange lemma version 2)
Let be a vector space over a field and a basis of . Further, let . Then there is an index such that is also a basis of
We can thus exchange for .
Proof (Exchange lemma version 2)
We write as a linear combination of vectors from . Let also with .
Since , at least one of the scalars must be non-zero. Indeed, if we had for all , then would also have to hold. So let such that . With this the condition from the upper version of the exchange lemma is fulfilled.
Application of the exchange lemma[Bearbeiten]
Let be the canonical basis of and .
We show that is a basis of .
According to the exchange lemma, we can replace the vector by if for the (unique) linear combination we have that: .
We recognise that:
Thus it follows from the exchange lemma that is a basis of .
But we also see from this discussion that we cannot use the exchange lemma to show that is a basis: In the linear combination of , we have . Therefore, we cannot apply the exchange lemma here.
We even have that is really not a basis of :
, so the vectors are linearly dependent, so in particular they are not a basis.
Example (Basis completion by substitution in a known basis)
We want to complete the two vectors
to a basis of .
First we should check whether the two vectors are linearly independent, but this is easy to see because for
there must be , which then means that as well.
We now want to exchange for two basis vectors of a known basis of using the exchange lemma. For the we simply take the canonical basis
By repeatedly applying the exchange lemma, the vectors are exchanged one after the other. Here we proceed as follows:
The vector is represented as a linear combination of the vectors .
According to the exchange lemma, we can exchange any basis vector , since for every the associated scalars are .
So, for example, if we exchange for , then we get that is a basis of .
We now repeat the above procedure for with the basis .
Again, we may exchange any of the vectors , but exchanging is not purposeful, so we exchange . Thus the vectors form a basis of . So in total we have completed the linearly independent vectors with to a basis of .
Steinitz's exchange theorem[Bearbeiten]
Theorem (Steinitz's theorem)
be an -element basis of the -vector space and let
be a -element set of linearly independent vectors.
Then, we have that and there is a certain choice of vectors from the basis that can be replaced by the vectors
such that the replacement results in a new basis of the -vector space .
More precisely, after renumbering the indices (if necessary) we can write
Proof (Steinitz's theorem)
We prove the theorem by induction over k.
Proof step: Induction base
Let be a basis of and let be linearly independent, i.e. , then it follows with above exchange lemma, that for a given is a basis of .
Now we rename to .
It then follows that is a basis. This is the base case of our induction.
Proof step: Induction step
Let be linearly independent. By the induction assumption, we have that , from which we want to infer . Suppose there was . Then since and we have that . As is linearly independent and , we can replace with by induction assumption. So we get that is a basis of .
We can also represent as a linear combination in . Let , with . Then we have:
But this is a contradiction to the linear independence of . So must also hold true.
It remains to show that after any renaming of
is a basis of . By induction assumption, is a basis of . In this case, the indices of may have been interchanged. We write as a linear combination of .
Let for this , with . Note that these are not necessarily the same as before. Suppose there was for all . Then
would hold, which would be a contradiction to the linear independence of . So, let with . By the exchange lemma, is a basis of .
Finally, we rename to .
Then is a basis of , which concludes the proof.