Lineare Gleichungssysteme

Das Lösen von Gleichungen ist ein zentraler Aspekt der Mathematik. In der linearen Algebra betrachtet man die Aufgabe, $m$ lineare Gleichungen in $n$ Unbekannten zu lösen. Solche Gleichungen sind von der Form:
\[
\begin{array}{cccccccccc}
G_1\colon&a_{11}x_1&+&a_{12}x_2&+&\cdots&+&a_{1n}x_n&=&b_1\\
G_2\colon&a_{21}x_1&+&a_{22}x_2&+&\cdots&+&a_{2n}x_n&=&b_2\\
\vdots&\vdots & &\vdots & & & &\vdots && \vdots\\
G_m\colon&a_{m1}x_1&+&a_{m2}x_2&+&\ldots&+&a_{mn}x_n&=&b_m\\
\end{array}
\]
Hier bezeichnen $a_{ij}$ und $b_j$ als gegeben angenommene Elemente eines Körpers $K$. Gefragt ist nach Tupeln $(x_1,\ldots, x_n)$ von Elementen $x_j\in K$, die die $m$ Gleichungen $G_1,\ldots, G_m$ gleichzeitig erfüllen.
Sei $L(G_1,\ldots,G_m)\subset K^n$ die Lösungsmenge eines solchen Gleichungssystems. Es wird im Folgenden ein Algorithmus angegeben, der es erlaubt, diese Lösungsmenge vollständig zu beschreiben. Den Chinesen ist dieser Algorithmus schon seit über zweitausend Jahren bekannt. Sie nennen ihn Fang Chen Algorithmus. In Deutschland wird er Gauß-Elimination genannt. Carl Friedrich Gauß selbst nannte ihn eliminatio vulgaris.