Kap. 1: Grundlagen

Ein lineares Gleichungssystem (LGS) besteht aus $m$ Gleichungen in $n$ Unbekannten $x_1, x_2, \ldots, x_n$. Jede Gleichung ist eine Linearkombination der Variablen. In Matrixform lautet das System $A\mathbf{x} = \mathbf{b}$ mit der Koeffizientenmatrix $A \in \mathbb{R}^{m \times n}$, dem Lösungsvektor $\mathbf{x} \in \mathbb{R}^n$ und der rechten Seite $\mathbf{b} \in \mathbb{R}^m$.

Zum Rechnen schreiben wir die augmentierte Matrix $[A \mid \mathbf{b}]$: alle Koeffizienten links, die rechten Seiten rechts des senkrechten Strichs. Sie enthält die volle Information des Systems in einem einzigen Objekt. Zeilenoperationen auf $[A \mid \mathbf{b}]$ entsprechen äquivalenten Umformungen der Gleichungen und verändern die Lösungsmenge nicht.

Unser Ziel ist, das System in eine Form zu bringen, aus der die Lösung direkt ablesbar ist. Der Weg dahin heißt Gauss-Elimination: elementare Zeilenoperationen erzeugen schrittweise Nullen unter den Pivots, bis die Matrix in Zeilenstufenform vorliegt. Je nach Struktur der resultierenden Matrix entscheidet sich, ob das System keine, genau eine oder unendlich viele Lösungen besitzt (siehe Abschnitt 1.2).

In der Zeilensicht liest man jede Zeile einer Matrixgleichung $A\mathbf{x} = \mathbf{b}$ als eine einzelne Gleichung. Im $\mathbb{R}^2$ beschreibt jede Zeile eine Gerade; die Lösungsmenge des Systems ist der Schnitt aller Geraden.

Für ein $2 \times 2$-System $a_{11}x_1 + a_{12}x_2 = b_1$, $a_{21}x_1 + a_{22}x_2 = b_2$ gibt es drei geometrische Fälle: die Geraden schneiden sich in genau einem Punkt (eindeutige Lösung), sie sind parallel und verschieden (keine Lösung), oder sie fallen zusammen (unendlich viele Lösungen). Im $\mathbb{R}^3$ ersetzt man Geraden durch Ebenen; die Lösungsmenge ist dann der Schnitt von Ebenen, der je nach Lage ein Punkt, eine Gerade, eine Ebene oder leer sein kann.

Die Zeilensicht ist die natürliche Lesart eines physikalischen oder ökonomischen Modells. Jede Zeile kodiert eine Bedingung, und die Lösung muss alle Bedingungen gleichzeitig erfüllen.

Die Spaltensicht liest $A\mathbf{x}$ als Linearkombination der Spalten von $A$. Sind $\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n$ die Spalten, so gilt $A\mathbf{x} = x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n \mathbf{a}_n$. Die Frage nach der Lösbarkeit von $A\mathbf{x} = \mathbf{b}$ wird dann zu: Liegt $\mathbf{b}$ im Erzeugnis (Span) der Spalten von $A$?

Geometrisch heißt das: Wir dürfen die Spalten frei skalieren und addieren. Das Ergebnis landet irgendwo im Spaltenraum $\operatorname{im}(A) = \operatorname{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}$. Liegt $\mathbf{b}$ in diesem Raum, ist das System lösbar. Sind die Spalten linear unabhängig, ist die Darstellung eindeutig; sind sie abhängig, gibt es mehrere Koeffizientensätze, die $\mathbf{b}$ erzeugen.

Die Spaltensicht ist die natürliche Lesart für Optimierung und numerische lineare Algebra. Sie zeigt sofort, wann der Lösungsraum leer ist, nämlich genau dann, wenn $\mathbf{b}$ außerhalb des Spaltenraums liegt.

Um ein LGS zu lösen, bringen wir die augmentierte Matrix schrittweise in eine einfachere Form. Erlaubt sind genau drei elementare Zeilenoperationen, die die Lösungsmenge nicht verändern:

(1) Zeilentausch: Tausche zwei Zeilen $R_i$ und $R_j$. Kurz: $R_i \leftrightarrow R_j$. (2) Skalieren: Multipliziere eine Zeile mit einem Skalar $\lambda \neq 0$. Kurz: $R_i \to \lambda R_i$. (3) Zeilenaddition: Addiere ein Vielfaches einer Zeile zu einer anderen. Kurz: $R_i \to R_i + \alpha R_j$ mit $i \neq j$.

Jede dieser Operationen ist reversibel (Umkehrung durch Operation gleichen Typs mit inversem Parameter). Daraus folgt, dass die Lösungsmenge $\{\mathbf{x} : A\mathbf{x} = \mathbf{b}\}$ unverändert bleibt. Vermeiden muss man nur $\lambda = 0$ beim Skalieren (nicht invertierbar) und $i = j$ bei der Zeilenaddition (würde die Zeile selbst löschen).

Die Gauss-Elimination (auch Gauss'sches Eliminationsverfahren) wendet elementare Zeilenoperationen systematisch an, bis die Matrix in Zeilenstufenform (ZSF) vorliegt. In der ZSF ist in jeder Zeile das erste Nicht-Null-Element (der Pivot) strikt weiter rechts als der Pivot der Zeile darüber; Nullzeilen stehen ganz unten.

Der Algorithmus durchläuft die Spalten von links nach rechts. In jeder Spalte wird ein möglichst großes Pivot-Element ausgewählt (Zeilentausch, falls nötig), und dann werden alle Einträge unter dem Pivot durch Zeilenaddition eliminiert. Das Ergebnis ist eine obere Dreiecksstruktur mit möglichen Sprüngen.

Ist $[A \mid \mathbf{b}]$ in ZSF, so lässt sich durch Rückwärtseinsetzen die Lösung ablesen: man beginnt bei der untersten nicht-trivialen Zeile und arbeitet sich nach oben vor, indem man bereits bekannte Variablen einsetzt.

Der Rang einer Matrix $A$ ist die Anzahl der Pivots in der Zeilenstufenform; gleichbedeutend die Anzahl linear unabhängiger Zeilen bzw. Spalten. Notation: $\operatorname{rang}(A)$ oder $\mathrm{rk}(A)$. Es gilt stets $\operatorname{rang}(A) \le \min(m, n)$, weil mehr Pivots als Zeilen oder Spalten geometrisch unmöglich sind.

Die Spalten, in denen ein Pivot steht, heißen Pivot-Spalten. Die übrigen Spalten heißen freie Spalten; die zugehörigen Variablen werden beim Rückwärtseinsetzen zu frei wählbaren Parametern. Die Anzahl der freien Variablen ist $n - \operatorname{rang}(A)$.

Der Rang ist invariant unter Zeilen- und Spaltenoperationen. Zwei äquivalente Matrizen haben denselben Rang. Er misst die effektive Dimension der durch $A$ realisierten linearen Abbildung.

Die reduzierte Zeilenstufenform (RREF, reduced row echelon form) ist eine eindeutige Normalform einer Matrix. Zusätzlich zur Zeilenstufenform erfüllt sie: (a) jeder Pivot ist gleich $1$, (b) in jeder Pivot-Spalte steht über und unter dem Pivot nur $0$. Erreicht wird die RREF durch Gauss-Jordan-Elimination, eine Erweiterung der Gauss-Elimination.

Der Nutzen: ist $[A \mid \mathbf{b}]$ in RREF, lässt sich die Lösung direkt ablesen, ohne Rückwärtseinsetzen. Pivot-Variablen erhalten den Wert der letzten Spalte der zugehörigen Zeile; freie Variablen bleiben Parameter.

Die RREF ist eindeutig, während die (nicht reduzierte) ZSF von der Reihenfolge der Umformungen abhängt. Daher wird die RREF in Beweisen und bei der Bestimmung von Kernbasen bevorzugt.

Experimentiere frei: tippe eigene Koeffizienten in die augmentierte Matrix $[A \mid \mathbf{b}]$, wähle eine andere Grösse oder starte aus einem Preset. Jede Änderung triggert Gauss-Elimination, Klassifikation und Lösungsberechnung. So sieht man direkt, wie sich kleine Zahlenänderungen in der Struktur der Lösungsmenge niederschlagen.

Die Schritte-Liste protokolliert jede Zeilenoperation als lesbaren Ausdruck (etwa $R_2 - 2 \cdot R_1$). Die Lösungsanzeige unterscheidet zwischen eindeutiger Lösung, Lösung mit freien Parametern und Inkonsistenz. Für homogene Systeme $\mathbf{b} = \mathbf{0}$ setze die rechte Spalte auf Null.

Nach Anwendung der Gauss-Elimination lässt sich jedes lineare Gleichungssystem in genau einen von drei Fällen einordnen: keine Lösung, genau eine Lösung oder unendlich viele Lösungen. Zwischentöne gibt es nicht.

Die Einordnung hängt von den Rängen $r = \operatorname{rang}(A)$, $r' = \operatorname{rang}([A \mid \mathbf{b}])$ und der Anzahl Unbekannter $n$ ab: (1) Ist $r < r'$ (eine Nullzeile in $A$ hat nichtverschwindenden rechten Eintrag), so ist das System inkonsistent: keine Lösung. (2) Ist $r = r' = n$, so ist das System eindeutig lösbar. (3) Ist $r = r' < n$, so ist das System unendlich oft lösbar, und die Lösungsmenge hat $n - r$ freie Parameter.

Das Frobenius-Kriterium formuliert die Lösbarkeitsbedingung kompakt über Ränge: Das System $A\mathbf{x} = \mathbf{b}$ ist genau dann lösbar, wenn $\operatorname{rang}(A) = \operatorname{rang}([A \mid \mathbf{b}])$.

Die Richtung „lösbar $\Rightarrow$ Rangbedingung" folgt aus der Spaltensicht: Ist $\mathbf{b}$ eine Linearkombination der Spalten von $A$, so bringt das Hinzufügen von $\mathbf{b}$ als weitere Spalte keinen zusätzlichen Rang. Die Rückrichtung ergibt sich aus der Zeilenstufenform: stimmen die Ränge überein, enthält die erweiterte Matrix keine inkonsistente Nullzeile vom Typ $[0 \cdots 0 \mid c]$ mit $c \neq 0$.

Praktisch genügt also, die Ränge von $A$ und $[A \mid \mathbf{b}]$ via Gauss-Elimination zu vergleichen. Stimmen sie, ist das System lösbar; stimmen sie nicht, ist es unlösbar.

Hat das System unendlich viele Lösungen, so parametrisiert man die Lösungsmenge durch freie Parameter. Die Anzahl ist genau $n - \operatorname{rang}(A)$; das sind die Variablen der freien Spalten. Jeder freie Parameter entspricht einer unabhängigen Richtung, in die man von einer beliebigen Partikulärlösung abweichen kann.

Die allgemeine Lösung hat die Form $\mathbf{x} = \mathbf{x}_p + t_1 \mathbf{k}_1 + t_2 \mathbf{k}_2 + \cdots + t_{n-r} \mathbf{k}_{n-r}$, wobei $\mathbf{x}_p$ eine beliebige Partikulärlösung und $\{\mathbf{k}_1, \ldots, \mathbf{k}_{n-r}\}$ eine Basis des Kerns $\operatorname{ker}(A)$ ist (siehe 1.4). Die $t_j$ durchlaufen unabhängig voneinander $\mathbb{R}$.

Geometrisch ist die Lösungsmenge ein affiner Unterraum: parallel zum Kern, verschoben um $\mathbf{x}_p$. Sie ist genau dann ein Unterraum (enthält Null), wenn das System homogen ist, also $\mathbf{b} = \mathbf{0}$.

Welche Kombinationen von Rängen führen zu welchem Lösungstyp? Diese Sandbox zeigt die Klassifikation live: wähle eines der Presets (je ein Beispiel pro Fall) oder editiere die augmentierte Matrix direkt. Die Klassifikationsbox und die Schritte-Liste aktualisieren sich nach jeder Änderung.

Nützliches Experiment: starte mit einem Kreuzungs-Preset und ändere einen einzelnen Koeffizienten so, dass die beiden Zeilen parallel werden. Beobachte, wie die Klassifikation von „eindeutig" auf „keine Lösung" umspringt, sobald $\operatorname{rang}(A) < \operatorname{rang}([A \mid \mathbf{b}])$ eintritt.

Für eine quadratische Matrix $A \in \mathbb{R}^{n \times n}$ ist jede der folgenden neun Aussagen mit jeder anderen äquivalent. Das heißt: sobald eine erfüllt ist, sind alle erfüllt; scheitert eine, scheitern alle.

(1) $\operatorname{rang}(A) = n$ (voller Rang). (2) $\det(A) \neq 0$. (3) $A$ ist invertierbar. (4) $A\mathbf{x} = \mathbf{b}$ ist für jedes $\mathbf{b}$ lösbar. (5) $A\mathbf{x} = \mathbf{b}$ hat genau eine Lösung. (6) $\operatorname{ker}(A) = \{\mathbf{0}\}$ (nur triviale Lösung der homogenen Gleichung). (7) Die Spalten von $A$ sind linear unabhängig. (8) Die Spalten bilden eine Basis von $\mathbb{R}^n$. (9) Keiner der Eigenwerte ist $0$.

Der gemeinsame Kern aller Aussagen: die Spalten spannen $\mathbb{R}^n$ auf und sind linear unabhängig. Jede Aussage beschreibt dieses Faktum aus einer anderen Perspektive. In der Praxis genügt es, eine dieser Aussagen zu prüfen, um den Rest zu erhalten.

Für eine $2 \times 2$-Matrix $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ ist die Determinante definiert als $\det(A) = ad - bc$. Der absolute Betrag $|\det(A)|$ ist die Fläche des von den Spalten aufgespannten Parallelogramms; das Vorzeichen kodiert die Orientierung.

Konkret: stehen die Spalten $\mathbf{a}_1 = (a, c)$ und $\mathbf{a}_2 = (b, d)$ in „positiver" Drehrichtung zueinander (wie $\mathbf{e}_1, \mathbf{e}_2$ der Standardbasis), so ist $\det(A) > 0$. Dreht man die Spalten zurück (gespiegelte Orientierung), wird $\det(A) < 0$. Sind die Spalten parallel (Fläche kollabiert zu einer Strecke), ist $\det(A) = 0$.

Diese geometrische Sicht erklärt die Algebra: $\det(A) = 0$ bedeutet, dass die Spalten linear abhängig sind, das Parallelogramm zu einer Linie entartet, der Spaltenraum nicht ganz $\mathbb{R}^2$ aufspannt und $A$ nicht invertierbar ist.

Für $n \geq 3$ lässt sich die Determinante rekursiv über Cofaktor-Entwicklung (auch Laplace-Entwicklung) bestimmen. Man wählt eine Zeile oder Spalte, streicht abwechselnd Zeile und Spalte zu jedem Eintrag (ergibt die $(n-1)\times(n-1)$-Minor-Matrix), multipliziert mit dem Eintrag und dem zugehörigen Vorzeichen $(-1)^{i+j}$ und summiert auf.

Formel bei Entwicklung nach Zeile $i$: $\det(A) = \sum_{j=1}^n (-1)^{i+j} a_{ij} M_{ij}$, wobei $M_{ij}$ die Determinante der Matrix ist, die entsteht, wenn man Zeile $i$ und Spalte $j$ streicht.

Für $3 \times 3$-Matrizen gibt es außerdem die Sarrus-Regel: $\det(A) = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}$. Praktischer Merksatz: die drei nach rechts unten absteigenden Diagonalen addieren, die drei nach links unten absteigenden subtrahieren. Die Sarrus-Regel gilt nur für $3 \times 3$; für größere Matrizen muss die Cofaktor-Entwicklung verwendet werden.

Die Determinante erfüllt mehrere grundlegende Rechenregeln. Für quadratische $A, B \in \mathbb{R}^{n \times n}$ und $\lambda \in \mathbb{R}$ gilt: $\det(AB) = \det(A)\det(B)$ (multiplikativ), $\det(A^\mathsf{T}) = \det(A)$, $\det(\lambda A) = \lambda^n \det(A)$ und, falls $A$ invertierbar, $\det(A^{-1}) = 1/\det(A)$. Bei Zeilentausch flippt das Vorzeichen; das Skalieren einer Zeile mit $\lambda$ zieht $\lambda$ aus der Determinante heraus; die Zeilenaddition lässt die Determinante unverändert.

Für eine invertierbare $2 \times 2$-Matrix $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ liefert die Adjugate-Formel die Inverse explizit: $A^{-1} = \frac{1}{\det(A)} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. Die Matrix $\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ heißt Adjugate oder Kofaktormatrix transponiert. Merkhilfe: Hauptdiagonale vertauschen, Nebendiagonale mit Minuszeichen versehen.

Für größere Matrizen ist die Gauss-Jordan-Elimination oder LR-Zerlegung numerisch sinnvoller als die allgemeine Adjugate-Formel (die bei $n \geq 4$ sehr aufwändig wird).

Die neun Äquivalenzen für quadratische Matrizen leben oder sterben gemeinsam. Diese Sandbox prüft alle neun gleichzeitig: ändere die Matrix und beobachte, ob die Indikatoren reihenweise grün (invertierbar) oder rot (singulär) werden. Für $\operatorname{rang}(A) = n$ sind alle Aussagen erfüllt; sobald $\det(A) = 0$, fallen alle.

Die Presets decken die Kernfälle ab: Identität (trivial invertierbar), Drehmatrix (invertierbar, kein Eigenwert 0), singulär (kollineare Spalten) und Zufall. Editiere die Matrix direkt in der Zelle; die neun Indikatoren aktualisieren sich synchron nach jedem Tastendruck.

Ein lineares Gleichungssystem der Form $A\mathbf{x} = \mathbf{0}$ heißt homogen. Es hat immer mindestens eine Lösung: den Nullvektor $\mathbf{x} = \mathbf{0}$, die sogenannte triviale Lösung. Die Frage ist, ob darüber hinaus noch weitere (nicht-triviale) Lösungen existieren.

Die Menge aller Lösungen heißt Kern (auch Nullraum) von $A$ und wird mit $\operatorname{ker}(A)$ notiert. Formal: $\operatorname{ker}(A) = \{\mathbf{x} \in \mathbb{R}^n : A\mathbf{x} = \mathbf{0}\}$. Der Kern ist stets ein Unterraum von $\mathbb{R}^n$: Er enthält $\mathbf{0}$, ist abgeschlossen unter Addition ($\mathbf{x}, \mathbf{y} \in \operatorname{ker} \Rightarrow \mathbf{x}+\mathbf{y} \in \operatorname{ker}$) und abgeschlossen unter Skalar-Multiplikation ($\lambda\mathbf{x} \in \operatorname{ker}$ für jedes $\lambda \in \mathbb{R}$).

Geometrisch ist $\operatorname{ker}(A)$ die Menge aller Vektoren, die durch $A$ auf Null abgebildet werden. Für $\operatorname{rang}(A) = n$ wird nur der Nullvektor auf Null abgebildet; für $\operatorname{rang}(A) < n$ wird ein ganzer Unterraum zerquetscht.

Das Rang-Nullity-Theorem (auch Dimensionssatz) verknüpft Rang und Kerndimension: für jede Matrix $A \in \mathbb{R}^{m \times n}$ gilt $\operatorname{rang}(A) + \dim \operatorname{ker}(A) = n$.

Die Begründung folgt aus der Zeilenstufenform: Jede Pivot-Spalte trägt $+1$ zum Rang bei, jede freie Spalte trägt $+1$ zur Kerndimension bei. Die Gesamtzahl der Spalten ist $n$, also summieren sich beide Größen zu $n$.

Das Theorem erlaubt schnelle Schlüsse: Ist $\operatorname{rang}(A) = n$, so ist $\dim \operatorname{ker}(A) = 0$, also $\operatorname{ker}(A) = \{\mathbf{0}\}$: nur die triviale Lösung. Ist dagegen $\operatorname{rang}(A) < n$, so ist $\dim \operatorname{ker}(A) \geq 1$: es existiert eine nicht-triviale Lösung, und die Lösungsmenge des homogenen Systems hat mindestens eine frei wählbare Richtung.

Das Bild (auch Spaltenraum) von $A$ ist die Menge aller Vektoren, die von $A$ erzeugt werden können: $\operatorname{im}(A) = \{A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n\}$. Äquivalent ist $\operatorname{im}(A)$ der Erzeugnis (Span) der Spalten von $A$: $\operatorname{im}(A) = \operatorname{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}$.

Das Bild ist ein Unterraum von $\mathbb{R}^m$ (Ziel-Raum), und seine Dimension ist der Rang von $A$: $\dim \operatorname{im}(A) = \operatorname{rang}(A)$. Diese Identität ergibt sich, weil die Pivot-Spalten eine Basis des Bildes bilden.

Die Spaltensicht macht klar: $A\mathbf{x} = \mathbf{b}$ ist genau dann lösbar, wenn $\mathbf{b} \in \operatorname{im}(A)$. Das ist die geometrische Interpretation des Frobenius-Kriteriums (siehe 1.2.2).

Ist $A\mathbf{x} = \mathbf{b}$ lösbar, so hat die Lösungsmenge eine klare Struktur: Sei $\mathbf{x}_p$ irgendeine Partikulärlösung, also ein Vektor mit $A\mathbf{x}_p = \mathbf{b}$. Dann ist jede Lösung $\mathbf{x}$ von der Form $\mathbf{x} = \mathbf{x}_p + \mathbf{k}$ mit $\mathbf{k} \in \operatorname{ker}(A)$. Kurz: Lösungsmenge $= \mathbf{x}_p + \operatorname{ker}(A)$.

Die Idee: Ist $\mathbf{x}$ eine Lösung, so folgt $A(\mathbf{x} - \mathbf{x}_p) = A\mathbf{x} - A\mathbf{x}_p = \mathbf{b} - \mathbf{b} = \mathbf{0}$, also $\mathbf{x} - \mathbf{x}_p \in \operatorname{ker}(A)$. Umgekehrt erfüllt jedes $\mathbf{x} = \mathbf{x}_p + \mathbf{k}$ mit $\mathbf{k} \in \operatorname{ker}$ die Gleichung $A\mathbf{x} = A\mathbf{x}_p + A\mathbf{k} = \mathbf{b} + \mathbf{0} = \mathbf{b}$.

Geometrisch ist die Lösungsmenge ein affiner Unterraum: parallel zum Kern, verschoben um $\mathbf{x}_p$. Für $\mathbf{b} = \mathbf{0}$ (homogener Fall) ist $\mathbf{x}_p = \mathbf{0}$ zulässig, und die Lösungsmenge wird zum Unterraum $\operatorname{ker}(A)$ selbst.

Für eine Matrix $A$ ohne rechte Seite löst die Sandbox das homogene System $A\mathbf{x} = \mathbf{0}$ und liefert eine Basis des Kerns. Bei vollem Spaltenrang ist der Kern trivial; bei defektem Rang erscheinen die kern-aufspannenden Richtungsvektoren als $\mathbf{k}_1, \mathbf{k}_2, \ldots$.

Die Schritte-Liste zeigt die Reduktion zur RREF, aus der man Kern und Bild direkt ablesen kann. Pivot-Spalten spannen das Bild $\operatorname{im}(A)$ auf; freie Spalten steuern die Parameter der Kernbasis. Experimentiere mit den Presets: voller Rang (ker = $\{\mathbf{0}\}$), Rang 1 (ker ist Gerade), Nullmatrix (ker = $\mathbb{R}^n$) und Projektion (ker ist die orthogonale Achse).