Ψ Die Informatikseite

Menü

Beweis des Austauschsatzes von Steinnitz

Der Beweis läuft mit Hilfe des Austauschlemmas. Das Austauschlemma nimmt einen Vektor aus der Basis und fügt einen anderen ein:
Austauschlemma
Geben ist ein $K-$Vektorraum $V$ mit der Basis

\begin{displaymath}B:=\{v_{1},\ldots,v_{r}\}\end{displaymath}

und ein $w$ mit

\begin{displaymath}w=\lambda_{1}v_{1}+\ldots+\lambda_{k-1}v_{k-1}+\underline{\un...
..._{r}v_{r}\in V\,\,\,mit\,\,\,\lambda_{k}\not=0\,\,\,\,\,(\star)\end{displaymath}

und

\begin{displaymath}\lambda_{k}\not=0.\end{displaymath}

So ist

\begin{displaymath}B':=\{v_{1},\ldots,v_{k-1},w,v_{k+1},\ldots,v_{r}\}\end{displaymath}

wieder eine Basis von $V$. Man kann also $v_{k}$ gegen $w$ austauschen. (Die anderen $\lambda_{1}\ldots\lambda_{r}$ ohne $\lambda_{k}$ müssen nicht unbedingt 0 sein, können es aber.)

Beweis des Austauschlemmas
  • Wir nehmen zur Vereinfachung der Schreibweise an, daß $k=1$ ist. Wir zeigen also, daß

    \begin{displaymath}B':=\{w,v_{2},\ldots,v_{r}\}\end{displaymath}

    auch eine Basis von $V_{K}$ ist.
  • Alle Vektoren $v\in V$ lassen sich als Linearkombination der Basis3.2 herstellen:

    \begin{displaymath}v=\mu_{1}v_{1}+\ldots+\mu_{r}v_{r}\,\,\,\,\,(\star\star)\end{displaymath}

  • Da $\lambda_{1}\not=0$ können wir wie folgt umformen

    \begin{displaymath}\begin {array}{ll}&w=\lambda_{1}v_{1}+\ldots+\lambda_{r}v_{r}...
..._{2}-\ldots-\frac{\lambda_{r}}{\lambda_{1}}v_{r}\\ \end {array}\end{displaymath}

  • Nun können wir dies in $\star\star$ einsetzen

    \begin{displaymath}\begin {array}{ll}
v&=\mu_{1}\left(\frac{w}{\lambda_{1}}-\fra...
...\mu_{1}\frac{\lambda_{r}}{\lambda_{1}}\right)v_{r}
\end {array}\end{displaymath}

    $\Rightarrow$ Die neue Basis ist zumindest ein Erzeugendensystem
  • Zu zeigen ist jetzt noch die lineare Unabhängigkeit

    \begin{displaymath}\mu w+\mu_{2}v_{2}+\ldots+\mu_{r}v_{r}=0\end{displaymath}

    Einsetzen von $\star$ :

    \begin{displaymath}\begin{array}{ll}&\mu(\lambda_{1}v_{1}+\lambda_{2}v_{2}+\ldot...
...{3})v_{3}+\ldots+(\mu\lambda_{r}+\mu_{r})v_{r}=0\\ \end {array}\end{displaymath}

    Also $\mu\lambda_{1}=\mu\lambda_{2}+\mu_{2}=\mu\lambda_{3}+\mu_{3}=\ldots=\mu\lambda_{r}+\mu_{r}=0$, da $B$ linear unabhängig war ( $\mu_{2}=\mu_{3}=\ldots=\mu_{r}=0$) und $\mu=0$, da $\lambda_{1}\not=0$.
    $\Rightarrow$ linear unabhängig
Beweis des Austauschsatzes
Nachdem wir nun bewiesen haben, dass man einen Vektor $v_{k}$ aus der Basis nehmen kann und gegen den Vektor $w$ tauschen kann, wenn das dazugehörige $\lambda_{k}\not=0$ ist (kann man durch Umnummerieren an die richtige Stelle stellen), müssen wir beweisen, das es tatsächlich immer ein $\lambda_{k}\not=0$ für einen Vektor der alten Basis gibt, so dass wir die Vektoren nacheinander austauschen können:
  • Wenn wir null Vektoren austauschen, haben wir nichts zu beweisen. Wir brauchen keinen Vektor zu finden, durch den wir einen Basisvektor austauschen. Dies ist unser Induktionsanfang.
  • Unsere Induktionsvoraussetzung ist, dass wir schon $k$ Vektoren ausgetauscht haben und wieder eine Basis erhalten haben:

    \begin{displaymath}B'=\{w_{1},\ldots,w_{k},v_{k+1},\ldots,v_{r}\}\end{displaymath}

  • Der Induktionsschluss:
    Wenn wir den Vektor $w_{k+1}$ austauschen, so müssen wir ein $\lambda_{i}$ mit $k+1\leq i\leq r$ finden, für welches gilt $\lambda_{i}\not=0$. Es gilt

    \begin{displaymath}\begin {array}{ll}w_{k+1}=\lambda_{1}w_{1}+\ldots+\lambda_{k}...
...{r}}\\
&\mbox{mindestens ein }\lambda_{i}\not=0\\ \end {array}\end{displaymath}

    Da die linear unabhängige Familie $(w_{1},\ldots,w_{k},w_{k+1},\ldots)$ linear unabhängig war, darf kein $\lambda_{1}=\ldots=\lambda_{k}\not=0$ sein, da sonst die lineare Unabhängigkeit verletzt würde. Da $w_{k+1}$ auch nicht Nullvektor, da wiederum die lineare Unabhängigkeit verletzt werden würde, gibt es ein $\lambda_{i}$ ( $k+1\leq i\leq r$) mit $\lambda_{i}=0$.
$\Box$