Theorem 3.7

Sei $Ax=b$ ein lineares Gleichungssystem mit $m$ Gleichungen in $m$ Variablen.

Die folgenden beiden Aussagen sind äquivalent:

• (i) Gauss-Elimination ist erfolgreich
• (ii) Die Spalten von $A$ sind linear unabhängig ($A$ ist invertierbar)

Beweis:

(i) $⟹$ (ii)

Wenn die Gauss-Elimination erfolgreich ist, dann ist $A\to U$ , $U$ eine obere Dreiecksmatrix mit allen $u_{jj}\ne 0$
So ein $U$ hat lineare unabhängige Spalten nach Korrollar 1.21 (iii): Keine Spalte ist Linearkombination der vorherigen. (ii) folgt mit Lemma 3.4 (Invarianz linearer Unabhängigkeit), welches wiederholt angewandt wird. ($A\to A^{\prime }\to \dots \to U$)

(ii) $⟹$ (i)
Zeige $\neg$ (i) $⟹$ $\neg$ (ii)
Wenn Gauss scheitert $\neg$ (ii), scheitert Gauss in einer Spalte $j$ und zu diesem Zeitpunkt haben wir ein $U$ mit $u_{11},u_{22},\dots ,u_{j-1,j-1}\ne 0$ mit der folgenden Form:

• $v$ ist Linearkombination der Spalten von $U^{\prime }$ (Rückwärtseinsetzung für $U^{\prime }x=v$ $\to$ Lösungen geben dann an, für welches $\lambda$ sie Linearkombinationen sind.)
• Aufgrund der Nullen unter $U^{\prime }$ und $v$ schreibt dieses $x$ auch Spalte $j$ von $U$ als Linearkombination der Spalten davor.
• Spalten von $U$ sind linear abhängig und deshalb auch die Spalten von $A$ (Lemma 3.4)

Damit ist $\neg$ (ii) gezeigt.