Steinitz's theorem – Serlo

We prove the exchange theorem to show well-definedness of the term "dimension" later.

Motivation

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.

Exchange lemma

The exchange lemma

Theorem (Exchange lemma)

Let $V$ be a vector space over a field $K$ and $B=\left\{b_{1},\,b_{2},\,\ldots ,b_{n}\right\}$ a Basis of $V$. Further, let $w\in V$ which can be written as a linear combination $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$, where $\lambda _{1},\ldots ,\lambda _{n}\in K$. If $k\in \lbrace 1,\ldots ,n\rbrace$ such that $\lambda _{k}\neq 0$, then $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ is also a Basis of $V$.

Proof (Exchange lemma)

Let $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ be the set where $b_{k}$ has been replaced by $w$ . We need to prove that $B'$ is a basis, as well. For this, we show that $B'$ is a generator of $V$ and linearly independent.

Proof step: $B'$ is a generator

We know$w=\sum _{i=1}^{n}\lambda _{i}b_{i}$ with $\lambda _{i}\in K$ and $b_{i}\in B$. According to the above assumption, $\lambda _{k}\neq 0$ and therefore it has an inverse in $K$. Thus we may transform:

${\begin{aligned}w=&\sum _{i=1}^{n}\lambda _{i}b_{i}=\sum _{i=1 \atop i\neq k}^{n}\lambda _{i}b_{i}+\lambda _{k}b_{k}\\[0.3em]\iff \ &\lambda _{k}b_{k}=w-\sum _{i=1 \atop i\neq k}^{n}\lambda _{i}b_{i}\\[0.3em]\iff \ &b_{k}={\dfrac {1}{\lambda _{k}}}w-\sum _{i=1 \atop i\neq k}^{n}{\dfrac {\lambda _{i}}{\lambda _{k}}}b_{i}\end{aligned}}$

Because $B$ is a basis of $V$, we may find for every vector $v\in V$ some scalars $\mu _{i}\in K$, such that $v=\sum _{i=1}^{n}\mu _{i}b_{i}$. We now plug in the above result for $b_{k}$ and obtain:

${\begin{aligned}v&=\mu _{k}b_{k}+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}\\[0.3em]&=\mu _{k}\left({\dfrac {1}{\lambda _{k}}}w-\sum _{i=1 \atop i\neq k}^{n}{\dfrac {\lambda _{i}}{\lambda _{k}}}b_{i}\right)+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}\\[0.3em]&={\dfrac {\mu _{k}}{\lambda _{k}}}w-\sum _{i=1 \atop i\neq k}^{n}\mu _{k}{\dfrac {\lambda _{i}}{\lambda _{k}}}b_{i}+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}\\[0.3em]&={\dfrac {\mu _{k}}{\lambda _{k}}}w+\sum _{i=1 \atop i\neq k}^{n}(\mu _{i}-\mu _{k}{\dfrac {\lambda _{i}}{\lambda _{k}}})b_{i}\end{aligned}}$

So the vector $v$ has been represented as a linear combination of $B^{*}=\left\{b_{1},\,b_{2},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ and $B'$ is indeed a generator of $V$.

Proof step: $B'$ is linearly independent

Let $\beta ,\mu _{1},\ldots ,\mu _{k-1},\mu _{k+1},\ldots ,\mu _{n}\in K$, such that $\beta w+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}=0$. We replace $w$ by its representation as a linear combination of the basis elements $b_{i}$ and obtain:

${\begin{aligned}0=\beta w+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}=\beta \cdot \left(\sum _{i=1}^{n}\lambda _{i}b_{i}\right)+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}=\beta \lambda _{k}b_{k}+\sum _{i=1 \atop i\neq k}^{n}(\beta \lambda _{i}+\mu _{i})b_{i}\end{aligned}}$

Since $B=\lbrace b_{1},\cdots ,b_{n}\rbrace$ is linearly independent, we have that $\beta \lambda _{k}=0$ and $\beta \lambda _{l}+\mu _{l}=0$ for all $l\neq k$.

From $\beta \lambda _{k}=0$ and $\lambda _{k}\neq 0$ we have $\beta =0$. But this also implies $\mu _{l}=0$ for all $l\neq k$. Hence, $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ is linearly independent which finishes the proof.

Hint

The converse of the exchange lemma also holds true (without proof, here):

Let $V$ be a vector space over a field $K$ and $B=\left\{b_{1},\,b_{2},\,\ldots ,b_{n}\right\}$ be a basis of $V$. Further, let $w\in V$ with the linear combination $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$, where $\lambda _{1},\ldots ,\lambda _{n}\in K$. If $k\in \lbrace 1,\ldots ,n\rbrace$ such that $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ is also a basis of $V$, then we already have that $\lambda _{k}\neq 0$.

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 $w$ is not the zero vector:

Theorem (Exchange lemma version 2)

Let $V$ be a vector space over a field $K$ and $B=\left\{b_{1},\,\ldots ,b_{n}\right\}$ a basis of $V$. Further, let $0\neq w\in V$. Then there is an index $k\in \lbrace 1,\ldots ,n\rbrace$ such that $B^{*}=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ is also a basis of $V$

We can thus exchange $b_{k}$ for $w$.

Proof (Exchange lemma version 2)

We write $w$ as a linear combination of vectors from $B$. Let also $\lambda _{1}\,\ldots \,\lambda _{n}\in K$ with $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$.

Since $w\neq 0$, at least one of the scalars $\lambda _{1},\ldots ,\lambda _{n}$ must be non-zero. Indeed, if we had $\lambda _{k}=0$ for all $k$, then $w=0$ would also have to hold. So let $k\in \{1,\ldots n\}$ such that $\lambda _{k}\neq 0$. With this $k$ the condition from the upper version of the exchange lemma is fulfilled.

Application of the exchange lemma

Example

Let $E:=\{e_{1},e_{2},e_{3}\}$ be the canonical basis of $\mathbb {R} ^{3}$ and $w:=(1,1,0)^{T}$. We show that $\{w,e_{2},e_{3}\}$ is a basis of $\mathbb {R} ^{3}$. According to the exchange lemma, we can replace the vector $e_{1}$ by $w$ if for the (unique) linear combination $w=\sum _{i=1}^{3}\lambda _{i}e_{i}$ we have that: $\lambda _{1}\neq 0$.

We recognise that: $w={\begin{pmatrix}1\\1\\0\end{pmatrix}}=\underbrace {1} _{\lambda _{1}\neq 0}\cdot {\begin{pmatrix}1\\0\\0\end{pmatrix}}+\underbrace {1} _{\lambda _{2}}\cdot {\begin{pmatrix}0\\1\\0\end{pmatrix}}+\underbrace {0} _{\lambda _{3}}\cdot {\begin{pmatrix}0\\0\\1\end{pmatrix}}$

Thus it follows from the exchange lemma that $\{w,e_{2},e_{3}\}$ is a basis of $\mathbb {R} ^{3}$.

But we also see from this discussion that we cannot use the exchange lemma to show that $\{e_{1},e_{2},w\}$ is a basis: In the linear combination of $w=\sum _{i=1}^{3}\lambda _{i}e_{i}$, we have $\lambda _{3}=0$. Therefore, we cannot apply the exchange lemma here.

We even have that $\{e_{1},e_{2},w\}$ is really not a basis of $\mathbb {R} ^{3}$: $w=e_{1}+e_{2}$, 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 $v_{1}=(1,1,2)^{T},\,v_{2}=(0,1,1)^{T}\in \mathbb {R} ^{3}$ to a basis $\{v_{1},\,v_{2},\,v_{3}\}$ of $\mathbb {R} ^{3}$.

First we should check whether the two vectors are linearly independent, but this is easy to see because for ${\begin{aligned}\alpha _{1}\cdot {\begin{pmatrix}1\\1\\2\end{pmatrix}}+\alpha _{2}\cdot {\begin{pmatrix}0\\1\\1\end{pmatrix}}={\begin{pmatrix}\alpha _{1}\\{\alpha _{1}+\alpha _{2}}\\{2\alpha _{1}+\alpha _{2}}\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}\end{aligned}}$

there must be $\alpha _{1}=0$, which then means that $\alpha _{2}=0$ as well.

We now want to exchange $v_{1},\,v_{2}$ for two basis vectors of a known basis of $\mathbb {R} ^{3}$ using the exchange lemma. For the $\mathbb {R} ^{3}$ we simply take the canonical basis $E=\lbrace e_{1}=(1,0,0)^{T},\,e_{2}=(0,1,0)^{T},\,e_{3}=(0,0,1)^{T}\rbrace$. By repeatedly applying the exchange lemma, the vectors are exchanged one after the other. Here we proceed as follows:

The vector $v_{1}$ is represented as a linear combination of the vectors $\{e_{1},e_{2},e_{3}\}$.

${\begin{aligned}v_{1}={\begin{pmatrix}1\\1\\2\end{pmatrix}}=\beta _{1}\cdot {\begin{pmatrix}1\\0\\0\end{pmatrix}}+\beta _{2}\cdot {\begin{pmatrix}0\\1\\0\end{pmatrix}}+\beta _{3}\cdot {\begin{pmatrix}0\\0\\1\end{pmatrix}}=1\cdot {\begin{pmatrix}1\\0\\0\end{pmatrix}}+1\cdot {\begin{pmatrix}0\\1\\0\end{pmatrix}}+2\cdot {\begin{pmatrix}0\\0\\1\end{pmatrix}}=1\cdot e_{1}+1\cdot e_{2}+2\cdot e_{3}.\end{aligned}}$

According to the exchange lemma, we can exchange any basis vector $e_{i}$, since for every $1\leqslant i\leqslant 3$ the associated scalars are $\beta _{i}\neq 0$.

So, for example, if we exchange $e_{2}$ for $v_{1}$, then we get that $\{e_{1},v_{1},e_{3}\}$ is a basis of $\mathbb {R} ^{3}$. We now repeat the above procedure for $v_{2}$ with the basis $\{e_{1},v_{1},e_{3}\}$. ${\begin{aligned}v_{2}={\begin{pmatrix}0\\1\\1\end{pmatrix}}=(-1)\cdot {\begin{pmatrix}1\\0\\0\end{pmatrix}}+1\cdot {\begin{pmatrix}1\\1\\2\end{pmatrix}}+(-1)\cdot {\begin{pmatrix}0\\0\\1\end{pmatrix}}=(-1)\cdot e_{1}+1\cdot v_{1}+(-1)\cdot e_{3}.\end{aligned}}$

Again, we may exchange any of the vectors $\{e_{1},v_{1},e_{3}\}$, but exchanging $v_{1}$ is not purposeful, so we exchange $e_{3}$. Thus the vectors $\{e_{1},v_{1},v_{2}\}$ form a basis of $\mathbb {R} ^{3}$. So in total we have completed the linearly independent vectors $\{v_{1},v_{2}\}$ with $e_{1}$ to a basis of $\mathbb {R} ^{3}$.

Steinitz's exchange theorem

Theorem (Steinitz's theorem)

Let $B=\lbrace b_{1},\,\ldots ,b_{n}\rbrace$ be an $n$-element basis of the $K$-vector space $V$ and let $W=\lbrace w_{1},\ldots ,w_{k}\rbrace \subseteq V$ be a $k$-element set of linearly independent vectors. Then, we have that $k\leq n$ and there is a certain choice of $k$ vectors from the basis $B$ that can be replaced by the vectors $w_{1},\ldots ,w_{k}$ such that the replacement results in a new basis $B^{*}$ of the $K$-vector space $V$.

More precisely, after renumbering the indices (if necessary) we can write

$B^{*}=\lbrace w_{1},\ldots ,w_{k},\,b_{k+1},\ldots ,b_{n}\rbrace$

Proof (Steinitz's theorem)

We prove the theorem by induction over k.

Proof step: Induction base $k=1$

Let $\lbrace b_{1},\ldots ,b_{n}\rbrace$ be a basis of $V$ and let $w_{1}$ be linearly independent, i.e. $w_{1}\neq 0$, then it follows with above exchange lemma, that $\lbrace b_{1},\ldots ,b_{m-1},w_{1},b_{m+1},\ldots ,b_{n}\rbrace$ for a given $m\in \lbrace 1,\ldots ,n\rbrace$ is a basis of $V$.

Now we rename $b_{1}$ to $b_{m}$. It then follows that $\lbrace w_{1},b_{2},\ldots ,b_{n}\rbrace$ is a basis. This is the base case of our induction.

Proof step: Induction step $k\rightarrow k+1$

Let $\lbrace w_{1},\ldots ,w_{k},w_{k+1}\rbrace$ be linearly independent. By the induction assumption, we have that $k\leq n$, from which we want to infer $k+1\leq n$. Suppose there was $n<k+1$. Then since $k\leq n$ and $n\leq k$ we have that $k=n$. As $\lbrace w_{1},\ldots ,w_{k}\rbrace$ is linearly independent and $k=n$, we can replace $b_{1},\ldots ,b_{n}$ with $w_{1},\ldots ,w_{k}$ by induction assumption. So we get that $w_{1},\ldots ,w_{k}\rbrace$ is a basis of $V$.

We can also represent $w_{k+1}$ as a linear combination in $\lbrace w_{1},\ldots ,w_{k}\rbrace$. Let $\lambda _{1},\ldots ,\lambda _{k}\in K$, with $w_{k+1}=\sum _{i=1}^{k}\lambda _{i}w_{i}$. Then we have:

$\sum _{i=1}^{k}\lambda _{i}w_{i}+(-1)w_{k+1}=0$

But this is a contradiction to the linear independence of $\lbrace w_{1},\ldots ,w_{k+1}\rbrace$. So $k+1\leq n$ must also hold true.

It remains to show that after any renaming of $b_{1},\ldots ,b_{n}$

$\lbrace w_{1},\ldots ,w_{k+1},b_{k+2},\ldots ,b_{n}\rbrace$

is a basis of $V$. By induction assumption, $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{n}\rbrace$ is a basis of $V$. In this case, the indices of $b_{1},\ldots ,b_{n}$ may have been interchanged. We write $w_{k+1}$ as a linear combination of $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{n}\rbrace$.

Let for this $\lambda _{1},\ldots ,\lambda _{n}\in K$, with $w_{k+1}=\sum _{i=1}^{k}\lambda _{i}w_{i}+\sum _{j=k+1}^{n}\lambda _{j}b_{j}$. Note that these are not necessarily the same $\lambda _{i}$ as before. Suppose there was $\lambda _{j}=0$ for all $j\in \lbrace k+1,\ldots ,n\rbrace$. Then

$\sum _{i=1}^{k}\lambda _{i}w_{i}+(-1)w_{k+1}=0$

would hold, which would be a contradiction to the linear independence of $\lbrace w_{1},\ldots ,w_{k+1}\rbrace$ . So, let $j\in \lbrace k+1,\ldots ,n\rbrace$ with $\lambda _{j}\neq 0$. By the exchange lemma, $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{j-1},w_{k+1},b_{j+1},\ldots ,b_{n}\rbrace$ is a basis of $V$.

Finally, we rename $b_{k+1}$ to $b_{j}$. Then $\lbrace w_{1},\ldots ,w_{k+1},b_{k+2},\ldots ,b_{n}\rbrace$ is a basis of $V$, which concludes the proof.