- Source: 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
by Saunders Mac Lane
of Steinitz's lemma to matroids.
Statement
Let
U
{\displaystyle U}
and
W
{\displaystyle W}
be finite subsets of a vector space
V
{\displaystyle V}
. If
U
{\displaystyle U}
is a set of linearly independent vectors, and
W
{\displaystyle W}
spans
V
{\displaystyle V}
, then:
1.
|
U
|
≤
|
W
|
{\displaystyle |U|\leq |W|}
;
2. There is a set
W
′
⊆
W
{\displaystyle W'\subseteq W}
with
|
W
′
|
=
|
W
|
−
|
U
|
{\displaystyle |W'|=|W|-|U|}
such that
U
∪
W
′
{\displaystyle U\cup W'}
spans
V
{\displaystyle V}
.
Proof
Suppose
U
=
{
u
1
,
…
,
u
m
}
{\displaystyle U=\{u_{1},\dots ,u_{m}\}}
and
W
=
{
w
1
,
…
,
w
n
}
{\displaystyle W=\{w_{1},\dots ,w_{n}\}}
. We wish to show that
m
≤
n
{\displaystyle m\leq n}
, and that after rearranging the
w
j
{\displaystyle w_{j}}
if necessary, the set
{
u
1
,
…
,
u
m
,
w
m
+
1
,
…
,
w
n
}
{\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}}
spans
V
{\displaystyle V}
. We proceed by induction on
m
{\displaystyle m}
.
For the base case, suppose
m
{\displaystyle m}
is zero.
In this case, the claim holds because there are no vectors
u
i
{\displaystyle u_{i}}
, and the set
{
w
1
,
…
,
w
n
}
{\displaystyle \{w_{1},\dotsc ,w_{n}\}}
spans
V
{\displaystyle V}
by hypothesis.
For the inductive step, assume the proposition is true for
m
−
1
{\displaystyle m-1}
. By the inductive hypothesis we may reorder the
w
i
{\displaystyle w_{i}}
so that
{
u
1
,
…
,
u
m
−
1
,
w
m
,
…
,
w
n
}
{\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}}
spans
V
{\displaystyle V}
. Since
u
m
∈
V
{\displaystyle u_{m}\in V}
, there exist coefficients
μ
1
,
…
,
μ
n
{\displaystyle \mu _{1},\ldots ,\mu _{n}}
such that
u
m
=
∑
i
=
1
m
−
1
μ
i
u
i
+
∑
j
=
m
n
μ
j
w
j
{\displaystyle u_{m}=\sum _{i=1}^{m-1}\mu _{i}u_{i}+\sum _{j=m}^{n}\mu _{j}w_{j}}
.
At least one of the
μ
j
{\displaystyle \mu _{j}}
must be non-zero, since otherwise this equality would contradict the linear independence of
{
u
1
,
…
,
u
m
}
{\displaystyle \{u_{1},\ldots ,u_{m}\}}
; it follows that
m
≤
n
{\displaystyle m\leq n}
. By reordering
μ
m
w
m
,
…
,
μ
n
w
n
{\displaystyle \mu _{m}w_{m},\ldots ,\mu _{n}w_{n}}
if necessary, we may assume that
μ
m
{\displaystyle \mu _{m}}
is nonzero. Therefore, we have
w
m
=
1
μ
m
(
u
m
−
∑
j
=
1
m
−
1
μ
j
u
j
−
∑
j
=
m
+
1
n
μ
j
w
j
)
{\displaystyle 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
{\displaystyle w_{m}}
is in the span of
{
u
1
,
…
,
u
m
,
w
m
+
1
,
…
,
w
n
}
{\displaystyle \{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}}
. Since this span contains each of the vectors
u
1
,
…
,
u
m
−
1
,
w
m
,
w
m
+
1
,
…
,
w
n
{\displaystyle u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}}
, by the inductive hypothesis it contains
V
{\displaystyle V}
.
Applications
The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.
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
Kata Kunci Pencarian:
- Steinitz exchange lemma
- Dimension theorem for vector spaces
- Basis (linear algebra)
- Rank–nullity theorem
- Ernst Steinitz
- Steinitz's theorem (disambiguation)
- Rank (linear algebra)
- Pregeometry (model theory)
- Matroid
- List of abstract algebra topics
