5.2 Der Gauß-Algorithmus
5.2.1 Elementare Zeilenumformungen
Die Standardmethode, um die Lösungsmenge eines linearen Gleichungssystems zu bestimmen, ist der Gauß-Algorithmus. Das Ziel des Algorithmus ist es, ein gegebenes lineares Gleichungssystem durch Äquivalenzumformungen auf ein lineares Gleichungssystem möglichst einfacher Gestalt zu bringen, das dieselbe Lösungsmenge hat wie das ursprüngliche lineare Gleichungssystem.
Um das Ziel zu illustrieren, hier zwei Beispiele.
Am einfachsten ist der Fall, dass die Koeffizientenmatrix des Gleichungssystems die Einheitsmatrix \(E_n\) ist (Einsen auf der Diagonale, Nullen überall sonst). Die Lösungsmenge des Gleichungssystems mit erweiterter Koeffizientenmatrix \((E_n \mid b)\) ist \(\{ b\} \).
Eine ganz so einfache Form wie in Teil (1) werden wir nicht immer erreichen können (jedenfalls kann das ja nur für eindeutig lösbare Gleichungssysteme die richtige Lösungsmenge geben).
Betrachten wir als weiteres Beispiel das Gleichungssystem mit erweiterter Koeffizientenmatrix (mit Elementen \(a\) und \(b_i\) im fixierten Körper \(K\))
\[ \left( \begin{array}{ccc|c} 1 & a & 0 & b_1 \\ 0 & 0 & 1 & b_2 \\ 0 & 0 & 0 & b_3 \end{array} \right). \]In diesem Fall ist es immer noch einfach, die Lösungsmenge abzulesen. Ist \(b_3\ne 0\), so ist die Lösungsmenge leer.
Sei nun \(b_3=0\). Die dritte Zeile besteht dann sämtlich aus Nullen und ist als Gleichung gesehen die Gleichung \(0=0\), die immer erfüllt ist. Die zweite Zeile besagt dann als Gleichung ausgeschrieben, dass \(x_3=b_2\). Die erste Zeile beschreibt die Gleichung \(x_1 + ax_2 = b_1\), also \(x_1 = b_1-ax_2\). Das bedeutet, dass wir für jede Wahl von \(x_2\) in \(K\) den Lösungsvektor \((b_1-ax_2, x_2, b_2)^t\) erhalten, und alle Lösungsvektoren entstehen auf diese Art und Weise. Die Lösungsmenge ist
\[ \{ (b_1-ax_2, x_2, b_2)^t;\ x_2\in K\} . \]Auch in diesem Fall braucht man also nicht weiter zu rechnen, sondern kann die Lösungsmenge aus der erweiterten Koeffizientenmatrix direkt ablesen. Das streben wir auch im allgemeinen Fall an.
Wir beginnen nun damit, die Umformungen zu beschreiben, die wir erlauben werden, um das gegebene lineare Gleichungssystem zu verändern. Danach überlegen wir uns, dass diese Umformungen die Lösungsmenge nicht verändern.
Gegeben ein lineares Gleichungssystem, so nennen wir die folgenden Umformungen elementare Zeilenumformungen vom Typ I, II bzw. III:
(I) Addition eines Vielfachen (mit \(a\in K\)) einer Gleichung zu einer anderen Gleichung.
(II) Vertauschung zweier Gleichungen.
(III) Multiplikation einer Gleichung mit einem Skalar \(a\in K^\times \).
In (I) kann man natürlich statt von der Addition des \(a\)-fachen auch von der Subtraktion des \((-a)\)-fachen sprechen.
Betrachten Sie das folgende lineare Gleichungssystem über \(\mathbb Q\):
Wir führen eine Zeilenumformung vom Typ I durch und zwar addieren wir das \(2\)-fache der ersten Zeile zur zweiten Zeile. Wir erhalten das Gleichungssystem
Analog haben wir den Begriff der elementaren Zeilenumformungen vom Typ I, II, III von Matrizen:
(I) Addition eines Vielfachen (mit \(a\in K\)) einer Zeile zu einer anderen Zeile.
(II) Vertauschung zweier Zeilen.
(III) Multiplikation einer Zeile mit einem Skalar \(a\in K^\times \) (d.h. jeder Eintrag der Zeile wird mit \(a\) multipliziert).
Das bedeutet, dass eine elementare Zeilenumformung eines linearen Gleichungssystem genau der gleichen elementaren Zeilenumformung der erweiterten Koeffizientenmatrix entspricht.
(Entsprechend kann man auch von elementaren Spaltenumformungen von Matrizen sprechen. Das wird aber für uns erst später in der Vorlesung eine Rolle spielen.)
Wir benutzen für diese Zeilenumformungen die folgende Notation:
Addition des \(a\)-fachen von Zeile \(j\) zu Zeile \(i\ne j\): \(Z_i\rightsquigarrow Z_i+aZ_j\),
Vertauschen der Zeilen \(i\) und \(j\): \(Z_i \leftrightsquigarrow Z_j\),
Multiplizieren von Zeile \(i\) mit \(a\in K\), \(a\ne 0\): \(Z_i\rightsquigarrow aZ_i\).
Wenn ein lineares Gleichungssystem (oder analog eine Matrix) aus einer anderen Matrix durch eine elementare Zeilenumformung entsteht, dann kann man das ursprüngliche lineare Gleichungssystem (bzw. die ursprüngliche Matrix) durch eine elementare Zeilenumformung wieder zurückerhalten. Wir sagen deshalb, dass elementare Zeilenumformungen umkehrbar sind. In der Tat, entsteht \(A^\prime \) aus \(A\) durch Addition des \(a\)-fachen von Zeile \(j\) zu Zeile \(i\), so entsteht \(A\) aus \(A^\prime \) durch Addition des \((-a)\)-fachen von Zeile \(j\) zu Zeile \(i\). Entsteht \(A^\prime \) aus \(A\) durch Vertauschen der Zeilen \(i\) und \(j\), so entsteht auch \(A\) aus \(A^\prime \) durch Vertauschen dieser Zeilen. Entsteht schließlich \(A^\prime \) aus \(A\) durch Multiplikation der \(i\)-ten Zeile mit \(a\ne 0\), so entsteht \(A\) aus \(A^\prime \) durch Multiplikation der \(i\)-ten Zeile mit \(a^{-1}\). (Hier ist es wichtig, dass wir für Typ (III) nur Elemente \(\ne 0\) in \(K\) als Faktoren erlauben.)
Zwei lineare Gleichungssysteme, die durch elementare Zeilenumformungen auseinander hervorgehen, haben dieselbe Lösungsmenge.
Sei \((A\mid b)\) die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems, und gehe das lineare Gleichungssystem mit erweiterter Koeffizientenmatrix \((A^\prime \mid b^\prime )\) daraus durch eine elementare Zeilenumformung hervor. Wegen der Umkehrbarkeit der Operationen genügt es zu zeigen, dass jede Lösung von \((A\mid b)\) auch eine Lösung von \((A^\prime \mid b^\prime )\) ist. Das ist offensichtlich für Umformungen vom Typ (II) und (III). Für Zeilenumformungen vom Typ (I), etwa \(Z_i\rightsquigarrow Z_i+aZ_j\), haben wir für ein Element \(x=(x_1,\dots , x_n)^t\) der Lösungsmenge des ursprünglichen Gleichungssystems die Ausgangssituation
und sehen, dass
das bedeutet, dass \(x\) auch die neu erhaltene Gleichung erfüllt. (Wie man an der Rechnung sieht und wie auch direkt einsichtig ist, ist es natürlich wichtig, die Zeilenumformungen immer auch in der ganz rechten Spalte der erweiterten Koeffizientenmatrix anzuwenden.)
5.2.2 Die Zeilenstufenform
Wir beschreiben als nächstes die spezielle Form von Matrizen, die wir mit dem Gauß-Algorithmus erreichen wollen. (Danach werden wir uns überlegen, dass man jede Matrix durch eine Folge von elementaren Zeilenumformungen auf diese Form bringen kann; das ist der eigentliche Gauß-Algorithmus.)
Sei \(A\) eine Matrix mit \(m\) Zeilen und \(n\) Spalten.
Wir sagen, die Matrix \(A\) habe Zeilenstufenform, wenn die folgenden Bedingungen erfüllt sind:
In jeder Zeile ist der erste Eintrag, der von Null verschieden ist, gleich \(1\). Diese erste Eins (von links gesehen), bezeichnen wir als die führende Eins der entsprechenden Zeile.
Alle Einträge in der Spalte einer führenden Eins, die unter der führenden Eins liegen, sind gleich Null.
Die führende Eins einer Zeile liegt rechts von der führenden Eins der darüberliegenden Zeile.
(Es ist in Teil (a) erlaubt, dass eine Zeile nur aus Nullen besteht. Wegen Teil (c) müssen dann aber auch alle darunterliegenden Zeilen sämtlich aus Nullen bestehen. »Gleiche Höhe« ist in Bedingung (c) nicht ausreichend, die führende Eins einer Zeile darf nicht in derselben Spalte sein wie die der darüberliegenden Zeile.)
Wir sagen, die Matrix \(A\) habe reduzierte Zeilenstufenform, wenn sie Zeilenstufenform hat und zusätzlich alle Einträge in einer Spalte einer führenden Eins, abgesehen von der führenden Eins selbst, gleich Null sind (also auch die Einträge über der führenden Eins).
Schematisch dargestellt bedeutet Zeilenstufenform, dass die Matrix die folgende Gestalt hat:
![\begin{tikzpicture}
\tikzstyle{matrx}=[rectangle, thick, minimum size=.5cm, draw=white, fill=gray!20]
\matrix[left delimiter={(},right delimiter={)}]{
\node{\phantom{.}}; &&& \node[matrx]{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};& \node{\ast}; \\
\node{\phantom{.}}; &&&& && \node[matrx]{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&&&&&&& & & \node[matrx]{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&&&&&&& & & & \node[matrx]{$1$}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &\\
\node{\phantom{.}}; & \\
\node{\phantom{.}}; & \\
};
\draw (-2.45,1)--(-2.45,1.6);
\draw (-1.07, .45)--(-1.07, 1);
\draw (.79, -.1)--(.79, .45);
\draw (1.32, -.65)--(1.32, -.1);
\draw (-2.45,1)--(-1.07, 1);
\draw (.79,.45)--(-1.07, .45);
\draw (.79, -.1)--(1.32, -.1);
\draw (1.32, -.65)--(2.7, -.65);
\end{tikzpicture}](images/img-0013.svg)
Hier sind die »Stufen« eingezeichnet. Die führenden Einsen sind grau hinterlegt. An den mit Sternchen \(\ast \) markierten Stellen dürfen beliebige Elemente von \(K\) stehen (selbstverständlich auch \(0\) und \(1\)). Im leeren Bereich unten links stehen nur Nullen.
In der reduzierten Zeilenstufenform wird zusätzlich gefordert, dass über den führenden Einsen nur Nullen stehen:
![\begin{tikzpicture}
\tikzstyle{matrx}=[rectangle, thick, minimum size=.5cm, draw=white, fill=gray!20]
\matrix[left delimiter={(},right delimiter={)}]{
\node{\phantom{.}}; &&& \node[matrx]{$1$}; & \node{\ast}; & \node{\ast}; & \node{}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{}; & \node{}; & \node{\ast};& \node{\ast}; \\
\node{\phantom{.}}; &&&& && \node[matrx]{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{};& \node{}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&&&&&&& & & \node[matrx]{$1$}; & \node{}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&&&&&&& & & & \node[matrx]{$1$}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &\\
\node{\phantom{.}}; & \\
\node{\phantom{.}}; & \\
};
\draw (-2.45,1)--(-2.45,1.6);
\draw (-1.07, .45)--(-1.07, 1);
\draw (.79, -.1)--(.79, .45);
\draw (1.32, -.65)--(1.32, -.1);
\draw (-2.45,1)--(-1.07, 1);
\draw (.79,.45)--(-1.07, .45);
\draw (.79, -.1)--(1.32, -.1);
\draw (1.32, -.65)--(2.7, -.65);
\end{tikzpicture}](images/img-0014.svg)
Über anderen, »nicht-führenden« Einsen (an den Sternchen-Stellen) müssen natürlich nicht unbedingt Nullen stehen.
Wir erklären zuerst, wie sich eine Matrix \(A\) in Zeilenstufenform überführen lässt. Dazu führen wir Induktion nach Anzahl der Zeilen. Der Induktionsanfang (wahlweise für \(0\) Zeilen oder eine Zeile) ist klar.
Bringe nun eine der Zeilen, die mit einer minimalen Anzahl von Nullen beginnen, durch eine Zeilenvertauschung in die erste Zeile. Sei \(a\) der erste von Null verschiedene Eintrag der neuen ersten Zeile; er liege in Spalte \(j\). Multipliziere die erste Zeile mit \(a^{-1}\), so dass also der erste von Null verschiedene Eintrag der neuen ersten Zeile gleich \(1\) ist:
![\begin{tikzpicture}
\tikzstyle{matrx}=[rectangle, thick, minimum size=.5cm, draw=white, fill=gray!20]
\matrix[left delimiter={(},right delimiter={)}]{
\node{\phantom{.}}; &&& \node{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
};
\end{tikzpicture}](images/img-0015.svg)
Durch dieses Vorgehen sind alle Einträge in Spalten mit Index \({\lt} j\) gleich Null. Gibt es in den Zeilen \(2, 3, \dots \) in der \(j\)-ten Spalte Einträge \(\ne 0\), so ziehe nun geeignete Vielfache der ersten Zeile von diesen Zeilen ab, um eine Matrix zu erhalten, in denen die \(1\) in der ersten Zeile der einzige Eintrag in Spalte \(j\) ist, der von Null verschieden ist. Bezeichne die Matrix, die wir so erhalten, mit \(A^\prime \):
![\begin{tikzpicture}
\tikzstyle{matrx}=[rectangle, thick, minimum size=.5cm, draw=white, fill=gray!20]
\matrix[left delimiter={(},right delimiter={)}]{
\node{\phantom{.}}; &&& \node{$1$}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
\node{\phantom{.}}; &&& \node{}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast}; & \node{\ast};\\
};
\end{tikzpicture}](images/img-0016.svg)
Nach Induktionsvoraussetzung wissen wir bereits, dass wir die Matrix, die durch die Zeilen \(2, 3,\dots , m\) von \(A^\prime \) gegeben ist, durch elementare Zeilenumformungen in Zeilenstufenform bringen können. Wenn wir dieselben Umformungen auf die Matrix \(A^\prime \) anwenden (und die erste Zeile von \(A^\prime \) unverändert lassen), erhalten wir eine Matrix in Zeilenstufenform.
Es bleibt nun nur noch zu zeigen, dass sich eine Matrix in Zeilenstufenform durch elementare Zeilenumformungen in reduzierte Zeilenstufenform überführen lässt. Das können wir aber offensichtlich erreichen, indem wir jeweils geeignete Vielfache der Zeilen mit führenden Einsen von den Zeilen darüber abziehen.
Beispiele für die Durchführung des Gauß-Algorithmus.
Sei \(K=\mathbb Q\) und
\[ A = \left( \begin{array}{ccc} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{array} \right). \]Wir bringen \(A\) mit dem Gauß-Algorithmus zunächst auf Zeilenstufenform.
\begin{align*} & \left( \begin{array}{ccc} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{array} \right) \xrightarrow {Z_1 \leftrightsquigarrow Z_2} \left( \begin{array}{ccc} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 6 & 7 & 8 \end{array} \right) \xrightarrow {Z_1 \rightsquigarrow \frac13 Z_1} \left( \begin{array}{ccc} 1 & \frac43 & \frac53 \\ 0 & 1 & 2 \\ 6 & 7 & 8 \end{array} \right) \xrightarrow {Z_3 \rightsquigarrow Z_3 - 6Z_1}\\ & \left( \begin{array}{ccc} 1 & \frac43 & \frac53 \\ 0 & 1 & 2 \\ 0 & -1 & -2 \end{array} \right) \xrightarrow {Z_3 \rightsquigarrow Z_3 + Z_2} \left( \begin{array}{ccc} 1 & \frac43 & \frac53 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{array} \right) \end{align*}Schließlich können wir noch die reduzierte Zeilenstufenform herstellen:
\[ \left( \begin{array}{ccc} 1 & \frac43 & \frac53 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{array} \right) \xrightarrow {Z_1 \rightsquigarrow Z_1 - \frac43 Z_2} \left( \begin{array}{ccc} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{array} \right). \]Sei \(K=\mathbb C\), sei \(a\in \mathbb C\) eine fixierte Zahl und sei
\[ A = \left( \begin{array}{cc} a & i \\ i & 1 \end{array} \right). \]Wir wenden auf die Matrix \(A\) den Gauß-Algorithmus an. Da wir nicht wissen, ob \(a\ne 0\) ist, beginnen wir damit, die Zeilen zu vertauschen.
\[ \left( \begin{array}{cc} a & i \\ i & 1 \end{array} \right)\xrightarrow {Z_1 \leftrightsquigarrow Z_2} \left( \begin{array}{cc} i & 1\\ a & i \\ \end{array} \right)\xrightarrow {Z_1 \rightsquigarrow -iZ_1} \left( \begin{array}{cc} 1 & -i\\ a & i \\ \end{array} \right)\xrightarrow {Z_2 \rightsquigarrow Z_2 - aZ_1} \left( \begin{array}{cc} 1 & -i\\ 0 & (a+1)i \\ \end{array} \right). \]An dieser Stelle müssen wir eine Fallunterscheidung machen. Ist \(a=-1\), so hat \(A\) die reduzierte Zeilenstufenform
\[ \left( \begin{array}{cc} 1 & -i\\ 0 & 0 \\ \end{array} \right). \]Ist \(a\ne -1\), so können wir die zweite Zeile durch \((a+1)i\) teilen und das \(i\)-fache der neuen zweiten Zeile zur ersten Zeile addieren. In diesem Fall hat \(A\) als reduzierte Zeilenstufenform die Einheitsmatrix \(E_2\).
Wir sehen im ersten Beispiel, dass eine Matrix in aller Regel keine eindeutig bestimmte Zeilenstufenform hat (die Matrix, die wir durch die ersten Umformungen erhalten hatten, hat ja Zeilenstufenform, genau wie die Matrix in reduzierter Zeilenstufenform, die beiden Matrizen unterscheiden sich aber). Der folgende Satz sagt aber, dass die »Form«, d.h. die Anzahl und Position der Stufen bzw. der führenden Einsen für alle Matrizen in Zeilenstufenform, die man aus einer Matrix \(A\) durch elementare Zeilenumformungen erhalten kann, die gleiche ist. Und es gibt sogar nur eine einzige Matrix in reduzierter Zeilenstufenform, die man aus einer Matrix \(A\) so erhalten kann.
Sei \(A \in M_{m\times n}(K)\) eine Matrix.
Alle Matrizen in Zeilenstufenform, die man aus \(A\) durch elementare Zeilenumformungen erhalten kann, haben dieselbe Anzahl an führenden Einsen und haben die führenden Einsen in denselben Spalten.
Es gibt genau eine Matrix in reduzierter Zeilenstufenform, die aus \(A\) durch elementare Zeilenumformungen hervorgeht. Wir nennen diese auch die reduzierte Zeilenstufenform von \(A\).
Wir betrachten \(A\) als die Koeffizientenmatrix eines homogenen linearen Gleichungssystems. Da wir bereits wissen (Lemma 5.12), dass elementare Zeilenumformungen die Lösungsmenge nicht ändern, genügt es zu zeigen, dass die Anzahl und Position der führenden Einsen in einer Matrix in Zeilenstufenform durch die Lösungsmenge des zugehörigen homogenen Gleichungssystems eindeutig bestimmt ist. Und entsprechend für Teil (2), dass eine Matrix in reduzierter Zeilenstufenform durch die Lösungsmenge des zugehörigen homogenen linearen Gleichungssystems eindeutig bestimmt ist.
zu (1). Sei \(\mathbb L\) die Lösungsmenge des durch \(A\) gegebenen homogenen linearen Gleichungssystems. Sei \(A^\prime \) eine Matrix in Zeilenstufenform, die aus \(A\) durch elementare Zeilenumformungen entsteht.
Wir zeigen durch Induktion nach der Anzahl der Spalten von \(A\), dass wir die Anzahl und Positionen der führenden Einsen in \(A^\prime \) an \(\mathbb L\) ablesen können. Wenn \(A\) nur eine Spalte hat, dann ist \(A^\prime \) die Nullmatrix (wenn \(A\) selbst die Nullmatrix ist, also genau dann, wenn \(\mathbb L=K\)) oder die Matrix \((1, 0, \dots , 0)^t\) (in allen anderen Fällen, also genau dann, wenn \(\mathbb L=\{ 0\} \)). In diesem Fall ist die Zeilenstufenform eindeutig bestimmt.
Nun sei die Anzahl \(n\) der Spalten \({\gt}1\). Wir können die Induktionsvoraussetzung anwenden: Für jede Matrix in Zeilenstufenform sind auch die ersten \(n-1\) Spalten in Zeilenstufenform, und elementare Zeilenumformungen verändern jede Spalte für sich, unabhängig von den anderen Spalten. Wir erhalten die Lösungsmenge des durch die ersten \(n-1\) Spalten gegebenen homogenen Gleichungssystems als
diese ist also durch \(\mathbb L\) eindeutig bestimmt. Es folgt per Induktion, dass die Anzahl und Lage der führenden Einsen in den ersten \(n-1\) Spalten durch \(\mathbb L\) eindeutig bestimmt ist.
Schließlich enthält die letzte Spalte genau dann eine führende \(1\), wenn der \(n\)-te Eintrag in allen Elementen der Lösungsmenge \(=0\) ist.
zu (2). Den Beweis von Teil (2) erläutern wir hier nur an einem Beispiel, das das Prinzip erklärt. Damit könnten Sie den Beweis auch an dieser Stelle schon in der allgemeinen Situation ausarbeiten. Wir verschieben das im Skript auf etwas später, weil es mit dem Produkt von Matrizen einfacher (und durchsichtiger) möglich sein wird, siehe Satz 5.59. Betrachten wir als Beispiel die Matrix
in reduzierter Zeilenstufenform. Wir wissen aus Teil (1) bereits, dass die Anzahl und Lage der Stufen bzw. der führenden Einsen durch die Lösungsmenge \(\mathbb L\) des homogenen Gleichungssystems dazu eindeutig bestimmt sind. Es geht nun noch darum, die Koeffizienten \(a\), …, \(f\) durch \(\mathbb L\) auszudrücken. Dafür können wir sagen, dass das einzige Element von \(\mathbb L\) von der Form \((*, *, 1, 0, 0)^t\) (wobei die Sternchen wie üblich beliebige Elemente aus dem Grundkörper bezeichnen) der Vektor \((-a, -d, 1, 0, 0)^t\) ist. Genauso ist \((-b, -e, 0,1,0)^t\) der einzige Vektor in \(\mathbb L\), dessen letzte drei Einträge \(0,1,0\) sind, und \((-c, -f, 0,0,1)^t\) der einzige Vektor in \(\mathbb L\), dessen letzte drei Einträge \(0,0,1\) sind. Wir können also alle Einträge der Matrix in \(\mathbb L\) »wiederfinden«.
Sei \((A\mid b)\) die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems mit \(m\) Gleichungen und \(n\) Unbestimmten. Wir setzen voraus, dass die Matrix \(A\) Zeilenstufenform hat.
Wenn es ein \(i\) gibt, so dass die \(i\)-te Zeile von \(A\) eine Nullzeile, aber die \(i\)-te Zeile von \((A\mid b)\) keine Nullzeile ist, dann ist die Lösungsmenge leer. Hat sogar \((A\mid b)\) Zeilenstufenform, dann können wir die Bedingung formulieren als: die letzte Spalte von \((A\mid b)\) enthält eine führende Eins.
Nun gelte, dass in den Matrizen \(A\) und \((A\mid b)\) genau dieselben Zeilen Nullzeilen sind. Dann ist die Lösungsmenge nicht leer. Wir benennen die Spalten von \(A\), die eine führende Eins enthalten, mit \(1 \le j_1 {\lt} \cdots {\lt} j_r \le n\). Dann besteht die Lösungsmenge aus den folgenden Elementen von \(K^n\): Jede Wahl von Elementen \(x_j\in K\), \(j\not \in \{ j_1, \dots , j_r \} \) lässt sich durch die Vorschrift
\[ x_{j_i} = b_i-\sum _{j {\gt} j_i} a_{i j} x_j,\qquad i=1, \dots , r \]zu einem Lösungsvektor ergänzen, und auf diese Art und Weise erhält man alle Lösungsvektoren.
(Wenn \(A\) sogar reduzierte Zeilenstufenform hat, dann treten auf den rechten Seiten dieser Gleichungen nur \(x_j\) mit \(j\not \in \{ j_1, \dots , j_r \} \) auf (die anderen \(a_{ij}\) sind Null). Sonst muss man die \(x_{j_i}\) beginnend mit \(x_{j_r}\) bestimmen und sich dann Schritt für Schritt zu \(x_{j_1}\) vorarbeiten.)
zu (1). Wenn die angegebene Bedingung erfüllt ist, dann hat die \(i\)-te Gleichung die Form \(0 = b_i\) mit \(b_i\ne 0\) und ist daher nicht erfüllbar.
zu (2). Bei der oben angegebenen Darstellung für \(x_{j_i}\) (\(i=1, \dots , r\)) handelt es sich einfach um eine äquivalente Formulierung der \(i\)-ten Gleichung des Systems, \(i=1, \dots , r\). Die Zeilen nach der \(r\)-ten Zeile sind Nullzeilen, die als Gleichung einfach \(0=0\) aussagen – das ist immer erfüllt.
Daher beschreibt der Satz genau die Bedingungen, die ein Lösungsvektor erfüllen muss.
Schauen Sie sich auch die folgenden Beispiele an, die das etwas konkreter machen.
Sei \(K=\mathbb Q\) und
\[ A = \left( \begin{array}{ccc} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{array} \right). \]Wir haben in Beispiel 5.16 (1) gesehen, dass \(A\) die Zeilenstufenform
\[ \left( \begin{array}{ccc} 1 & \frac43 & \frac53 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{array} \right) \]hat. Daran können wir die Lösungsmenge des durch \(A\) gegebenen homogenen Gleichungssystems ablesen als
\[ \mathbb L = \left\{ \left( \begin{array}{c} z \\ -2z \\ z \end{array} \right);\ z\in \mathbb Q\right\} , \]denn \(-\frac43 \cdot (-2z) - \frac53 z = z\). Statt diese Rechnung an dieser Stelle zu machen, kann man auch die Matrix auf die reduzierte Zeilenstufenform
\[ \left( \begin{array}{ccc} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{array} \right). \]bringen und dann die Lösungsmenge noch direkter ablesen. Das Ergebnis ist natürlich dasselbe.
Sei \(K\) irgendein Körper und seien \(a,b,c, d, e\in K\). Wir betrachten die erweiterte Koeffizientenmatrix
\[ \left( \begin{array}{cccc|c} 1 & a & 0 & b & c \\ 0 & 0 & 1 & d & e \\ 0 & 0 & 0 & 0 & 0 \end{array} \right) \]in reduzierter Zeilenstufenform. Die Lösungsmenge des zugehörigen linearen Gleichungssystems ist
\[ \mathbb L = \left\{ \left( \begin{array}{c} c-ax -bx^\prime \\ x\\ e-d x^{\prime }\\ x^\prime \end{array} \right);\ x, x^\prime \in K \right\} \]Eine etwas andere Art, die Elemente der Lösungsmenge zu notieren, ist die folgende:
\[ \mathbb L = \left\{ \left( \begin{array}{c} c\\ 0\\ e\\ 0 \end{array} \right) +x \left( \begin{array}{r} -a \\ 1\\ 0\\ 0 \end{array} \right) + x^\prime \left( \begin{array}{r} -b\\ 0\\ -d\\ 1 \end{array} \right) ; x, x^\prime \in K \right\} \]Damit sehen wir auch direkt die Darstellung von \(\mathbb L\) in der Form \(t+\mathbb L_0\), wobei \(\mathbb L_0\) die Lösungsmenge des zugehörigen homogenen Systems ist:
\[ \mathbb L = \left( \begin{array}{c} c\\ 0\\ e\\ 0 \end{array} \right) + \left\{ x\left( \begin{array}{r} -a \\ 1\\ 0\\ 0 \end{array} \right) + x^\prime \left( \begin{array}{r} -b\\ 0\\ -d\\ 1 \end{array} \right) ; x, x^\prime \in K \right\} \]
Sei \((A\mid b)\) die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems. Wenn man in \(A\) Spalten vertauscht, entspricht das in Termen des Gleichungssystems einfach einem Umsortieren der Unbestimmten. Da alle Zeilenumformungen separat auf jede einzelne Spalte wirken, ist es zulässig, zunächst eine Spaltenvertauschung von \(A\) vorzunehmen, dann den Gauß-Algorithmus anzuwenden, und dann in der so erhaltenen Matrix die umgekehrte Spaltenumformung durchzuführen, und am Ergebnis die Lösungsmenge abzulesen. Allerdings muss man dabei besonders gut aufpassen, dass keine Flüchtigkeitsfehler passieren (zum Beispiel vergisst man leicht, am Ende wieder zurückzutauschen). Die letzte Spalte von \((A\mid b)\) spielt selbstverständlich eine Sonderrolle und darf nicht mitvertauscht werden.
Bei den Gleichungssystemen, die Sie »per Hand« lösen müssen, sollte es nicht erforderlich sein, Spalten zu vertauschen. In der Praxis, bei der Berechnung der Lösungsmengen von Gleichungssystemen mit »vielen« Gleichungen und Unbestimmten mit einem Computerprogramm, wo auch Rundungsfehler ein Problem darstellen können, kann das aber sinnvoll sein (so wie es dann auch wichtiger ist, die Zeilenumformungen geschickt zu wählen).
Wir fassen unsere Ergebnisse noch einmal zusammen:
Sei \((A\mid b)\) die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems. Sei \((A^\prime \mid b^\prime )\) eine Matrix in Zeilenstufenform, die aus \((A\mid b)\) durch elementare Zeilenumformungen entsteht.
Es sind äquivalent:
Das durch \((A\mid b)\) gegebene lineare Gleichungssystem besitzt eine Lösung.
Die Matrizen \(A^\prime \) und \((A^\prime |b^\prime )\) haben gleich viele Stufen.
Es sind äquivalent:
Das durch \((A\mid b)\) gegebene lineare Gleichungssystem besitzt eine eindeutige Lösung.
Die Matrix \(A^\prime \) hat in jeder Spalte eine Stufe, und für jede Nullzeile in \(A^\prime \) ist der entsprechende Eintrag in \(b^\prime \) ebenfalls gleich \(0\).
Sei nun in der obigen Situation \(A\) eine quadratische Matrix. Dann sind äquivalent:
Das durch \((A\mid b)\) gegebene lineare Gleichungssystem besitzt eine eindeutige Lösung.
Für die Matrix \(A^\prime = (a_{ij}^\prime )_{i,j}\) gilt \(a_{ii}=1\) für alle \(i\), d.h. die Diagonaleinträge sind alle \(=1\), und \(a_{ij} = 0\) für alle \(i{\gt}j\), d.h. die »Einträge unterhalb der Diagonale« sind alle gleich Null.
Insbesondere ist diese Eigenschaft unabhängig von \(b\).
Hat in dieser Situation \(A^\prime \) sogar reduzierte Zeilenstufenform, dann beschreibt \((A\mid b)\) ein eindeutig lösbares lineares Gleichungssystem genau dann, wenn \(A^\prime \) die Einheitsmatrix ist.
Vorbemerkung: Wenn \((A^\prime \mid b^\prime )\) durch elementare Zeilenumformungen aus \((A\mid b)\) entsteht und (reduzierte) Zeilenstufenform hat, so entsteht auch \(A^\prime \) durch elementare Zeilenumformungen (nämlich durch genau dieselben Umformungen) aus \(A\) und hat (reduzierte) Zeilenstufenform.
zu (1). Das ist eine Umformulierung von Satz 5.18 (1).
zu (2). Dass das Gleichungssystem eindeutig lösbar ist, ist gleichbedeutend damit, dass es eine Lösung gibt, aber dass wir keine Elemente in \(K\) wie in Satz 5.18 (2) wählen können, denn sonst gäbe es mindestens zwei Lösungen. Das heißt genau, dass in jeder Spalte eine Stufe ist.
zu (3). Dies folgt aus Teil (2) mit der Bemerkung, dass eine quadratische Matrix in Zeilenstufenform genau dann in jeder Spalte eine Stufe hat, wenn es sich um eine Matrix mit der beschriebenen Form handelt. (Wir sprechen von einer »oberen Dreiecksmatrix« mit Einsen auf der Diagonale, siehe Abschnitt 5.3.2.)
Die Bemerkung am Ende ergibt sich daraus, dass die einzige quadratische Matrix in reduzierter Zeilenstufenform, die in jeder Spalte eine Stufe hat, die Einheitsmatrix ist.
Teil (2) zeigt, dass ein lineares Gleichungssystem mit erweiterter Koeffizientenmatrix \((A\mid b)\), \(A\in M_{m\times n}(K)\) mit \(m {\lt} n\) (mehr Unbestimmte als Gleichungen, man spricht auch von einem unterbestimmten linearen Gleichungssystem) nicht eindeutig lösbar sein kann. Dass in Teil (3) des Satzes die reduzierte Zeilenstufenform von \(A\) die Einheitsmatrix ist, ist eine Bedingung, die nicht von \(b\) abhängt. Wir können noch ein bisschen mehr zeigen:
Sei \(A\in M_n(K)\) eine quadratische Matrix. Dann sind äquivalent:
Für alle \(b\in K^n\) ist das durch \((A\mid b)\) gegebene Gleichungssystem eindeutig lösbar.
Für alle \(b\in K^n\) ist das durch \((A\mid b)\) gegebene Gleichungssystem lösbar.
Es existiert \(b\in K^n\), so dass das Gleichungssystem, das durch \((A\mid b)\) gegeben ist, eindeutig lösbar ist.
Die reduzierte Zeilenstufenform von \(A\) ist \(E_n\).
Es ist offensichtlich, dass (i) \(\Rightarrow \) (ii) gilt, und aus dem vorherigen Satz folgt (iii) \(\Rightarrow \) (iv) \(\Rightarrow \) (i). Es genügt daher, nun noch die Implikation (ii) \(\Rightarrow \) (iii) zu zeigen. Wir zeigen, dass aus (ii) die Aussage (iii) für \(b=0\) folgt. Wenn das durch \(A\) gegebene homogene lineare Gleichungssystem mehrere Lösungen hat, dann hat die reduzierte Zeilenstufenform \(A^\prime \) von \(A\) eine Nullzeile. Es ist dann klar, dass \(b^\prime \in K^n\) existiert, so dass das Gleichungssystem zu \((A^\prime \mid b^\prime )\) nicht lösbar ist – wir müssen nur einen Eintrag von \(b^\prime \) in einer Zeile, die in \(A^\prime \) eine Nullzeile ist, auf einen Wert \(\ne 0\) festsetzen.
Da \(A^\prime \) aus \(A\) durch elementare Zeilenumformungen entsteht, können wir auch \(A\) aus \(A^\prime \) durch elementare Zeilenumformungen erhalten. Wenden wir diese Zeilenumformungen auf die erweiterte Matrix \((A^\prime \mid b^\prime )\) an, so erhalten wir eine Matrix \((A\mid b)\) mit \(b\in K^n\), deren Gleichungssystem dieselbe Lösungsmenge hat wie das System \((A^\prime \mid b^\prime )\), also die leere Menge. Das zeigt, dass (ii) falsch ist, wenn (iii) nicht gilt, oder mit anderen Worten (ii) \(\Rightarrow \) (iii).
5.2.3 Teilräume von \(K^n\)
Um die Struktur der Lösungsmenge eines linearen Gleichungssystems noch besser beschreiben zu können (und um später die Frage zu beantworten, welche Teilmengen von \(K^n\) als Lösungsmenge eines linearen Gleichungssystemes auftreten können), machen wir die folgende Definition:
Die Teilmengen \(\{ 0\} \) und \(K^n\) sind Teilräume von \(K^n\). Den Teilraum \(\{ 0\} \) nennt man auch den Nullraum; manchmal bezeichnet man den Nullraum auch mit \(0\) (ohne Mengenklammern).
Die einzigen Teilräume von \(K^1=K\) sind \(0\) und \(K\). (Warum?)
Ist \(x\in K^n\), so ist die Menge \(\{ ax;\ a\in K\} \) ein Teilraum von \(K^n\). (Warum?)
Jede Gerade in \(\mathbb R^2\), die den Ursprung enthält, ist ein Teilraum (von der Form von Teil (3) dieses Beispiels). Wir werden sehen: Die Teilräume von \(\mathbb R^2\) sind \(\{ 0\} \), \(\mathbb R^2\) und die Geraden in \(\mathbb R^2\), die den Ursprung \((0,0)^t\) enthalten. Können Sie zeigen, dass es keine anderen gibt?
Die leere Menge \(\emptyset \) ist kein Teilraum. Die Teilmenge \(\{ (x, y);\ y = x^2 \} \) ist kein Teilraum von \(\mathbb R^2\), denn sie enthält \((1,1)^t\) und \((-1,1)^t\), aber nicht die Summe \((1,1)^t + (-1,1)^t = (0,2)^t\).
Die grüne Gerade im Bild rechts erfüllt keine der Bedingungen (a), (b), (c): Zum Beispiel ist (b) verletzt, weil sie \(p\) und \(p^\prime \) enthält, aber nicht die Summe \(p+p^\prime \). Finden Sie ein Beispiel, das zeigt, dass (c) ebenfalls nicht erfüllt ist.
![\begin{tikzpicture} [scale=0.9] \begin{axis} [axis x line=middle, axis y line=middle, xmin=-2.5, xmax=4.5, ymin=-2.5, ymax=3.5, xtick={-2, -1, ..., 4}, ytick={-2, -1, 1, 3}]
\draw [dotted] (0,0) – (2,1); \draw [dotted] (0,0) – (.5, 2); \draw [dotted] (.5, 2) – (2.5, 3); \draw [dotted] (2.5, 3) – (2,1);
\draw [green, thick] (-2.5, 4) – (5, -1);
\fill [red] (2, 1) circle[radius=.5mm] node[below right, black] {$p$}; \fill [red] (.5, 2) circle[radius=.5mm] node[above left, black] {$p^\prime $}; \fill [red] (2.5, 3) circle[radius=.5mm] node[below right, black] {$p+p^\prime $}; \end{axis}
\end{tikzpicture}](images/img-0017.svg)
Die (für den Moment) wichtigsten Beispiele für Teilräume liefert uns das folgende Lemma.
Sei \(U\subseteq K^n\) die Lösungsmenge eines homogenen linearen Gleichungssystems. Dann ist \(U\) ein Teilraum von \(K^n\).
Zunächst liegt sicher der Nullvektor in der Lösungsmenge jedes homogenen linearen Gleichungssystems: \(0\in U\). Sind \(v=(v_j)_j, w=(w_j)_j\in U\), erfüllen also \((v_1,\dots , v_n)\) und \((w_1, \dots , w_n)\) alle Gleichungen des gegebenen homogenen linearen Gleichungssystems, so gilt das auch für die Summe \((v_1+w_1, \dots , v_n+w_n)\). In der Tat, betrachten wir eine Gleichung der Form
so sehen wir
Ähnlich, aber noch einfacher, ist es zu zeigen, dass für jede Lösung \(v\) eines homogenen linearen Gleichungssystems und jedes Element \(a\in K\) auch \(av\) eine Lösung ist. Damit sind alle Eigenschaften gezeigt, die wir überprüfen müssen, um zu beweisen, dass \(U\) ein Teilraum von \(K^n\) ist.
Wir wollen diesen Abschnitt damit beenden, zwei Fragen zu formulieren, die sich an dieser Stelle stellen, die wir aber erst mit etwas mehr Theorie werden befriedigend beantworten können.
Ist jeder Teilraum von \(K^n\) die Lösungsmenge eines homogenen linearen Gleichungssystems? (Das ist in der Tat der Fall, siehe Satz 7.40.)
In Korollar 5.22 haben wir gesehen, dass für eine quadratische Matrix \(A\) die Eigenschaft, dass das Gleichungssystem \((A|0)\) eindeutig lösbar ist, dazu äquivalent ist, dass alle Gleichungssysteme \((A|b)\) lösbar sind.
Können wir diese Beziehung zwischen der Eindeutigkeit der Lösung und der Existenz von Lösungen verallgemeinern? Kann man zum Beispiel »quantifizieren«, wie viele Lösungen ein lineares Gleichungssystem \((A\mid 0)\) hat, auch wenn es nicht eindeutig lösbar ist, und das in Beziehung dazu setzen, für »wie viele« \(b\) das Gleichungssystem \((A\mid b)\) lösbar ist?
Weil wir (wenn \(K\) unendlich viele Elemente hat) darüber sprechen, dass unendlich viele Lösungen existieren, ist nicht klar, was man unter »quantifizieren« verstehen soll. Wir werden diese Frage in einer sehr schönen (und nützlichen) Art und Weise beantworten; siehe Abschnitt 7.4.