Es reicht, die folgende Abschwächung zu beweisen:

Jedes lösbare, nullzeilenfreie lineares n × m - System ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ lässt sich durch elementare Zeilenoperationen in ein äquivalentes n' × m - System ${\displaystyle \left(a{\mathit{\text{'}}}_{ij}\right)\mathit{x}=\mathit{b}\mathit{\text{'}},n\mathit{\text{'}}\le n}$, überführen, in dem die Einheitsvektoren ${\displaystyle {\mathit{e}}_1,\dots ,{\mathit{e}}_{n\mathit{\text{'}}}}$ des ${\displaystyle {ℝ}^{n\mathit{\text{'}}}}$ unter den Spaltenvektoren der Matrix vorkommen.

Falls nötig lassen sich lassen nämlich anschließend die Vektoren ${\displaystyle {\mathit{e}}_1,\dots ,{\mathit{e}}_{n\mathit{\text{'}}}}$ durch Spaltentausch rechtsbündig sortieren, so dass ein maximal diagonalisiertes System entsteht (wobei dann jedoch die Koordinatenreihenfolge des Unbekanntenvektors verändert wird!).

 

Nun zum Beweis der Abschwächung, den wir per Induktion über die Zeilenanzahl n führen. Um die Beweiskonstruktion besser nachvollziehen zu können, werden dabei die einzelnen Schritte parallel an dem rechts stehenden 3 × 4 - System durchgeführt.		${\displaystyle \left(\begin{array}{cccc}4& 7& 3& 1\\ 3& 8& 5& 2\\ 2& 6& 4& 2\end{array}\right)\mathit{x}=\left(\begin{array}{c}2\\ 3\\ 2\end{array}\right)}$
${\displaystyle \underset{¯}{n=1}}$: Man hat ein 1 × m - System zu betrachten: ${\displaystyle \left(a_{11}\cdots a_{1m}\right)\mathit{x}=\mathit{b}}$. Da es nullzeilenfrei ist, muß mindestens ein ${\displaystyle a_{1i}\ne 0}$ sein; teilt man nun die erste (und einzige) Zeile durch ${\displaystyle a_{1i}}$, so steht an i-ter Stelle 1, der (einzige) Einheitsvektors des ${\displaystyle {ℝ}^1}$. Mit ${\displaystyle n\mathit{\text{'}}=1}$ ist dieser Fall damit bewiesen.
${\displaystyle \underset{¯}{n\Rightarrow n+1}}$: Sei nun ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ ein (n + 1) × m - System. Wie gerade findet man in der letzten Zeile ein ${\displaystyle a_{n+\mathrm{1,}i}\ne 0}$. Teilt man diese Zeile durch ${\displaystyle a_{n+\mathrm{1,}i}}$, steht an i-ter Stelle wieder 1. Die oberhalb dieser 1 liegenden Eintragungen werden nun der Reihe in 0 umgewandelt, und zwar subtrahieren wir von der 1. Zeile das ${\displaystyle a_{1i}}$-fache der letzten Zeile, von der 2. Zeile das ${\displaystyle a_{2i}}$-fache der letzten Zeile, .                                . .                                . .                                . von der n. Zeile das ${\displaystyle a_{ni}}$-fache der letzten Zeile.   Auf diese Weise entsteht ein zu ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ äquivalentes System ${\displaystyle \left({\mathit{a"}}_{ij}\right)\mathit{x}=\mathit{b"}}$, dessen i-ter Spaltenvektor der Einheitsvektor ${\displaystyle {\mathit{e}}_{n+1}}$ des ${\displaystyle {ℝ}^{n+1}}$ ist:		${\displaystyle \begin{array}{c} \\ \Updownarrow \\ \left(\begin{array}{cccc}4& 7& 3& 1\\ 3& 8& 5& 2\\ 1& 3& 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}2\\ 3\\ 1\end{array}\right)\\ \Updownarrow \\ \left(\begin{array}{cccc}3& 4& 1& 0\\ 3& 8& 5& 2\\ 1& 3& 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 3\\ 1\end{array}\right)\\ \Updownarrow \\ \left(\begin{array}{cccc}3& 4& 1& 0\\ 1& 2& 1& 0\\ 1& 3& 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)\end{array}}$
${\displaystyle \begin{array}{lll}\hfill & \left(a_{ij}\right)\mathit{x}=\mathit{b}\hfill & \hfill \\ \multicolumn{3}{c}{}\\ \iff \hfill & \left(\begin{array}{ccccc}{\mathit{a"}}_{11}& \cdots & 0& \cdots & {\mathit{a"}}_{1m}\\ ⋮& & ⋮& & ⋮\\ {\mathit{a"}}_{n1}& \cdots & 0& \cdots & {\mathit{a"}}_{nm}\\ {\mathit{a"}}_{n+\mathrm{1,1}}& \cdots & 1& \cdots & {\mathit{a"}}_{n+\mathrm{1,}m}\end{array}\right)\mathit{x}=\mathit{b"}\hfill & \hfill \\ \multicolumn{3}{c}{}\\ \iff \hfill & \left(\begin{array}{ccccc}{\mathit{a"}}_{11}& \cdots & 0& \cdots & {\mathit{a"}}_{1m}\\ ⋮& & ⋮& & ⋮\\ {\mathit{a"}}_{n1}& \cdots & 0& \cdots & {\mathit{a"}}_{nm}\end{array}\right)\mathit{x}=\left(\begin{array}{c}{\mathit{b"}}_1\\ ⋮\\ {\mathit{b"}}_n\end{array}\right)\hfill & (+)\hfill \\ \hfill & \hfill \wedge \hfill & \hfill \\ \hfill & \left(\begin{array}{ccccc}{\mathit{a"}}_{n+\mathrm{1,1}}& \cdots & 1& \cdots & {\mathit{a"}}_{n+\mathrm{1,}m}\end{array}\right)\mathit{x}=\left({\mathit{b"}}_{n+1}\right)\hfill & (++)\hfill \end{array}}$		${\displaystyle \begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}3& 4& 1& 0\\ 1& 2& 1& 0\end{array}\right)\mathit{x}=\left(\begin{array}{c}1\\ 1\end{array}\right)\\ \wedge \\ \left(\begin{array}{cccc}1& 3& 2& 1\end{array}\right)\mathit{x}=\left(1\right)\end{array}}$
Man beachte, dass in der i-ten Spalte von (+) der Nullvektor 0 steht. Falls das System (+) nur Nullzeilen enthält, muss auch die rechte Seite gleich 0 sein (denn sonst wäre die vorausgesetzte Lösbarkeit verletzt), so dass (+) vollständig weggelassen werden kann und somit ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ zu (++) äquivalent ist. In diesem Fall ist mit ${\displaystyle \mathit{n\text{'}}=1}$ der Beweis fertig.
Im anderen Fall streicht man alle möglicherweise entstandenen Nullzeilen und erhält so ein System, auf das die Induktuionsvoraussetzung angewandt werden kann. Es gibt also ein zu (+) äquivalentes ${\displaystyle \mathit{n\text{'}}\times m}$ - System ${\displaystyle \left({\mathit{a\text{'}}}_{ij}\right)\mathit{x}=\mathit{b\text{'}}}$, ${\displaystyle \mathit{n\text{'}}\le \mathit{n"}\le n}$,  dessen i-te Spalte wieder der Nullvektor ist, und das die Einheitsvektoren ${\displaystyle {\mathit{e}}_1,\dots ,{\mathit{e}}_{\mathit{n\text{'}}}}$ des ${\displaystyle {ℝ}^{\mathit{n\text{'}}}}$ als weitere Spaltenvektoren enthält. Wir setzen dieses System mit (++) zusammen und erhalten ein zu ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ äquivalentes ${\displaystyle (\mathit{n\text{'}}+1)\times m}$ - System: ${\displaystyle \begin{array}{ll}\hfill & \left(a_{ij}\right)\mathit{x}=\mathit{b}\hfill \\ \iff \hfill & \left(\begin{array}{ccccc}a{\mathit{\text{'}}}_{11}& \cdots & 0& \cdots & a{\mathit{\text{'}}}_{1m}\\ ⋮& & ⋮& & ⋮\\ a{\mathit{\text{'}}}_{n\mathit{\text{'}}1}& \cdots & 0& \cdots & a{\mathit{\text{'}}}_{n\mathit{\text{'}}m}\\ {\mathit{a"}}_{n\mathit{\text{'}}+\mathrm{1,1}}& \cdots & 1& \cdots & {\mathit{a"}}_{n\mathit{\text{'}}+\mathrm{1,}m}\end{array}\right)\mathit{x}=\left(\begin{array}{c}\mathit{b}{\mathit{\text{'}}}_1\\ ⋮\\ b{\mathit{\text{'}}}_{n\mathit{\text{'}}}\\ {\mathit{b"}}_{n\mathit{\text{'}}+1}\end{array}\right).(\ast )\hfill \end{array}}$		${\displaystyle \begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 0& 1& 0\\ 1& 3& 2& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)\end{array}}$
Offensichtlich kommt dabei ${\displaystyle {\mathit{e}}_{n\mathit{\text{'}}+1}}$, der letzte Einheitsvektor  des ${\displaystyle {ℝ}^{n\mathit{\text{'}}+1}}$, bereits vor. Die noch fehlenden Vektoren ${\displaystyle {\mathit{e}}_1,\dots ,{\mathit{e}}_{n\mathit{\text{'}}}}$ konstruieren wir aus den in ${\displaystyle \left(a{\mathit{\text{'}}}_{ij}\right)}$ vorkommenden Einheitsvektoren des ${\displaystyle {ℝ}^{n\mathit{\text{'}}}}$: Steht etwa der i-te dieser Vektoren in der k-ten Spalte von ${\displaystyle \left(a{\mathit{\text{'}}}_{ij}\right)}$, so ist ${\displaystyle \left(\begin{array}{c}\mathit{a}{\mathit{\text{'}}}_{•k}\\ {\mathit{a"}}_{n\mathit{\text{'}}+\mathrm{1,}k}\end{array}\right)=\left(\begin{array}{c}{\mathit{e}}_i\\ {\mathit{a"}}_{n\mathit{\text{'}}+\mathrm{1,}k}\end{array}\right)}$ k-ter Spaltenvektor von (*). Subtrahiert man nun das ${\displaystyle {\mathit{a"}}_{n\mathit{\text{'}}+\mathrm{1,}k}}$-fache der i-ten Zeile von der letzten, erhält man den i-ten Einheitsvektor des ${\displaystyle {ℝ}^{n\mathit{\text{'}}+1}}$. Dabei wird keiner der bereits hergestellten Einheitsvektoren wieder zerstört, denn die i-te Zeile ist bei allen diesbezüglich relevanten Spalten mit 0 besetzt!		${\displaystyle \begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 0& 1& 0\\ 3& 3& 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ 1\\ -1\end{array}\right)\\ \Updownarrow \\ \left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ 1\\ -1\end{array}\right)\end{array}}$

Da nun schließlich ${\displaystyle n\mathit{\text{'}}+1\le n+1}$, ist der Induktionsschluß bewiesen.