Title: ETH_Basisjahr / Math / Lineare_Algebra_I / 3 Matrizen und lineare Gleichungssysteme

Q: Definition Lineares Gleichungssystem (LGS)
A: Ein lineares Gleichungssystem über einen Körper \(\mathbb{K}\) ist ein System von Gleichungen \[\sum_{j=1}^n a_{ij}x_j = b_i\] für alle \(1 \leqslant i \leqslant m\), wobei \(m\) und \(n\) natürliche Zahlen sind.
\(m\) ist dabei die Anzahl Gleichungen, während \(n\) für die Anzahl Variablen steht.
Sind alle \(b_i = 0\) so heisst das Gleichungssystem homogen.

Q: Definition elementare Zeilenumformungen
A: Es gibt drei Arten elementarer Zeilenumformungen für ein LGS:
(a) Addieren von \(\lambda\)-mal einer Zeile zu einer anderen
(b) Multiplizieren einer Zeile mit \(\lambda\)
(c) Vertauschen zweier Zeilen
Hierbei ist \(\lambda \in \mathbb{K}\).
Alle obigen Operationen sind zudem umkehrbar.

Q: Definition Zeilenstufenform
A: Ein Gleichungssystem ist in Zeilenstufenform, wenn die von Null verschiedenen Terme in jeder Zeile echt später beginnen als in der Zeile davor.

Q: Satz zur Gauss-Elimination
A: Jedes lineare Gleichungssytem lässt sich durch eine Folge elementarer Zeilenumformungen in Zeilenstufenform bringen.

Q: Satz: Jedes lineare Gleichungssystem lässt sich durch eine Folge elementarer Zeilenoperationen sowie das Vertauschen von Spalten in die folgende Form bringen:
[...]
Aus dieser Form kann zudem noch folgendes abgelesen werden:
A: \[\begin{matrix} x_1 & \: & \: & + & a_{1,r+1}x_{r+1} & + & \ldots & +a_{1n}x_n & = & b_1 \\ \: & \ddots & \: & \: & \vdots & \: & \: & \vdots & \: & \vdots \\ \: & \: & x_r & + & a_{r, r+1}x_{r+1} & + & \ldots & +a_{rn}x_n & = & b_r \\ \: & \: & \: & \: & \: & \: & \: & 0 & = & b_{r+1} \\ \: & \: & \: & \: & \: & \: & \: & \vdots & \: & \vdots \end{matrix}\] für ein gewisses \(0 \leqslant r \leqslant min\{m,n\}\).
Back Extra: Ist \(b_j \neq 0\) für ein \(j > r\), so hat das Gleichungssystem keine Lösung.

Q: Definition Matrix
A: Eine Matrix mit m Zeilen und n Spalten, oder kurz eine \(m \times n\)-Matrix, über \(\mathbb{K}\) ist ein Ausdruck \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) mit Koeffizienten \(a_{ij} \in \mathbb{K}\), ausführlich geschrieben als rechteckiges Schema
\[\begin{pmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \ldots & a_{mn} \end{pmatrix}\]
Der erste Index \(i\) in \((\ldots)_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) bezeichnet stets die Zeile, der zweite \(j\) die Spalte.
Intuition: "Zeilen zuerst, Spalten später."

Q: Definition Nullmatrix
A: Die Nullmatrix ist die Matrix \(O := O_{m,n} := (0)_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}} \) mit allen Einträgen gleich 0.

Q: Definition Einheitsmatrix
A: Die (quadratische) Einheitsmatrix ist die Matrix \(I := I_m := (\delta_{ij})_{1 \leqslant i,j \leqslant m}\) mit der Kronecker-Deltafunktion:
\[\delta_{ij} :=  \left \{ \begin{array}{cc} 1 \: \text{für} \: i = j, \\ 0 \: \text{für} \: i \neq j \end{array} \right. \]
Das heisst, mit allen Diagonaleinträgen gleich 1 und allen übrigen Einträgen gleich 0.

Q: Definition Produkt zwischen einer Matrix und einem Skalar
A: Das Produkt einer \(m \times n\)-Matrix \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) mit einem Element \(\lambda \in \mathbb{K}\) ist die \(m \times n\)-Matrix \[\lambda \cdot A := A \cdot \lambda := (\lambda a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant m}}\]

Q: Definition Summe zweier Matrizen
A: Die Summe zweier \(m \times n\)-Matrizen \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) und \(B = (b_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) ist die \(m \times n\)-Matrix \[A + B := (a_{ij}+b_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\]

Q: Definition:
- Eine \(m \times m\)-Matrix heisst [...]
- Eine \(m \times 1\)-Matrix heisst [...]
- Eine \(1 \times n\)-Matrix heisst [...]
A: quadratisch; Spaltenvektor; Zeilenvektor

Q: Definition Matrixmultiplikation
A: Das Produkt einer \(m \times n\)-Matrix \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) mit einer \(n \times l\)-Matrix \(B = (b_{jk})_{\substack{1 \leqslant j \leqslant n \\ 1 \leqslant k \leqslant l}}\) ist die \(m \times l\)-Matrix \[A \cdot B := (\sum_{j=1}^n a_{ij}b_{jk})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant k \leqslant l}}\]

Q: Die Menge aller \(m \times n\)-Matrizen über \(\mathbb{K}\) zusammen mit der [...] und [...] eine [...].
A: Addition; dem neutralen Element \(O_{m,n}\); abelsche Gruppe

Die Menge aller \(m \times n\)-Matrizen über \(\mathbb{K}\) zusammen mit der Addition und Multiplikation und dem Nullelement \(O_{m,m}\)  und dem  Einselement \(I_m\)  ist ein unitärer Ring.

Q: Definition Transponierte
A: Die Transponierte einer \(m \times n\)-Matrix \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m \\ 1 \leqslant j \leqslant n}}\) ist die durch Vertauschen der Zeilenindizes mit den Spaltenindizes enstehende \(n \times m\)-Matrix
\[A^T := (a_{ij})_{\substack{1 \leqslant j \leqslant n \\ 1 \leqslant i \leqslant m}} = \begin{pmatrix} a_{11} & \ldots & a_{m1} \\ \vdots & \ddots & \vdots \\ a_{1n} & \ldots & a_{mn} \end{pmatrix}\]

Proposition: Für alle Matrizen \(A, B\) über \(\mathbb{K}\) und alle \(\lambda \in \mathbb{K}\) gilt, sofern die Matrizen für die jeweilige Formel die richtige Grösse besitzen:
\((A^T)^T \) = \(A\)
\((A + B)^T \) =  \( A^T + B^T \) 
\((\lambda \cdot A)^T \) = \( \lambda \cdot A^T \) 
\((A \cdot B)^T \) = \( B^T \cdot A^T\) 
\(O_{m,n}^T \) = \( O_{m,n} \) 
\(I_m^T \) = \( I_m \)

Q: Definition Invertierbarkeit
A: Eine \(m \times m\)-Matrix \(A\), zu der eine \(m \times m\)-Matrix \(A'\) existiert mit \(A \cdot A' = A' \cdot A = I_m\) heisst invertierbar. Die betreffende Matrix \(A'\) heisst dann Inverse von \(A\) und wird mit \(A^{-1}\) bezeichnet. Die Menge aller invertierbaren \(m \times m\)-Matrizen über \(\mathbb{K}\) wird mit \(GL_m(\mathbb{K})\) bezeichnet.

Proposition: Für alle \(m \times m\)-Matrizen \(A\) und \(B\) gilt:
- Ist \(A\) invertierbar, so ist die Inverse \(A^{-1}\) eindeutig bestimmt.
- Ist \(A\) invertierbar, so ist auch  \(A^{-1}\)  invertierbar mit \((A^{-1})^{-1} = A\)
- Sind \(A\) und \(B\) invertierbar, so ist  \(A \cdot B\)  invertierbar und es gilt  \((A \cdot B)^{-1} = B^{-1} \cdot A^{-1}\).
- Ist \(A\) invertierbar, so ist \(B\) invertierbar genau dann, wenn  \(A \cdot B\) invertierbar ist genau dann, wenn  \(B \cdot A\) invertierbar ist.
- Es ist \(A\) invertierbar genau dann, wenn  \(A^T\) invertierbar ist, und dann ist  \((A^T)^{-1} = (A^{-1})^T \).

Proposition: Für jede invertierbare \(m \times m\)-Matrix \(A\) gilt:
- Für alle \(m \times n\)-Matrizen \(B, C\) gilt  \(A \cdot B = C\)  genau dann wenn  \(B = A^{-1} \cdot C\)  ist.
- Für alle \(n \times m\)-Matrizen \(B, C\) gilt  \(B \cdot A = C\)  genau dann wenn  \(B = C \cdot A^{-1}\)  ist.

Proposition: Für jede invertierbare \(m \times m\)-Matrix \(A\) über \(\mathbb{K}\) sind äquivalent:
- Die Matrix \(A\) ist invertierbar.
- Es existiert eine  \(m \times m\)-Matrix \(A'\) über \(\mathbb{K}\) mit  \(A' \cdot A = I_m\) (Linksinverse).
- Es existiert eine  \(m \times m\)-Matrix \(A''\)  über \(\mathbb{K}\) mit  \(A \cdot A'' = I_m\) (Rechtsinverse).

Q: Definition Elementarmatrix
A: Eine Matrix mit genau einem Eintrag 1 und allen übrigen Einträgen 0 heisst Elementarmatrix. Genauer betrachtet man für gegebene \(1 \leqslant i \leqslant m\) und \(1 \leqslant j \leqslant n\) die Elementarmatrix \(E_{ij} := (\delta_{ii'} \delta_{jj'})_{\substack{1 \leqslant i' \leqslant m \\ 1 \leqslant j' \leqslant n}} \).

Q: Proposition: Seien \(A\) eine \(m \times n\)-Matrix und \(\lambda \in \mathbb{K}\), und \(1 \leqslant i, j \leqslant m\) mit \(i \neq j\). Dann gilt:
- Addieren von \(\lambda\) mal der \(j\)-ten Zeile zur \(i\)-ten ergibt die Matrix [...].
- Die Matrix \(I_m + \lambda E_{ij}\) ist [...].
A: \((I_m + \lambda E_{ij}) \cdot A\); invertierbar mit der Inversen \(I_m - \lambda E_{ij}\)

Q: Definition Diagonalmatrix
A: Eine \(m \times m\)-Matrix \(D = (d_{ij})_{1 \leqslant i, j \leqslant m}\) mit \(d_{ij} = 0 \) für alle \(i \neq j\) heisst Diagonalmatrix.

Q: Proposition: Seien \(D = (d_{ij})_{1 \leqslant i, j \leqslant m}\) eine Diagonalmatrix und \(A\) eine \(m \times n\)-Matrix. Dann gilt:
- Multiplizieren der \(i\)-ten Zeile von \(A\) mit \(d_{ij}\) für jedes \(i\) ergibt die Matrix [...].
- Die Matrix \(D\) ist invertierbar genau dann, wenn [...].
- Falls die Matrix \(D\) invertierbar ist, so ist ihre Inverse [...].
A: \(D \cdot A\); alle \(d_{ii} \neq 0\) sind; die Diagonalmatrix mit den Diagonaleinträgen \(d_{11}^{-1}, \ldots, d_{mm}^{-1}\)

Q: Definition Permutationsmatrix
A: Eine \(m \times m\)-Matrix, in der jede Zeile und jede Spalte genau eine 1 und sonst nur Einträge 0 besitzt heisst Permutationsmatrix. In Formeln: \(P = (p_{ij})_{1 \leqslant i, j \leqslant m}\) ist eine Permutationsmatrix wenn gilt:
\( \forall i \: \exists j: p_{ij} =1 \wedge \forall j' \neq j: p_{ij'} = 0, \) und
\( \forall j \: \exists i: p_{ij} = 1 \wedge \forall i' \neq i: p_{i'j} = 0.\)

Proposition: Seien \(P\) eine \(m \times m\)-Permutationsmatrix und \(A\) eine \(m \times n\)-Matrix. Dann gilt:
- Die Matrix  \(P \cdot A\)  entsteht aus \(A\) durch eine gewisse Permutation der Zeilen.
- Jede Permutation von Zeilen von \(A\) kann als  Multiplikation mit einer Permutationsmatrx \(P\)  beschrieben werden.
- Die Matrix \(P\) ist  invertierbar mit \(P^{-1} = P^T\).

Q: Proposition: Jede Folge elementarer Zeilen- (bzw. Spalten-) Operationen wird durch [...] repräsentiert.
A: Multiplikation von links (bzw. von rechts) mit einer geeigneten invertierbaren Matrix

Q: Definition Dreiecksmatrix
A: Eine \(m \times m\)-Matrix \(A = (a_{ij})_{1 \leqslant i, j \leqslant m}\) mit \(\ldots\)
- \(\ldots a_{ij} = 0\) für alle \(i > j\) heisst obere Dreiecksmatrix.
- \( \ldots a_{ij} = 0\) für alle \(i < j\) heisst untere Dreiecksmatrix.

Q: Proposition: Für jede obere (bzw. untere) Dreiecksmatrix \(A\) ist \(A^T\) eine [...].
A: untere (bzw. obere) Dreiecksmatrix

Proposition: Betrachte die Matrix \(W := (\delta_{i, m+1-j})_{1 \leqslant i, j \leqslant m}\) mit allen Einträgen auf der Antidiagonalen (Diagonale von rechts oben nach links unten) gleich 1 und allen übrigen Einträgen 0. Dies ist eine Permutationsmatrix, und Linksmultiplikation mit \(W\) bewirkt  die Umkehrung der Reihenfolge der Zeilen.
Weiter gilt \(W^{-1} = W \), und für jede obere (bzw. untere) Dreiecksmatrix \(A\) ist die Matrix \(W \cdot A \cdot W^{-1}\) eine  untere (bzw. obere) Dreiecksmatrix.

Q: Proposition: Für jede obere Dreiecksmatrix mit allen Diagonaleinträgen gleich 1 gilt:
- Sie kann durch eine Folge elementarer Zeilenumformungen der Art "Addiere ein Vielfaches einer späteren Zeile zu einer früheren" in [...] überführt werden.
- Sie ist ein Produkt von Matrizen [...] für gewisse \(\lambda \in \mathbb{K}\) und \(i < j\).
A: die Einheitsmatrix; \( I_m + \lambda E_{ij}\)

Q: Proposition: Jede Links- oder Rechtsinverse einer oberen/unteren Dreiecksmatrix ist [...].
A: wieder eine obere/untere Dreiecksmatrix

Proposition: Für jede Dreiecksmatrix \(A\) der Grösse \(m \times m\) sind äquivalent:
- Die Matrix \(A\) ist invertierbar.
- Es existiert eine \(m \times m\)-Matrix \(A'\) über \(\mathbb{K}\) mit  \(A' \cdot A = I_m\) (Linksinverse).
- Es existiert eine \(m \times m\)-Matrix \(A''\) über \(\mathbb{K}\) mit  \(A \cdot A'' = I_m\) (Rechtsinverse).
- Alle Diagonaleinträge von \(A\) sind  ungleich 0.

Q: Definition Zeilenstufenform (für Matrizen)
A: Eine Matrix heisst in Zeilenstufenform, wenn die von Null verschiedenen Terme in jeder Zeile echt später beginnen als in der Zeile davor.

Q: Fakt: Jede quadratische Matrix in Zeilenstufenform ist [...].
A: eine obere Dreiecksmatrix

Q: Satz: (Dreieckszerlegung) Für jede Matrix \(A\) existieren eine [...] \(P\) und eine [...] \(U\), so dass \(UPA\)[...] hat.
A: Permutationsmatrix; invertierbare untere Dreiecksmatrix; Zeilenstufenform

Satz: (LR-Zerlegung) Für jede invertierbare Matrix \(A\) existieren eine Permutationsmatrix \(P\), eine invertierbare untere Dreiecksmatrix \(L\), und eine  invertierbare obere Dreiecksmatrix \(R\), so dass gilt:
 \[ PA = LR \]

Q: Satz: (Bruhat-Zerlegung) Für jede invertierbare Matrix \(A\) existieren eine [...] \(P\) und [...] \(B\) und \(B'\), so dass gilt:
[...]
A: Permutationsmatrix; invertierbare obere Dreiecksmatrizen; \[A = BPB'\]

Satz: Für jede \(m \times m\)-Matrix sind äquivalent:
- Die Matrix ist invertierbar.
- Die Matrix lässt sich durch elementare Zeilenoperationen in eine invertierbare Dreiecksmatrix überführen.
- Die Matrix lässt sich durch elementare Zeilenoperationen in die  Einheitsmatrix überführen.
- Die Matrix ist ein Produkt von Matrizen der Form  \(I_m + \lambda E_{ij}\) für \(i \neq j\) und Permutationsmatrizen und invertierbaren Diagonalmatrizen.
- Während der Gausselimination bleiben alle Zeilen  ungleich Null.

Proposition: Sei \(A\) eine \(m \times n\)-Matrix, und sei \((A, I_m)\) die durch Zusammensetzen entstehende \(m \times (n+m)\)-Matrix. Seien \(B\) eine \(m \times n\)-Matrix und \(U\) eine \(m \times m\)-Matrix, so dass \((B,U)\) durch eine Folge elementarer Zeilenoperationen aus \((A, I_m)\) entsteht. Dann gilt:
\[B = UA\]
Variante: Seien \(A\) eine \(m \times m\)-Matrix und \(B\) eine \(m \times n\)-Matrix, und sei \((A, B)\) die durch Zusammensetzen entstehende \(m \times (m+n)\)-Matrix. Sei \(C\) eine \(m \times n\)-Matrix, so dass \((I_m, C)\) durch eine Folge elementarer Zeilenoperationen aus \((A, B)\) entsteht. Dann ist \(A\)  invertierbar und \(C\) die eindeutige Lösung der Gleichung \(AC = B\), das heisst:
 \[C = A^{-1}B\]

Q: Folge: Für jede invertierbare \(m \times m\)-Matrix \(A\) führt die vollständige Gauss-Elimination von der Matrix \((A, I_m)\) auf die Matrix [...].
A: \((I_m, A^{-1})\)

Q: Fakt: Jedes lineare Gleichungssystem kann man folgendermassen in Matrixform schreiben:
[...]
für die Matrix \(A = (a_{ij})_{\substack{1 \leqslant i \leqslant m, \\ 1 \leqslant j \leqslant n}}\) und die Spaltenvektoren \(b = (b_i)_{1 \leqslant i \leqslant m}\) und \(x = (x_j)_{1 \leqslant j \leqslant n}\).
A: \[A \cdot x = b\]

Q: Fakt: Oft stellt man das LGS durch die zusammengesetzte \(m \times (n + 1)\)-Matrix dar:
[...]
Dann ist die Gleichung \(A \cdot x = b\) äquivalent zu der Gleichung in Blockmatrixform:
A: \[ (A, b) := \begin{pmatrix} a_{11} & \ldots & a_{1n} & \vert & b_1 \\ \vdots & \ddots & \vdots & \: & \vdots \\ a_{m1} & \ldots & a_{mn} & \vert & b_m \end{pmatrix} \]
Back Extra: \[(A, b) \cdot \begin{pmatrix} x \\ -1 \end{pmatrix} = \underline{0} \]
Die Wirkung jeder elementaren Zeilenumformung auf das Gleichungssystem \(Ax = b\) entspricht der Wirkung derselben elementaren Zeilenumformung auf die Matrix \((A, b)\).

Q: Proposition: Ist \(A\) eine invertierbare quadratische Matrix, so besitzt das lineare Gleichungssystem \(A \cdot x = b\) die eindeutige Lösung [...]
A: \[x = A^{-1} \cdot b\]

Q: Satz: Jede Matrix lässt sich durch eine Folge elementarer Zeilenoperationen und Vertauschen von Spalten für ein geeignetes \(r\) in die folgende Blockmatrixform bringen:
[...]
A: \[ \begin{pmatrix} I_r & C \\ O & O \end{pmatrix} \]

Q: Satz: Ein lineares Gleichungssystem der Form \[ \begin{pmatrix} I_r & C \\ O & O_{\ast, l} \end{pmatrix} \cdot \underline{y} = \begin{pmatrix} \underline{d} \\ \underline{e} \end{pmatrix} \]
mit einem Spaltenvektor \(\underline{d}\) der Länge \(r\) besitzt eine Lösung genau dann, wenn [...] ist.
In diesem Fall ist [...] eine partikuläre Lösung, und die allgemeine Lösung ist
[...]
für einen beliebigen Spaltenvektor \(\underline{z}\) der Länge \(l\).
A: der Spaltenvektor \(\underline{e}\) gleich Null; \( \underline{y} = \begin{pmatrix} \underline{d} \\ \underline{0} \end{pmatrix} \); \[ \underline{y} = \begin{pmatrix} \underline{d} \\ \underline{0} \end{pmatrix} + \begin{pmatrix} -C \\ I_l \end{pmatrix} \cdot \underline{z} = \begin{pmatrix} \underline{d} - C \underline{z} \\ \underline{z} \end{pmatrix} \]