Austauschlemma und Austauschsatz von Steinitz – Serlo „Mathe für Nicht-Freaks“

Wir beweisen den Austauschssatz, um später die Wohldefiniertheit der Dimension zu zeigen.

Motivation

In diesem Artikel wollen wir das Austauschlemma und den Austauschssatz von Steinitz behandeln. Diese besagen, wie eine gegebene Basis eines Vektorraums in eine andere umgewandelt werden kann, indem man manche der alten Basisvektoren geschickt durch neue Vektorraumelemente ersetzt. Das ist vor allem dann hilfreich, wenn man eine Basis konstruieren möchte, die gewisse vorher überlegte Vektoren enthält. Eine weitere Aussage des Austauschsatzes ist die Tatsache, dass linear unabhängige Mengen allgemein höchstens so mächtig sind wie Basen. Dieses Resultat ist zum Beispiel für die Definition der Dimension eines Vektorraums wesentlich. Wir beweisen zunächst das Austauschlemma.

Austauschlemma

Das Austauschlemma

Satz (Austauschlemma)

Sei $V$ ein Vektorraum über einem Körper $K$ und $B=\left\{b_{1},\,b_{2},\,\ldots ,b_{n}\right\}$ eine Basis von $V$. Weiterhin sei $w\in V$ mit der Linearkombination $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$, wobei $\lambda _{1},\ldots ,\lambda _{n}\in K$. Ist $k\in \lbrace 1,\ldots ,n\rbrace$ derart, dass $\lambda _{k}\neq 0$, dann ist $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ ebenfalls eine Basis von $V$.

Beweis (Austauschlemma)

Sei $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ die Menge, in der $b_{k}$ mit $w$ ausgetauscht wurde. Wir müssen zeigen, dass auch die neue Menge $B'$ eine Basis ist. Dazu zeigen wir, dass $B'$ ein Erzeugendensystem von $V$ und linear unabhängig ist.

Beweisschritt: $B'$ ist ein Erzeugendensystem

Wir wissen $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$ mit $\lambda _{i}\in K$ und $b_{i}\in B$. Nach obiger Annahme ist $\lambda _{k}\neq 0$ und hat deshalb ein Inverses in $K$. Damit gilt folgende Umformung:

${\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}}$

Weil $B$ eine Basis von $V$ ist, gibt es für jeden Vektor $v\in V$ Skalare $\mu _{i}\in K$, sodass $v=\sum _{i=1}^{n}\mu _{i}b_{i}$ ist. Wir setzen nun für $b_{k}$ obiges Ergebnis ein und erhalten:

${\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}}$

Damit ist der Vektor $v$ dargestellt als Linearkombination von $B^{*}=\left\{b_{1},\,b_{2},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ und $B'$ ist ein Erzeugendensystem von $V$.

Beweisschritt: $B'$ ist linear unabhängig

Seien $\beta ,\mu _{1},\ldots ,\mu _{k-1},\mu _{k+1},\ldots ,\mu _{n}\in K$, sodass $\beta w+\sum _{i=1 \atop i\neq k}^{n}\mu _{i}b_{i}=0$. Wir ersetzen $w$ durch seine Darstellung als Linearkombination der Basiselemente $b_{i}$ und erhalten:

${\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}}$

Da $B=\lbrace b_{1},\cdots ,b_{n}\rbrace$ linear unabhängig ist, gilt $\beta \lambda _{k}=0$ und $\beta \lambda _{l}+\mu _{l}=0$ für alle $l\neq k$.

Aus $\beta \lambda _{k}=0$ und $\lambda _{k}\neq 0$ folgt $\beta =0$. Damit ist aber auch $\mu _{l}=0$ für alle $l\neq k$. Das bedeutet $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ ist linear unabhängig.

Hinweis

Es gilt auch (hier ohne Beweis) die Rückrichtung des Austauschlemmas:

Sei $V$ ein Vektorraum über einem Körper $K$ und $B=\left\{b_{1},\,b_{2},\,\ldots ,b_{n}\right\}$ eine Basis von $V$. Weiterhin sei $w\in V$ mit der Linearkombination $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$, wobei $\lambda _{1},\ldots ,\lambda _{n}\in K$. Ist $k\in \lbrace 1,\ldots ,n\rbrace$ derart, dass $B'=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ ebenfalls eine Basis von $V$ist, dann gilt bereits $\lambda _{k}\neq 0$.

Als nächstes beweisen wir eine leichte Abwandlung des Austauschlemmas. Sie zeigt, dass das Lemma "fast immer" anwendbar ist. Dabei setzen wir nämlich nur voraus, dass der neue Basisvektor $w$ nicht der Nullvektor ist:

Satz (Austauschlemma Version 2)

Sei $V$ ein Vektorraum über einem Körper $K$ und $B=\left\{b_{1},\,\ldots ,b_{n}\right\}$ eine Basis von $V$. Weiterhin sei $0\neq w\in V$. Dann gibt es einen Index $k\in \lbrace 1,\ldots ,n\rbrace$ derart, dass $B^{*}=\left\{b_{1},\,\ldots ,b_{k-1},\,w,\,b_{k+1},\,\ldots ,b_{n}\right\}$ ebenfalls eine Basis von $V$ ist.

Wir können damit $b_{k}$ gegen $w$ austauschen.

Beweis (Austauschlemma Version 2)

Wir schreiben $w$ als Linearkombination in $B$. Seien also $\lambda _{1}\,\ldots \,\lambda _{n}\in K$ mit $w=\sum _{i=1}^{n}\lambda _{i}b_{i}$.

Da $w\neq 0$ ist, muss mindestens einer der Skalare $\lambda _{1},\ldots ,\lambda _{n}$ ungleich Null sein. Wenn nämlich alle $\lambda _{k}=0$ wären, dann müsste auch $w=0$ sein. Also sei $k\in \{1,\ldots n\}$, so dass $\lambda _{k}\neq 0$. Mit diesem $k$ ist die Voraussetzung aus der oberen Version des Austauschlemmas erfüllt.

Anwendung des Austauschlemmas

Beispiel

Seien $E:=\{e_{1},e_{2},e_{3}\}$ die kanonische Basis des $\mathbb {R} ^{3}$ und $w:=(1,1,0)^{T}$ Wir zeigen, dass $\{w,e_{2},e_{3}\}$ eine Basis des $\mathbb {R} ^{3}$ ist. Gemäß dem Austauschlemma können wir den Vektor $e_{1}$ mit $w$ ersetzen, wenn die Linearkombination $w=\sum _{i=1}^{3}\lambda _{i}e_{i}$ gilt: $\lambda _{1}\neq 0$.

Wir erkennen, dass gilt: $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}}$

Somit folgt mit dem Austauschlema, dass $\{w,e_{2},e_{3}\}$ eine Basis des $\mathbb {R} ^{3}$ ist.

Wir sehen aber aus dieser Diskussion auch, dass wir mithilfe des Austauschlemmas nicht zeigen könne, dass $\{e_{1},e_{2},w\}$ eine Basis ist: In der Linearkombination von $w=\sum _{i=1}^{3}\lambda _{i}e_{i}$ ist $\lambda _{3}=0$. Deshalb kann man das Austauschlemma hier nicht anwenden.

Es gilt sogar, dass $\{e_{1},e_{2},w\}$ keine Basis des $\mathbb {R} ^{3}$ ist: $w=e_{1}+e_{2}$, also sind die Vektoren linear abhängig, insbesondere also keine Basis.

Beispiel (Basisergänzung durch Hereintauschen in eine bekannte Basis)

Wir wollen die beiden Vektoren $v_{1}=(1,1,2)^{T},\,v_{2}=(0,1,1)^{T}\in \mathbb {R} ^{3}$ zu einer Basis $\{v_{1},\,v_{2},\,v_{3}\}$ des $\mathbb {R} ^{3}$ ergänzen.

Zunächst sollten wir prüfen, ob die beiden Vektoren linear unabhängig sind, dies ist aber leicht einzusehen, denn für ${\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}}$

muss $\alpha _{1}=0$ sein, was dann bedeutet, dass auch $\alpha _{2}=0$ ist.

Wir wollen nun mit Hilfe des Austauschlemmas $v_{1},\,v_{2}$ gegen zwei Basisvektoren einer bekannten Basis des $\mathbb {R} ^{3}$ austauschen. Für den $\mathbb {R} ^{3}$ nehmen wir einfach die kanonische Basis $E=\lbrace e_{1}=(1,0,0)^{T},\,e_{2}=(0,1,0)^{T},\,e_{3}=(0,0,1)^{T}\rbrace$. Durch wiederholte Anwendung des Austauschlemmas werden die Vektoren nacheinander ausgetauscht. Dabei gehen wir folgendermaßen vor:

Der Vektor $v_{1}$ wird als Linearkombination der Vektoren $\{e_{1},e_{2},e_{3}\}$ dargestellt.

${\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}}$

Nach dem Austauslemma können wir irgendein Basiselement $e_{i}$ austauschen, da für jedes $1\leqslant i\leqslant 3$ die zugehörigen Skalare $\beta _{i}\neq 0$ sind.

Tauschen wir also etwa $e_{2}$ gegen $v_{1}$ aus, es ist nun also $\{e_{1},v_{1},e_{3}\}$ eine Basis des $\mathbb {R} ^{3}$. Wir wiederholen nun das obige Verfahren für $v_{2}$ mit der 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}}$

Auch hier können wir jeden der Vektoren $\{e_{1},v_{1},e_{3}\}$ austauschen, allerdings ist der Austausch von $v_{1}$ nicht zielführend, also tauschen wir etwa $e_{3}$ aus. Damit bilden die Vektoren $\{e_{1},v_{1},v_{2}\}$ eine Basis des $\mathbb {R} ^{3}$ und wir haben die linear unabhängigen Vektoren $\{v_{1},v_{2}\}$ mit $e_{1}$ zu einer Basis des $\mathbb {R} ^{3}$ ergänzt.

Austauschsatz von Steinitz

Satz (Austauschsatz von Steinitz)

Sei $B=\lbrace b_{1},\,\ldots ,b_{n}\rbrace$ eine $n$-elementige Basis des $K$-Vektorraums $V$ und sei $W=\lbrace w_{1},\ldots ,w_{k}\rbrace \subseteq V$ eine $k$-elementige Menge linear unabhängiger Vektoren. Dann gilt $k\leq n$ und man kann bestimmte $k$ Vektoren der Basis $B$, durch die Vektoren $w_{1},\ldots ,w_{k}$ ersetzen und erhält mit diesen Vektoren eine neue Basis $B^{*}$ des $K$-Vektorraums $V$.

Nach eventueller Umnummerierung der Indizes können wir schreiben

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

Beweis (Austauschsatz von Steinitz)

Wir beweisen den Satz durch vollständige Induktion nach k.

Beweisschritt: Induktionsanfang $k=1$

Sei $\lbrace b_{1},\ldots ,b_{n}\rbrace$ eine Basis von $V$ und sei $w_{1}$ linear unabhängig, also $w_{1}\neq 0$, dann folgt mit obigem Austauschlemma, dass $\lbrace b_{1},\ldots ,b_{m-1},w_{1},b_{m+1},\ldots ,b_{n}\rbrace$ für ein bestimmtes $m\in \lbrace 1,\ldots ,n\rbrace$ eine Basis von $V$ ist.

Jetzt benennen wir $b_{1}$ zu $b_{m}$ um. Es folgt dann, dass $\lbrace w_{1},b_{2},\ldots ,b_{n}\rbrace$ eine Basis ist. Das zeigt den Induktionsanfang.

Beweisschritt: Induktionsschritt $k\rightarrow k+1$

Seien $\lbrace w_{1},\ldots ,w_{k},w_{k+1}\rbrace$ linear unabhängig. Nach Induktionsvoraussetzung gilt $k\leq n$, woraus wir $k+1\leq n$ folgern wollen. Angenommen es wäre $n<k+1$. Dann folgt, wegen $k\leq n$ und $n\leq k$, dass $k=n$ gilt. Da $\lbrace w_{1},\ldots ,w_{k}\rbrace$ linear unabhängig ist und $k=n$, können wir nach Induktionsvoraussetzung $b_{1},\ldots ,b_{n}$ durch $w_{1},\ldots ,w_{k}$ ersetzen. Wir erhalten, dass $\lbrace w_{1},\ldots ,w_{k}\rbrace$ eine Basis von $V$ ist.

Wir können also $w_{k+1}$ als Linearkombination in $\lbrace w_{1},\ldots ,w_{k}\rbrace$ darstellen. Seien $\lambda _{1},\ldots ,\lambda _{k}\in K$, mit $w_{k+1}=\sum _{i=1}^{k}\lambda _{i}w_{i}$. Dann gilt:

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

Das ist aber ein Widerspruch zur linearen Unabhängigkeit von $\lbrace w_{1},\ldots ,w_{k+1}\rbrace$. Also muss auch $k+1\leq n$ gelten.

Es bleibt zu zeigen, dass nach eventueller Umbennenung der $b_{1},\ldots ,b_{n}$

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

eine Basis von $V$ ist. Nach Induktionsvoraussetzung ist $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{n}\rbrace$ eine Basis von $V$. Dabei wurden unter Umständen die Indizes der $b_{1},\ldots ,b_{n}$ vertauscht. Wir schreiben $w_{k+1}$ als Linearkombination in $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{n}\rbrace$.

Seien dafür $\lambda _{1},\ldots ,\lambda _{n}\in K$, mit $w_{k+1}=\sum _{i=1}^{k}\lambda _{i}w_{i}+\sum _{j=k+1}^{n}\lambda _{j}b_{j}$. Beachte dabei, dass dies nicht zwingend die gleichen $\lambda _{i}$ wie vorher sind. Angenommen es wäre $\lambda _{j}=0$ für alle $j\in \lbrace k+1,\ldots ,n\rbrace$. Dann würde

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

gelten, was der linearen Unabhängigkeit von $\lbrace w_{1},\ldots ,w_{k+1}\rbrace$ widersprechen würde. Sei also $j\in \lbrace k+1,\ldots ,n\rbrace$, mit $\lambda _{j}\neq 0$. Nach dem Austauschlemma ist $\lbrace w_{1},\ldots ,w_{k},b_{k+1},\ldots ,b_{j-1},w_{k+1},b_{j+1},\ldots ,b_{n}\rbrace$ eine Basis von $V$.

Schließlich benennen wir $b_{k+1}$ zu $b_{j}$ um. Dann ist $\lbrace w_{1},\ldots ,w_{k+1},b_{k+2},\ldots ,b_{n}\rbrace$ eine Basis von $V$, was den Beweis abschließt.