In dem zu besprechenden Verfahren werden aus den gegebenen Gleichungen neue so konstruiert, dass sich die Lösungsmenge dabei nicht ändert, symbolisch
\[L(G_1,\ldots,G_m)=L(G'_1,\ldots,G'_m).\] Dieser Prozess wird so lange wiederholt, bis man zu einem Gleichungssystem kommt, dem man die Lösungsmenge unmittelbar ansieht.
Hier sind drei elementare Umformungen, die die Lösungsmenge nicht verändern:
- Vertauschen der Reihenfolge der Gleichungen.
- Multiplikation einer Gleichung mit einer von Null verschiedenen Zahl $k\in K\setminus\{0\}$, also zum Beispiel
\[L(G_1,\ldots,G_m)=L(k G_1,\ldots,G_m).\] - Addition des $k$-fachen einer Gleichung zu einer anderen, zum Beispiel die Addition von $k G_2$ zu $G_1$
\[L(G_1,G_2,\ldots,G_m)=L(G_1+k G_2,G_2,\ldots,G_m).\]
Lösungen von linearen Gleichungen lösen offensichtlich auch die durch elementare Umformungen gewonnenen Gleichungen. Da elementare Umformungen rückgängig gemacht werden können, ändern sie die Lösungsmenge nicht.
Das gegebene Gleichungssystem wird nun schrittweise umgeformt. Wir konzentrieren uns zuerst auf die Koeffizienten $a_{j1}$ von $x_1$. Sind alle diese Koeffizienten gleich Null, so können wir beliebige Werte für $x_1$ einsetzen, ohne Auswirkungen auf etwaige restliche Koeffizienten einer Lösung. In diesem Fall brauchen wir $x_1$ nicht weiter betrachten. Andernfalls sei etwa $a_{j1}\not=0$. Wir setzen dann die Gleichung $G_j$ an die erste Stelle. Dann benutzen wir Umformung 2 um in der nun an erster Stelle stehenden Gleichung den Koeffizienten von $x_1$ zu $1$ zu machen und subtrahieren mittels Umformung 3 geeignete Vielfache der nunmehr an erster Stelle stehenden Gleichung von den folgenden, um dort jeweils den Koeffizienten von $x_1$ zu Null zu machen. Jetzt lassen wir die erste Gleichung in Ruhe und behandeln die weiteren Gleichungen nach demselben Verfahren, nun aber beginnend mit $x_2$, da ja $x_1$ eliminiert ist.
Schließlich langen wir bei einem Gleichungssystem an, in dem die letzte Gleichung entweder die Form \[x_j+a'_{m,j+1}x_{j+1}+\ldots +a'_{m,n}x_n=b'_m,\] für ein $j\leq n$ hat oder aber von der Form \[0=b'_m\] ist. Im letzteren Fall ist für $b'_m\not=0$ ein Widerspruch erreicht; es gibt also keine Lösung des Gleichungssystems. Im ersten Fall können wir $x_{j+1},\ldots,x_n$ beliebig vorgeben und dann $x_j$ durch die Gleichung ausrechnen. Nun steigen wir die Gleichungen von unten nach oben auf, setzen die schon festgelegten Werte der $x_i$ ein und rechnen das jeweils am Anfang stehende $x_l$ durch die restlichen aus, wobei gegebenenfalls vorher noch nicht festgelegte $x_r$ willkürlich gewählt werden dürfen.
An dieser Stelle ist ein Beispiel angebracht. Angenommen, das Endergebniss der elementaren Umformungen sei das System
\begin{eqnarray*}
x_1+2x_2+5x_3+x_4+x_6&=&3\\
x_3+7x_4-4x_5+x_6&=&1\\
x_5&=&17.
\end{eqnarray*} Dann ist durch die dritte Gleichung zunächst einmal $x_5=17$ festgelegt. In der zweiten Gleichung setzen wir für $x_5$ die $17$ ein, wählen $x_4$ und $x_6$ willkürlich und können damit $x_3$ ausrechnen. Sodann steigen wir zur ersten Gleichung auf; $x_3$ bis $x_6$ sind bereits festgelegt. Für $x_2$ wählen wir wiederum willkürlich einen Wert. Damit können wir schließlich $x_1$ ausrechnen.
Auf die eine oder andere Weise ist Ihnen der soeben beschriebene Algorithmus sicherlich in der Schule bereits begegnet. Wir wollen uns diesen Algorithmus aus der Sichtweise der linearen Algebra und insbesondere der Matrizenrechnung näher anschauen.