Study Guides / Lineare Algebra / Übungsstunde 11
ÜBUNGSSTUNDE 11 · ETH ZURICH · HS19 · linalg

Kleinste Quadrate, Permutationen und Determinanten

Methode der kleinsten Quadrate, Normalengleichung, Permutation, Symmetrische Gruppe, Determinante, Satz von Kirchhoff

SB
Steven Battilana Quant · ex-ETH

Erinnerung: Orthogonale und unitäre Matrizen (II)

Definition

Die Matrix A∈En×nA \in \mathbb{E}^{n \times n} ist orthogonal/unitär genau dann, wenn die Zeilen von AA paarweise orthonormal (bezüglich dem Standardskalarprodukt) zueinander stehen und die Spalten von AA paarweise orthonormal (bezüglich dem Standardskalarprodukt) zueinander stehen.

Definition

Eine komplexe n×nn \times n - Matrix AA heisst unitär, falls AHA=AAH=𝟙A^HA = AA^H = \text{𝟙}. Eine reelle n×nn \times n - Matrix AA heisst orthogonal, falls ATA=AAT=𝟙A^TA = AA^T = \text{𝟙}.

Bemerkung

Der Begriff der orthogonalen/unitären Matrizen A∈En×nA \in \mathbb{E}^{n \times n} ist unabhängig vom Skalarprodukt (per Definition vom euklidischen Skalarprodukt, d.h. AAH=AHA=𝟙AA^H = A^HA = \text{𝟙}). Der Begriff der orthogonalen Vektoren ist hingegen abhängig vom betrachteten Skalarprodukt ⟨⋅,⋅⟩V\langle \cdot, \cdot \rangle_V.

Bemerkung

Warnung: Diese Bemerkung ist ein Gedankenspiel und dient zur Vertiefung des bereits erworbenen Verständnisses. Würde man die Definition von der orthogonalen/unitären Matrix auf ein allgemeines Skalarprodukt ⟨⋅,⋅⟩M\langle \cdot, \cdot \rangle_M erweitern, würde man folgendes erhalten:

AMAH=AHMA=𝟙AMA^H = A^HMA = \text{𝟙}

Die Matrix MM des MM-Skalarprodukts wird wie folgt berechnet, falls das Skalarprodukt bereits gegeben ist:

M=(⟨e1,e1⟩M⟨e1,e2⟩M⋯⟨e1,en⟩M⟨e2,e1⟩M⟨e2,e2⟩M⋱⋮⋮⋱⋱⟨en−1,en⟩M⟨en,e1⟩M⋯⟨en,en−1⟩M⟨en,en⟩M)M = \begin{pmatrix} \langle e_1, e_1 \rangle_M & \langle e_1, e_2 \rangle_M & \cdots & \langle e_1, e_n \rangle_M\\ \langle e_2, e_1 \rangle_M & \langle e_2, e_2 \rangle_M & \ddots & \vdots\\ \vdots & \ddots & \ddots & \langle e_{n-1}, e_n \rangle_M\\ \langle e_n, e_1 \rangle_M & \cdots & \langle e_n, e_{n-1} \rangle_M & \langle e_n, e_n \rangle_M \end{pmatrix}
Bemerkung

Für das Standard-Skalarprodukt würde man dann folgendes erhalten:

A𝟙AH=AH𝟙A=𝟙⇔AAH=AHA=𝟙A\text{𝟙}A^H = A^H\text{𝟙}A = \text{𝟙} \Leftrightarrow AA^H = A^HA = \text{𝟙}
Beispiel 1

Betrachte das MM-Skalarprodukt für symmetrisch positiv definites M∈Rn×nM \in \mathbb{R}^{n \times n}:

⟨v,w⟩M:=vTMw\langle v,w \rangle_M := v^T M w

Dann steht vv senkrecht auf ww bezüglich ⟨⋅,⋅⟩M⇔vTMw=0\langle \cdot, \cdot \rangle_M \Leftrightarrow v^T M w = 0.

Beispiel 2

Gegeben: ONB (bezüglich dem Standardskalarprodukt) A, B\mathcal{A},\, \mathcal{B} mit

A={(10),(01)},B={(3545),(−4535)}.\mathcal{A} = \left \{ \begin{pmatrix} 1\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1 \end{pmatrix} \right \}, \quad \mathcal{B} = \left \{ \begin{pmatrix} \frac{3}{5}\\ \frac{4}{5} \end{pmatrix}, \begin{pmatrix} -\frac{4}{5}\\ \frac{3}{5} \end{pmatrix} \right \}.

Gesucht: TBAT_B^A und TABT_A^B

Lösung anzeigenLösung ausblenden TAB=(35−454535) ist orthogonal mit (TAB)−1=(TAB)TT_A^B = \begin{pmatrix} \frac{3}{5} & -\frac{4}{5}\\ \frac{4}{5} & \frac{3}{5} \end{pmatrix} \text{ ist orthogonal mit } (T_A^B)^{-1} = (T_A^B)^TTBA=(TAB)−1=(TAB)T=(3545−4535)T_B^A = (T_A^B)^{-1} = (T_A^B)^T = \begin{pmatrix} \frac{3}{5} & \frac{4}{5}\\ -\frac{4}{5} & \frac{3}{5} \end{pmatrix}

⇒\Rightarrow Bei orthogonalen/unitären Matrizen ist es einfach die Inverse zu bestimmen, d.h. hat man TABT_A^B erhält man sofort TBAT_B^A.

Methode der kleinsten Quadrate

Bemerkung Idee

Wir betrachten für A∈Em×n,  m>nA \in \mathbb{E}^{m \times n}, \,\, m>n das überbestimmte LGS Ax=yAx=y. Oftmals haben solche LGS keine (exakten) Lösungen, daher löst man sie mit Hilfe von Näherungsverfahren, wobei ein Fehler entsteht. Die Methode der kleinsten Quadrate (manchmal auch als lineare Ausgleichsrechnung bezeichnet) versucht den Fehler zu minimieren. Der Residuenvektor (das Residuum, der Fehler) r:=y−Axr := y - Ax soll minimale euklidische Norm haben, d.h. wir suchen x∈Rnx \in \mathbb{R}^n, so dass

∥r∥22=∑k=1m∣rk∣2=∑k=1m∣yk−∑l=1naklxl∣2\left\lVert r \right\rVert_2^2 = \sum_{k=1}^m |r_k|^2 = \sum_{k=1}^m | y_k -\sum_{l=1}^n a_{kl} x_l |^2

minimal ist.

Bemerkung

Die Methode der kleinsten Quadrate lässt sich auf allgemeine Normen erweitern. (Beispiel: HS17 S10A2)

Bemerkung

Betrachte für A∈Em×n,  m>nA \in \mathbb{E}^{m \times n}, \,\, m>n das überbestimmte LGS

Ax=!yAx\stackrel{!}{=}y

Methode der kleinsten Quadrate: Finde x∈Enx \in \mathbb{E}^n, so dass Residuum r=y−Axr = y - Ax minimale Norm hat. Formal ausgedrückt:

arg min⁡x∈En∥y−Ax∥2\operatorname*{arg\,min} \limits_{x \in \mathbb{E}^n} \left\lVert y - Ax \right\rVert_2

Lösungsansatz:

  1. Normalengleichung
  2. QR-Zerlegung

Normalengleichung

Lemma 7.3

Sind die Kolonnen einer A∈Em×nA \in \mathbb{E}^{m \times n} Matrix linear unabhängig, d.h. ist rang(A)=n(≤m)(A) = n (\leq m), so ist AHAA^HA regulär.

Satz 7.4

Die Orthogonalprojektion PA:Em→P_A : \mathbb{E}^m \to Im(A)⊂Em(A) \subset \mathbb{E}^m auf den Kolonnenraum Im(A)(A) einer A∈Em×nA \in \mathbb{E}^{m \times n} Matrix mit Rang n(≤m)n (\leq m) ist gegeben durch:

PA:=A(AHA)−1AH.P_A := A(A^HA)^{-1} A^H.
Satz 7.6

Für eine Orthogonalprojektion P∈En×nP \in \mathbb{E}^{n \times n} gilt:

∥y−Py∥2=min⁡z∈Im(P)∥y−z∥2,∀y∈En\left\lVert y - Py \right\rVert_2 = \min \limits_{z \in \text{Im}(P)} \left\lVert y - z \right\rVert_2, \quad \forall y \in \mathbb{E}^n
Bemerkung

Angenommen die Kolonnen von A∈Em×nA \in \mathbb{E}^{m \times n} sind linear unabhängig, also ker(A)={0}(A)=\{0\} gilt und AHAA^HA gemäss Lemma 7.3 regulär ist. Auf Grund von Satz 7.6 wissen wir, dass ∥r∥\left\lVert r \right\rVert minimal ist, wenn gilt:

Ax=PAy⟹Satz 7.4Ax=A(AHA)−1AHy⟹ker(A)={0}x=(AHA)−1AHy⇒AHAx=AHyNormalengleichung\begin{aligned} Ax = P_Ay &\stackrel{\text{Satz 7.4}}{\Longrightarrow} Ax = A(A^HA)^{-1} A^Hy\\ &\stackrel{\text{ker}(A)=\{0\}}{\Longrightarrow} x = (A^HA)^{-1}A^Hy\\ &\Rightarrow A^HAx = A^Hy \quad \text{\textit{Normalengleichung}} \end{aligned}
Definition Pseudoinverse
A†:=(AHA)−1AH⇒A†A=(AHA)−1AHA=𝟙⟹ABERAA†=A(AHA)−1AH≠im Allgemeinen𝟙\begin{aligned} A^\dag &:= (A^HA)^{-1}A^H\\ &\Rightarrow A^\dag A = (A^HA)^{-1}A^HA = \text{𝟙}\\ &\stackrel{\text{ABER}}{\Longrightarrow} AA^\dag = A (A^HA)^{-1}A^H \stackrel{\text{im Allgemeinen}}{\neq} \text{𝟙} \end{aligned}
Satz 7.7

Es sei A∈Em×nA \in \mathbb{E}^{m \times n}, rang(A)=n≤m,  y∈Em(A) = n \leq m, \,\, y \in \mathbb{E}^m. Dann hat das überbestimmte Gleichungssystem Ax=yAx = y eine eindeutig bestimmte Lösung xx im Sinne der kleinsten Quadrate, d.h. xx mit

∥y−Ax∥22=min⁡x~∈En∥y−Ax~∥22,x∈En(1)\left\lVert y - Ax \right\rVert_2^2 = \min \limits_{\widetilde{x} \in \mathbb{E}^n} \left\lVert y - A\widetilde{x} \right\rVert_2^2, \quad x \in \mathbb{E}^n \tag{1}

xx kann berechnet werden durch Lösen des regulären Systems der Normalgleichungen (Bemerkung nach Satz 7.6). Der Residuenvektor r⊥r \perp Im(A)(A).

Beispiel 3

Gegeben:

A=(01132−2),⇒m=3>2=n,y=(224)A = \begin{pmatrix} 0 & 1\\ 1 & 3\\ 2 & -2 \end{pmatrix}, \quad \Rightarrow \quad m=3 > 2=n, \quad y = \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}

Gesucht: Bestimme mit Hilfe der Normalengleichung x=(x1,x2)Tx = (x_1, x_2)^T, so dass ∥r∥22=∥y−Ax∥22\left\lVert r \right\rVert_2^2 = \left\lVert y - Ax \right\rVert_2^2 minimal ist bezüglich dem Standard-Skalarprodukt ⟨x,y⟩=xHy\langle x,y \rangle = x^Hy.

Lösung anzeigenLösung ausblenden Ax=y⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)ATA=(01213−2)(01132−2)=(5−1−114)(ATA)−1=15⋅14−(−1)⋅(−1)(14115)=169(14115)ATy=(01213−2)(224)=(100)⟹(∗)x=169(14115)(100)=169(14010)\begin{aligned} Ax = y &\Rightarrow A^TAx = A^Ty\\ &\Leftrightarrow x = (A^TA)^{-1}A^Ty \quad (*)\\ A^TA &= \begin{pmatrix} 0 & 1 & 2\\ 1 & 3 & -2 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 3\\ 2 & -2 \end{pmatrix} = \begin{pmatrix} 5 & -1\\ -1 & 14 \end{pmatrix}\\ (A^TA)^{-1} &= \frac{1}{5 \cdot 14 - (-1) \cdot (-1)} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix} = \frac{1}{69} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix}\\ A^Ty &= \begin{pmatrix} 0 & 1 & 2\\ 1 & 3 & -2 \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix} = \begin{pmatrix} 10\\ 0 \end{pmatrix}\\ \stackrel{(*)}{\Longrightarrow} x &= \frac{1}{69} \begin{pmatrix} 14 & 1\\ 1 & 5 \end{pmatrix} \begin{pmatrix} 10\\ 0 \end{pmatrix} = \frac{1}{69} \begin{pmatrix} 140\\ 10 \end{pmatrix} \end{aligned}
Beispiel 4

Gegeben: Lege die bestmögliche Gerade (d.h. der Abstand zwischen Punkt und Gerade ist minimal) durch P1,P2,P3,P4P_1, P_2, P_3, P_4 wobei

P1=(0,6),  P2=(1,0),  P3=(2,0),  P4=(3,−4)P_1 = (0, 6), \,\, P_2 = (1, 0), \,\, P_3 = (2,0), \,\, P_4 = (3,-4)

Gesucht: Geradengleichung y=ax+b,y = ax + b, wobei a,b∈Ra,b \in \mathbb{R} unbekannte Parameter sind.

Lösung anzeigenLösung ausblenden Pi=(x,y)⇒{6=a⋅0+b0=a⋅1+b0=a⋅2+b−4=a⋅3+b⇔(01112131)⏟=A(ab)⏟=x=(600−4)⏟=yP_i = (x,y) \Rightarrow \begin{cases} 6 = a \cdot 0 + b\\ 0 = a \cdot 1 + b\\ 0 = a \cdot 2 + b\\ -4 = a \cdot 3 + b \end{cases} \quad \Leftrightarrow \quad \underbrace{ \begin{pmatrix} 0 & 1\\ 1 & 1\\ 2 & 1\\ 3 & 1 \end{pmatrix}}_{=A} \underbrace{ \begin{pmatrix} a\\ b \end{pmatrix}}_{=x} = \underbrace{ \begin{pmatrix} 6\\ 0\\ 0\\ -4 \end{pmatrix}}_{=y}Ax=y⇒ATAx=ATy⇔x=(ATA)−1ATy(∗)ATA=(01231111)(01112131)=(14664)(ATA)−1=114⋅4−6⋅6(4−6−614)=120(4−6−614)=110(2−3−37)ATy=(01231111)(600−4)=(−122)\begin{aligned} Ax = y &\Rightarrow A^TAx = A^Ty\\ &\Leftrightarrow x = (A^TA)^{-1}A^Ty \quad (*)\\ A^TA &= \begin{pmatrix} 0 & 1 & 2 & 3\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\\ 2 & 1\\ 3 & 1 \end{pmatrix} = \begin{pmatrix} 14 & 6\\ 6 & 4 \end{pmatrix}\\ (A^TA)^{-1} &= \frac{1}{14 \cdot 4 - 6 \cdot 6} \begin{pmatrix} 4 & -6\\ -6 & 14 \end{pmatrix} = \frac{1}{20} \begin{pmatrix} 4 & -6\\ -6 & 14 \end{pmatrix} = \frac{1}{10} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix}\\ A^Ty &= \begin{pmatrix} 0 & 1 & 2 & 3\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 6\\ 0\\ 0\\ -4 \end{pmatrix} = \begin{pmatrix} -12\\ 2 \end{pmatrix} \end{aligned}⟹(∗)x=(ATA)−1ATy=110(2−3−37)(−122)=15(2−3−37)(−61)=15(−1525)=(−35)⟹Gerade:  y=−3x+5\begin{aligned} \stackrel{(*)}{\Longrightarrow} x &= (A^TA)^{-1}A^Ty\\ &= \frac{1}{10} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix} \begin{pmatrix} -12\\ 2 \end{pmatrix}\\ &= \frac{1}{5} \begin{pmatrix} 2 & -3\\ -3 & 7 \end{pmatrix} \begin{pmatrix} -6\\ 1 \end{pmatrix}\\ &= \frac{1}{5} \begin{pmatrix} -15\\ 25 \end{pmatrix}\\ &= \begin{pmatrix} -3\\ 5 \end{pmatrix}\\ \Longrightarrow \quad \text{Gerade:} \,\, y &= -3x + 5 \end{aligned}
Bemerkung Normalengleichung vs. QR-Zerlegung

Normalengleichung

  • Pro:
    • "schön" um von Hand zu rechnen
    • AHAA^HA ist hermitesch positiv definit ⇒\Rightarrow kann für Cholesky-Zerlegung ausgenutzt werden
  • Con:
    • Wenn AA schlecht konditioniert ist, ist AHAA^HA quadratisch schlecht konditioniert. ⇒\Rightarrow Cholesky liefert unbrauchbare Resultate (Rundungsfehler massiv verstärkt, Implementierung instabil)

QR-Zerlegung

  • Pro:
    • kann numerisch stabil implementiert werden (Verfahren hängt weniger von der Kondition ab)
    • Die Spalten von QQ bilden eine ONB von Im(A)(A) (die Orthogonalprojektion auf Im(A)(A) ist QQHQQ^H)
  • Con:
    • "hässlich", um von Hand zu rechnen (Wurzeln)

Symmetrische Gruppe

Definition

Eine Permutation ist eine bijektive Abbildung:

p:{1,...,n}→{1,...,n}p: \{1, ..., n\} \to \{1, ..., n\}
Definition

Die Menge aller Permutationen heisst symmetrische Gruppe SnS_n.

Definition

Eine Permutation, welche nur zwei Elemente vertauscht, heisst Transposition.

Satz

Jede Permutation kann als Produkt (Hintereinanderschaltung von Abbildungen) von Transpositionen geschrieben werden.

Bemerkung

Die Darstellung einer Permutation als Produkt von Transpositionen ist nicht eindeutig. Aber die Anzahl benötigter Transpositionen ist eindeutigerweise entweder gerade oder ungerade.

Definition

Ist p∈Snp \in S_n, so nennt man jedes Paar i,j∈{1,...,n}i,j \in \{1, ..., n\} mit

i<jaberp(i)>p(j),i<j \quad \text{aber} \quad p(i) > p(j),

einen Fehlstand von pp.

Beispiel 5

Gegeben:

p=[123231]p = \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{bmatrix}

Gesucht: Fehlstände von pp

Definition

Das Signum einer Permutation ist definiert als

sign(p)=(−1)k={1,falls p eine gerade Anzahl k von Fehlsta¨nden hat−1,falls p eine ungerade Anzahl k von Fehlsta¨nden hat.\text{sign}(p) = (-1)^k = \begin{cases} 1, \hspace{0.5cm} \text{falls } p \text{ eine \textit{gerade} Anzahl } k \text{ von Fehlständen hat}\\ -1, \hspace{0.2cm} \text{falls } p \text{ eine \textit{ungerade} Anzahl } k \text{ von Fehlständen hat.} \end{cases}
Definition

Man nennt p∈Snp \in S_n:

  • gerade, falls sign(p)=+1(p) = +1,
  • ungerade, falls sign(p)=−1(p) = -1.

Determinanten

Definition

Die Determinante ist eine Abbildung:

det:  En×n→EA↦det(A)=∑p∈Snsign(p)⋅∏i=1naip(i)\begin{aligned} \text{det}: \; \mathbb{E}^{n \times n} &\to \mathbb{E}\\ A &\mapsto \text{det}(A) = \sum_{p \in S_n} \text{sign}(p) \cdot \prod_{i=1}^n a_{ip(i)} \end{aligned}
Bemerkung

In der obigen Definition summieren wir über n!n! Summanden.

Bemerkung Tricks um Determinanten zu berechnen
  • 1×11 \times 1-Matrix: det(a11)=∣a11∣=a11\quad \text{det}(a_{11}) = |a_{11}| = a_{11}
  • 2×22 \times 2-Matrix:
det(abcd)=∣abcd∣=ad−bc\text{det} \begin{pmatrix} a & b\\ c & d \end{pmatrix} = \begin{vmatrix} a & b\\ c & d \end{vmatrix} = ad-bc
  • 3×33 \times 3-Matrix (Regel von Sarrus):
det(abcdefghi)=∣abcdefghi∣=aei+bfg+cdh−gec−hfa−idb\text{det} \begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix} = \begin{vmatrix} a & b & c\\ d & e & f\\ g & h & i \end{vmatrix} = aei + bfg + cdh - gec - hfa - idb

Es wird das folgende Muster bei der Regel von Sarrus angewendet:

+++abcabdefdeghigh−−−\begin{array}{ccc:cc} + & + & + & & \\ a & b & c & a & b\\ d & e & f & d & e\\ g & h & i & g & h\\ - & - & - & & \end{array}
Bemerkung

Für eine n×nn \times n-Matrix kann man die Determinante über die Definition mit Permutationen berechnen, aber ist sehr ineffizient (Aufwand proportional zu n!n!).

Satz

Sei A~\widetilde{A} die Zeilenstufenform von AA (d.h. A~\widetilde{A} ist eine obere/untere Dreiecksmatrix), welche man durch den Gauss-Algorithmus aus AA berechnet hat. Sei k∈N0k \in \mathbb{N}_0 die Anzahl ausgeführter Zeilenvertauschungen:

⇒det(A)=(−1)k⋅det(A~)=(−1)k∏i=1nA~ii,wobei   ∏i=1nA~ii das Produkt der Diagonaleintra¨ge ist.\begin{aligned} \Rightarrow \quad &\text{det}(A) = (-1)^k \cdot \text{det}(\widetilde{A}) = (-1)^k \prod_{i=1}^n \widetilde{A}_{ii},\\ &\text{wobei } \; \prod_{i=1}^n \widetilde{A}_{ii} \text{ das Produkt der Diagonaleinträge ist.} \end{aligned}
Satz

Laplace’scher Entwicklungssatz

Sei A∈En×nA \in \mathbb{E}^{n \times n} und Aij′∈E(n−1)×(n−1)A'_{ij} \in \mathbb{E}^{(n-1) \times (n-1)} die Streichmatrix ohne ii-te Zeile und jj-te Spalte.

⇒Entwicklung nach der i-ten Zeile:  det(A)=∑j=1n(−1)i+j⋅aij⋅det(Aij′)\Rightarrow \quad \text{Entwicklung nach der } i\text{-ten Zeile: \hspace{0.5cm} det} (A) = \sum_{j=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \text{det} (A'_{ij})⇒Entwicklung nach der j-ten Spalte:  det(A)=∑i=1n(−1)i+j⋅aij⋅det(Aij′).\Rightarrow \quad \text{Entwicklung nach der } j\text{-ten Spalte: \hspace{0.25cm} det} (A) = \sum_{i=1}^n (-1)^{i+j} \cdot a_{ij} \cdot \text{det} (A'_{ij}).
Beispiel 6

Gegeben:

A=(1203−10105)A = \begin{pmatrix} 1 & 2 & 0\\ 3 & -1 & 0\\ 1 & 0 & 5 \end{pmatrix}

Gesucht: det(A)\text{det}(A)

Satz Axiomatischer Zugang, Eigenschaften der Determinante

Die Abbildung

det:En×n→EA↦det(A)\begin{aligned} \text{det}: \mathbb{E}^{n \times n} &\to \mathbb{E}\\ A &\mapsto \text{det}(A) \end{aligned}

heisst Determinante, falls folgende Eigenschaften gelten: Sei A∈En×nA \in \mathbb{E}^{n \times n} eine quadratische Matrix, dann gilt:

(D1) det(𝟙)=1\text{det}(\text{𝟙}) = 1

(D2) Hat AA zwei gleiche oder linear abhängige Zeilen/Spalten, so ist

det(A)=0\text{det}(A)=0

(D3) Linearität in jeder Zeile/Spalte (in der Literatur auch nn-Linearität genannt)

det(v1,...,λvi+w,...,vn)=λdet(v1,...,vi,...,vn)+det(v1,...,w,...,vn)\text{det}(v_1, ..., \lambda v_i + w, ..., v_n) = \lambda \text{det}(v_1, ..., v_i, ..., v_n) + \text{det}(v_1, ..., w, ..., v_n)

Die Determinante hat folgende weitere Eigenschaften, die sich aus den ersten drei herleiten lassen:

(D4) det(λA)=λndet(A)\text{det}(\lambda A) = \lambda^n \text{det}(A) für alle λ∈E\lambda \in \mathbb{E}

(D5) Ist eine Zeile/Spalte gleich Null, so ist:

det(A)=0\text{det}(A)=0

(D6) Vertauscht man zwei Zeilen/Spalten von AA, so ändert sich das Vorzeichen von det(A)\text{det}(A):

det(v1,...,vi,...,vj,...,vn)=−det(v1,...,vj,...,vi,...,vn)\text{det}(v_1, ..., v_i, ..., v_j, ..., v_n) = - \text{det}(v_1, ..., v_j, ..., v_i, ..., v_n)

(D7) Entsteht BB aus AA durch Addition des λ\lambda-fachen (λ≠0\lambda \neq 0) der ii-ten zur jj-ten Zeile/Spalte, dann ist:

det(A)=det(B)\text{det}(A) = \text{det}(B)

(D8) Ist AA eine obere/untere Dreiecksmatrix, so ist:

det(A)=∏i=1naii\text{det}(A) = \prod_{i=1}^n a_{ii}

(D9) det(AB)=det(A)det(B)\text{det}(AB) = \text{det}(A)\text{det}(B)

(D10) det(A‾)=det(A)‾\text{det}(\overline{A}) = \overline{\text{det}(A)}

(D11) det(A−1)=1det(A)\text{det}(A^{-1}) = \frac{1}{\text{det}(A)}

(D12) det(AT)=det(A)\text{det}(A^T) = \text{det}(A)

(D13) Ist

A=(A1A20A3)so ist:det(A)=det(A1)⋅det(A3)A = \begin{pmatrix} A_1 & A_2\\ 0 & A_3 \end{pmatrix} \quad \text{so ist:} \quad \text{det}(A) = \text{det}(A_1) \cdot \text{det}(A_3)

und analog gilt:

det(B1∗⋯∗0⋱⋱⋮⋮⋱⋱∗0⋯0Bn)=det(B1)⋅...⋅det(Bn)\text{det} \begin{pmatrix} B_1 & * & \cdots & *\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & *\\ 0 & \cdots & 0 & B_n \end{pmatrix} = \text{det}(B_1) \cdot ... \cdot \text{det}(B_n)

(D14) det(A)=∏i=1nλi\text{det}(A) = \prod \limits_{i=1}^n \lambda_i, wobei λi\lambda_i ein Eigenwert von AA ist.

(D15) Definition der Determinante ist basisinvariant:

det(B)=det(S−1BS)=1det(S)⋅det(B)⋅det(S)\text{det}(B) = \text{det}(S^{-1} B S) = \frac{1}{\text{det}(S)} \cdot \text{det}(B) \cdot \text{det}(S)

(D16) Orthogonale/unitäre Matrizen AA haben:

Orthogonale AA:

det(A)=±1,weil    det(AAT)=det(A)det(AT)=det(A)det(A)=det(A)2=!det(𝟙)=1\begin{aligned} \text{det}(A) &= \pm 1,\\ \text{weil} \;\; \text{det}(AA^T) &= \text{det}(A) \text{det}(A^T)\\ &= \text{det}(A) \text{det}(A)\\ &= \text{det}(A)^2\\ &\stackrel{!}{=} \text{det}(\text{𝟙})=1 \end{aligned}

Unitäre AA:

∣det(A)∣=1,weil    det(AAH)=det(A)det(A‾T)=det(A)det(A)‾=∣det(A)∣2=!det(𝟙)=1\begin{aligned} |\text{det}(A)| &= 1,\\ \text{weil} \;\; \text{det}(AA^H) &= \text{det}(A) \text{det}(\overline{A}^T)\\ &= \text{det}(A) \overline{\text{det}(A)}\\ &= |\text{det}(A)|^2\\ &\stackrel{!}{=} \text{det}(\text{𝟙})=1 \end{aligned}

(D17) Für hermitesche Matrizen (AH=A)(A^H=A) haben wir:

det(A)∈R,weil  det(AH)=det(A‾T)=det(A‾)=det(A)‾=!det(A)\begin{aligned} \text{det}(A) \in \mathbb{R},\\ \text{weil} \,\, \text{det}(A^H) &= \text{det}(\overline{A}^T)\\ &= \text{det}(\overline{A})\\ &= \overline{\text{det}(A)}\\ &\stackrel{!}{=} \text{det}(A) \end{aligned}
Satz
  • det(A)=0⇔A\text{det}(A) = 0 \Leftrightarrow A nicht invertierbar ⇔\Leftrightarrow rang(A)<n(A) < n
  • Ax=bAx = b eindeutig lösbar ⇔det(A)≠0\Leftrightarrow \text{det}(A) \neq 0.
Definition

Zu jedem Element akla_{kl} einer n×nn \times n-Matrix AA werde die (n−1)×(n−1)(n-1) \times (n-1)-Untermatrix A[k,l]A_{[k,l]} definiert durch Streichen der Zeile kk und der Kolonne ll von AA. Der Kofaktor κkl\kappa_{kl} von akla_{kl} ist dann die Zahl:

κkl:=(−1)k+l det(A[k,l]).\kappa_{kl} := (-1)^{k+l} \text{ det}\left(A_{[k,l]} \right).
Definition

Der Grad djd_j des Knotens jj ist wie folgt definiert:

dj:=∑i=1n(A)ij.d_j := \sum_{i=1}^n (A)_{ij}.
Satz Satz von Kirchhoff

Der Satz von Kirchhoff besagt, dass die Anzahl der aufspannenden Teilbäume eines Graphen gleich dem Wert eines beliebigen Kofaktors von LL ist, wobei LL wie folgt definiert ist:

L:=D−Amit D=diag(d1,...,dn),    di=^ Grad des Knotens iundA=^ Adjazenzmatrix mit (Aij)={1,falls i mit j durch eine Kante verbunden ist0, sonst.\begin{aligned} L &:= D-A\\ &\text{mit } \quad D = \text{diag}(d_1, ..., d_n), \;\; d_i \mathrel{\hat{=}} \text{ Grad des Knotens } i\\ &\text{und} \quad A \mathrel{\hat{=}} \text{ Adjazenzmatrix mit } \left( A_{ij} \right) = \begin{cases} 1, &\text{falls $i$ mit $j$ durch eine Kante verbunden ist}\\ 0, &\text{ sonst}. \end{cases} \end{aligned}