Steinitz exchange lemma

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.^[2]

Statement[]

Let ${\displaystyle U}$ and ${\displaystyle W}$ be finite subsets of a vector space ${\displaystyle V}$. If ${\displaystyle U}$ is a set of linearly independent vectors, and ${\displaystyle W}$ spans ${\displaystyle V}$, then:

1. ${\displaystyle |U|\leq |W|}$;

2. There is a set ${\displaystyle W'\subseteq W}$ with ${\displaystyle |W'|=|W|-|U|}$ such that ${\displaystyle U\cup W'}$ spans ${\displaystyle V}$.

Proof[]

Suppose ${\displaystyle U=\{u_{1},\dots ,u_{m}\}}$ and ${\displaystyle W=\{w_{1},\dots ,w_{n}\}}$. We wish to show that for each ${\displaystyle k\in \{0,\dots ,m\}}$, we have that ${\displaystyle k\leq n}$, and that the set ${\displaystyle \{u_{1},\dotsc ,u_{k},w_{k+1},\dotsc ,w_{n}\}}$ spans ${\displaystyle V}$ (where the ${\displaystyle w_{j}}$ have possibly been reordered, and the reordering depends on ${\displaystyle k}$). We proceed by induction on ${\displaystyle k}$.

For the base case, suppose ${\displaystyle k}$ is zero. In this case, the claim holds because there are no vectors ${\displaystyle u_{i}}$, and the set ${\displaystyle \{w_{1},\dotsc ,w_{n}\}}$ spans ${\displaystyle V}$ by hypothesis.

For the inductive step, assume the proposition is true for some ${\displaystyle k<m}$. Since ${\displaystyle u_{k+1}\in V}$, and ${\displaystyle \{u_{1},\ldots ,u_{k},w_{k+1},\ldots ,w_{n}\}}$ spans ${\displaystyle V}$ (by the induction hypothesis), there exist coefficients ${\displaystyle \mu _{1},\ldots ,\mu _{n}}$ such that

${\displaystyle u_{k+1}=\sum _{j=1}^{k}\mu _{j}u_{j}+\sum _{j=k+1}^{n}\mu _{j}w_{j}}$.

At least one of ${\displaystyle \{\mu _{k+1},\ldots ,\mu _{n}\}}$ must be non-zero, since otherwise this equality would contradict the linear independence of ${\displaystyle \{u_{1},\ldots ,u_{k+1}\}}$; note that this additionally implies that ${\displaystyle k+1\leq n}$. By reordering the ${\displaystyle \mu _{k+1}w_{k+1},\ldots ,\mu _{n}w_{n}}$, we may assume that ${\displaystyle \mu _{k+1}}$ is not zero. Therefore, we have

${\displaystyle w_{k+1}={\frac {1}{\mu _{k+1}}}\left(u_{k+1}-\sum _{j=1}^{k}\mu _{j}u_{j}-\sum _{j=k+2}^{n}\mu _{j}w_{j}\right)}$.

In other words, ${\displaystyle w_{k+1}}$ is in the span of ${\displaystyle \{u_{1},\ldots ,u_{k+1},w_{k+2},\ldots ,w_{n}\}}$. The latter span therefore contains each of the vectors ${\displaystyle u_{1},\ldots ,u_{k},w_{k+1},w_{k+2},\ldots ,w_{n}}$, and hence must contain the span of these latter vectors as a subset. But since the latter span is ${\displaystyle V}$ (by the induction hypothesis), this simply means that the span of ${\displaystyle \{u_{1},\ldots ,u_{k+1},w_{k+2},\ldots ,w_{n}\}}$ contains ${\displaystyle V}$ as a subset (thus is ${\displaystyle V}$). We have therefore shown that our claim is true of ${\displaystyle k+1}$, completing the inductive step.

We have thus shown that for each ${\displaystyle k\in \{0,\dots ,m\}}$, we have that ${\displaystyle k\leq n}$, and that the set ${\displaystyle \{u_{1},\dotsc ,u_{k},w_{k+1},\dotsc ,w_{n}\}}$ spans ${\displaystyle V}$ (where the ${\displaystyle w_{j}}$ have possibly been reordered, and the reordering depends on ${\displaystyle k}$).

The fact that ${\displaystyle m\leq n}$ follows from setting ${\displaystyle k=m}$ in this result.

Applications[]

The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.^[3]

References[]

• Julio R. Bastida, Field extensions and Galois Theory, Addison–Wesley Publishing Company (1984).

External links[]

• Mizar system proof: http://mizar.org/version/current/html/vectsp_9.html#T19