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

{{citation|last=Mac Lane|first=Saunders|authorlink=Saunders Mac Lane|year=1936|title=Some interpretations of abstract linear dependence in terms of projective geometry|journal=American Journal of Mathematics|volume=58|pages=236–240|doi=10.2307/2371070| jstor=2371070 | issue=1|publisher=The Johns Hopkins University Press}}.

by Saunders Mac Lane

of Steinitz's lemma to matroids.

{{citation|editor-last=Kung|editor-first=Joseph P. S.|title=A Source Book in Matroid Theory|publisher=Birkhäuser|mr=0890330|isbn=0-8176-3173-9|location=Boston|year=1986|doi=10.1007/978-1-4684-9199-9|url-access=registration|url=https://archive.org/details/sourcebookinmatr0000kung}}.

Statement

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

1. $|U| \leq |W|$ ;

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

Proof

Suppose $U=\{u_1, \dots, u_m\}$ and $W=\{w_1, \dots, w_n\}$ . We wish to show that $m \le n$ , and that after rearranging the $w_j$ if necessary, the set $\{u_1, \dotsc, u_m, w_{m + 1}, \dotsc, w_n\}$ spans $V$ . We proceed by induction on $m$ .

For the base case, suppose $m$ is zero.

In this case, the claim holds because there are no vectors $u_i$ , and the set $\{w_1, \dotsc, w_n\}$ spans $V$ by hypothesis.

For the inductive step, assume the proposition is true for $m-1$ . By the inductive hypothesis we may reorder the $w_i$ so that $\{ u_1,\ldots, u_{m-1},w_{m},\ldots,w_n\}$ spans $V$ . Since $u_{m}\in V$ , there exist coefficients $\mu_1, \ldots, \mu_n$ such that

: $u_{m}=\sum_{i=1}^{m-1} \mu_i u_i+\sum_{j=m}^n \mu_j w_j$ .

At least one of the $\mu_j$ for $j \ge m$ must be non-zero, since otherwise this equality would contradict the linear independence of $\{ u_1,\ldots,u_{m} \}$ ; this also shows that indeed $m \le n.$ By reordering $\mu_{m}w_{m},\ldots,\mu_{n}w_n$ if necessary, we may assume that $\mu_{m}$ is nonzero. Therefore, we have

: $w_{m}= \frac{1}{\mu_{m}}\left(u_{m} - \sum_{j=1}^{m-1} \mu_j u_j - \sum_{j=m+1}^n \mu_j w_j\right)$ .

In other words, $w_{m}$ is in the span of $\{ u_1,\ldots, u_{m},w_{m+1},\ldots,w_n\}$ . Since this span contains each of the vectors $u_1, \ldots, u_{m-1}, w_{m}, w_{m+1}, \ldots, w_n$ , by the inductive hypothesis it contains $V$ .

Applications

The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.Page v in Stiefel:

{{cite book|last=Stiefel|first=Eduard L.|authorlink=Eduard Stiefel|title=An introduction to numerical mathematics|url=https://archive.org/details/introductiontonu1963stie|url-access=registration|edition=Translated by Werner C. Rheinboldt & Cornelie J. Rheinboldt from the second German|publisher=Academic Press|location=New York|year=1963|pages=x+286|mr=181077}}

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

Category:Lemmas in linear algebra

Category:Matroid theory