21.10.2026 - Woche 5

Sonderfall der Gauss-Elimination aus 16.10.2026 - Woche 5

Wenn man versucht in der folgenden Matrix

$$A=\left[\begin{array}{ccc}2& 3& 4\\ 4& 6& 14\\ 2& 8& 17\end{array}\right]$$

die erste Spalte zu eliminieren

$$A=\left[\begin{array}{ccc}2& 3& 4\\ 0& 0& 6\\ 0& 5& 13\end{array}\right]$$

steht man vor dem Problem, dass in der zweiten Zeile, welche man jetzt eigentlich dazu verwenden würde, um die $5$ der dritten Zeile zu eliminieren eine $0$ steht. Das ist unpraktisch, da es nun keine Zahl gibt, welche man mit $0$ multiplizieren kann um die $5$ zu entfernen.

Die Lösung für dieses Problem ist, dass man die Zeile 2 und 3 vertauscht (in einem Gleichungssystem $Ax=b$ muss man, wenn man Zeilen in $A$ vertauscht natürlich die gleiche Vertauschung auch bei $b$ machen).

Diese Vertauschung lässt sich durch eine Permutationsmatrix $P$ beschreiben. In diesem konkreten Fall gilt:

$$P_{23}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$$

Die Lösungen bleiben gleich, da man die Permutationsmatrix einfach noch einmal anwenden kann und wieder zur ursprünglichen Matrix kommt.

Mittels $P_{23}$ kommt man dann auf folgendes $A$:

$$A=\left[\begin{array}{ccc}2& 3& 4\\ 0& 5& 13\\ 0& 0& 6\end{array}\right]$$

und kann normal mit der Elimination weitermachen.

Allerdings hat auch dieses Vertauschen von Zeilen seine Grenzen. Kommt man an einen Punkt, an dem es keine Zeile mehr gibt, welche in der gewünschten Spalte einen Eintrag $\ne 0$ hat, so muss man aufgeben und dieses Gleichungssytem ist nicht mittels der Gauss-Elimination lösbar.

Definition einiger Lemmas:

Lemma 3.2

Invarianz der Lösungen

Sei $A$ eine $m\times n$ Matrix, $M$ eine invertierbare $m\times m$ Matrix und $b\in {\mathbb{R}}^m$.

Dann haben die Systeme $Ax=b$ und $MAx=Mb$ die gleiche Lösung.

Beweis:

Für alle $x\in {\mathbb{R}}^n$

$$Ax=b⟹MAx=Mb$$ $$MAx=Mb⟹M^{-1}MAx=M^{-1}Mb⟹Ax=b$$Link to original

Lemma 3.3

Invarianz des Nullraums

Sei $A$ eine $m\times n$ Matrix, $M$ eine invertierbare $m\times m$ Matrix und $b\in {\mathbb{R}}^m$.

Dann haben $A$ und $MA$ den gleichen Nullraum.

Beweis:

Verwende Lineare Algebra/Lemmas/Lemma 3.2 mit $b=0$

Link to original

Lemma 3.4

Invarianz der linearen Unabhängigkeit

Sei $A$ eine $m\times n$ Matrix, $M$ eine invertierbare $m\times m$ Matrix und $b\in {\mathbb{R}}^m$.

Dann hat $A$ genau dann linear unabhängige Spalten, wenn $MA$ linear unabhängige Spalten hat.

Beweis:

Aus Beobachtung 2.5 folgt, dass die Spalten einer Matrix genau dann linear unabhängig sind, wenn der Nullraum nur die $0$ enthält. Da aus Lemma 3.3 hervorgeht, dass sowohl $A$ als auch $MA$ den gleichen Nullraum haben muss auch diese Aussage zur linearen Unabhängigkeit gelten.

Link to original

Lemma 3.5

Invarianz des Zeilenraums

Sei $A$ eine $m\times n$ Matrix, $M$ eine invertierbare $m\times m$ Matrix und $b\in {\mathbb{R}}^m$.

Dann haben $A$ und $MA$ den gleichen Zeilenraum: $R(A)=R(MA)$

Beweis:

Übungen

Im allgemeinen gilt allerdings: $C(A)\ne C(MA)$ (Skript)

Link to original

Lemma 3.6

Invarianz unabhängiger Spaltenindizes und des Rangs

Sei $A$ eine $m\times n$ Matrix, $M$ eine invertierbare $m\times m$ Matrix und $b\in {\mathbb{R}}^m$.

Für alle $j\in [n]$ gilt:
Die Spalte $j$ von $A$ ist genau dann unabhängig, wenn die Spalte $j$ in $MA$ unabhängig ist.

Also haben $A$ und $MA$ die gleiche Anzahl unabhängiger Spalten und somit den Gleichen Rang.

Beweis:

Der Beweis folgt also unteranderem aus Lineare Algebra/Lemmas/Lemma 3.2.

Link to original

Erfolg und Scheitern:

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.

Link to original

Laufzeit zur Lösung von $Ax=b$

Es werden Einzelschritte wie +,-,$\cdot$ ,/ oder Variabeländerungern gezählt.

In O-Notation sieht das ganze dann folgendermassen aus:

Elimination:

• Es werden höchstens $m^2$ Zeilensubtraktionen durchgeführt (Das heisst eine für jeden Eintrag unterhalb der Diagonalen)
• In einer Zeilensubtraktion werden $O(m)$ Einzelschritte durchgeführt.

Das sind also $m^2\cdot O(m)$ Operationen für die Elimination, daraus folgt, dass die Laufzeit für die Elimination $O(m^3)$ beträgt. In dieser Laufzeit sind auch alle anderen Operationen wie z.B. Zeilenvertauschungen enthalten.

Rückwärtseinsetzung:

• Berechnung von $m$ Werten
• $O(m)$ Einzelschritte pro Wert

Daraus folgt dann eine Laufzeit von $m\cdot O(m)$ Operationen. Für die Rückwärtseinsetzung werden also $O(m^2)$ Einzelschritte benötigt.

Für das ganze Verfahren muss jetzt die Anzahl der Operationen für die Elimination und die Rückwärtseinsetzung kombiniert werden: $O(m^3)+O(m^2)$. Daraus lässt sich nun sagen, dass sich das linearen Gleichungssystems $Ax=b$ mit einer asymptotischen Laufzeit von $O(m^3)$ lösen lässt.

Laufzeit der Berechnung von $A^{-1}$

Die Berechnung der Inversen $A^{-1}$ von $A$ lässt sich auf das Lösen von $m$ linearen Gleichungssystem zurückführen ($Ax=e_1$, $Ax=e_2$ , $\dots$ , $Ax=e_m$). Der Vektor $b$ ist dabei immer eine Zeile der Inversen $A^{-1}$. Wenn dieses Gleichungssystem für alle $m$ Spalten von $A$ gelöst wird, so ist das die Inverse.

Es müssen also $m$ Gleichungssysteme in Laufzeit $O(m^3)$ gelöst werden. Daraus ergibt sich eine Laufzeit von $O(m^4)$ für die Berechnung von $A^{-1}$.
Wenn man sich die Gleichungssysteme genauer anschaut sieht man, dass alle Systeme immer mit der gleichen Matrix $A$ arbeiten. Wenn man den Eliminationsschritt, welchen man eigentlich nur auf einen Vektor der rechten Seite auf alle $m$ Vektoren gleichzeitig anwendet spart man sich das $m$ Mal ausführen der Elimination. Hier ist das Berechnen der Inverse auch in $O(m^3)$ möglich.