The Steinitz exchange lemma is a basic theorem in linear algebra used, for example, to show that any two bases for a finite-dimensional vector space have the same number of elements.
The result is named after the German mathematician Ernst Steinitz.
The result is often called the Steinitz–Mac Lane exchange lemma, also recognizing the generalization[1] by Saunders Mac Lane of Steinitz's lemma to matroids.
be finite subsets of a vector space
is a set of linearly independent vectors, and
spans
spans
spans
We proceed by induction on
For the base case, suppose
In this case, the claim holds because there are no vectors
spans
by hypothesis.
For the inductive step, assume the proposition is true for
By the inductive hypothesis we may reorder the
spans
, there exist coefficients
μ
μ
μ
must be non-zero, since otherwise this equality would contradict the linear independence of
By reordering
μ
μ
μ
Therefore, we have In other words,
is in the span of
Since this span contains each of the vectors
, by the inductive hypothesis it contains
The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.