Theorem 3.17

Sei $A$ eine $m\times n$ Matrix und ($R,j_1,j_2,\dots j_r,M$) die Ausgabe des Algorithmus bei Eingabe von ($A,I$). Dann ist $M$ invertierbar, $R=MA$ und $R$ in RREF($j_1,j_2,\dots j_r$)

Beweis

$$\underset{M}{\underbrace{C}}=\stackrel{M}{\overbrace{\underset{\text{Matrizen der Zeilenoperationen}}{\underbrace{M_l,M_{l-1},\dots M_1}}}}\underset{I}{\underbrace{B}}⟹R=MA$$

Da alle $M_i$ invertierbar sind (Zeilenoperationen sind umkehrbar), ist auch das Produkt M invertierbar (Lemma 2.58)