Die folgenden Umformungen sind die für den Gauß-Algorithmus "geeigneten Manipulationen":

Bemerkung und Bezeichnung: ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ sei ein lineares n × m - System. Die folgenden Manipulationen heißen elementare Zeilenoperationen; sie verändern die Lösungsmenge nicht. Vertauschen zweier Zeilen: ${\displaystyle \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}\\ ⋮\\ {\mathit{a}}_{j•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i\\ ⋮\\ b_j\\ ⋮\end{array}\right)\iff \left(\begin{array}{c}⋮\\ {\mathit{a}}_{j•}\\ ⋮\\ {\mathit{a}}_{i•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_j\\ ⋮\\ b_i\\ ⋮\end{array}\right)}$ .   Multiplizieren einer Zeile mit einem ${\displaystyle \alpha \ne 0}$:    ${\displaystyle \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i\\ ⋮\end{array}\right)\iff \left(\begin{array}{c}⋮\\ \alpha {\mathit{a}}_{i•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ \alpha b_i\\ ⋮\end{array}\right)}$ .   Addieren einer Zeile zu einer anderen: ${\displaystyle \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i\\ ⋮\end{array}\right)\iff \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}+{\mathit{a}}_{j•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i+b_j\\ ⋮\end{array}\right)}$ .   Von den analogen elementaren Spaltenoperationen benötigen (und notieren) wir nur eine. Sie verändert allerdings die Koordinatenfolge in den Lösungsvektoren! Vertauschen zweier Spalten: ${\displaystyle \left(\begin{array}{ccccc}\cdots & {\mathit{a}}_{•i}& \cdots & {\mathit{a}}_{•j}& \cdots \end{array}\right)\left(\begin{array}{c}⋮\\ x_i\\ ⋮\\ x_j\\ ⋮\end{array}\right)=\mathit{b}\iff \left(\begin{array}{ccccc}\cdots & {\mathit{a}}_{•j}& \cdots & {\mathit{a}}_{•i}& \cdots \end{array}\right)\left(\begin{array}{c}⋮\\ x_j\\ ⋮\\ x_i\\ ⋮\end{array}\right)=\mathit{b}}$ . Die Kombination von 2. und 3. ist das am häufigsten eingesetzte Werkzeug: Subtrahieren eines von Null verschieden Vielfachen einer Zeile von einer anderen: ${\displaystyle \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i\\ ⋮\end{array}\right)\iff \left(\begin{array}{c}⋮\\ {\mathit{a}}_{i•}-\alpha {\mathit{a}}_{j•}\\ ⋮\end{array}\right)\mathit{x}=\left(\begin{array}{c}⋮\\ b_i-\alpha b_j\\ ⋮\end{array}\right)}$ .

Satz (Gauß-Algorithmus): Jedes lösbare, nullzeilenfreie lineare Gleichungssystem ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ läßt sich mit Hilfe von elementaren Zeilen- und Spaltenoperationen maximal diagonalisieren. Den Beweis führen wir auf einer eigenen Seite per Induktion.

 
Wir üben das Gauß'sche Lösungsverfahren. Dabei "diagonalisieren" wir, parallel zum Beweis, von rechts nach links. Zwischenzeitlich auftretende Nullzeilen werden - wenn möglich - weggelassen, oder führen bei unlösbaren Systemen zum Abbruch. Die bei einem Umformungsschritt eingesetzten Manipulationen sind unter dem entsprechenden Äquivalenzzeichen in Kurzform notiert. So bedeutet etwa "I − 2II": Subtrahiere von der ersten Zeile das Doppelte der zweiten.
 

Beispiel: ${\displaystyle \begin{array}{ll}\hfill \hfill & \left(\begin{array}{cc}6& 2\\ 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}4\\ 1\end{array}\right)\hfill \\ \hfill \underset{\text{I}-2\text{II}}{\iff }\hfill & \left(\begin{array}{cc}2& 0\\ 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}2\\ 1\end{array}\right)\hfill \\ \hfill \underset{\text{I}:2}{\iff }\hfill & \left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\end{array}\right)\hfill \\ \hfill \underset{\text{II}-2\text{I}}{\iff }\hfill & \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ -1\end{array}\right)\hfill \\ \hfill \iff \hfill & \mathit{x}=\left(\begin{array}{c}1\\ -1\end{array}\right)\text{ .}\hfill \end{array}}$ ${\displaystyle \begin{array}{ll}\hfill & \left(\begin{array}{ccc}3& 2& 1\\ 1& 1& 0\\ 4& 2& 2\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)\hfill \\ \hfill \underset{\text{III}:2}{\iff }\hfill & \left(\begin{array}{ccc}3& 2& 1\\ 1& 1& 0\\ 2& 1& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)\hfill \\ \hfill \underset{\text{I}-\text{III}}{\iff }\hfill & \left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 0\\ 2& 1& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)\hfill \\ \hfill \underset{\text{I}-\text{II}\text{, III}-\text{II}}{\iff }\hfill & \left(\begin{array}{ccc}0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ 0\\ -1\end{array}\right)\hfill \\ \hfill \iff \hfill & \left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ -1\end{array}\right)\hfill \\ \hfill \iff \hfill & \mathit{x}\in \left(\begin{array}{c}0\\ 0\\ -1\end{array}\right)+<\left(\begin{array}{c}1\\ -1\\ -1\end{array}\right)>\text{.}\hfill \end{array}}$

Mit dem folgenden Applet lassen sich beliebige lineare Gleichungssysteme (bis zu einer Abmessung von 10 × 10) lösen. Wie bisher wird dabei von rechts nach links diagonalisiert; allerdings unter Verzicht auf Zeilen- und Spaltenvertauschungen, so dass die Einheitsvektoren möglicherweise nicht rechtsbündig und nicht in der gewohnten Reihenfolge notiert sind. Bei der Angabe der Lösungsmenge ist dies natürlich berücksichtigt.