Das obige lineare Gleichungssystem läßt sich in Matrixschreibweise darstellen durch \[Ax=b.\] Hier ist $A=(a_{ij})$ die $m\times n$-Matrix der Koeffizenten des Gleichungssystems, $x\in K^n$ ein Spaltenvektor von Unbekannten und $b\in K^m$ ein Spaltenvektor. $A$ und $b$ werden als gegeben angenommen. Die Matrix $A$ beschreibt eine lineare Abbildung $f:K^n\to K^m$ bezüglich der Standardbasen und die Frage nach Lösungen des Gleichungssystems $Ax=b$ ist nichts Anderes als die Frage nach dem Urbild $f^{-1}(b)$ eines vorgegebenen Punktes.
Ist $b=0$, so spricht man von einem homogenen Gleichungssystem. Dann ist $f^{-1 }(0)=\ker f\subset K^n$ ein linearer Unterraum. Im inhomogenen Fall ist das Gleichungssystem $Ax=b$ genau dann lösbar, wenn $b\in \mathrm{im}\,f$ im Bild von $f$ liegt. Ist $y$ irgendeine Lösung des Systems, so ist die Lösungsgesamtheit der affine Teilraum \[y+\ker f:=\{y+u \,\vert\,u\in \ker f\}\] von $K^n$. Da die Spaltenvektoren in der Matrix $A$ das Bild von $f$ aufspannen, liegt $b$ genau dann im Bild von $f$, wenn $b$ sich als Linearkombination der Spaltenvektoren in $A$ darstellen läßt. Letzteres ist genau dann der Fall, wenn die Matrix $A$ und die sogenannte erweiterte Matrix
\[(A,b)=\left(\begin{array}{cccc}a_{11}&\cdots&a_{1n}&b_1\\
\vdots&&\vdots&\vdots\\
a_{m1}&\cdots&a_{mn}&b_m
\end{array}\right)\] gleichen Rang haben.
Das oben beschriebene Eliminationsverfahren wird im Folgenden in Matrixschreibweise interpretiert.
Definition. Die Elementarmatrix $E_{ij}$ für $i\not=j$ ist die $m\times m$-Matrix, die sich von der Einheitsmatrix ${\mathbb I}_m$ durch eine Eins an der $(i,j)$-ten Stelle unterscheidet. Die Elementarmatrix $E_i(k)$ unterscheidet sich von der Einheitsmatrix ${\mathbb I}_m$ höchstens an der $(i,i)$-ten Stelle, an der die Zahl $k$ steht.
Beispiele. Für $m=5$ ist \[E_{3,5}=\left(\begin{array}{ccccc}
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1
\end{array}\right)\;\text{ und }\;E_{4}\left(k\right)=\left(\begin{array}{ccccc}
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & k & 0\\
0 & 0 & 0 & 0 & 1
\end{array}\right).\]
Das Produkt $E_{ij}\cdot A$ der Elementarmatrix $E_{ij}$ mit einer Matrix $A$ läßt sich wie folgt beschreiben: Die $i$-te Zeile der resultierenden Matrix ist die Summe der $i$-ten und der $j$-ten Zeile von $A$. Alle anderen Zeilen bleiben unverändert. Das Produkt $E_i(k)\cdot A$ verändert die Matrix nur in der $i$-ten Zeile, die mit $k$ multipliziert wird. Durch Multiplikation von links mit Elementarmatrizen können wir also die folgenden elementaren Zeilenumformungen realisieren:
- Multiplikation einer Zeile in $A$ mit einer Konstanten $k\not=0$ in $K$.
- Addition einer Zeile zu einer anderen.
Tatsächlich lassen sich weitere elementare Zeilenumformungen aus diesen beiden kombinieren: Die Addition des $k$-fachen der $j$-ten Zeile zur $i$-ten erhält man zum Beispiel als Kombination
\[
\left(\begin{array}{c}Z_i\\Z_j\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}Z_i\\ k Z_j\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}Z_i+k Z_j\\ k Z_j\end{array}\right)\rightsquigarrow
\left(\begin{array}{c}Z_i+k Z_j\\Z_j\end{array}\right).
\] Hier wird zuerst (1) auf die $j$--te Zeile angewandt, dann (2) und schließlich wieder (1) auf die $j$--te Zeile. Diese Sequenz wird also durch Multiplikation von links mit der Matrix
\[
\left(\begin{array}{cc}1&0\\0&k^{-1}\end{array}\right)
\left(\begin{array}{cc}1&1\\0&1\end{array}\right)
\left(\begin{array}{cc}1&0\\0&k\end{array}\right)=
\left(\begin{array}{cc}1&k \\0&1\end{array}\right)
\] bewirkt. Die Vertauschung zweier Zeilen erhält man in folgender Sequenz:
\[
\left(\begin{array}{c}Z_i\\Z_j\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}Z_i\\Z_i+ Z_j\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}-Z_j\\Z_i+ Z_j\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}-Z_j\\Z_i\end{array}\right) \rightsquigarrow
\left(\begin{array}{c}Z_j\\Z_i\end{array}\right).
\] Hier wird zuerst Umformung 2 angewandt, dann wird das $(-1)$-fache der nun $j$-ten Zeile zur $i$-ten Zeile addiert. Daraufhin wird die nun $i$-te Zeile zur $j$-ten Zeile addiert. Zuletzt wird noch eine Zeile mit $(-1)$ multipliziert. Die Vertauschung zweier Zeilen wird somit durch Multiplikation von links mit folgender Matrix bewirkt:
\[
\left(\begin{array}{cc}-1&0\\0&1\end{array}\right)
\left(\begin{array}{cc}1&0\\1&1\end{array}\right)
\left(\begin{array}{cc}1&-1\\0&1\end{array}\right)
\left(\begin{array}{cc}1&0\\1&1\end{array}\right)=
\left(\begin{array}{cc}0&1 \\1&0\end{array}\right).
\] Das Eliminationsverfahren bewirkt also, dass wir durch elementare Zeilenumformungen, oder äquivalent durch Multiplikation von links mit Elementarmatrizen, eine Matrix $A$ in Zeilenstufenform bringen können:
\[
\left(
\begin{array}{ccccccccccccccccccc}
0&0&0&1&*&*&*&*&*&*&*&*&*&*&*&*&*&*&*\\
0&0&0&0&0&0&0&1&*&*&*&*&*&*&*&*&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&1&*&*&*&*&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0
\end{array}
\right)
\] Hier stehen die Sterne $*$ für nicht näher bezeichnete Zahlen. Die Spalten mit Einsen heißen Stufen, unter der Treppe stehen die Nullen. Durch weitere elementare Zeilenumformungen, nämlich Addition von geeigneten Vielfachen einer Zeile zu den darüber liegenden Zeilen, können wir außerdem in den Stufenspalten die über den Einsen stehenen Terme zum Verschwinden bringen. Insbesondere können wir eine Matrix $A$ in normierte Zeilenstufenform bringen:
\[
\left(
\begin{array}{ccccccccccccccccccc}
0&0&0&1&* &* &*&0&*&*&*&0&*&*&*&0&*&*&*\\
0&0&0&0&0&0&0&1&*&*&*&0&*&*&*&0&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&1&*&*&*&0&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&*&*&*\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0
\end{array}
\right)
\] Wir fassen unsere Überlegungen in mehreren Sätzen zusammen:
Satz. Sei $A$ eine $m\times n$-Matrix. Durch elementare Zeilenumformungen, oder äquivalent durch Multiplikation mit einem Produkt $R$ von $m\times m$-Elementarmatrizen von links, erhalten wir eine Matrix $RA=S$ in (normierter) Zeilenstufenform. Die Lösungsmenge des homogenen Gleichungssystems $Ax=0$ ändert sich nicht durch elementare Zeilenumformungen
\[\{x\in K^n\,\vert\,Ax=0\}=\{x\in K^n\,\vert\,Sx=0\}.\]
Satz. Sei $A$ eine $m\times n$-Matrix und $b\in K^m$. Durch elementare Zeilenumformungen in der erweiterten Matrix $(A,b)$, oder äquivalent durch Multiplikation mit einem Produkt $R$ von $m\times m$-Elementarmatrizen, erhalten wir eine erweiterte Matrix $R\cdot(A,b)=(S,Rb)$ in (normierter) Zeilenstufenform. Die Lösungsmengen der inhomogenen Gleichungssysteme $Ax=b$ und $Sx=Rb$ sind gleich
\[\{x\in K^n\,\vert\,Ax=b\}=\{x\in K^n\,\vert\,Sx=Rb\}.\]
Der Witz bei dieser Umformung ist, dass sich bei einer Matrix in Zeilenstufenform (und noch besser in der normierten Version) die Lösungsmenge eines inhomogenen Gleichungssystems direkt ablesen läßt.