Es reicht, die folgende Abschwächung zu beweisen:

Jedes lösbare, nullzeilenfreie lineares n × m - System ( a_ij ) x = b läßt sich durch elementare Zeilenoperationen in ein äquivalentes n' × m - System ( a'_ij ) x = b', n' £ n,  überführen, in dem die Einheitsvektoren e₁,...,e_n' des R ^n' unter den Spaltenvektoren der Matrix vorkommen.

Falls nötig lassen sich lassen nämlich anschließend die Vektoren e₁,...,e_n' 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.		$\left(\begin{array}{cccc}4& 7& 3& 1\\ 3& 8& 5& 2\\ 2& 6& 4& 2\end{array}\right)x=\left(\begin{array}{c}2\\ 3\\ 2\end{array}\right)$
n = 1: Man hat ein 1 × m - System zu betrachten: ( a11···· a1m ) x  = b. Da es nullzeilenfrei ist, muß mindestens ein a1i ¹ 0 sein; teilt man nun die erste (und einzige) Zeile durch a1i, so steht an i-ter Stelle 1, der (einzige) Einheitsvektors des R 1. Mit n' = 1 ist dieser Fall damit bewiesen.
n Þ n + 1: Sei nun ( aij ) x = b ein (n + 1) × m - System. Wie gerade findet man in der letzten Zeile ein an + 1,i ¹ 0. Teilt man diese Zeile durch an + 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 a1i-fache der letzten Zeile, von der 2. Zeile das a2i-fache der letzten Zeile, .                                . .                                . .                                . von der n. Zeile das ani-fache der letzten Zeile.		$\begin{array}{c}\left(\begin{array}{cccc}4& 7& 3& 1\\ 3& 8& 5& 2\\ 2& 6& 4& 2\end{array}\right)x=\left(\begin{array}{c}2\\ 3\\ 2\end{array}\right)\\ \Updownarrow \\ \left(\begin{array}{cccc}4& 7& 3& 1\\ 3& 8& 5& 2\\ 1& 3& 2& 1\end{array}\right)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)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)x=\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)\end{array}$
Auf diese Weise entsteht ein zu ( aij ) x = b äquivalentes System ( a"ij ) x = b", dessen i-ter Spaltenvektor der Einheitsvektor en + 1 des R n + 1 ist: $\begin{array}{lll}& \multicolumn{2}{c}{(a_{ij})x=b}\\ \multicolumn{3}{c}{ }\\ \iff & \left(\begin{array}{ccccc}a{"}_{11}& \cdots & 0& \cdots & a{"}_{1m}\\ ⋮& & ⋮& & ⋮\\ a{"}_{n1}& \cdots & 0& \cdots & a{"}_{nm}\\ a{"}_{n+1,1}& \cdots & 1& \cdots & a{"}_{n+1,m}\end{array}\right)x=b"& \\ \multicolumn{3}{c}{}\\ \iff & \left(\begin{array}{ccccc}a{"}_{11}& \cdots & 0& \cdots & a{"}_{1m}\\ ⋮& & ⋮& & ⋮\\ a{"}_{n1}& \cdots & 0& \cdots & a{"}_{nm}\end{array}\right)x=\left(\begin{array}{c}b{"}_1\\ ⋮\\ b{"}_n\end{array}\right)& (+)\\ \hfill \wedge \hfill & \\ \left(\begin{array}{ccccc}a{"}_{n+1,1}& \cdots & 1& \cdots & a{"}_{n+1,m}\end{array}\right)x=\left(b{"}_{n+1}\right)& (++)\end{array}$		$\begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}3& 4& 1& 0\\ 1& 2& 1& 0\end{array}\right)x=\left(\begin{array}{c}1\\ 1\end{array}\right)\\ \wedge \\ \left(\begin{array}{cccc}1& 3& 2& 1\end{array}\right)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, muß 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 ( aij  ) x = b zu (++) äquivalent ist. In diesem Fall ist mit n' = 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 n' × m - System ( a'ij )  x = b', n' £ n" £ n,  dessen i-te Spalte wieder der Nullvektor ist, und das die Einheitsvektoren e1,...,en' des R n' als weitere Spaltenvektoren enthält. Wir setzen dieses System mit (++) zusammen und erhalten ein zu ( aij ) x = b äquivalentes (n' + 1) × m - System: $\begin{array}{ll}& (a_{ij})x=b\\ \iff & \left(\begin{array}{ccccc}a{\text{'}}_{11}& \cdots & 0& \cdots & a{\text{'}}_{1m}\\ ⋮& & ⋮& & ⋮\\ a{\text{'}}_{n\text{'}1}& \cdots & 0& \cdots & a{\text{'}}_{n\text{'}m}\\ a{"}_{n\text{'}+1,1}& \cdots & 1& \cdots & a{"}_{n\text{'}+1,m}\end{array}\right)x=\left(\begin{array}{c}b{\text{'}}_1\\ ⋮\\ b{\text{'}}_{n\text{'}}\\ b{"}_{n\text{'}+1}\end{array}\right)\text{.\&quad;(*)}\end{array}$		$\begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 0& 1& 0\\ 1& 3& 2& 1\end{array}\right)x=\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)\end{array}$
Offensichtlich kommt dabei en' + 1, der letzte Einheitsvektor  des R n' + 1 , bereits vor. Die noch fehlenden Vektoren e1,...,en' konstruieren wir aus den in ( a'ij ) vorkommenden Einheitsvektoren des R n': Steht etwa der i-te dieser Vektoren in der k-ten Spalte von ( a'ij ), so ist $\left(\begin{array}{c}a{\text{'}}_{ċk}\\ a{"}_{n\text{'}+1,k}\end{array}\right)=\left(\begin{array}{c}{e}_i\\ a{"}_{n\text{'}+1,k}\end{array}\right)$ k-ter Spaltenvektor von (*). Subtrahiert man nun das a"n' + 1,k-fache der i-ten Zeile von der letzten, erhält man den i-ten Einheitsvektor des R n' + 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!		$\begin{array}{c}\Updownarrow \\ \left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 0& 1& 0\\ 3& 3& 0& 1\end{array}\right)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)x=\left(\begin{array}{c}0\\ 1\\ -1\end{array}\right)\end{array}$

Da nun schließlich n' + 1 £ n + 1, ist der Induktionsschluß bewiesen.