222

Kapitel 12

Lineare Algebra

12.1 Vektorräume

↓20.1.04

Definition 12.1: (Vektorräume)

Ein Vektorraum V über dem Skalarenkörper K ist eine nichtleere Menge von Objekten (Vektoren genannt). Es muss eine Addition

v_{1}, v_{2} ∈ V ⇒ v_{1} + v_{2} ∈ V

mit den Eigenschaften

v_{1} + v_{2} = v_{2} + v_{1} (Kommutativität),
(v_{1} + v_{2}) + v_{3} = v_{1} + (v_{2} + v_{3}) (Assoziativität)

für alle v_{i} ∈ V gegeben sein, es muss ein neutrales Element 0 (der Nullvektor) mit v + 0 = v ∀v ∈ V existieren, zu jedem v ∈ V muss es einen negativen Vektor −v mit v + (−v) = 0 geben.

Weiterhin muss jedes v ∈ V mit jedem ”Skalar“ λ ∈ K multiplizierbar sein, so dass λ · v wieder in V liegt und

λ_{1} · (λ_{2} · v) = (λ_{1} · λ_{2}) · v (Assoziativität),

1 · v = v (neutrales Element der Multiplikation),

(λ_{1} + λ_{2}) · v = λ_{1} · v + λ_{2} · v (Distributivität)

für alle λ_{1}, λ_{2} ∈ K und v ∈ V gilt. Hierbei sei 1 das neutrale Element der Multiplikation im Körper K.

Bemerkung 12.2: Als Skalarenkörper K interessiert uns hier nur ℝ oder ℂ, wir sprechen dann von einem ”reellen“ oder einem ”komplexen“ Vektorraum.

224 KAPITEL 12. LINEARE ALGEBRA

Beispiel 12.3: 1) Der Raum^{1}

ℝ^{n} := {(x_{1}, x_{2}, …, x_{n})^{T} ; x_{1}, … x_{n} ∈ ℝ}

bzw.

ℂ^{n} := {(x_{1}, x_{2}, …, x_{n})^{T} ; x_{1}, … x_{n} ∈ ℂ}

mit den Operationen

( x_{1} ; ⋮ ; x_{n} ) + ( y_{1} ; ⋮ ; y_{n} ) = ( x_{1} + y_{1} ; ⋮ ; x_{n} + y_{n} )

und

λ · ( x_{1} ; ⋮ ; x_{n} ) = ( λ · x_{1} ; ⋮ ; λ · x_{n} )

ist ein reeller bzw. komplexer Vektorraum.

2) Die Menge

\{λ_{1} · ( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ) + λ_{2} · ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ); λ_{1}, λ_{2} ∈ ℝ\} ⊂ ℝ^{3}

mit den Operationen des ℝ^{3} (Addition und skalare Multiplikation) ist ein in den ℝ^{3} eingebetteter Vektorraum. Man nennt diese auch einen ”Unterraum“ des ℝ^{3}. Es handelt sich um eine den Ursprung enthaltende Ebene im ℝ^{3}. Man beachte, dass die Summe zweier Ebenenvektoren wieder in der Ebene liegt.

3) Der Raum der stetigen Funktionen

C([0, 1]) = {f : [0, 1] → ℝ; f ist eine stetige Funktion}

mit den Operationen der punktweisen Addition

f + g : x → f(x) + g(x)

und der Multiplikation

λ · f : x → λ · f(x)

(x_{1}, …, x_{n})^{T} := ( x_{1} ; ⋮ ; x_{n} )

1Vektoren des ℝ^{n} bzw. ℂ^{n} sind bei uns immer Spalten. Aus Platzgründen verwendet man im Text lieber eine Zeilendarstellung (x_{1}, …, x_{n}). Damit die Bezeichnungen konsistent sind, wird das Symbol T (Transposition)

benutzt, das anzeigt, dass dieser Vektor als Spalte zu interpretieren ist.

ist ein reeller Vektorraum (man beachte, dass die Summe stetiger Funktionen wieder stetig ist und dass mit f auch λ · f stetig ist).

Notation 12.4:

Für allgemeine Vektorräume V benutzen wir die Notation v ∈ V ohne Vektorpfeil über dem Vektor v. Für V = ℝ^{n} bzw. V = ℂ^{n} schreiben wir Vektoren mit einem Vektorpfeil (Physikernotation), also v⃗ ∈ ℝ^{n} bzw. v⃗ ∈ ℂ^{n}.

Definition 12.5: (lineare Unabhängigkeit)

Eine Menge von Vektoren v_{1}, …, v_{n} eines Vektorraums heißt ”linear unabhängig“, wenn eine Linearkombination ∑_{i=1}^{n} λ_{i} · v_{i} nur dann der Nullvektor sein kann, wenn alle ”Linearkoeffizienten“ λ_{i} verschwinden:

∑_{i=1}^{n} λ_{i} · v_{i} = 0 ⇒ λ_{1} = … = λ_{n} = 0.

Sind Vektoren nicht linear unabhängig, nennt man sie ”linear abhängig“.

Bemerkung 12.6: In einer Menge linear unabhängiger Vektoren {v_{1}, …, v_{n}} kann keiner der Vektoren 0 sein. Angenommen, v_{1} = 0. Dann wäre

λ_{1} · v_{1} + … + λ_{n} · v_{n} = 0

für beliebiges λ_{1} und λ_{2} = … = λ_{n} = 0 erfüllt.

Beispiel 12.7: Die Vektoren

v⃗_{1} = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) , v⃗_{2} = ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ) , v⃗_{3} = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} )

sind linear unabhängige Vektoren im ℝ^{3}, denn aus

∑_{i=1}^{3} λ_{1} · v⃗_{i} = λ_{1} · ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ) + λ_{2} · ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ) + λ_{3} · ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ) = ( \begin{matrix}λ_{1} \\ λ_{2} \\ λ_{3} \end{matrix} ) =^{(!)} 0 = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} )

folgt sofort λ_{1} = λ_{2} = λ_{3} = 0. Die Vektoren

v⃗_{1} = ( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ) , v⃗_{2} = ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ) , v⃗_{3} = ( \begin{matrix}1 \\ 2 \\ 1 \end{matrix} )

hingegen sind nicht linear unabhängig, denn z.B. die Linearkombination

v⃗_{1} + v⃗_{2} − v⃗_{3} = 0

verschwindet, obwohl die Linearfaktoren λ_{1} = λ_{2} = 1, λ_{3} = −1 nicht verschwinden.

Definition 12.8: (von Vektoren aufgespannte Räume)

Seien v_{1}, …, v_{n} Vektoren eines Vektorraums über dem Skalarenkörper K. Die Menge der Vektoren

span(v_{1}, …, v_{n}) = {∑_{i=1}^{n} λ_{i} · v_{i} ; λ_{1}, …, λ_{n} ∈ K}

nennt man ”den von den Vektoren v_{1}, …, v_{n} aufgespannten (Unter-)Raum“. Bezeichnung: die Vektoren v_{1}, …, v_{n} bilden ein ”Erzeugendensystem“ des (Unter-)Raums.

Definition 12.9: (Basis eines Vektorraums)

Eine Menge {v_{1}, …, v_{n}} von Vektoren eines Vektorraums V heißt ”Basis“, wenn die Vektoren linear unabhängig sind und V = span(v_{1}, …, v_{n}) gilt.

Satz und Definition 12.10:

Besitzt ein Vektorraum eine Basis mit endlich vielen Elementen, so hat jede alternative Basis die selbe Anzahl von Elementen. Diese Anzahl von Basiselementen wird die ”Dimension“ des Vektorraums genannt.

Beweis: ist technisch (z.B. über den ”Steinitzschen Austauschsatz“). Siehe Bücher über Lineare Algebra.

Satz 12.11:

a) Seien {v_{1}, …, v_{m}} linear unabhängig. Für jeden Vektor v, der sich nicht als Linearkombination von v_{1}, …, v_{m} schreiben läßt, sind die Vektoren {v_{1}, …, v_{m}, v} linear unabhängig.

b) In einem Raum der Dimension n bildet jede Menge mit n linear unabhängigen Vektoren eine Basis.

c) In einem Raum der Dimension n gibt es maximal n linear unabhängige Vektoren.

Beweis: (für technisch Interessierte)

a) Sei {v_{1}, …, v_{m}} eine beliebige Menge linear unabhängiger Vektoren. Sei v ein Vektor, der nicht Linearkombination von v_{1}, …, v_{m} ist, d.h., für jede Wahl von skalaren Linearfaktoren μ_{1}, …, μ_{m} gilt

v − ∑_{i=1}^{m} μ_{i} · v_{i} ≠ 0. (#)

Betrachte nun die Vektorgleichung

λ_{0} · v + ∑_{i=1}^{m} λ_{i} · v_{i} = 0. (##)

Es folgt, dass λ_{0} = 0 gelten muss, denn sonst würde

v − ∑_{i=1}^{m} ( − \frac{λ_{i}}{λ_{0}} ) · v_{i} = 0

folgen, was im Widerspruch zu (#) steht. Damit wird aus (##) die Gleichung ∑_{i=1}^{m} λ_{i} · v_{i} = 0, woraus wegen der linearen Unabhängigkeit von v_{1}, …, v_{m} folgt, dass λ_{1} = … = λ_{m} = 0 gilt. Also impliziert (##) insgesamt λ_{0} = λ_{1} = … = λ_{m} = 0, d.h., die m + 1 Vektoren v_{1}, …, v_{m}, v sind linear unabhängig.

b) Seien v_{1}, …, v_{n} linear unabhängige Vektoren. Sei {e_{1}, …, e_{n}} irgendeine Basis. Seien e_{j_{1}}, …, e_{j_{m}} die Basisvektoren, die sich nicht als Linearkombination von v_{1}, …, v_{n} schreiben lässen. Nach a) sind {v_{1}, …, v_{n}, e_{j_{1}}, …, e_{j_{m}}} linear unabhängig. Jeder Vektor v des Vektorraums kann als Linearkombination der Basiselemente e_{i} geschrieben werden. Jedes e_{i} läßt sich aber nach Konstruktion als Linearkombination von v_{1}, …, v_{n}, e_{j_{1}}, …, e_{j_{m}} ausdrücken, so dass sich insgesamt jedes v als Linearkombination der Vektoren v_{1}, …, v_{n}, e_{j_{1}}, …, e_{j_{m}} darstellen läßt. Damit ist span(v_{1}, …, v_{n}, e_{j_{1}}, …, e_{j_{m}}) der gesamte Vektorraum, also ist {v_{1}, …, v_{n}, e_{j_{1}}, …, e_{j_{m}}} eine Basis mit n + m Elementen. Dies darf nach Satz 12.10 aber nur für m = 0 sein, d.h., die n linear unabhängigen Vektoren v_{1}, …, v_{n} bildeten schon eine Basis.

c) Von m linear unabhängigen Vektoren (mit m > n) bilden die ersten n Vektoren nach b) schon eine Basis, der (n + 1)-te Vektor kann damit als Linearkombination der ersten n geschrieben werden und ist damit nicht linear unabhängig von den ersten n.

Q.E.D.

Beispiel 12.12: 1) Der reelle Raum

ℝ^{n} = {(x_{1}, x_{2}, …, x_{n})^{T} ; x_{1}, …, x_{n} ∈ ℝ}

und der komplexe Raum

ℂ^{n} = {(x_{1}, x_{2}, …, x_{n})^{T} ; x_{1}, …, x_{n} ∈ ℂ}

haben jeweils die Dimension n. Die ”Standardbasis“ besteht jeweils aus den Vektoren

e⃗_{1} = ( 1 0 ⋮ 0 ) , e⃗_{2} = ( 0 1 ⋮ 0 ) , …, e⃗_{n} = ( 0 0 ⋮ 1 ) .

Beachte dazu

∑_{i=1}^{n} x_{i} · e⃗_{i} = ( x_{1} ; x_{2} ; ⋮ ; x_{n} ) .

Jede Menge von n linear unabhängigen Vektoren bildet jeweils eine alternative Basis.

2) Seien v⃗_{1}, v⃗_{2} zwei linear unabhängige Vektoren im ℝ^{n} (mit n ≥ 2). Sie bilden eine Basis der 2-dimensionalen Ebene

E = span(v⃗_{1}, v⃗_{2}) = {λ_{1} · v⃗_{1} + λ_{2} · v⃗_{2} ; λ_{1}, λ_{2} ∈ ℝ}.

Eine alternative Basis des Vektorraums E (Unterraum des ℝ^{n}) ist z.B.

v⃗_{1}′ = v⃗_{1} + v⃗_{2}, v⃗_{2}′ = v⃗_{1} − v⃗_{2},

denn v⃗_{1}′, v⃗_{2}′ sind wieder linear unabhängig und jeder von v⃗_{1}, v⃗_{2} aufgespannte Vektor läßt sich auch von v⃗_{1}′, v⃗_{2}′ aufspannen:

v⃗ = λ_{1} · v⃗_{1} + λ_{2} · v⃗_{2} = (\frac{λ_{1}}{2} + \frac{λ_{2}}{2} ) · v⃗_{1}′ + (\frac{λ_{1}}{2} − \frac{λ_{2}}{2} ) · v⃗_{2}′.

3) Sei V die Menge aller Polynome vom Grad ≤ n. In Blatt 13 ist zu zeigen, dass die

Monome {1, x, x^{2}, …, x^{n}} eine Basis dieses n + 1 dimensionalen Vektorraums sind.

4) Sei V die Menge aller Polynome (mit beliebigem Grad). Die Dimension dieses Raums ist ∞, denn es gibt beliebig viele linear unabhängige Elemente (z.B. die Monome x^{n} mit beliebig großem n).

Für analytische Betrachtungen auf dem ℝ^{n} bzw. dem ℂ^{n} braucht man einen Längenbegriff, mit dem man den Abstand ∥v⃗ − w⃗∥ zwischen Vektoren messen kann:

Definition 12.13: (Norm)

Sei V ein Vektorraum über dem Skalarenkörper K. Eine ”Norm” auf V ist eine Abbildung ∥ . ∥ : V → [0, ∞) mit den Eigenschaften:

a) ∥v + w∥ ≤ ∥v∥ + ∥w∥ für alle v, w ∈ V (”Dreiecksungleichung”).

b) ∥λ · v∥ = |λ| · ∥v∥ für alle v ∈ V, λ ∈ K (”Homogenität”).

c) ∥v∥ = 0 ⇔ v = 0.

Beispiel 12.14: Auf dem ℝ^{n} bzw. dem ℂ^{n} existieren die sogenannten p-Normen:

∥( x_{1} ; ⋮ ; x_{n} )∥_{p} = ( ∑_{i=1}^{n} |x_{i}|^{p})^{1/p}, p ∈ [1, ∞).

Die Norm-Eigenschaften b) und c) sind offensichtlich, der Beweis der Dreiecksungleichung

∥x + y∥_{p} ≤ ∥x∥_{p} + ∥y∥_{p}

ist jedoch nicht-trivial. Zusätzlich kann man die Norm

∥( x_{1} ; ⋮ ; x_{n} )∥_{∞} = max_{i=1,...,n} |x_{i}|

betrachten. Die Namensgebung entstammt der Tatsache, dass

∥x⃗∥_{∞} = lim_{p→∞} ∥x⃗∥_{p}

für jedes x⃗ ∈ ℝ^{n} bzw. x⃗ ∈ ℂ^{n} gilt.

Eine wichtige Struktur auf dem ℝ^{n} bzw. dem ℂ^{n} ist das Skalarprodukt: Definition 12.15: (Skalarprodukt)

Ein ”Skalarprodukt“ auf einem Vektorraum V über dem Skalarenkörper K ist eine Abbildung ⟨., .⟩ : V × V → ℂ mit den Eigenschaften

a) Linearität:

⟨v, λ_{1} · w_{1} + λ_{2} · w_{2}⟩ = λ_{1} · ⟨v, w_{1}⟩ + λ_{2} · ⟨v, w_{2}⟩,
⟨λ_{1} · v_{1} + λ_{2} · v_{2}, w⟩ = \overline{λ_{1}} · ⟨v_{1}, w⟩ + \overline{λ_{2}} · ⟨v_{2}, w⟩,

für alle v, v_{1}, v_{2}, w, w_{1}, w_{2} ∈ V, λ_{1}, λ_{2} ∈ K.

b) ⟨v, w⟩ = \overline{⟨w, v⟩} (komplexe Konjugation) für alle v, w ∈ V.

c) ⟨v, v⟩ ≥ 0 für alle v ∈ V. (Beachte: b) impliziert ⟨v, v⟩ ∈ ℝ.)

d) ⟨v, v⟩ = 0 ⇔ v = 0.

Beispiel 12.16: 1) Auf dem ℝ^{n} ist das interessanteste Skalarprodukt

x⃗ · y⃗ = ⟨( x_{1} ; ⋮ ; x_{n} ) , ( y_{1} ; ⋮ ; y_{n} )⟩ = ∑_{i=1}^{n} x_{i} · y_{i}.

Offensichtlich sind alle geforderten Eigenschaften a) – d) des Skalarprodukts erfüllt. Die komplexe Konjugation ist dabei irrelevant.

2) Auf dem ℂ^{n} ist das interessanteste Skalarprodukt

x⃗ · y⃗ = ⟨( x_{1} ; ⋮ ; x_{n} ) , ( y_{1} ; ⋮ ; y_{n} )⟩ = ∑_{i=1}^{n} \overline{x_{i}} · y_{i}.

Offensichtlich sind alle geforderten Eigenschaften a) – d) des Skalarprodukts erfüllt, wobei die komplexe Konjugation wesentlich ist.

Definition 12.17: (Orthogonalität)

Zwei Vektoren x⃗, y⃗ im ℝ^{n} bzw. ℂ^{n} heissen ”orthogonal“, wenn ⟨x⃗, y⃗ ⟩ = 0 gilt.

Bemerkung 12.18: Offensichtlich erzeugt das Skalarprodukt die p-Norm aus Bemerkung 12.14 mit p = 2:

∥x⃗∥_{2} = \sqrt{⟨x⃗, x⃗ ⟩}.

Es gilt die Cauchy-Schwarzsche Ungleichung

|⟨x⃗, y⃗ ⟩| ≤ ∥x⃗∥_{2} · ∥y⃗∥_{2},

die wir schon in Satz 11.5 kennengelernt haben (für den Beweis siehe Aufgabe 99 auf Blatt 12). Das Gleichheitszeichen gilt in der Cauchy-Schwarzschen Ungleichung genau dann, wenn die Vektoren x⃗ und y⃗ parallel (= linear abhängig) sind.

12.2 Etwas Geometrie im ℝ^{3}

12.2.1 Skalar-, Vektor- und Spatprodukt

Auf dem ℝ^{3} (und dem darin eingebetteten ℝ^{2}) gelten einige wichtige geometrische Interpretationen der eingeführten Struktuen.

12.2. ETWAS GEOMETRIE IM ℝ^{3} 231

Satz 12.19: (Geometrische Interpretation der 2-Norm)

Die 2-Norm ∥x⃗∥_{2} eines Vektors x⃗ ∈ ℝ^{2} bzw. x⃗ ∈ ℝ^{3} ist seine geometrische Länge.

Beweis:

[figure: x; x_{1}; y; x_{2}; z; x_{3}; x⃗ = (x_{1}, x_{2}, x_{3})^{T}; ∥x⃗∥_{2}]

Pythagoras liefert als geometrische Länge \sqrt{x_{1}^{2} + x_{2}^{2} + x_{3}^{2}} = ∥x⃗∥_{2}.

Q.E.D.

Satz 12.20: (Geometrische Interpretation des Skalarprodukts)

Für beliebige Vektoren x⃗, y⃗ ∈ ℝ^{2} bzw. x⃗, y⃗ ∈ ℝ^{3} gilt

⟨x⃗, y⃗ ⟩ = ∥x∥_{2} · ∥y∥_{2} · cos(α),

wo α der Winkel zwischen den Vektoren x⃗ und y⃗ ist.

Beweis: Das Skalarprodukt ist invariant unter Drehungen, d.h., es gilt

⟨x⃗, y⃗ ⟩ = ⟨x′, y′ ⟩,

wenn x′ = O x⃗ y′ = O y⃗ durch die selbe Drehung (beschrieben durch eine orthogonal Matrix O) aus x⃗ und y⃗ hervorgehen (wir erläutern dies, sobald wir orthogonale Matrizen eingeführt haben). Damit können wir o.B.d.A. die Vektoren so drehen, dass x⃗ = (∥x⃗∥_{2}, 0, 0)^{T} und y⃗ = (y_{1}, y_{2}, 0)^{T} = (∥y⃗∥·cos(α), ∥y⃗∥·sin(α), 0)^{T} gilt:

Die Definition des Skalarprodukts liefert dann sofort

⟨x⃗, y⃗ ⟩ = ⟨( \begin{matrix}∥x∥_{2} \\ 0 \\ 0 \end{matrix} ) , ( \begin{matrix}∥y∥_{2} · cos(α) \\ ∥y∥_{2} · sin(α) \\ 0 \end{matrix} )⟩ = ∥x∥_{2} · ∥y∥_{2} · cos(α).

[figure: α; x⃗; ∥y⃗∥_{2} · sin(α); ∥y⃗∥_{2} · cos(α); y⃗]

Q.E.D.

Speziell auf dem ℝ^{3} ist ein interessantes Produkt zweier Vektoren definiert, das einen Vektor liefert, der auf den zwei gegebenen Vektoren senkrecht steht:

Definition 12.21: (Das Kreuzprodukt auf dem ℝ^{3})

Das Kreuzprodukt x⃗ × y⃗ zweier Vektoren x⃗, y⃗ ∈ ℝ^{3} ist der Vektor

( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) × ( \begin{matrix}y_{1} \\ y_{2} \\ y_{3} \end{matrix} ) = ( \begin{matrix}x_{2} · y_{3} − x_{3} · y_{2} \\ x_{3} · y_{1} − x_{1} · y_{3} \\ x_{1} · y_{2} − x_{2} · y_{1} \end{matrix} ) .

Bemerkung 12.22: a) Wie leicht nachzurechnen ist, gilt

⟨x⃗, x⃗ × y⃗ ⟩ = ⟨y⃗, x⃗ × y⃗ ⟩ = 0,

d.h., das Kreuzprodukt zweier Vektoren steht senkrecht auf jedem der beiden Vektoren.

b) Das Kreuzprodukt verschwindet genau dann, wenn die beiden Vektoren parallel sind (oder einer der Vektoren verschwindet).

c) Das Kreuzprodukt ist weder kommutativ noch assoziativ. Es gilt

x⃗ × y⃗ = −y⃗ × x⃗

und die ”Jacobi-Identität“

x⃗ × (y⃗ × z⃗) + y⃗ × (z⃗ × x⃗) + z⃗ × (x⃗ × y⃗) = 0

für alle x⃗, y⃗, z⃗ ∈ ℝ^{3}.

Satz 12.23: (Geometrische Interpretation des Kreuzprodukts)

Für beliebige Vektoren x⃗, y⃗ ∈ ℝ^{3} gilt

∥x⃗ × y⃗∥_{2} = ∥x∥_{2} · ∥y∥_{2} · | sin(α)|,

wo α der Winkel zwischen den Vektoren x⃗ und y⃗ ist. Die Länge des Kreuzprodukts ist damit die Fläche des von x⃗, y⃗ aufgespannten Parallelogramms.

Beweis: Wir argumentieren ähnlich wie bei Satz 12.20. Das Kreuzprodukt ist invariant unter Drehungen: es gilt^{2}

(Ox⃗) × (Oy⃗) = ±O(x⃗ × y⃗),

wobei O eine orthogonale Drehmatrix ist (das Vorzeichen hängt davon ab, ob O eine Spiegelung enthält). Da Drehungen die Längen der Vektoren und den Winkel zwischen den Vektoren nicht ändern, können wir o.B.d.A. die Vektoren so drehen, dass

x⃗ = (∥x⃗∥_{2}, 0, 0)^{T} und y⃗ = (y_{1}, y_{2}, 0)^{T} = (∥y⃗∥ · cos(α), ∥y⃗∥ · sin(α), 0)^{T}

gilt:

[figure: α; x⃗; ∥y⃗∥_{2} · sin(α); ∥y⃗∥_{2} · cos(α); y⃗]

Die Definition des Kreuzprodukts liefert dann sofort

x⃗ × y⃗ = ( \begin{matrix}∥x∥_{2} \\ 0 \\ 0 \end{matrix} ) × ( \begin{matrix}∥y∥_{2} · cos(α) \\ ∥y∥_{2} · sin(α) \\ 0 \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ ∥x∥_{2} · ∥y∥_{2} · sin(α) \end{matrix} ) .

Die Fläche des von x⃗, y⃗ aufgespannten Parallelogramms ist die Seitenlänge ∥x⃗∥_{2} mal der Höhe ∥y⃗∥_{2} · sin(α).

Q.E.D.

Bemerkung 12.24: Die Beobachtung, dass x⃗ × y⃗ senkrecht auf x⃗ und y⃗ steht, legt die Richtung von x⃗ × y⃗ bis auf ein Vorzeichen geometrisch fest. Der letzte Satz legt die Länge von x⃗ × y⃗ geometrisch fest. Das Vorzeichen von x⃗ × y⃗ ist geometrisch durch die ”Rechte-Hand-Regel“ bestimmt: das aus x⃗, y⃗, x⃗ × y⃗ bestehende Dreibein entspricht Daumen, Zeigefinger und (gekrümmtem) Mittelfinger der rechten Hand. Dies legt in der Tat die Richtung von x⃗ × y⃗ fest, wenn man sich nicht den Mittelfinger brechen will.

Und noch ein interessantes Produkt auf dem ℝ^{3}:

Definition 12.25: (Das Spatprodukt auf dem ℝ^{3})

Das Spatprodukt |[x⃗, y⃗, z⃗]| dreier Vektoren x⃗, y⃗, z⃗ ∈ ℝ^{3} ist der skalare Wert

|[x⃗, y⃗, z⃗]| = ⟨x⃗, y⃗ × z⃗ ⟩ = ⟨y⃗, z⃗ × x⃗ ⟩ = ⟨z⃗, x⃗ × y⃗ ⟩.

Ein ”Dreibein“ x⃗, y⃗, z⃗ heißt ”rechtshändig“, wenn |[x⃗, y⃗, z⃗]| > 0 gilt. Für |[x⃗, y⃗, z⃗]| < 0 heißt das Dreibein ”linkshändig“.

2Dies ist etwas mühselig nachzurechnen.

Satz 12.26: (Geometrische Interpretation des Spatprodukts)

Für beliebige Vektoren x⃗, y⃗, z⃗ ∈ ℝ^{3} gilt |[x⃗, y⃗, z⃗]| = ±V, wo V das Volumen des von den Vektoren x⃗, y⃗, z⃗ aufgespannten Spats ist:

Beweis: Wir argumentieren ähnlich wie bei Satz 12.20 und Satz 12.23. Das Spatprodukt ist invariant unter Drehungen: es gilt

|[x⃗, y⃗, z⃗]| = ±|[Ox⃗, Oy⃗, Oz⃗]|,

wobei O eine orthogonale Drehmatrix ist (das Vorzeichen hängt davon ab, ob O eine Spiegelung enthält). O.B.d.A. können wir die Vektoren so drehen, dass

x⃗ = (∥x⃗∥_{2}, 0, 0)^{T} und y⃗ = (y_{1}, y_{2}, 0)^{T} = (∥y⃗∥ · cos(α), ∥y⃗∥ · sin(α), 0)^{T}

gilt:

[figure: α; x⃗; ∥y⃗∥_{2} · sin(α); ∥y⃗∥_{2} · cos(α); y⃗]

Die Definition des Kreuzprodukts liefert dann sofort

|[x⃗, y⃗, z⃗]| = ⟨z⃗, x⃗ × y⃗⟩ = ⟨( \begin{matrix}z_{1} \\ z_{2} \\ z_{3} \end{matrix} ) , ( \begin{matrix}∥x∥_{2} \\ 0 \\ 0 \end{matrix} ) × ( \begin{matrix}∥y∥_{2} · cos(α) \\ ∥y∥_{2} · sin(α) \\ 0 \end{matrix} )⟩

= ⟨( \begin{matrix}z_{1} \\ z_{2} \\ z_{3} \end{matrix} ) , ( \begin{matrix}0 \\ 0 \\ ∥x∥_{2} · ∥y∥_{2} · sin(α) \end{matrix} )⟩ = z_{3} · ∥x∥_{2} · ∥y∥_{2} · sin(α).

Hierbei ist ∥x∥_{2} · ∥y∥_{2} · sin(α) die Fläche des von x⃗, y⃗ aufgespannten Parallelogramms (die Grundfläche des Spats) und z_{3} ist die Höhe des Spats (die Grundfläche liegt hier in der x-y-Ebene). Das Spatvolumen ist Grundfläche mal Höhe.

Q.E.D.

12.2.2 Geraden und Ebenen

Definition 12.27: (Geraden)

Zu gegebenen x⃗_{0} ∈ ℝ^{2} bzw. ℝ^{3} und 0 ≠ d⃗ ∈ ℝ^{2} bzw. ℝ^{3} definieren wir die Gerade durch x⃗_{0} mit dem Richtungsvektor d⃗ als die Menge aller Punkte der Form

{x⃗_{0} + λ · d⃗; λ ∈ ℝ}.

Definition 12.28: (Ebenen)

Zu gegebenem x⃗_{0} ∈ ℝ^{3} und linear unabhängigen Vektoren d⃗_{1}, d⃗_{2} ∈ ℝ^{3} definieren wir die Ebene durch x⃗_{0} mit den Tangentialvektoren d⃗_{1}, d⃗_{2} als die Menge aller Punkte der Form

{x⃗_{0} + λ_{1} · d⃗_{1} + λ_{2} · d⃗_{2} ; λ_{1}, λ_{2} ∈ ℝ}.

In dieser Definition werden 9 Parameter (jeweils 3 Komponenten der Vektoren x⃗_{0}, d⃗_{1}, d⃗_{2}) zur Definition der Ebene vorgegeben. Alternativ kann man die Ebene auch durch insgesamt nur 3 Parameter festlegen, denn eine Ebene ist als die Menge aller Punkte (x_{1}, x_{2}, x_{3})^{T} bestimmt, die eine lineare Gleichung

⟨( \begin{matrix}n_{1} \\ n_{2} \\ n_{3} \end{matrix} ) , ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} )⟩ = n_{1} · x_{1} + n_{2} · x_{2} + n_{3} · x_{3} = d

bestimmen, wobei o.B.d.A. durch Multiplikation der Gleichung mit einer geeigneten Zahl der Wert von d auf 0 oder 1 festgelegt werden kann. Sei

n⃗ = d⃗_{1} × d⃗_{2}

der ”Normalenvektor“ der Ebene, der senkrecht auf den beiden Tangentenvektoren d⃗_{1}, d⃗_{2} steht. In der Tat folgt aus der Parameterform

x⃗ = x⃗_{0} + λ_{1} · d⃗_{1} + λ_{2} · d⃗_{2}

der Ebenenpunkte durch skalare Multiplikation mit n⃗:

⟨n⃗, x⃗ ⟩ = ⟨n⃗, x⃗_{0} ⟩ + λ_{1} · \underbrace{⟨n⃗, d⃗_{1} ⟩}_{=0} +λ_{2} · \underbrace{⟨n⃗, d⃗_{2} ⟩}_{=0} = ⟨n⃗, x⃗_{0} ⟩,

d.h., ⟨n⃗, x⃗ ⟩ hat für alle Ebenenpunkte den selben Wert ⟨n⃗, x⃗_{0}⟩ (=: d). Die Gleichung

⟨n⃗, x⃗ ⟩ = d

heißt ”Hessesche Normalform“ der Ebene. Der Vektor n⃗ ist dabei der Normalenvektor der Ebene. Der Parameter d hat folgende geometrische Interpretation: Wir starten am Nullpunkt und laufen orthogonal auf die Ebene zu, d.h., wir betrachten die Punkte auf der Geraden x⃗ = λ · n⃗. Für den Durchstoßpunkt durch die Ebene muß

⟨n⃗, x⃗ ⟩ = ⟨n⃗, λ · n⃗ ⟩ = λ · ⟨n⃗, n⃗ ⟩ = d  ⇒  λ = \frac{d}{⟨n⃗, n⃗ ⟩}

gelten, der Durchstoßpunkt ist also

x⃗ = \frac{d}{⟨n⃗, n⃗ ⟩} · n⃗.

Der Betrag dieses Vektors

∥x⃗∥_{2} = \frac{d}{⟨n⃗, n⃗ ⟩} · ∥n⃗∥_{2} = \frac{d}{∥n⃗∥_{2}}

ist der Abstand der Ebene zum Nullpunkt:

Für ∥n⃗∥_{2} = 1 ist der Parameter d der durch ⟨n⃗, x⃗ ⟩ = d gegebenen Ebene der Abstand der Ebene vom Nullpunkt.

Ist d > 0, zeigt der Normalenvektor vom Ursprung in Richtung der Ebene:

[figure: n⃗; d; ℝ^{3}; Ebene]

12.3 Matrizen

Betrachten wir den Fall eines Vektors x⃗ = (x_{1}, …, x_{n})^{T}, der mit der Standardbasis

e⃗_{j} = ( 0 ⋮ 1 ⋮ 0 )

als x⃗ = ∑_{j} x_{j} · e⃗_{j} gegeben ist. Angenommen, wir haben eine alternative Basis e⃗_{i}′ gegeben, die durch die Linearkombinationen

e⃗_{j} = ∑_{i=1}^{n} e⃗_{i}′ · a_{ij}, j = 1, …, n

mit der Standardbasis verknüpft ist. In der neuen Basis gilt x⃗ = ∑_{i} x′_{i}·e⃗_{i}′, wobei sich die neuen Koeffizienten x′_{i} durch

x⃗ = ∑_{i=1}^{n} x′_{i} · e⃗_{i}′ = ∑_{j=1}^{n} x_{j} · e⃗_{j} = ∑_{j=1}^{n} x_{j} · ∑_{i=1}^{n} e⃗_{i}′ · a_{ij} = ∑_{i=1}^{n} \underbrace{( ∑_{j=1}^{n} a_{ij} · x_{j})}_{x′_{i}} ·e⃗_{i}′

ergeben, also

x′_{i} = ∑_{j=1}^{n} a_{ij} · x_{j}, i = 1, …, n.

Wir schreiben dies formal als

( x′_{1} ; ⋮ ; x′_{n} ) = ( \begin{matrix}a_{11} & … & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{n1} & … & a_{nn} \end{matrix} ) ( x_{1} ; ⋮ ; x_{n} ) ,

wobei wir die Koeffizienten (a_{ij}) in ein rechteckiges Schema (”Matrix“) einordnen. Wir führen solche Rechteck-Schemata nun formal ein und vereinbaren, wie wir damit rechnen.

Definition 12.29: (Matrizen)

Sei K ein Skalarenkörper (also für uns K = ℝ bzw. K = ℂ). Die Menge

K^{n×m} = \{( \begin{matrix}a_{11} & … & a_{1m} \\ ⋮ & ... & ⋮ \\ a_{n1} & … & a_{nm} \end{matrix} ); a_{11}, …, a_{nm} ∈ K\}

wird als Raum der (n × m)-Matrizen bezeichnet. Wir benutzen die Notation A = (a_{ij}) ∈ K^{n×m}. Der Raum K^{n×m} wird mit den Operationen

(A + B)_{ij} = a_{ij} + b_{ij}, (λ · A)_{ij} = λ · a_{ij}, i = 1, …, n, j = 1, …, m

für A = (a_{ij}) ∈ K^{n×m}, B = (b_{ij}) ∈ K^{n×m}, λ ∈ K zu einem Vektorraum über K.

Neben der Addition von Matrizen und der Multiplikation mit Skalaren definieren wir eine Multiplikation von Matrizen:

(n × p)-Matrix × (p × m)-Matrix = (n × m)-Matrix.

Definition 12.30: (Matrizenmultiplikation)

Für A = (a_{ij}) ∈ K^{n×p}, B = (b_{ij}) ∈ K^{p×m} definieren wir das Produkt C = AB als die Matrix C = (c_{ij}) ∈ K^{n×m} mit

c_{ij} = ∑_{k=1}^{p} a_{ik} · b_{kj}, i = 1, …, n, j = 1, …, m.

Spaltenvektoren entsprechen Matrizen mit nur einer Spalte

( x_{1} ; ⋮ ; x_{n} ) ∈ K^{n×1},

Zeilenvektoren entsprechen Matrizen mit nur einer Zeile:

(x_{1}, …, x_{n}) ∈ K^{1×n}.

Das Matrixprodukt einer Zeile mit einer Spalte entspricht dem Skalarprodukt:

(a_{1}, …, a_{n}) ( b_{1} ; ⋮ ; b_{n} ) = ∑_{k=1}^{n} a_{k} · b_{k}.

Bemerkung 12.31: Das Matrixprodukt läßt sich damit folgendermassen verinnerlichen:

( a_{11} … a_{1p} ; ⋮ ... ⋮ ; a_{i1} … a_{ip} ; ⋮ ... ⋮ ; a_{n1} … a_{np} ) ( \begin{matrix}b_{11} & … & b_{1j} & … & b_{1m} \\ ⋮ & ... & ⋮ & ... & ⋮ \\ b_{p1} & … & b_{pj} & … & b_{pm} \end{matrix} ) = ( \begin{matrix}c_{11} & … & c_{1m} \\ ⋮ & c_{ij} & ⋮ \\ c_{n1} & … & c_{nm} \end{matrix} ) ,

wobei

c_{ij} = Skalarprodukt((i-te Zeile von A) × (j-te Spalte von B))

= (a_{i1}, …, a_{ip}) ( b_{1j} ; ⋮ ; b_{pj} ) = ∑_{k=1}^{n} a_{ik} · b_{kj}.

Bemerkung 12.32: Das Matrixprodukt (mit Matrizen A, B, C zulässiger Dimension) ist assoziativ:

(AB)C = A(BC),

denn

((AB)C)_{ij} = ∑_{k_{2}} (∑_{k_{1}} a_{ik_{1}} · b_{k_{1}k_{2}} ) · c_{k_{2}j} = ∑_{k_{1}} ∑_{k_{2}} a_{ik_{1}} · b_{k_{1}k_{2}} · c_{k_{2}j}
∥
(A(BC))_{ij} = ∑_{k_{1}} a_{ik_{1}} (∑_{k_{2}} b_{k_{1}k_{2}} · c_{k_{2}j}) = ∑_{k_{1}} ∑_{k_{2}} a_{ik_{1}} · b_{k_{1}k_{2}} · c_{k_{2}j}.

Warnung: Das Matrixprodukt ist nicht kommutativ, i.A. gilt AB ≠ BA. Beispiel:

A  B
AB = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}1 & 0 \\ 2 & 1 \end{matrix} ) ,
∦
BA = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) = ( \begin{matrix}1 & 2 \\ 0 & 1 \end{matrix} ) .

Wir führen weiterhin ein:

Definition 12.33: (Transposition)

a) Die Transponierte A^{T} = (b_{ij}) einer (n × m)-Matrix A = (a_{ij}) ist die (m × n)-Matrix

b_{ij} = a_{ji}, i = 1, …, m, j = 1, …, n,

b) Eine Matrix heißt symmetrisch (oder auch selbstadjungiert), wenn A = A^{T} gilt, also a_{ij} = a_{ji}. Sie heißt antisymmetrisch (oder auch schiefsymmetrisch), wenn A = −A^{T} gilt, also a_{ij} = −a_{ji}.

c) Die hermitesch Transponierte A^{H} = (c_{ij}) einer (komplexen) (n× m)-Matrix A = (a_{ij}) ist die (m × n)-Matrix

c_{ij} = \overline{a_{ji}}, i = 1, …, m, j = 1, …, n,

(Transposition plus komplexe Konjugation).

d) Eine Matrix heißt hermitesch, wenn A = A^{H} gilt, also a_{ij} = \overline{a_{ji}}. Sie heißt antihermitesch (oder auch schiefhermitesch), wenn A = −A^{H} gilt, also a_{ij} = −\overline{a_{ji}}.

Bemerkung 12.34: Für das reelle Skalarprodukt ⟨x⃗, y⃗ ⟩ = ∑_{k} x_{k} · y_{k} auf dem ℝ^{n} gilt offensichtlich

⟨x⃗, A y⃗ ⟩ = ⟨A^{T} x⃗, y⃗ ⟩ = ∑_{ij} x_{i} · a_{ij} · y_{j}

für jedes x⃗, y⃗ ∈ ℝ^{n} und jedes A ∈ ℝ^{n×n}. Für das komplexe Skalarprodukt ⟨x⃗, y⃗ ⟩ = ∑_{k} \overline{x_{k}} · y_{k} auf dem ℂ^{n} gilt offensichtlich

⟨x⃗, A y⃗ ⟩ = ⟨A^{H}x⃗, y⃗ ⟩ = ∑_{ij} \overline{x_{i}} · a_{ij} · y_{j}

für jedes x⃗, y⃗ ∈ ℂ^{n} und jedes A ∈ ℂ^{n×n}.

Durch (hermitesche) Transposition kann eine Matrix von einer Seite des Skalarprodukts auf die andere Seite bewegt werden.

Definition 12.35: (Einheitsmatrix)

Die Matrix

I 1 = (δ_{ij}) = ( \begin{matrix}1 & 0 & … & 0 \\ 0 & 1 & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & … & 0 & 1 \end{matrix} )

auf dem K^{n×n} heißt (n × n)-Einheitsmatrix. Es gilt

I 1x⃗ = x⃗, I 1A = A, B I 1 = B

für alle x⃗ ∈ K^{n}, alle A ∈ K^{n×m} und alle B ∈ K^{m×n}.

Definition 12.36: (Inverse einer Matrix)

Existiert zu einer quadratischen Matrix A ∈ K^{n×n} eine Matrix A^{−1} ∈ K^{n×n} mit

A^{−1}A = I 1,

so heißt A^{−1} Inverse von A. Es gilt dann automatisch auch AA^{−1} = I 1.

Wegen der Nichtkommutativität des Matrixprodukts ist dabei kurz zu überlegen, dass die ”Linksinverse“ mit der Eigenschaft A^{−1}A = I 1 auch automatisch eine ”Rechtsinverse“ mit AA^{−1} = I 1 ist: Angenommen, eine Rechtsinverse B mit AB = I 1 existiere. Multiplizieren wir von links mit A^{−1}, erhalten wir A^{−1}AB = B = A^{−1} I 1 = A^{−1}, also: B = A^{−1}.

Es ist eine fundamentale Aufgabe, Kriterien zu suchen, wann eine Matrix invertierbar ist. Wir werden sehen, dass z.B. eine Matrix genau dann invertierbar ist, wenn die Determinante von A nicht verschwindet. Weiterhin ist es wichtig, einen Algorithmus zur Berechnung der Inversen anzugeben. Dies wird in den Abschnitten 12.3 und 12.5 geschehen.

12.4 Determinanten

Definition 12.37: (Permutation)

Eine invertierbare Abbildung p : {1, …, n} → {1, …, n} heißt ”Permutation“ der Zahlen 1, …, n.

Die ”Inversionszahl“ einer Permutation ist

I_{p} = |{(j, k); j, k ∈ {1, …, n}, j < k, p(j) > p(k)}|

(also: I_{p} ist die Anzahl aller Paare (j, k) mit j < k, bei denen die Permutation die Anordung j < k zu p(j) > p(k) vertauscht).

Das ”Signum“ einer Permutation ist sign(p) = (−1)^{I_{p}}.

Satz 12.38:

Es gibt n! verschiedene Permutationen der Zahlen 1, …, n.

Beweis: Für p(1) gibt es n verschiedene Möglichkeiten, für p(2) gibt es n − 1 verschiedene Möglichkeiten (da p(2) ≠ p(1) gelten muss), für p(3) gibt es n − 2 verschiedene Möglichkeiten (da p(3) ≠ p(1) und p(3) ≠ p(2) gelten muss), usw. Damit gibt es insgesamt n · (n − 1) · (n − 2) · . . . · 1 = n! Möglichkeiten, eine Permutation von 1, …, n zu konstruieren.

Q.E.D. ↓27.1.04

Konstruiert man alle Permutationen, indem man Schritt für Schritt einzelne Zahlenpaare in einer Permutation austauscht, kann man leicht das Signum nachhalten: mit jeder Vertauschung ändert das Signum sein Vorzeichen.

Satz 12.39:

Unterscheiden sich zwei Permutationen p und p̃ nur durch den Austausch eines einzelnen Paares (j_{0}, k_{0}), also

p̃(j_{0}) = p(k_{0}), p̃(k_{0}) = p(j_{0}),
p̃(i) = p(i) ∀i ∈ {1, …, n} \ {j_{0}, k_{0}},

so gilt

sign(p) = −sign(p̃).

Beweis: (für technisch Interessierte) Es gelte o.B.d.A. j_{0} < k_{0} und p(k_{0}) > p(j_{0}) (für p(k_{0}) < p(j_{0}) sind in den folgenden Betrachtungen die Mengen A und Ã auszutauschen). Die Paare (j, k) mit j, k ∈ {1, …, n} \ {j_{0}, k_{0}} sind jeweils in beiden Mengen

A = {(j, k); j, k ∈ {1, …, n}, j < k, p(j) > p(k)}

und

Ã = {(j, k); j, k ∈ {1, …, n}, j < k, p̃(j) > p̃(k)}

gemeinsam vorhanden oder nicht vorhanden, da für diese Zahlen p̃(j) = p(j) und p̃(k) = p(k) gilt. Für j ∈ {j_{0}, k_{0}} bzw. k ∈ {j_{0}, k_{0}} enthält A die Teilmenge

{(k_{0}, k); k ∈ {k_{0} + 1, …, n}, p(k_{0}) > p(k)}
∪ {(j_{0}, k); k ∈ {k_{0} + 1, …, n} \ {k_{0}}, p(j_{0}) > p(k)}
∪ {(j, k_{0}); j ∈ {1, …, k_{0} − 1} \ {j_{0}}, p(j) > p(k_{0})}
∪ {(j, j_{0}); j ∈ {1, …, j_{0} − 1}, p(j) > p(j_{0})},

während Ã die Teilmenge

\{(j_{0}, k_{0})\} ∪ \{(k_{0}, k); k ∈ \{k_{0} + 1, …, n\}, \underbrace{p̃(k_{0})}_{=p(j_{0})} > \underbrace{p̃(k)}_{=p(k)} \}
∪ \{(j_{0}, k); k ∈ \{k_{0} + 1, …, n\} \ \{k_{0}\}, \underbrace{p̃(j_{0})}_{=p(k_{0})} > \underbrace{p̃(k)}_{=p(k)} \}
∪ \{(j, k_{0}); j ∈ \{1, …, j_{0} − 1\} \ \{j_{0}\}, \underbrace{p̃(j)}_{=p(j)} > \underbrace{p̃(k_{0})}_{=p(j_{0})} \}
∪ \{(j, k_{0}); j ∈ \{1, …, j_{0} − 1\}, \underbrace{p̃(j)}_{=p(j)} > \underbrace{p̃(j_{0})}_{=p(k_{0})} \}

enthält. Unter der Annahme p(k_{0}) > p(j_{0}) folgt damit:

\begin{aligned}Ã \ A = \{(j_{0}, k_{0})\} & ∪ & \{(j_{0}, k); k ∈ \{j_{0} + 1, …, n\}, p(j_{0}) < p(k) < p(k_{0})\} \\ & ∪ & \{(j, k_{0}); j ∈ \{1, …, k_{0} − 1\}, p(j_{0}) < p(j) < p(k_{0})\} \end{aligned}

und

\begin{aligned}A \ Ã = & \{(k_{0}, k); k ∈ \{k_{0} + 1, …, n\}, p(j_{0}) < p(k) < p(k_{0})\} \\ & ∪\{(j, j_{0}); j ∈ \{1, …, j_{0} − 1\}, p(j_{0}) < p(j) < p(k_{0})\}. \end{aligned}

Mit A = (A ∩ Ã) ∪ (A \ Ã) und Ã = (A ∩ Ã) ∪ (Ã \ A) folgt

|Ã| − |A| = 1 + 2 · |{j; j ∈ {j_{0} + 1, …, k_{0} − 1}, p(j_{0}) < p(j) < p(k_{0})}|.

Damit unterscheiden sich |Ã| und |A| um eine ungerade ganze Zahl, womit sign(p̃) = (−1)^{|Ã|} = −(−1)^{|A|} = −sign(p) folgt.

Q.E.D.

Beispiel 12.40: Wir schreiben eine Permutation in der Form

\begin{matrix}1 & 2 & … & n \\ p(1) & p(2) & … & p(n) \end{matrix} .

Für die 3! = 6 möglichen Permutationen der Zahlen 1, 2, 3 gilt:

p_{1} :  1 2 3 1 2 3 , sign(p_{1}) = 1,
p_{2} :  1 2 3 1 3 2 , sign(p_{2}) = −1,
p_{3} :  1 2 3 3 1 2 , sign(p_{3}) = 1,
p_{4} :  1 2 3 3 2 1 , sign(p_{4}) = −1,
p_{5} :  1 2 3 2 3 1 , sign(p_{5}) = 1,
p_{6} :  1 2 3 2 1 3 , sign(p_{6}) = −1.

Definition 12.41: (Determinante einer Matrix)

Die Determinante einer quadratischen Matrix A = (a_{i,j}) ∈ K^{n×n} ist

det(A) = ∑_{p} sign(p) · a_{1p(1)} · a_{2p(2)} · . . . · a_{np(n)},

wobei sich diese Summe über alle n! Permutationen p der Zahlen 1, …, n erstreckt.

Beispiel 12.42: Für die Fälle n = 1, 2, 3 ergibt sich

det((a_{11})) = a_{11},

det (( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )) = a_{11} · a_{22} − a_{12} · a_{21},

det (( \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix} )) \begin{aligned}= & a_{11} · a_{22} · a_{33} + a_{12} · a_{23} · a_{31} + a_{13} · a_{21} · a_{32} \\ & −a_{11} · a_{23} · a_{32} − a_{12} · a_{21} · a_{33} − a_{13} · a_{22} · a_{31}. \end{aligned}

Bezeichnung 12.43:

Seien

a⃗_{1} = ( a_{11} ; ⋮ ; a_{n1} ) , …, a⃗_{n} = ( a_{1n} ; ⋮ ; a_{nn} )

Vektoren im K^{n}. Die aus diesen Spalten aufgebaute Matrix wird mit [a⃗_{1}, …, a⃗_{n}] bezeichnet:

[a⃗_{1}, …, a⃗_{n}] = ( \begin{matrix}a_{11} & … & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{n1} & … & a_{nn} \end{matrix} ) .

Bemerkung 12.44: Die Definition der Matrixmultiplikation ist so, dass

A [b⃗_{1}, …, b⃗_{n}] = [A b⃗_{1}, …, A b⃗_{n}]

gilt, d.h., in einem Produkt AB ergeben sich die Spalten des Produkts als A wirkend auf die einzelnen Spalten von B.

Satz 12.45: (Linearität der Determinante bzgl. der Spalten)

Die Determinante ist linear in jeder Matrixspalte:

det([a⃗_{1}, …, λ · a⃗_{i} + λ′ · a′_{i}, …, a⃗_{n}]) =
λ · det([a⃗_{1}, …, a⃗_{i}, …, a⃗_{n}]) + λ′ · det([a⃗_{1}, …, a′_{i}, …, a⃗_{n}]).

Beweis: Dies folgt unmittelbar aus der Definition

det(A) = ∑_{p} sign(p) · a_{1p(1)} · a_{2p(2)} · . . . · a_{np(n)},

denn in jedem Summanden taucht genau eine Komponente jeder Spalte genau einmal auf.

Q.E.D.

Satz 12.46: (Antisymmetrie der Determinante bzgl. der Spalten)

Vertauscht man zwei Spalten, so wechselt die Determinante das Vorzeichen:

det([a⃗_{1}, …, a⃗_{i}, …, a⃗_{j}, …, a⃗_{n}]) = − det([a⃗_{1}, …, a⃗_{j}, …, a⃗_{i}, …, a⃗_{n}]).

Beweis: Dies folgt unmittelbar aus der Definition

det(A) = ∑_{p} sign(p) · a_{1p(1)} · a_{2p(2)} · . . . · a_{np(n)}.

Sei A die Ausgangsmatrix, sei Ã die Matrix, die durch Austausch zweier Spalten entsteht. Sei τ die Permutation, die die beiden Spaltenindizes austauscht und alle anderen Indizes beibehält. Es gilt

det(Ã) = ∑_{p} sign(p) · ã_{1p(1)} · ã_{2p(2)} · . . . · ã_{np(n)},

wobei ã_{ij} = a_{iτ(j)}. Damit folgt

det(Ã) = ∑_{p} sign(p) · a_{1τ(p(1))} · a_{2τ(p(2))} · . . . · a_{nτ(p(n))}.

Läuft p über alle Permutationen, läuft auch p̃ = τ ∘ p über alle Permutationen, wobei nach Satz 12.39 sign(p̃) = −sign(p) gilt:

det(Ã) = ∑_{p̃}(−sign(p̃)) · a_{1p̃(1)} · a_{2p̃(2)} · . . . · a_{np̃(n)} = − det(A).

Q.E.D.

Folgerung 12.47:

a) Stimmen in einer Matrix zwei Spalten überein, so verschwindet ihre Determinante.

b) Addiert man zu einer Spalte ein beliebiges Vielfaches einer anderen Spalte hinzu, so verändert sich der Wert der Determinante nicht.

Beweis: a) Vertauscht man die beiden übereinstimmenden Spalten, muss die Determinante das Vorzeichen wechseln, andererseits aber gleich bleiben. Das kann nur sein, wenn die Determinante 0 ist.

b) Mit der Linearität nach Satz 12.45 gilt

det([a⃗_{1}, …, a⃗_{i}, …, a⃗_{j} + λ · a⃗_{i}, …, a⃗_{n}])

= det([a⃗_{1}, …, a⃗_{i}, …, a⃗_{j} …, a⃗_{n}]) + λ · det([a⃗_{1}, …, a⃗_{i}, …, a⃗_{i} …, a⃗_{n}]), wobei die 2-te Determinante nach a) verschwindet.

Q.E.D.

Satz 12.48: (Invarianz unter Transposition)

Für jedes A ∈ K^{n×n} gilt det(A^{T}) = det(A).

Beweis: Zu jeder Permutation p gibt es die inverse Permutation p^{−1} mit p ∘ p^{−1} = p^{−1} ∘ p = identische Abbildung : i → i, wobei sign(p^{−1}) = sign(p) gilt. Läuft p durch alle Permutationen, läuft auch p^{−1} durch alle Permutationen. Damit gilt

det(A) = ∑_{p} sign(p) · a_{1p(1)} · a_{2p(2)} · . . . · a_{np(n)},

= ∑_{p} sign(p^{−1}) · a_{1p^{−1}(1)} · a_{2p^{−1}(2)} · . . . · a_{np^{−1}(n)}.

Für j = p^{−1}(i) ergibt sich mit a_{ip^{−1}(i)} = a_{p(j)j} nach geeigneter Umsortierung der Reihenfolge der Faktoren im Produkt:

det(A) = ∑_{p} \underbrace{sign(p^{−1})}_{=sign(p)} ·a_{p(1)1} · a_{p(2)2} · . . . · a_{p(n)n}. (#)

Dies ist mit a_{ji} = (A^{T})_{ij} die Formel für det(A^{T}).

Q.E.D.

Folgerung 12.49:

Die Rolle von Zeilen und Spalten sind bei der Determinantenberechnung austauschbar.

Beispielsweise verschwindet analog zu Folgerung 12.47.a) die Determinante, wenn zwei Zeilen übereinstimmen. Man kann ein Vielfaches einer Zeile zu einer anderen addieren, ohne die Determinante zu verändern usw.

Definition 12.50: (Minoren)

Zu A ∈ K^{n×n} und i, j ∈ {1, …, n} definiere den ”Minor“

m_{ij} = det (( a_{11} … a_{1j} … a_{1n} ; ⋮ ... ⋮ ... ⋮ ; a_{i1} … a_{ij} … a_{in} ; ⋮ ... ⋮ ... ⋮ ; a_{n1} … a_{nj} … a_{nn} )) ,

d.h., die (Unter-)Determinante, die durch Streichen der Zeile i und der Spalte j entsteht.

Der folgende Satz liefert eine rekursive Berechnungsmöglichkeit für Determinanten. Durch ”Entwicklung nach einer Spalte bzw. Zeile“ ergibt sich eine (n × n)- Determinante als Summe über Minoren (also ((n−1)×(n−1))-Determinanten), so dass man rekursiv die Matrixdimension reduzieren kann, bis sich eine große Summe von (1×1)-Determinanten ergibt, die durch den entsprechenden Matrixeintrag gegeben sind.

Satz 12.51: (Laplacescher Entwicklungssatz)

Seien m_{ij} die Minoren der Matrix A ∈ K^{n×n}. Für jede Spalte j gilt

det(A) = ∑_{i=1}^{n}(−1)^{i+j} · a_{ij} · m_{ij}.

Man nennt diese Formel ”Entwicklung der Determinante nach der j-ten Spalte“.

Für jede Zeile i gilt

det(A) = ∑_{j=1}^{n}(−1)^{i+j} · a_{ij} · m_{ij}.

Man nennt diese Formel ”Entwicklung der Determinante nach der i-ten Zeile“.

Beweisskizze: (Technisch) Wir entwickeln zunächst nach der letzten Spalte, wobei wir die Darstellung (#) aus dem Beweis von Satz 12.48 verwenden. In

det(A) = ∑_{p} sign(p) · a_{p(1)1} · a_{p(2)2} · . . . · a_{p(n)n}

fixieren wir beim Durchlauf durch alle Permutationen zunächst den Bildwert für n, d.h., wir geben p(n) = i mit i ∈ {1, …, n} vor:

det(A) = ∑_{i=1}^{n} a_{in} · ∑_{p_{i}} sign(p_{i}) · a_{p_{i}(1)1} · . . . · a_{p_{i}(n−1),n−1},

wobei im i-ten Summanden die (Teil-)Permutation p_{i} alle invertierbaren Abbildungen {1, 2, …, n−1} → {1, …, n}\{i} zu durchlaufen hat. (In sign(p_{i}) ist p_{i} als Permutation aller Zahlen {1, …, n} mit vorgebenem p_{i}(n) = i aufzufassen.) Offensichtlich enthält

∑_{p_{i}} sign(p_{i}) · a_{p_{i}(1)1} · . . . · a_{p_{i}(n−1),n−1}

alle Terme, die in der Definition des Minors m_{in} auftauchen (der Zeilenindex nimmt alle Werte in {1, …, n} \ {i} an, der Spaltenindex n taucht im Produkt a_{p_{i}(1)1} · . . . · a_{p_{i}(n−1),n−1} nicht auf). Es verbleibt, die Vorzeichen sign(p_{i}) nachzuhalten. Sei

p̃_{i}(k) = \{ \begin{matrix}p_{i}(k) & falls p_{i}(k) ∈ \{1, …, i − 1\}, \\ i & falls p_{i}(k) = i, also k = n, \\ p_{i}(k) − 1 & falls p_{i}(k) ∈ \{i + 1, …, n\}. \end{matrix}

Diese Permutation unterscheidet sich von p_{i} durch die n − i Vertauschungen i ↔ i + 1, i + 1 ↔ i + 2, …, n − 1 ↔ n, also gilt sign(p_{i}) = (−1)^{n−i} · sign(p̃_{i}):

∑_{p_{i}} sign(p_{i})·a_{p_{i}(1)1}·. . .·a_{p_{i}(n−1),n−1} = (−1)^{n−i} ∑_{p̃_{i}} sign(p̃_{i})·ã_{p̃_{i}(1)1}·. . .·ã_{p̃_{i}(n−1),n−1},

wobei (ã_{ij}) die Matrix ist, die durch Streichen der i-ten Zeile aus A = (a_{ij}) entsteht (die ursprüngliche i-te Zeile kann man sich als n-te Zeile von (ã_{ij}) vorstellen). Die Permutation p̃_{i} : {1, …, n − 1} → {1, …, n − 1} ist als Permutation der Zahlen {1, …, n − 1} interpretierbar. Damit ist die obige Summe über die p̃_{i} nichts anderes als die Determinate der Ausgangsmatrix A, aus der die i-te Zeile und die n-te Spalte gestrichen wurde (also der Minor m_{in} der Matrix (a_{ij})):

∑_{p_{i}} sign(p_{i}) · a_{p_{i}(1)1} · . . . · a_{p_{i}(n−1),n−1} = (−1)^{n−i} · m_{in} = (−1)^{n+i} · m_{in}.

Insgesamt erhält man also die ”Entwicklung nach der n-ten Spalte“

det(A) = ∑_{i=1}^{n}(−1)^{i+n} · a_{in} · m_{in}.

Will man nicht nach der n-ten Spalte sondern nach der j-ten Spalte entwickeln, lösche man in der Ausgangsmatrix die j-te Spalte, lasse die Spalten j + 1 bis n nach links rücken und stecke die ursprünglich j-te Spalte in die n-te Spalte (dies entspricht den n − j Spaltenvertauschungen j ↔ j + 1, dann j + 1 ↔ j + 2 usw. bis n − 1 ↔ n. Entwickle nach der neuen n-ten Spalte (dies ist die alte j-te Spalte). Nach den obigen Überlegungen gilt

det(A′) = ∑_{i=1}^{n}(−1)^{i+n} · a′_{in} · m′_{in},

wo A′ = (a′_{ij}) durch die obigen Spaltenvertauschungen aus A entsteht. Speziell gilt also a′_{in} = a_{ij}. Für die entsprechenden Minoren gilt m′_{in} = m_{ij}. Nach n − j Spaltenvertauschungen gilt

det(A′) = (−1)^{n−j} · det(A) = (−1)^{j−n} · det(A),

12.4. DETERMINANTEN 249

also

det(A) = ∑_{i=1}^{n}(−1)^{i+j} · a_{ij} · m_{ij}.

Damit haben wir die ”Entwicklung nach der j-ten Spalte“.

Da nach Satz 12.48 die Rolle von Zeilen und Spalten gegeneinander ausgetauscht werden können, kann man statt nach Spalten auch nach Zeilen entwickeln.

Q.E.D.

Beispiel 12.52: Wir entwickeln eine (2 × 2)-Determinante nach der ersten Spalte:

det (( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )) = a_{11} · det((a_{22})) − a_{21} · det((a_{12})) = a_{11} · a_{22} − a_{12} · a_{21}.

Entwicklung nach der zweiten Zeile:

det (( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )) = −a_{21} · det((a_{12})) + a_{22} · det((a_{11})) = a_{11} · a_{22} − a_{12} · a_{21}.

Beispiel 12.53: Wir entwickeln eine (3 × 3)-Determinante nach der zweiten Spalte:

det (( \begin{matrix}1 & 2 & 1 \\ 0 & 3 & 2 \\ 0 & 4 & 5 \end{matrix} )) =

−2 · det (( \begin{matrix}1̸ & 2̸ & 1̸ \\ 0 & 3̸ & 2 \\ 0 & 4̸ & 5 \end{matrix} )) + 3 · det (( \begin{matrix}1 & 2̸ & 1 \\ 0̸ & 3̸ & 2̸ \\ 0 & 4̸ & 5 \end{matrix} )) − 4 · det (( \begin{matrix}1 & 2̸ & 1 \\ 0 & 3̸ & 2 \\ 0̸ & 4̸ & 5̸ \end{matrix} ))

= −2 · det (( \begin{matrix}0 & 2 \\ 0 & 5 \end{matrix} )) + 3 · det (( \begin{matrix}1 & 1 \\ 0 & 5 \end{matrix} )) − 4 · det (( \begin{matrix}1 & 1 \\ 0 & 2 \end{matrix} ))

= −2 · 0 + 3 · 5 − 4 · 2 = 7.

Entwicklung nach der ersten Spalte:

det ( ; ( \begin{matrix}1 & 2 & 1 \\ 0 & 3 & 2 \\ 0 & 4 & 5 \end{matrix} ) ; ) = 1 · det ( ; ( \begin{matrix}1̸ & 2̸ & 1̸ \\ 0̸ & 3 & 2 \\ 0̸ & 4 & 5 \end{matrix} ) ; ) − 0 · (...) + 0 · (...) = 1 · (15 − 8) = 7.

Beobachtung: man spart sich Rechenarbeit, wenn man nach Zeilen oder Spalten mit möglichst vielen Nullen entwickelt, da die entsprechenden Minoren gar nicht ausgerechnet werden brauchen (sie werden sowieso mit 0 multipliziert und tragen zur Determinante nichts bei).

Es ist rechentechnisch günstig, nach Zeilen oder Spalten mit möglichst vielen Nullen zu entwickeln.

↓28.1.04

Mit Folgerung 12.47.b) hat man eine Möglichkeit, Nullen in der Matrix zu erzeugen, indem man geeignete Vielfache einer Zeile/Spalte von einer anderen Zeile/Spalte abzieht. Hier ein Beispiel. In

det (( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{matrix} ))

subtrahieren wir zunächst die zweite Zeile von der dritten:

det (( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{matrix} )) = det (( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 3 & 3 & 4 \end{matrix} )) .

Wir subtrahieren die erste Zeile von der zweiten:

det (( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 3 & 3 & 4 \end{matrix} )) = det (( \begin{matrix}1 & 2 & 3 \\ 3 & 3 & 3 \\ 3 & 3 & 4 \end{matrix} )) .

Wir subtrahieren die erste Spalte von der zweiten:

det (( \begin{matrix}1 & 2 & 3 \\ 3 & 3 & 3 \\ 3 & 3 & 4 \end{matrix} )) = det (( \begin{matrix}1 & 1 & 3 \\ 3 & 0 & 3 \\ 3 & 0 & 4 \end{matrix} )) .

Entwicklung nach der zweiten Spalte liefert:

det (( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{matrix} )) = det (( \begin{matrix}1 & 1 & 3 \\ 3 & 0 & 3 \\ 3 & 0 & 4 \end{matrix} )) = −1 · det (( \begin{matrix}3 & 3 \\ 3 & 4 \end{matrix} )) = −3.

Definition 12.54: (Dreiecksmatrizen)

Eine Matrix der Form

( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ 0 & a_{22} & … & a_{2n} \\ ⋮ & ... & ... & ⋮ \\ 0 & … & 0 & a_{nn} \end{matrix} )

heißt ”obere Dreiecksmatrix“. Eine Matrix der Form

( \begin{matrix}a_{11} & 0 & … & 0 \\ a_{21} & a_{22} & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ a_{n1} & … & … & a_{nn} \end{matrix} )

heißt ”untere Dreiecksmatrix“.

Satz 12.55:

Die Determinante einer Dreiecksmatrix ist das Produkt der Diagonalelemente.

Beweis: Entwickle bei einer oberen Dreiecksmatrix die Determinanten rekursiv jeweils nach der ersten Spalte:

det (( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ 0 & a_{22} & … & a_{2n} \\ ⋮ & ... & ... & ⋮ \\ 0 & … & 0 & a_{nn} \end{matrix} ))

= a_{11} · det (( \begin{matrix}a_{22} & a_{23} & … & a_{2n} \\ 0 & a_{33} & … & a_{3n} \\ ⋮ & ... & ... & ⋮ \\ 0 & … & 0 & a_{nn} \end{matrix} ))

= a_{11} · a_{22} · det (( \begin{matrix}a_{33} & a_{34} & … & a_{3n} \\ 0 & a_{44} & … & a_{4n} \\ ⋮ & ... & ... & ⋮ \\ 0 & … & 0 & a_{nn} \end{matrix} ))

usw. Bei unteren Dreiecksmatrizen entwickelt man analog rekursiv nach der ersten Zeile.

Q.E.D.

Nun ein fundamentaler Satz, der das eindeutige Indiz dafür ist, dass der Determinantenbegriff vernünftig mit Matrizen und ihrer Multiplikation zusammenspielt:

Satz 12.56: (Determinante eines Matrixprodukts)

Für A, B ∈ K^{n×n} gilt

det(A B) = det(A) · det(B).

Beweis: Wir benutzen die Spaltenzerlegung A = [a⃗_{1}, …, a⃗_{n}]. Mit

(AB)_{ij} = ∑_{k=1}^{n} a_{ik} · b_{kj}

folgt die Spaltenzerlegung

AB = [ ∑_{k_{1}=1}^{n} a⃗_{k_{1}} · b_{k_{1}1}, ∑_{k_{2}=1}^{n} a⃗_{k_{2}} · b_{k_{2}2}, …, ∑_{k_{n}=1}^{n} a⃗_{k_{n}} · b_{k_{n}n}] .

Da die Determinante linear in jeder Spalte ist, folgt

det(AB) = ∑_{k_{1}=1}^{n} ∑_{k_{2}=1}^{n} ⋯ ∑_{k_{n}=1}^{n} det([a⃗_{k_{1}}, a⃗_{k_{2}}, …, a⃗_{k_{n}}]) · b_{k_{1}1} · b_{k_{2}2} · . . . · b_{k_{n}n}.

In dieser n-fachen Summe (mit n^{n} Termen) sind nur diejenigen Terme vorhanden, in denen die Summationsindizes k_{1}, …, k_{n} alle verschieden sind (bei den anderen Termen taucht in der Determinante der Spalten von A mindestens eine Spalte mehrfach auf und liefert 0). Die Mehrfachsumme reduziert sich damit auf die n! Summanden, in denen k_{1}, …, k_{n} eine Permutation von {1, …, n} darstellt:

det(AB) = ∑_{p} det([a⃗_{p(1)}, a⃗_{p(2)}, …, a⃗_{p(n)}]) · b_{p(1)1} · b_{p(2)2} · . . . · b_{p(n)n}.

Durch Vertauschen der Spalten in der Determinante der Spalten von A erhält man

det([a⃗_{p(1)}, a⃗_{p(2)}, …, a⃗_{p(n)}]) = sign(p) · det([a⃗_{1}, a⃗_{2}, …, a⃗_{n}]) = sign(p) · det(A),

so dass sich ergibt:

det(AB) = det(A) · ∑_{p} sign(p) · b_{p(1)1} · b_{p(2)2} · . . . · b_{p(n)n}

= det(A) · det(B^{T}) = det(A) · det(B).

Q.E.D.

Definition 12.57: (Adjunktenmatrix)

Einer Matrix A ∈ K^{n×n} mit den Minoren m_{ij} gemäß Definition 12.50 wird die “Adjunktenmatrix“ A_{adj} ∈ K^{n×n} zugeordnet:

(A_{adj})_{ij} = (−1)^{i+j} · m_{ji}.

Satz 12.58:

Für jedes A ∈ K^{n×n} mit der Adjunktenmatrix A_{adj} gilt:

A_{adj}A = A A_{adj} = det(A) · I 1.

Beweis: Sei A = (a_{ij}) = [a⃗_{1}, …, a⃗_{n}], A_{adj} = (b_{ij}) = ((−1)^{i+j} · m_{ji}). Es gilt

(A_{adj}A)_{ij} = ∑_{k=1}^{n} b_{ik} · a_{kj} = ∑_{k=1}^{n}(−1)^{i+k} · m_{ki} · a_{kj}.

Diese Summe ist die Entwicklung der Determinante

i
↓
det([a⃗_{1}, …, b⃗, …, a⃗_{n}])

mit b⃗ = a⃗_{j} nach der i-ten Zeile. Für i ≠ j taucht in dieser Determinante zweimal die Spalte a⃗_{j} auf und liefert 0. Für i = j ergibt sich det([a⃗_{1}, …, a⃗_{n}]) = det(A):

(A_{adj}A)_{ij} = \{ \begin{matrix}det(A) & für i = j, \\ 0 & für i ≠ j. \end{matrix}

Um zu zeigen, dass auch A A_{adj} = det(A) · I 1 gilt, betrachte man A_{adj}^{T}A^{T}. Nach Zerlegung von A^{T} in Spalten ergibt sich analog zu oben A_{adj}^{T}A^{T} = det(A^{T}) · I 1. Durch Transposition folgt dann

(A_{adj}^{T}A^{T})^{T} = AA_{adj} = (det(A^{T}) · I 1)^{T} = det(A) · I 1.

Q.E.D.

Folgerung 12.59:

Eine quadratische Matrix A ist genau dann invertierbar, wenn det(A) ≠ 0 gilt. Mit der Adjunktenmatrix A_{adj} gilt:

A^{−1} = \frac{1}{det(A)} · A_{adj}.

Satz 12.60: (Die Cramersche Regel)

Wir betrachten das System

a_{11} · x_{1} + ⋯ + a_{1n} · x_{n} = b_{1},
⋮  ⋮  ⋮  ⋮
a_{n1} · x_{1} + ⋯ + a_{nn} · x_{n} = b_{n}

von n linearen Gleichungen für die n Unbekannten x_{1}, …, x_{n}. Mit A = (a_{ij}) ∈ K^{n×n}, x⃗ = (x_{1}, …, x_{n})^{T}, b⃗ = (b_{1}, …, b_{n})^{T} ergibt sich die kompakte Schreibweise

Ax⃗ = b⃗.

Es gibt genau dann eine eindeutige Lösung x⃗ = A^{−1}b⃗, wenn det(A) ≠ 0 gilt. Die Komponenten der Lösung sind gegeben durch

i
↓

x_{i} = \begin{matrix}det & (( \begin{matrix}a_{11} & … & b_{1} & … & a_{1n} \\ ⋮ & ... & ⋮ & ... & ⋮ \\ a_{n1} & … & b_{n} & … & a_{nn} \end{matrix} )) \\ det & (( \begin{matrix}a_{11} & … & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{n1} & … & a_{nn} \end{matrix} )) \end{matrix}

mit i = 1, …, n.

Beweis: Wir benutzen (A^{−1})_{ij} = \frac{1}{det(A)} ·(−1)^{i+j} ·m_{ji} mit den Minoren m_{ij} von A. Es folgt

x_{i} = (A^{−1}b⃗)_{i} = ∑_{j=1}^{n}(A^{−1})_{ij} · b_{j} = \frac{1}{det(A)} · ∑_{j=1}^{n}(−1)^{i+j} · m_{ji} · b_{j}.

Hierbei ist ∑_{j=1}^{n}(−1)^{i+j} · m_{ji} · b_{j} die Entwicklung von

det([a⃗_{1}, …, b⃗, …, a⃗_{n}])

nach der i-ten Spalte, wo a⃗_{1}, …, a⃗_{n} die Spalten von A sind und die Spalte a⃗_{i} durch die Spalte b⃗ ersetzt wurde.

Q.E.D.

12.5 Lineare Gleichungssysteme

Im letzten Abschnitt haben wir ein System Ax⃗ = b⃗ von n linearen Gleichungen für n Unbekannte x⃗ = (x_{1}, …, x_{n})^{T} gelöst, vorausgesetzt dass die Koeffizientenmatrix A invertierbar ist:

x⃗ = A^{−1}b⃗.

Hierbei wurden explizite Lösungsformeln gefunden: die Inverse A^{−1} läßt sich über die Adjunktenmatrix von A mittels Determinanten bestimmen, die Lösung x⃗ ist direkt über die Cramersche Regel 12.60 mittels Determinanten auszudrücken. Dies ist jedoch noch nicht die endgültige Antwort auf die Aufgabenstellung ”Lösung linearer Gleichungssysteme“. Es verbleiben die Probleme:

• Was passiert bei nicht-invertierbaren Koeffizientenmatrizen? Was ist, wenn n Gleichungen für m Unbekannte (mit n ≠ m) zu lösen sind?

• Die Determinantenformeln sind uneffektiv: die bisher vorgestellte Berechnung von Determinanten (z.B. rekursiv über Laplace-Entwicklung nach Zeilen oder Spalten) braucht viel zu viele Rechenschritte. (Eine (n × n)- Determinante besteht aus einer Summe von n! Termen. Die Stirling-Nähe-rung 9.58 sagt z.B. für n = 100 etwa n! ≈ 9.3 × 10^{157} Summanden für die Determinante voraus).

Das Determinantenkalkül des letzten Abschnitts ist in der Tat mehr als allgemeine Strukturtheorie anzusehen, deren wesentliches Ergebnis die Aussage

Ax⃗ = b⃗ mit invertierbarem A hat genau dann eine eindeutige Lösung x⃗ = A^{−1}b⃗, wenn det(A) ≠ 0 gilt.

In der Praxis geht man anders vor. Gleichungssysteme mit z.B. n = 100 Unbekannten lassen sich in der Tat in Sekundenbruchteilen lösen, wobei Determinanten keinerlei Rolle spielen.

12.5.1 Quadratische Dreieckssysteme

Ist die Koeffizientenmatrix A in einem linearen Gleichungssystem Ax⃗ = b⃗ von Dreiecksform, so ist die Berechnung der Lösung sehr einfach (und mit wenig Rechenaufwand verbunden):

Satz 12.61: (Rücksubstitution)

Ein lineares System Ax⃗ = b⃗

a_{11} · x_{1}  = b_{1},
a_{21} · x_{1} + a_{22} · x_{2}  = b_{2},
⋮  ⋮  ...  ⋮
a_{n1} · x_{1} + a_{n2} · x_{2} + ⋯ + a_{nn} · x_{n} = b_{n}

mit einer invertierbaren unteren (n × n)-Dreiecksmatrix A = (a_{ij}) wird durch ”Rücksubstitution“

\begin{matrix}x_{1} := b_{1} / a_{11} ; \\ for i := 2 to n do x_{i} := ( b_{i} − ∑_{j=1}^{i−1} a_{ij} · x_{j} ) / a_{ii} ; \end{matrix}

mit

1 + ∑_{i=2}^{n} i = \frac{n(n + 1)}{2} = \frac{n^{2}}{2} ( 1 + O (\frac{1}{n}) )

Multiplikationen/Divisionen (und ähnlich vielen Additionen) gelöst.

Bei einem System

a_{11} · x_{1} + ⋯ + a_{1,n−1} · x_{n−1} + a_{1n} · x_{n} = b_{1}
...  ⋮  ⋮  ⋮
a_{n−1,n−1} · x_{n−1} + a_{n−1,n} · x_{n} = b_{n−1}
a_{nn} · x_{n} = b_{n}

mit invertierbarer oberer (n × n)-Dreiecksmatrix A = (a_{ij}) lautet die Rücksubstitution:

x_{n} := b_{n} / a_{nn} ;

for i := n − 1 downto 1 do x_{i} := ( b_{i} − ∑_{j=i+1}^{n} a_{ij} · x_{j} ) / a_{ii} ;

Beweis: Im Fall eines unteren Dreieckssystems liefert die erste Gleichung sofort x_{1} = b_{1}/a_{11}. Eingesetzt in die zweite Gleichung erhält man a_{22}·x_{2} = b_{2}−a_{21}·x_{1}, wodurch sich sofort x_{2} ergibt. Allgemein: hat man x_{1}, …, x_{i−1} bereits bestimmt, liefert die i-te Gleichung

a_{ii} · x_{i} = b_{i} − ∑_{j=1}^{i−1} a_{ij} · x_{j}

den Wert für x_{i}. Beachte: die Koeffizientenmatrix A ist genau dann invertierbar, wenn keines der Diagonalelmente verschwindet, man kann also durch die a_{ii} teilen!

Bei einem oberen Dreieckssystemen startet man mit der letzten Gleichung, um x_{n} zu bestimmen, setzt diesen Wert dann in die vorletzte Gleichung ein, aus der dann x_{n−1} bestimmbar ist usw.

Q.E.D.

Bemerkung 12.62: Der Rechenaufwand von etwa n^{2}/2 Multiplikationen entspricht exakt dem Aufwand, eine Multiplikation einer (n × n)-Dreicksmatrix mit einem Vektor mit n Komponenten durchzuführen. Die Lösung von Ax⃗ = b⃗ bekommt man bei Dreiecksmatrizen also genauso schnell wie die Multiplikation Ax⃗.

12.5.2 Der Gauß-Algorithmus

29.1.04↓ Nun wird der Standardalgorithmus zur Lösung linearer Gleichungssysteme vorgestellt, der

• die allgemeine Lösung von n Gleichungen mit m Unbekannten liefert (auch für n ≠ m),

• mit einer akzeptablen Anzahl von Rechenoperationen auskommt. Faustregel: für n Gleichungen mit n Unbekannten braucht man O(n^{3}) Rechenoperationen.

Es handelt sich dabei um den ”Gauss-Algorithmus“, der je nach Variante als ”Gauss-“, ”Gauss-Jordan-“, ”Entzerrungsalgorithmus“ oder auch als ”LR-Zerlegung“ bezeichnet wird.

Gegeben seien n lineare Gleichungen für m Unbekannte

a_{11} · x_{1} + ⋯ + a_{nm} · x_{m} = b_{1},
⋮  ⋮  ⋮  ⋮
a_{n1} · x_{1} + ⋯ + a_{nm} · x_{m} = b_{n},

die wir bequemer als (n × (m + 1))-Matrix

[A | b⃗ ] = ( \begin{matrix}a_{11} & … & a_{1m} & b_{1} \\ ⋮ & ... & ⋮ & ⋮ \\ a_{n1} & … & a_{nm} & b_{n} \end{matrix} )

kodieren (die ”erweiterte Koeffizientenmatrix“). Jede Zeile

( a_{i1} … a_{im} b_{i} )

ist dabei jeweils als Gleichung zu lesen:

a_{i1} · x_{1} + … + a_{im} · x_{m} = b_{i}.

Elementaroperationen 12.63:

Wir wollen das Gleichungssystem so umschreiben (vereinfachen), dass die Lösung möglichst direkt abgelesen werden kann. Dabei sollen lediglich folgende Elementaroperationen eingesetzt werden:

i) Vertauschen von Gleichungen (= Zeilen von [A | b⃗ ])

ii) Multiplikation einer Gleichung (= Zeile von [A | b⃗ ]) mit einer Zahl iii) Addieren eines Vielfachen einer Gleichung (= Zeile von [A | b⃗ ]) zu

einer anderen Gleichung (= Zeile von [A | b⃗ ]).

Diese Operationen lassen sich als Matrixmultiplikation mit ”Elementarmatrizen“ interpretieren (nicht angzeigte Einträge sind 0):

i) Die Multiplikation A → EA mit

\begin{matrix}i_{1} & i_{2} \\ ↓ & ↓ \end{matrix} ; E = ( \begin{matrix}1 \\ & . & . & . \\ & & & & 1 \\ & & & & & 0 & & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & . & . & . \\ & & & & & & & & & & 1 \\ & & & & & 1 & & & & & & 0 \\ & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & & & 1 \end{matrix} ) \begin{matrix}← i_{1} \\ ← i_{2} \end{matrix}

vertauscht die Zeilen i_{1} und i_{2} in A. Es gilt det(E) = −1 für i_{1} ≠ i_{2} bzw. det(E) = 1 für i_{1} = i_{2}.

ii) Die Multiplikation A → EA mit

\begin{matrix}i \\ ↓ \end{matrix} ; E = ( \begin{matrix}1 \\ & . & . & . \\ & & & & 1 \\ & & & & & λ \\ & & & & & & 1 \\ & & & & & & & . & . & . \\ & & & & & & & & & & 1 \end{matrix} ) ← i

multipliziert die i-te Zeile von A mit dem Faktor λ. Es gilt det(E) = λ.

iii) Die Multiplikation A → EA mit

\begin{matrix}i_{1} \\ ↓ \end{matrix} ; E = ( \begin{matrix}1 \\ & 1 \\ . & . & . \\ & & & . & . & . \\ & & λ & & & & 1 \\ & & & & & & & 1 \end{matrix} ) ← i_{2}

addiert das λ-fache der Zeile i_{1} zur Zeile i_{2}. Es gilt det(E) = 1.

Mit der Forderung λ ≠ 0 in ii) haben alle Elementarmatrizen nichtverschwindende Determinanten, sind also invertierbar. Die Anwendung dieser Matrizen entspricht also einer Äquivalenztransformation, die die Lösung des Gleichungssystems nicht verändert.

Mit diesen Operationen soll das Ausgangsschema

[A | b⃗ ] = ( \begin{matrix}a_{11} & … & a_{1m} & b_{1} \\ ⋮ & ... & ⋮ & ⋮ \\ a_{n1} & … & a_{nm} & b_{n} \end{matrix} )

in eine neue (einfachere) Form [A′ | b⃗′] gebracht werden. Welche Struktur sollte die vereinfachte Koeffizientenmatrix haben? Wenn es uns gelingt, das System Ax⃗ = b⃗ in ein äquivalentes System A′x⃗ = b⃗′ mit A′ = I 1 umzuschreiben, dann sind wir fertig. Nach Abschnitt 12.5.1 reicht es jedoch, als Endform A′ = Dreiecksmatrix anzusteuern, da das verbleibende Dreieckssystem A′x⃗ = b⃗′ schnell per Rücksubstitution 12.61 gelöst werden kann.

Hier nun der Gauß-Algorithmus zur Lösung von n Gleichungen

a_{11} · x_{1} + a_{12} · x_{2} + ⋯ + a_{1m} · x_{m} = b_{1}
a_{21} · x_{1} + a_{22} · x_{2} + ⋯ + a_{2m} · x_{m} = b_{2}
⋮  ⋮  ...  ⋮  ⋮
a_{n1} · x_{1} + a_{n2} · x_{2} + ⋯ + a_{nm} · x_{m} = b_{n}

für m Unbekannte:

1.ter Eliminationsschritt: ziehe geeignete Vielfache der ersten Zeile von den anderen ab, um Nullen unter a_{11} zu erzeugen:

a_{11} · x_{1} + a_{12} · x_{2} + ⋯ + a_{1m} · x_{m} = b_{1}
a_{21}/a_{11}  a′_{22} · x_{2} + ⋯ + a′_{2m} · x_{m} = b′_{2}
⋮  ⋮  ...  ⋮  ⋮
a_{n1}/a_{11}  a′_{n2} · x_{2} + ⋯ + a′_{nm} · x_{m} = b′_{n}

mit

a′_{ik} = a_{ik} − \frac{a_{i1}}{a_{11}} · a_{1k} , b′_{i} = b_{i} − \frac{a_{i1}}{a_{11}} · b_{1} , i = 2, …, n , k = 2, …, m .

Bezeichnung: a_{i1}/a_{11} = “Eliminationsfaktoren”. Im Prinzip stehen unter a_{11} Nullen, d.h., diese Speicherplätze sind frei geworden. Diese werden mit den Eliminationsfaktoren belegt, was nichts kostet, sich aber im Abschnitt 12.6.2 als äußerst wertvoll herausstellen wird.

2.ter Eliminationsschritt: erzeuge Nullen unter a′_{22}:

a_{11} · x_{1} + a_{12} · x_{2} + a_{13} · x_{3} + ⋯ + a_{1n} · x_{m} = b_{1}
a_{21}/a_{11}  a′_{22} · x_{2} + a′_{23} · x_{3} + ⋯ + a′_{2n} · x_{m} = b′_{2}
⋮  a′_{32}/a′_{22}  a′′_{33} · x_{3} + ⋯ + a′′_{3m} · x_{m} = b′′_{3}
⋮  ⋮  ⋮  ...  ⋮  ⋮
a_{n1}/a_{11}  a′_{n2}/a′_{22}  a′′_{n3} · x_{3} + ⋯ + a′′_{nm} · x_{m} = b′′_{n}

mit

a′′_{ik} = a′_{ik} − \frac{a′_{i2}}{a′_{22}} · a′_{2k} , b′′_{i} = b′_{i} − \frac{a′_{i2}}{a′_{22}} · b′_{2} , i = 3, …, n , k = 3, …, m .

j.ter Eliminationsschritt: ziehe Vielfaches der j.ten Zeile von den restlichen Zeilen ab, um unter dem j.ten Diagonalelement Nullen zu erzeugen.

Einzig mögliches Problem: das j.te Diagonalelement verschwindet.

1. Fall: Darunter stehen nur Nullen. Es ist nichts mehr zu tun, gehe zum (j + 1).ten Schritt. Dieser Fall tritt genau dann irgendwann ein, wenn A nicht invertierbar ist.

2. Fall: Es gibt mindestens einen nichtverschwindenden Eintrag unter dem j.ten Diagonalelement. Wähle \underline{irgendeinen} dieser Einträge (das “Pivotelement”), bringe es in die j.te Zeile, indem die \underline{gesamte} Pivotzeile (inklusive der abzuspeichernden Eliminationsfaktoren!) mit der j.ten Zeile ausgetauscht wird. Dann erzeuge die gewünschten Nullen.

Algorithmus 12.64: (Gauß-Elimination = LR-Zerlegung, siehe Satz 12.75) Erweitere A = (a_{ij}) ∈ K^{n×m} zum n × (m + 1)-Schema:

( \begin{matrix}a_{11} & … & a_{1m} & a_{1,m+1} \\ ⋮ & ... & ⋮ & ⋮ \\ a_{n1} & … & a_{nm} & a_{n,m+1} \end{matrix} ) mit a_{i,n+1} = b_{i}, i = 1, …, n .

for j := 1 to min(m, n) do begin falls a_{jj} = a_{j+1,j} = ⋯ = a_{nj} = 0, so gehe zum (j + 1).ten Schritt ; p := Pivotindex(j)∈ {j, j + 1, …, n} ; Vertauschung der Zeilen j und p im n × (m + 1)-Schema ; for i := j + 1 to n do begin

a_{ij} := a_{ij}/a_{jj} ; (∗ Abspeichern der Eliminationsfaktoren ∗) for k := j + 1 to m + 1 do a_{ik} := a_{ik} − a_{ij} a_{jk} ;

end ; end ;

Hierbei ist Pivotindex(j) der Aufruf einer Prozedur, welche unter den Werten {a_{jj}, a_{j+1,j}, …, a_{nj}} ein Element sucht, das nicht verschwindet, und den entsprechenden Zeilenindex p zurückgibt. Im Prinzip kann irgendein nichtverschwindendes Pivotelement gewählt werden. Aus Gründen der numerischen Stabilität (minimiere den Einfluss von Rundungsfehlern bei Gleitpunktarithmetik) wählt man meist p =Pivotindex(j) so, dass

|a_{pj}| = max(|a_{jj}|, |a_{j+1,j}|, …, |a_{nj}|)

gilt (d.h., das Pivotelement a_{pj} ist das betragsgrößte Element im unteren Teil der j-ten Spalte).

Resultat: zuletzt ist das zu Ax⃗ = b⃗ äquivalente obere Dreieckssystem Rx⃗ = c⃗

( \begin{matrix}r_{11} & ⋯ & r_{1n} & c_{1} \\ & ... & ⋮ & ⋮ \\ ∗ & & r_{nn} & c_{n} \end{matrix} ) (für n = m)

bzw.

( \begin{matrix}r_{11} & ⋯ & r_{1n} & … & r_{1m} & c_{1} \\ & ... & ⋮ & ... & ⋮ & ⋮ \\ ∗ & & r_{nn} & … & r_{nm} & c_{n} \end{matrix} ) (für n < m)

bzw.

( \begin{matrix}r_{11} & ⋯ & r_{1m} & c_{1} \\ ∗ & ... & ⋮ & ⋮ \\ ⋮ & ... & r_{mm} & c_{m} \\ ⋮ & ... & ∗ & c_{m+1} \\ ⋮ & ... & ⋮ & ⋮ \\ ∗ & ... & ∗ & c_{n} \end{matrix} ) (für n > m)

im (n × (m + 1))-Schema gespeichert. Mit ∗ sind dabei die abgespeicherten Eliminationsfaktoren angedeutet, die erst im Abschnitt 12.6.2 von Bedeutung sein werden.

Rechenaufwand zur Erzeugung des oberen Dreieckssystems:

∑_{j=1}^{min(m,n)} ∑_{i=j+1}^{n} (1 + ∑_{k=j+1}^{m+1} 1) =

\{ \begin{matrix}\frac{n · (n − 1) · (3 · m − n + 5)}{6} & für n ≤ m \\ \frac{m · (3 · m · n − m · n − 6 · m + 9 · n − 5)}{6} & für n ≥ m \end{matrix}

Multiplikationen (und ähnlich viele Additionen). Für den in der Praxis wichtigsten Fall m = n sind dies

\frac{n (n − 1) (2 · n + 5)}{6} = \frac{n^{3}}{3} · (1 + O(\frac{1}{n}))

Multiplikationen.

Bemerkung 12.65: Die Umformung Ax⃗ = b⃗ ⟺ Rx⃗ = c⃗ funktioniert immer, selbst wenn A nicht invertierbar ist (wobei dann auch R nicht invertierbar ist).

Bemerkung 12.66: Wir diskutieren den Fall, dass die Anzahl n der Gleichungen nicht mit der Anzahl m der Unbekannten übereinstimmt:

Fall n < m (weniger Gleichungen als Unbekannte):

Das vom Gauß-Algorithmus gelieferte obere Dreieckssystem hat die Form

( \begin{matrix}r_{11} & ⋯ & r_{1n} & … & … & r_{1m} & c_{1} \\ & ... & ⋮ & ... & ... & ⋮ & ⋮ \\ & & r_{nn} & … & … & r_{nm} & c_{n} \end{matrix} ) .

Durch Hinzufügen von m − n triviale Gleichungen 0 = 0

( \begin{matrix}r_{11} & ⋯ & r_{1n} & … & … & r_{1m} & c_{1} \\ & ... & ⋮ & ... & ... & ... & ⋮ \\ & & r_{nn} & … & … & r_{nm} & c_{n} \\ & & & 0 & … & 0 & 0 \\ & & & & ... & ⋮ & ⋮ \\ & & & & & 0 & 0 \end{matrix} )

ergibt sich ein quadratisches oberes (m × m)-System, dessen allgemeine Lösung im nächsten Abschnitt 12.5.3 beschrieben wird.

Fall n > m (mehr Gleichungen als Unbekannte):

Das vom Gauß-Algorithmus gelieferte obere Dreieckssystem hat die Form

( r_{11} ⋯ r_{1m} c_{1} ; ... ⋮  ⋮ ; r_{mm} c_{m} ; c_{m+1} ; ⋮ ; c_{n} ) .

Ist irgendeiner der Werte c_{m+1}, …, c_{n} ungleich 0, ist das Gleichungssystem nicht lösbar (dort stehen die Gleichungen 0 = c_{p} mit p = m + 1, … n). Sei nun c_{m+1} = … = c_{n} = 0. Man wirft diese trivialen Gleichungen fort und erhält ein (m × m)-Gleichungsystem

( \begin{matrix}r_{11} & ⋯ & r_{1m} & c_{1} \\ & ... & ⋮ & ⋮ \\ & & r_{mm} & c_{m} \end{matrix} ) ,

dessen allgemeine Lösung im nächsten Abschnitt 12.5.3 beschrieben wird. Es sollte im Fall n > m erwähnt werden, dass man in der Praxis nicht wirklich den Gauß-Algorithmus verwendet, da man wegen der Rundungsfehler bei Gleitpunktarithmetik die Entscheidung, ob c_{m+1} = … = c_{n} = 0 gilt, nicht fundiert treffen kann (es stehen dort kleine Zahlenwerte, die eventuell reine Rundungsartefakte sein können). Stattdessen benutzt man sogenannte ”Singulärwertzerlegungen“ zum Lösen überbestimmter Gleichungssysteme.

12.5.3 Die allgemeine Lösung des Dreieckssystems

↓3.2.04

Der Gauß-Algorithmus hat aus den ursprünglichen n Gleichungen Ax⃗ = b⃗ für m Unbekannte ein äquivalentes oberes Dreieckssystem Rx⃗ = c⃗ gemacht. Hierbei haben wir gemäß Bemerkung 12.66 für n < m triviale Gleichungen hinzugenommen bzw. für n > m triviale Gleichungen entfernt, um zu einem quadratischen System zu kommen (genausoviele Gleichungen wie Unbekannte). Wir haben nun also noch die Situtation eines quadratischen Systems (m = n) in oberer Dreiecksform

r_{11} · x_{1} + … + r_{1n} · x_{n} = c_{1}
...  ⋮  ⋮
r_{nn} · x_{n} = c_{n}

zu diskutieren, wobei allerdings evtl. einige Diagonalelemente verschwinden können.

Fall 1, kein Diagonalelement verschwindet: In diesem Fall gilt det(R) ≠ 0. Da R durch Anwendungen von invertierbaren Elementartransformationen 12.63 aus A entsteht, muss auch det(A) ≠ 0 gelten, d.h., wir lesen an den Diagonalelementen von R ab, dass das Ausgangssystem Ax⃗ = b⃗ wegen Invertierbarkeit von A eindeutig lösbar ist. Das vorliegende äquivalente Dreieckssystem Rx⃗ = c⃗ kann schnell durch Rücksubstitution 12.61 gelöst werden.

Fall 2, einige Diagonalelemente verschwinden (”Entzerrungsalgorithmus“): Wie oben folgt det(R) = 0 genau dann, wenn det(A) = 0 gilt. Wir lesen also an den verschwindenden Diagonalelementen von R ab, dass das Ausgangssystem Ax⃗ = b⃗ wegen Nichtinvertierbarkeit von A nicht eindeutig lösbar ist.

\underline{Reduktion auf Treppenform:} Wir haben ein quadratisches oberes Dreieckssystem vor uns, in dem längs der Diagonalen einige Elemente verschwinden. Mit ∗ deuten wir nicht-verschwindende Elemente an, der rechte obere Teil des Schemas ist mit irgendwelchen Elementen besetzt:

( \begin{matrix}∗ & & & & & ∗ & ∗ & & & & ∗ \\ & ... & & & & & ... & ... & & & ⋮ \\ & & ∗ & & & & & ... & ... & & ⋮ \\ & & & 0 & & & ∗ & & ... & ∗ & ∗ \\ & & & & ∗ & & & & & ∗ & ∗ \\ & & & & & ∗ & & & & & ∗ \\ & & & & & & 0 & ∗ & & & ∗ \\ & & & & & & & ∗ & & & ∗ \\ & & & & & & & & ... & & ∗ \\ & & & & & & & & & ... & ⋮ \end{matrix} )

Unser Ziel ist es zunächst, alle Zeilen mit 0 auf der Diagonalen zu Nullzeilen zu reduzieren. Dazu mache für jede Zeile mit einer 0 auf der Diagonale die folgenden Schritte. Sei i der Zeilenindex dieser Zeile.

• Ist die Zeile eine Nullzeile: tue gar nichts und gehe zur nächsten Zeile.

• Ist die i-te Zeile keine Nullzeile: Suche das erste nicht-verschwindende Element in dieser Zeile. Es habe den Spaltenindex j. Ist das j-te Diagonalelement des Schemas 0, so vertausche die Zeilen i und j. Ist das j-te Diagonalelement des Schemas ≠ 0, so ziehe ein geeignetes Vielfaches der j-ten Zeile von der i-ten Zeile ab, damit das j-te Element der i-ten Zeile verschwindet.

• Wiederhole die obigen Schritte für die i-te Zeile, bis diese eine Nullzeile ist.

Das Gleichungssystem hat nun ”obere Treppenform“:

( \begin{matrix}∗ & & & & ∗ & ∗ & & & & ∗ \\ & ... & & & & ... & ... & & & ⋮ \\ & & ∗ & & & & ... & ... & & ∗ \\ & & & 0 & 0 & 0 & … & 0 & 0 & ∗ \\ & & & & ∗ & ∗ & … & … & ∗ & ∗ \\ & & & & & 0 & 0 & … & 0 & ∗ \\ & & & & & & ∗ & & & ∗ \\ & & & & & & & ... & & ⋮ \\ & & & & & & & & ... & ⋮ \end{matrix} ) (#)

Rechts neben den Nullen auf der Diagonale können jetzt nur noch Nullen stehen. Steht in der letzten Spalte des Schemas (eine der Komponenten d_{i} der rechten Seite d⃗ von Rx⃗ = d⃗) rechts neben einer Nullzeile ein nicht-verschwindender Eintrag, so ist das Gleichungssystem insgesamt nicht lösbar: diese Gleichung besagt 0 = d_{i} ≠ 0.

\underline{Elimination ”nach oben“:} Laufe von rechts unten nach links oben durch die Diagonale:

• Ist das Diagonalelement ungleich Null, mache es zu 1, indem die gesamte Zeile durch das Diagonalelement geteilt wird. Dann erzeuge über dem Diagonalelement Nullen, in dem geeignete Vielfache diese Zeile von den oberen Zeilen abgezogen werden.

Es verbleiben längs der Diagonalen nur noch Nullen und Einsen. Über den Einsen stehen nur noch Nullen, über den Nullen auf der Diagonale verbleiben irgendwelche Einträge:

( \begin{matrix}1 & 0 & & ∗ & & 0 & & ∗ & & 0 & & d_{1} \\ & ... & & ⋮ & & ⋮ & & ⋮ & & ⋮ & & ⋮ \\ & & 1 & ∗ & & ⋮ & & ∗ & & ⋮ & & d_{i_{1}−1} \\ & & & 0 & & ⋮ & & 0 & & ⋮ & & 0 \\ & & & & 1 & 0 & & ∗ & & ⋮ & & d_{i_{1}+1} \\ & & & & & ... & & ⋮ & & ⋮ & & ⋮ \\ & & & & & & 1 & ∗ & & ⋮ & & d_{i_{2}−1} \\ & & & & & & & 0 & & ⋮ & & 0 \\ & & & & & & & & 1 & 0 & & d_{i_{2}+1} \\ & & & & & & & & & ... & & ⋮ \\ & & & & & & & & & & ... & ⋮ \end{matrix} ) . (##)

\underline{Entzerrung:}

• Ersetze die Nullen auf der Diagonale durch −1. Das Schema hat nun die Endform

( \begin{matrix}1 & 0 & & ∗ & & 0 & & ∗ & & 0 & & d_{1} \\ & ... & & ∗ & & ⋮ & & ∗ & & ⋮ & & ⋮ \\ & & 1 & ∗ & & ⋮ & & ∗ & & ⋮ & & d_{i_{1}−1} \\ & & & −1 & & ⋮ & & 0 & & ⋮ & & 0 \\ & & & & 1 & 0 & & ∗ & & ⋮ & & d_{i_{1}+1} \\ & & & & & ... & & ∗ & & ⋮ & & ⋮ \\ & & & & & & 1 & ∗ & & ⋮ & & d_{i_{2}−1} \\ & & & & & & & −1 & & ⋮ & & 0 \\ & & & & & & & & 1 & 0 & & d_{i_{2}+1} \\ & & & & & & & & & ... & & ⋮ \\ & & & & & & & & & & ... & ⋮ \end{matrix} ) , (###)

an dem sich die allgemeine Lösung unmittelbar ablesen läßt:

( x_{1} ; ⋮ ; ⋮ ; ⋮ ; ⋮ ; ⋮ ; ⋮ ; ⋮ ; x_{n} ) = ( d_{1} ; ⋮ ; d_{i_{1}−1} ; 0 ; d_{i_{1}+1} ; ⋮ ; d_{i_{2}−1} ; 0 ; d_{i_{2}+1} ; ⋮ ) + λ_{1} · ( ∗ ; ⋮ ; ∗ ; −1 ; 0 ; ⋮ ; ⋮ ; ⋮ ; ⋮ ; 0 ) + λ_{2} · ( ∗ ; ⋮ ; ∗ ; 0 ; ∗ ; ⋮ ; ∗ ; −1 ; 0 ; ⋮ ; 0 ) + ⋯

mit beliebigen freien Konstanten λ_{1}, λ_{1} etc.

Definition 12.67: (Kernvektoren einer Matrix)

Ein Vektor k⃗ ∈ K^{m} einer Matrix A ∈ K^{n×m} mit A k⃗ = 0 heißt ”Kernvektor“ von A. Die Menge aller Kernvektoren bilden entweder die leere Menge oder einen linearen Unterraum im K^{m} (den ”Kern“ von A). Die Dimension des Kerns heißt ”Defekt“ der Matrix. Der ”Rang“ einer (n × m)-Matrix ist

rg(A) = min(n, m) − Defekt(A).

Satz 12.68: (Die allgemeine Lösung linearer Systeme)

Die allgemeine Lösung eines lösbaren linearen Gleichungssystems Ax⃗ = b⃗ ist

x⃗ = x⃗_{0} + ∑_{j} λ_{j} · k⃗_{j},

wobei x⃗_{0} irgendeine spezielle Lösung von Ax⃗ = b⃗ ist, k⃗_{1}, k⃗_{2} etc. eine Basis des Kerns von A bilden und λ_{1}, λ_{2} etc. beliebige freie Parameter sind.

Beweis: Sei x⃗ eine beliebige Lösung von Ax⃗ = b⃗, sei x⃗_{0} eine spezielle Lösung. Die Differenz k⃗ = x⃗ − x⃗_{0} erfüllt dann Ak⃗ = A(x⃗ − x⃗_{0}) = Ax⃗ − Ax⃗_{0} = b⃗ − b⃗ = 0, ist also ein Kernvektor.

Q.E.D.

Jedes markierte Diagonalelement −1 in (###) entspricht einem Kernvektor der Ausgangsmatrix, der sich als die entsprechende Spalte des Endschemas ablesen läßt. Existieren mehrere solcher eingefügten Diagonalelemente −1, sind die entsprechenden Kernvektoren automatisch linear unabhängig, denn sie haben als untersten Eintrag jeweils −1 an unterschiedlichen Stellen:

Die Dimension des Kerns der Matrix ist durch die Anzahl der Diagonal-- Nullen in (#) bzw. (##) gegeben.

Fazit:

Der Gauß-Algorithmus wie oben beschrieben liefert nach Entzerrung des oberen Gleichungssystems sowohl eine spezielle Lösung x⃗_{0} = (d_{1}, d_{2}, …)^{T} (mit 0 in den Komponenten, die den Kernindizes entsprechen) sowie einen Satz von linear unbhängigen Kernvektoren (mit −1 in den Komponenten, die den Kernindizes entsprechen). Diese Kernvektoren bilden eine Basis des Kerns von A. Wir haben damit die allgemeine Lösung des Ausgangssystems Ax⃗ = b⃗ gefunden.

Beispiel 12.69: Wir berechnen die allgemeine Lösung des linearen Gleichungssystems (4 Gleichungen für 5 Unbekannte):

( \begin{matrix}0 & 1 & 1 & 2 & 1 \\ 1 & 1 & 2 & 3 & 1 \\ 1 & 2 & 3 & 5 & 2 \\ 1 & 2 & 3 & 6 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix} ) = ( \begin{matrix}6 \\ 10 \\ 16 \\ 16 \end{matrix} ) . (#)

Wir bilden die erweiterte Koeffizientenmatrix:

( \begin{matrix}0 & 1 & 1 & 2 & 1 & 6 \\ 1 & 1 & 2 & 3 & 1 & 10 \\ 1 & 2 & 3 & 5 & 2 & 16 \\ 1 & 2 & 3 & 6 & 1 & 16 \end{matrix} ) .

Gauß-Elimination der ersten Spalte. Zunächst vertauschen der Zeilen 1 und 2:

( \begin{matrix}1 & 1 & 2 & 3 & 1 & 10 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 1 & 2 & 3 & 5 & 2 & 16 \\ 1 & 2 & 3 & 6 & 1 & 16 \end{matrix} ) .

Erzeugen der Nullen in der ersten Spalte:

( \begin{matrix}1 & 1 & 2 & 3 & 1 & 10 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 0 & 1 & 1 & 3 & 0 & 6 \end{matrix} ) .

Erzeuge Nullen in der zweiten Spalte:

( \begin{matrix}1 & 1 & 2 & 3 & 1 & 10 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \end{matrix} ) .

12.5. LINEARE GLEICHUNGSSYSTEME 269

Obere Dreiecksform ist erreicht. Hinzufügen einer trivialen Gleichung, damit ein quadratisches (5 × 5)-System entsteht:

( \begin{matrix}1 & 1 & 2 & 3 & 1 & 10 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Reduktion auf Treppenstufenform (die Zeilen mit 0 auf der Diagonalen sind zu Nullzeilen zu machen). Es ist hier nichts zu tun. Wir markieren lediglich die Nullen längs der Diagonale:

( \begin{matrix}1 & 1 & 2 & 3 & 1 & 10 \\ 0 & 1 & 1 & 2 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Erzeuge Nullen über den nicht-verschwindenden Diagonalelementen. Zunächst die Nullen in der 4-ten Spalte. Ziehe dazu das 2-fache der 4-ten Zeile von der ersten und das 3-fache der 4-ten Zeile von der zweiten ab:

( \begin{matrix}1 & 1 & 2 & 0 & 4 & 10 \\ 0 & 1 & 1 & 0 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Erzeuge Nullen in der 2-ten Spalte. Subtrahiere dazu die zweite Zeile von der ersten:

( \begin{matrix}1 & 0 & 1 & 0 & 1 & 4 \\ 0 & 1 & 1 & 0 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Die 3-te und die 5-te Spalte haben 0 auf der Diagonale und liefern damit 2 Kernvektoren, indem man −1 auf der Diagonale einträgt:

( \begin{matrix}1 & 0 & 1 & 0 & 1 & 4 \\ 0 & 1 & 1 & 0 & 3 & 6 \\ 0 & 0 & −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & −1 & 0 \end{matrix} ) .

Die allgemeine Lösung des Ausgangssystems (#) hat damit zwei beliebige freie Parameter λ_{1} und λ_{2}:

( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix} ) = ( \begin{matrix}4 \\ 6 \\ 0 \\ 0 \\ 0 \end{matrix} ) + λ_{1} · ( \begin{matrix}1 \\ 1 \\ −1 \\ 0 \\ 0 \end{matrix} ) + λ_{2} · ( \begin{matrix}1 \\ 3 \\ 0 \\ −1 \\ −1 \end{matrix} ) .

12.6 Inverse von Matrizen

Zu einer invertierbaren n × n-Matrix A soll die Inverse A^{−1} berechnet werden. Zwar läßt sich dies mit der im nächsten Abschnitt vorgestellten Gauß-Jordan-Variante des Gauß-Algorithmus leicht bewerkstelligen, in der Praxis wird eine explizite Inverse von A jedoch selten benötigt (man hat in der Regel Ax⃗ = b⃗ mit einer konkret vorgegebenen rechten Seite b⃗ zu lösen). In einigen Fällen hat man immer wieder Ax⃗ = b⃗ zu lösen, wobei die Matrix A unverändert bleibt und sich im Laufe einer Iteration die rechte Seite b⃗ immer wieder neu ergibt. In diesem Fall mag man versucht sein, A^{−1} explizit zu berechnen und zu speichern, um Ax⃗ = b⃗ durch eine Matrix-Vektor-Multiplikation A^{−1}b⃗ mit O(n^{2}) Operationen berechnen zu können, anstatt immer wieder erneut den Gauß-Algorithmus mit einem Aufwand von O(n^{3}) Operationen auf Ax⃗ = b⃗ loszulassen. In Abschnitt 12.6.2 zeigt es sich jedoch, dass mit einem Durchlauf des Gauß-Algorithmus eine sogenannte LR-Zerlegung vorliegt, die genauso gut ist wie eine explizite Inverse A^{−1}.

12.6.1 Die Gauß-Jordan-Variante

Statt einer einzelnen Gleichung Ax⃗ = b⃗ mit A ∈ K^{n×n} und einer einzelnen rechten Seite b⃗ ∈ K^{n} lösen wir simultan Ax⃗ = e⃗_{i} mit i = 1, …, n, wobei e⃗_{i} die Standardbasis des K^{n} darstellt:

Bezeichnung 12.70:

Die Standardbasis des K^{n} wird mit e⃗_{i} = (0, …, 0, 1, 0, …, 0)^{T} (i = 1, …, n) bezeichnet.

Dies läuft darauf hinaus, dass wir das erweiterte Koeffizientenschema [A, e⃗_{1}, …, c⃗_{n}] = [A, I 1] betrachten. Wir lassen den Gauß-Algorithmus 12.64 auf das Schema los, wobei die Elementaroperationen auf das Gesamtschema angewendet werden (d.h., die Schleife über k in 12.64 ist bis zur Obergrenze 2 · n (statt m + 1) auszudehnen). Als Zwischenergebnis erhält man das Schema

[R, B]

mit einer oberen Dreiecksmatrix R. Verschwindet mindestens ein Diagonalelement von R, so ist R nicht invertierbar (und damit ist auch die Ausgangsmatrix A nicht invertierbar), und wir können die Berechnung von A^{−1} abbrechen. Seien also nun alle Diagonalelemente von R ungleich 0. Wir dividieren nun jede Zeile von [R, B] durch das entsprechende Diagonalelement von R, so dass längs der Diagonale nur Einsen stehen. Dann eliminieren wir mit der letzten Spalte von R beginnend ”nach oben“, indem wir durch Subtraktion geeigneter Vielfache einer Zeile von den darüber liegenden Zeilen Nullen über den Diagonalelementen erzeugen. Diese Elementaroperationen sind dabei jeweils auf das gesamte Schema anzuwenden. Zuletzt erhalten wir im linken Teil des Schemas die Einheitsmatrix:

[ I 1, C].

Satz 12.71:

Die Matrix C im rechten Teils des Schemas ist die Inverse A^{−1} der Ausgangsmatrix A.

Beweis: Alle Schritte des Gauß-Algorithmus zur Erzeugung der oberen Dreiecksform R als auch die Normierung der Diagonalelemente auf 1 und die folgende ”Elimination nach oben“ sind durch Multiplikation mit Elementarmatrizen 12.63 E_{1}, E_{2} etc. zu beschreiben, die auch auf den rechten Teil des Schemas angewendet werden:

[ I 1, C] = [E_{k} ⋯ E_{2}E_{1} A, E_{k} ⋯ E_{2}E_{1} I 1].

Vergleich der linken Teilschemata liefert

I 1 = E_{k} ⋯ E_{2}E_{1} A,

d.h., es gilt E_{k} ⋯ E_{2}E_{1} = A^{−1}. Vergleich der rechten Teilschemata liefert C = E_{k} ⋯ E_{2}E_{1} I 1 = A^{−1}.

Q.E.D.

12.6.2 LR-Zerlegung

Aus Zeitgründen wird dieser Abschnitt über die LR-Zerlegung in der Vorlesung nicht vorgestellt und hiermit als ”nicht prüfungsrelevant“ deklariert. ;-)

Wir betrachten noch einmal die Zeilenvertauschungen, die im Gauß-Algorithmus durchzuführen sind. Diese sind als Matrixmultiplikationen mit mit

P = ( I 1 0  1 I 1 1  0 I 1 ) \begin{matrix}← i \\ ← j \end{matrix} = I 1 − e⃗_{i} e_{i}^{T} − e⃗_{j} e_{j}^{T} + e⃗_{i} e_{j}^{T} + e⃗_{j} e_{i}^{T}

↑ ↑
i j

zu interpretieren: A → P A : Vertauschung der Zeilen i und j, A → AP : Vertauschung der Spalten i und j, Definition 12.72:

Eine Permutationsmatrix ist eine quadratische Matrix, die in jeder Zeile und jeder Spalte mit genau einer 1 und ansonsten mit 0 besetzt ist.

Lemma 12.73:

a) Produkte von Permutationsmatrizen sind wieder Permutationsmatrizen.

b) Permutationsmatrizen sind orthogonal: P P^{T} = P^{T} P = I 1.

c) Linksmultiplikation mit einer Permutationsmatrix entspricht einer Zeilenvertauschung, Rechtsmultiplikation einer Spaltenvertauschung.

Beweis: offensichtliche Übung.

Beispiel 12.74: Sei P = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , A = ( \begin{matrix} & z_{1}^{T} \\ & z_{2}^{T} \\ & z_{3}^{T} \end{matrix} ) = (s⃗_{1}, s⃗_{2}, s⃗_{3}) (Zerlegung

von A nach Zeilen bzw. Spalten). Es gilt P A = ( \begin{matrix} & z_{2}^{T} \\ & z_{3}^{T} \\ & z_{1}^{T} \end{matrix} ) , AP = (s⃗_{3}, s⃗_{1}, s⃗_{2}) .

Satz 12.75: (LR-Zerlegung)

Das System Ax⃗ = b⃗ wird im Gauß-Algorithmus 12.64 auf die Endform

( \begin{matrix}r_{11} & … & … & r_{1n} & c_{1} \\ l_{21} & ... & ... & ⋮ & ⋮ \\ ⋮ & ... & ... & ⋮ & ⋮ \\ l_{n1} & … & l_{n,n−1} & r_{nn} & c_{n} \end{matrix} )

gebracht (der untere Dreiecksanteil (l_{ij}) entsteht aus den abgespeicherten Eliminationsfaktoren). Es seien P_{1}, …, P_{n−1} (eventuell mit P_{j} = I 1) die bei der Pivotierung durchgeführten Zeilenvertauschungen. Mit

L = ( \begin{matrix}1 & & & 0 \\ l_{11} & ... \\ ⋮ & ... & ... \\ l_{n1} & … & l_{n,n−1} & 1 \end{matrix} ) , R = ( \begin{matrix}r_{11} & … & … & r_{1n} \\ & ... & ... & ⋮ \\ & & ... & ⋮ \\ 0 & & & r_{nn} \end{matrix} )

und P = P_{n−1} ⋯ P_{1} gilt: P A = LR (“LR-Faktorisierung”).

Beweis: (für technisch Interessierte) Zu Beginn des j.ten Schrittes liegt das Zwischenschema

( \begin{matrix}r_{11} & … & … & r_{1,j−1} & r_{1j} & … & r_{1n} \\ l_{21} & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ l_{j−1,j} & … & l_{j−1,j−2} & r_{j−1,j−1} & r_{j−1,j} & … & r_{j−1,n} \\ l_{j1}^{(j)} & … & … & l_{j,j−1}^{(j)} & a_{jj}^{(j)} & … & a_{jn}^{(j)} \\ ⋮ & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ l_{n1}^{(j)} & … & … & l_{n,j−1}^{(j)} & a_{nj}^{(j)} & … & a_{nn}^{(j)} \end{matrix} ) = L^{(j)} + R^{(j)}

mit

L^{(j)} = ( \begin{matrix}0 & & 0 \\ l_{21} & ... & & 0 \\ ⋮ & ... & 0 \\ l_{j1}^{(j)} & ... & l_{j,j−1}^{(j)} \\ ⋮ & ... & ⋮ & 0 \\ l_{n1}^{(j)} & … & l_{n,j−1}^{(j)} \end{matrix} )

und

R^{(j)} = ( \begin{matrix}r_{11} & … & … & … & … & r_{1n} \\ & ... & ... & ... & ... & ⋮ \\ 0 & & r_{j−1,j−1} & … & … & r_{j−1,n} \\ & & & a_{jj}^{(j)} & … & a_{jn}^{(j)} \\ & 0 & & ⋮ & ... & ⋮ \\ & & & a_{nj}^{(j)} & … & a_{nn}^{(j)} \end{matrix} )

vor. Die nächste Zeilenvertauschung P_{j} liefert L̃^{(j)} = P_{j}L^{(j)} und

R̃^{(j)} = P_{j}R^{(j)} = ( \begin{matrix}r_{11} & … & … & … & … & r_{1n} \\ & ... & ... & ... & ... & ⋮ \\ 0 & & r_{j−1,j−1} & … & … & r_{j−1,n} \\ & & & r_{jj} & … & r_{jn} \\ & & & ã_{j+1,j}^{(j)} & … & ã_{j+1,n}^{(j)} \\ & 0 & & ⋮ & ... & ⋮ \\ & & & ã_{nj}^{(j)} & … & ã_{nn}^{(j)} \end{matrix} ) .

Die neuen Eliminationsfaktoren l⃗_{j} = ( 0 ; ⋮ ; 0 ; ã_{j+1,j}^{(j)}/r_{jj} ; ⋮ ; ã_{n,j}^{(j)}/r_{jj} ) werden als j.te Spalte

an L̃^{(j)} angefügt:

L^{(j+1)} = L̃^{(j)} + l⃗_{j} e_{j}^{T} .

Vielfache der j.ten Zeile e_{j}^{T} R̃^{(j)} = (0, …, 0, r_{jj}, …, r_{jn}) von R̃^{(j)} werden von den unteren Zeilen von R̃^{(j)} abgezogen:

R^{(j+1)} = R̃^{(j)} − l⃗_{j} e_{j}^{T} R̃^{(j)} .

Beachte hierzu

( 0 ; ⋮ ; 0 ; l_{j+1} ; ⋮ ; l_{n} ) (0, …, 0, r_{jj}, …, r_{jn}) = ( \begin{matrix}0 & & 0 \\ & l_{j+1}r_{jj} & … & l_{j+1}r_{jn} \\ 0 & ⋮ & ... & ⋮ \\ & l_{n}r_{jj} & … & l_{n}r_{jn} \end{matrix} ) .

Ergebnis: der Gauß-Algorithmus wird beschrieben durch

L^{(j+1)} = P_{j}L^{(j)} + l⃗_{j}e_{j}^{T} , R^{(j+1)} = P_{j}R^{(j)} − l⃗_{j}e_{j}^{T} P_{j}R^{(j)}

mit L^{(1)} = 0 , R^{(1)} = A .

Behauptung: In jedem Schritt gilt ( I 1 + L^{(j)})R^{(j)} = P_{j−1} ⋯ P_{1} A. (Mit L = I 1 + L^{(n)}, R = R^{(n)}, P = P_{n−1} ⋯ P_{1} ist der Satz damit bewiesen). Beweis: Induktion nach j: j = 1: ( I 1 + L^{(1)})R^{(1)} = A gilt offensichtlich. Schritt j → j + 1:

( I 1 + L^{(j+1)}) R^{(j+1)}

= ( I 1 + P_{j}L^{(j)} + l⃗_{j}e_{j}^{T}) ( I 1 − l⃗_{j}e_{j}^{T}) P_{j}R^{(j)}
= ( I 1 − l⃗_{j}e_{j}^{T} [figure] + P_{j}L^{(j)} − P_{j}L^{(j)}l⃗_{j}e_{j}^{T} + l⃗_{j}e_{j}^{T} [figure] − l⃗_{j}e_{j}^{T} l⃗_{j}e_{j}^{T}) P_{j}R^{(j)}
= ( I 1 + P_{j}L^{(j)})P_{j}R^{(j)}  (beachte L^{(j)}l⃗_{j} = 0 , e_{j}^{T} l⃗_{j} = 0)
= P_{j}( I 1 + L^{(j)}P_{j}) R^{(j)} =^{(∗)} P_{j}( I 1 + L^{(j)}) R^{(j)} = P_{j} (P_{j−1} ⋯ P_{1} A) .

Für (∗) beachte L^{(j)}P_{j} = L^{(j)}, da Rechtsmultiplikation mit P_{j} die Spalten j, …, n von L^{(j)} vertauscht, die alle gleich (nämlich 0) sind.

Q.E.D.

Bemerkung 12.76: L = ( \begin{matrix}1 \\ ∗ & ... \\ ∗ & ∗ & 1 \end{matrix} ) ist immer invertierbar. Damit ist

R = L^{−1}P A genau dann invertierbar, wenn A invertierbar ist.

Bemerkung 12.77: Zu jeder quadratischen Matrix existiert damit eine Zeilenvertauschung P, so daß P A in der angegebenen Form LR faktorisiert werden kann. Bei invertierbarem A und fixiertem P sind die LR-Faktoren eindeutig:

LR = L̃R̃ ⟹ \underbrace{L̃^{−1}L}_{untere Dreiecksmatrix} = \underbrace{R̃R^{−1}}_{obere Dreiecksmatrix} = Diagonalmatrix D .

Mit L = L̃D folgt D = I 1, da die Diagonalen von L und L̃ mit 1 besetzt sind.

Bemerkung 12.78: Es gibt Matrizen, für die keine Faktorisierung A = LR existiert, man braucht i.a. P. Beispiel:

( \begin{matrix}0 & ∗ \\ 1 & ∗ \end{matrix} ) =^{(?)} ( \begin{matrix}1 & 0 \\ l_{21} & 1 \end{matrix} ) ( \begin{matrix}r_{11} & r_{12} \\ 0 & r_{22} \end{matrix} ) = ( \begin{matrix}r_{11} & r_{12} \\ l_{21} · r_{11} & l_{21} · r_{12} + r_{22} \end{matrix} ) .

Aus der ersten Spalte ergeben sich die Gleichungen

0 =^{(!)} r_{11}, 1 =^{(!)} l_{21} · r_{11},

die keine Lösung für l_{21} und r_{11} zulassen. In der Tat braucht der Gauß-Algo-

rithmus für die Matrix ( \begin{matrix}0 & ∗ \\ 1 & ∗ \end{matrix} ) gleich im ersten Schritt wegen der 0 links

oben eine Zeilenvertauschung, ohne die der Algorithmus zum Erliegen kommen würde.

Bemerkung 12.79: P ist die Gesamtheit aller im Gauß-Algorithmus durchgeführten Zeilenvertauschungen. Man speichert P nicht als Matrix, sondern als “Buchhaltungsvektor” p⃗. Dazu initialisiert man die Spalte p⃗ = (1, 2, …, n)^{T} und wendet die Zeilenvertauschungen auch auf p⃗ an. Zuletzt hat man p⃗ = (p_{1}, …, , p_{n})^{T}. Interpretation: die ursprüngliche Zeile p_{i} ist in die i.te Zeile gewandert. Hiermit ergibt sich für beliebiges b⃗ dann c⃗ = P b⃗ durch

for i := 1 to n do c_{i} := b_{p_{i}} ;

Bemerkung 12.80: Mit det(L) = 1 und leicht berechenbarem

det(R) = Produkt der Diagonalelemente

kann det(A) aus det(P) det(A) = det(R) berechnet werden. Mit det(P) = det(P_{n−1}) ⋯ det(P_{1}) und

det(P_{j}) = \{ \begin{matrix}1 & , falls P_{j} = I 1 \\ −1 & , falls P_{j} = Austausch zweier Zeilen \end{matrix}

braucht nur die Anzahl der nichttrivialen Zeilenvertauschungen im Gauß-Algorithmus mitgezählt zu werden.

Bemerkung 12.81: Die Faktorisierungsdaten P, L, R sind genauso gut wie eine explizite Inverse A^{−1}! Die Lösung von

Ax⃗ = b⃗ ⟹ P Ax⃗ = P b⃗ , d.h., L \underbrace{R x⃗}_{y⃗} = P b⃗

ist durch 2 Rücksubstitutionen

bestimme y⃗ aus Ly⃗ = P b⃗,
dann bestimme x⃗ aus Rx⃗ = y⃗

schnell zu berechnen. Der Aufwand (etwa n^{2} Multiplikationen) entspricht dem der Matrix-Vektor-Multiplikation A^{−1}b⃗ bei explizit vorliegendem A^{−1}.

Merke: Der Gauß-Algorithmus liefert mit ≈ n^{3}/3 Multiplikationen die Zerlegung P A = LR einer n × n-Matrix. Liegen P, L, R vor, dann ist Ax⃗ = b⃗ durch doppelte Rücksubstitution mit etwa n^{2} Multiplikationen schnell zu lösen.

12.7 Eigenwerte und -vektoren

4.2.04↓

Die ”Spektralanalyse“ = ”Diagonalisierung“ linearer Abbildungen (das Bestimmen von Eigenwerten und -vektoren) ist speziell für physikalische Anwendungen von zentraler Bedeutung.

12.7.1 Definitionen

Definition 12.82: (Eigenwerte und -vektoren)

Zu einer quadratischen Matrix A ∈ K^{n×n} gebe es λ ∈ ℂ und x⃗ ∈ ℂ^{n} mit x⃗ ≠ 0, so dass

A x⃗ = λ · x⃗.

Der Wert λ heißt ”Eigenwert“ von A, der Vektor x⃗ wird als ”Eigenvektor“ zum Eigenwert λ bezeichnet. Die Vektormenge

E_{λ} = {x⃗ ∈ ℂ^{n}; Ax⃗ = λ · x⃗ }

heißt ”Eigenraum“ zum Eigenvektor λ.

Bemerkung 12.83: Man überzeugt sich leicht davon, dass zu einem gegebenen Eigenwert λ von A der Eigenraum E_{λ} ein Unterraum des ℂ^{n} ist. Speziell heißt dies, dass Eigenvektoren nicht eindeutig sind. Jedes Vielfache eines Eigenvektors ist wieder ein Eigenvektor (falls das Vielfache nicht gerade 0 ist). Ist die Dimension des Eigenraums E_{λ} größer als 1, können auch linear unabhängige Eigenvektoren zu λ zu einem neuen Eigenvektor kombiniert werden.

Definition 12.84: (Das charakteristische Polynome einer Matrix) Zu A = (a_{ij}) ∈ K^{n×n} definieren wir das ”charakteristische Polynom“

p_{A}(λ) = det(A − λ · I 1) = det (( \begin{matrix}a_{11} − λ & a_{12} & ⋯ & a_{1n} \\ a_{21} & a_{22} − λ & ... & ⋮ \\ ⋮ & ... & ... & ⋮ \\ a_{n1} & … & … & a_{nn} − λ \end{matrix} ))

Man hat sich hierbei schnell davon überzeugt, dass das charakteristische Polynom

p_{A}(λ) = (−1)^{n} · λ^{n} + c_{n−1} · λ^{n−1} + … + c_{1} · λ + c_{0}

in der Tat ein Polynom vom Grad n ist (um den führenden Koeffizienten (−1)^{n} einzusehen, betrachte man einfach A = 0). Einige weitere der Koeffizienten c_{i} des Polynoms sind ebenfalls leicht der Matrix zuzuordnen. Z.B. gilt:

c_{n−1} = (−1)^{n} · \underbrace{∑_{i=1}^{n} a_{ii}}_{Spur(A)}, c_{0} = det(A).

Zu c_{0}: Werte einfach das charakteristische Polynom an der Stelle λ = 0 aus, wodurch sich nach Definition c_{0} = p_{A}(0) = det(A − 0 · I 1) = det(A) ergibt.

Satz 12.85: (Charakterisierung der Spektraldaten einer Matrix)

Die Eigenwerte einer Matrix A ∈ K^{n×n} sind die Nullstellen des charakteristischen Polynoms. Die zum Eigenwert λ gehörigen Eigenvektoren sind die nicht-verschwindenden Kernvektoren der Matrix A − λ · I 1.

Beweis: Die Gleichung Ax⃗ = λ·x⃗ kann als (A−λ· I 1) x⃗ = 0 geschrieben werden. Ist A − λ · I 1 invertierbar, gibt es nur die eindeutige Lösung x⃗ = 0, die wir nicht als Eigenvektor zulassen. Da A − λ · I 1 genau dann nicht invertierbar ist, wenn p_{A}(λ) = det(A − λ · I 1) verschwindet, sind die Eigenwerte die Nullstellen von p_{A}(λ). Für nicht-invertierbares A_{λ} := A − λ · I 1 existiert ein Kern der Matrix A_{λ}, der aus Eigenvektoren von A besteht.

Q.E.D.

Wir haben damit unmittelbar eine algorithmische Möglichkeit, sowohl die Eigenwerte als auch die dazugehörigen Eigenvektoren zu bestimmen:

a) Bestimme die Eigenwerte als die Nullstellen λ_{1}, λ_{2} etc. des charakteristischen Polynoms.

b) Berechne zum Eigenwert λ_{i} eine Basis des Kerns von A − λ_{i} · I 1. Dies kann beispielsweise durch den Gauß-Algorithmus angewendet auf die Gleichung (A − λ · I 1)x⃗ = 0 geschehen, wobei die Kernvektoren sich gemäß Abschnitt 12.5.3 algorithmisch ergeben. Dies liefert eine Basis des Eigenraums E_{λ_{i}}.

Beispiel 12.86: Zur Matrix

A = ( \begin{matrix}0 & 1 \\ −2 & 3 \end{matrix} )

ergibt sich das charakteristische Polynom

p_{A}(λ) = det (( \begin{matrix}−λ & 1 \\ −2 & 3 − λ \end{matrix} )) = −λ · (3 − λ) + 2 = λ^{2} − 3 · λ + 2

mit den Nullstellen (Eigenwerten)

λ_{1} = 1, λ_{2} = 2.

Die allgemeine Lösung von (A − λ_{1} · I 1) x⃗ = 0 ist der Kern der Matrix

A − λ_{1} · I 1 = ( \begin{matrix}−1 & 1 \\ −2 & 2 \end{matrix} ) .

Über den Entzerrungsalgorithmus ergibt sich die allgemeine Lösung x⃗ = α · ( \begin{matrix}1 \\ 1 \end{matrix} ) mit beliebigen α ∈ ℂ. Wir wählen als Basis des 1-dimensionalen Kerns den Eigenvektor

x⃗_{1} = ( \begin{matrix}1 \\ 1 \end{matrix} ) .

Die allgemeine Lösung von (A − λ_{2} · I 1) x⃗ = 0 ist der Kern der Matrix

A − λ_{2} · I 1 = ( \begin{matrix}−2 & 1 \\ −2 & 1 \end{matrix} ) .

Über den Entzerrungsalgorithmus ergibt sich die allgemeine Lösung x⃗ = α · ( \begin{matrix}1 \\ 2 \end{matrix} ) mit beliebigen α ∈ ℂ. Wir wählen als Basis des 1-dimensionalen Kerns den Eigenvektor

x⃗_{2} = ( \begin{matrix}1 \\ 2 \end{matrix} ) .

Wir gehen nun der Frage nach, wieviele Eigenvektoren man zu einer n × n-Matrix A finden kann. Speziell: kann ich die Eigenvektoren als Basis des ℂ^{n} benutzen?

Satz 12.87:

Eigenvektoren zu unterschiedlichen Eigenwerten sind linear unabhängig.

Beweis: Seien x⃗_{1}, …, x⃗_{k} Eigenvektoren von A ∈ K^{n×n} zu den Eigenwerten λ_{1}, …, λ_{k}, die alle paarweise verschieden seien. Wir betrachten die Linearkombination

∑_{i=1}^{k} c_{i} · x⃗_{i} = 0 (#)

und müssen hieraus schliessen, dass c_{1} = … = c_{k} = 0 folgt. Wir machen dazu Induktion nach k. Für k = 1 folgt sicherlich c_{1} = 0, da x⃗_{1} als Eigenvektor nicht verschwindet. Wir machen nun den Induktionsschritt k −1 → k. Seien also x⃗_{1}, …, x⃗_{k−1} linear unabhängige Eigenvektoren zu λ_{1}, …, λ_{k−1}, sei x⃗_{k} ein zusätzlicher Eigenvektor zum Eigenwert λ_{k}. Aus (#) folgt durch Anwendung von A

∑_{i=1}^{k} c_{i} · λ_{i} · x⃗_{i} = 0

und durch Multiplikation von (#) mit λ_{k}

∑_{i=1}^{k} c_{i} · λ_{k} · x⃗_{i} = 0.

Durch Differenzbildung folgt

∑_{i=1}^{k−1} c_{i} · (λ_{i} − λ_{k}) · x⃗_{i} = 0,

wobei der Term mit v⃗_{k} herausfällt. Nach Induktionsvoraussetzung folgt

c_{i} · (λ_{i} − λ_{k}) = 0

wegen der linearen Unabhängigkeit von v⃗_{1}, …, v⃗_{k−1} und damit c_{1} = … = c_{k−1} = 0, da λ_{i} − λ_{k} ≠ 0. Damit reduziert sich (#) zu λ_{k} · v⃗_{k} = 0, woraus auch c_{k} = 0 folgt.

Q.E.D.

Die Frage, ob man den gesamten ℂ^{n} durch Eigenvektoren einer Matrix aufspannen kann, läßt sich damit für den Spezialfall leicht beantworten, dass alle Eigenwerte unterschiedlich sind:

Folgerung 12.88:

Hat eine n × n-Matrix n unterschiedliche Eigenwerte, so bilden die entsprechenden Eigenvektoren eine Basis des ℂ^{n}.

Beweis: Nach Satz 12.87 gehören zu den n unterschiedlichen Eigenwerten n linear unabhängige Eigenvektoren. Mit Satz 12.11.b) bilden diese Vektoren eine Basis des ℂ^{n} und spannen den gesamten Raum auf.

Q.E.D.

Die Sache wird deutlich komplizierter, wenn es ”entartete Eigenwerte“ gibt.

Definition 12.89: (mehrfache Eigenwerte)

Sei λ ∈ ℂ ein Eigenwert von A ∈ K^{n×n}. Die Vielfachheit der Nullstelle λ des charakteristischen Polynoms von A im Sinne von Definition 1.24 heißt ”algebraische Vielfachheit“ des Eigenwerts. Im Gegensatz dazu wird die Dimension des Kerns von A−λ· I 1 als ”geometrische Vielfachheit“ bezeichnet.

Satz 12.90:

Für jeden Eigenwert einer Matrix gilt:

1 ≤ geometrische Vielfachheit ≤ algebraische Vielfachheit.

Beweis: Die Vielfachheit einer Polynomnullstelle (algebraische Vielfachheit des Eigenwerts) ist nach Definition ≥ 1. Für jeden Eigenwert λ_{0} einer Matrix A ist A − λ_{0} · I 1 nicht invertierbar und hat damit einen nicht-trivialen Kern. Damit gilt, dass auch für die geometrische Vielfachheit eines Eigenwerts stets ≥ 1 gilt. Nun zur Abschätzung

geometrische Vielfachheit ≤ algebraische Vielfachheit.

Zunächst beobachten wir, dass eine Matrix A ∈ K^{n×n} und T^{−1}AT (mit einer beliebigen invertierbaren Matrix T ∈ K^{n×n}) das selbe charakteristische Polynom haben:

det(T^{−1}AT − λ · I 1) = det(T^{−1}(A − λ · I 1)T)
= det(T^{−1}) · det(T) · det(A − λ · I 1)
= det(T^{−1}T) · det(A − λ · I 1)T) = det(A − λ · I 1).

Seien k⃗_{1}, …, k⃗_{g} Basisvektoren des Kerns von A − λ_{0} · I 1 für einen Eigenwert λ_{0} mit geometrischer Vielfachheit g. Wir wählen irgendwelche linear unabhängigen Vektoren v⃗_{g+1}, …, v⃗_{n}, die zusammen mit den Kernvektoren eine Basis des ℂ^{n} bilden. Betrachte nun

Ã = \underbrace{[k⃗_{1}, …, k⃗_{g}, v⃗_{g+1}, …, v⃗_{n}]^{−1}}_{T^{−1}} A \underbrace{[k⃗_{1}, …, k⃗_{g}, v⃗_{g+1}, …, v⃗_{n}]}_{T}

= T^{−1}[A · k⃗_{1}, …, A · k⃗_{g}, Av⃗_{g+1}, …, Av⃗_{n}]
= T^{−1}[λ_{0} · k⃗_{1}, …, λ_{0} · k⃗_{g}, Av⃗_{g+1}, …, Av⃗_{n}]

= [λ_{0} · T^{−1}k⃗_{1}, …, λ_{0} · T^{−1}k⃗_{g}, T^{−1}Av⃗_{g+1}, …, T^{−1}Av⃗_{n}].

Nach Konstruktion gilt

T^{−1} \underbrace{[k⃗_{1}, …, k⃗_{g}, v⃗_{g+1}, …, v⃗_{n}]}_{T} = [T^{−1}k⃗_{1}, …, T^{−1}k⃗_{g}, T^{−1}v⃗_{g+1}, …, T^{−1}v⃗_{n}]

= ( \begin{matrix}1 & 0 & … & 0 & … & 0 \\ 0 & ... & ... & ... & ... & ⋮ \\ ⋮ & ... & 1 & ... & ... & ⋮ \\ ⋮ & ... & ... & 1 & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & 0 \\ 0 & … & … & … & 0 & 1 \end{matrix} ) .

Betrachtet man die ersten g Spalten, folgt T^{−1}k⃗_{i} = e⃗_{i} (Standardbasis), also

Ã = [λ_{0} · T^{−1}k⃗_{1}, …, λ_{0} · T^{−1}k⃗_{g},∗, …,∗] = ( \begin{matrix}λ_{0} & 0 & … & ∗ & … \\ 0 & ... & ... & ⋮ & ... \\ ⋮ & ... & λ_{0} & ⋮ & ... \\ ⋮ & ... & 0 & ⋮ & ... \\ ⋮ & ... & ⋮ & ⋮ & ... \\ 0 & … & 0 & ∗ & … \end{matrix} ) .

Das charakteristische Polynom von Ã ergibt sich durch rekursive Entwicklung von det(Ã − λ · I 1) nach den ersten Spalten zu

det(Ã − λ · I 1) = (λ_{0} − λ)^{g} · p̃(λ)

mit irgendeinem Faktorpolynom, das durch den rechten unteren Block von Ã bestimmt wird. Das obige charakteristische Polynom von Ã, das mit dem von A übereinstimmt, hat den Eigenwert λ_{0} mit der Vielfachheit von mindestens g.

Q.E.D.

Seien λ_{1}, …, λ_{k} die unterschiedlichen Nullstellen des charakteristischen Polynoms vom Grad n, ihre algebraischen Vielfachheiten seien n_{1}, …, n_{k}. Nach dem Fundamentalsatz der Algebra 1.29 addieren sich die algebraischen Vielfachheiten zu Dimension n des Raums auf: n_{1} + … + n_{k} = n. Wenn dies auch für die geometrischen Vielfachheiten g_{1}, …, g_{k} gilt, so läßt sich aus den Eigenvektoren eine Basis bilden. Man wähle dazu aus jedem Kern von A − λ_{i} · I 1 jeweils g_{i} Basisvektoren, die insgesamt ein System von g_{1} + … + g_{k} linear unabhängigen Vektoren im ℂ^{n} bilden. Gilt g_{1} + … + g_{k} = n, so haben wir eine Basis des ℂ^{n} vor uns. Die entscheidende Frage ist also:

Gilt immer geometrische Vielfachheit =algebraische Vielfachheit?

Die Antwort ist leider:

Nein!

Beispiel 12.91: Die Matrix

A = ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} )

hat das charakteristische Polynom

p_{A}(λ) = det (( \begin{matrix}−λ & 1 \\ 0 & −λ \end{matrix} )) = λ^{2}.

Der Wert λ = 0 ist eine doppelte Nullstelle dieses Polynoms, damit ist λ = 0 ein Eigenwert mit der algebraischen Vielfachheit 2. Die Kernvektoren k⃗ = (k_{1}, k_{2})^{T} von A − 0 · I 1 = A sind durch

Ak⃗ = ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ) ( \begin{matrix}k_{1} \\ k_{2} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \end{matrix} )

charakterisiert, also durch die einzelne Gleichung k_{2} = 0. Der Kern von A besteht also aus dem 1-dimensionalen Raum

\{ ( \begin{matrix}k_{1} \\ 0 \end{matrix} ); k_{1} ∈ ℂ\}.

Man findet also die algebraische Vielfachheit 2 von λ = 0, aber die geometrische Vielfachheit 1. Mit dem einzigen Eigenvektor (1, 0)^{T}, der den Kern aufspannt, kann man nicht den ℂ^{2} aufspannen.

12.7.2 Symmetrische/hermitesche Matrizen

↓5.2.04

Zunächst einige einfache Beobachtungen zur den Eigenwerten und -vektoren zur (hermitesch) transponierten Matrix A^{H} (Definition 12.33) einer Matrix A:

Satz 12.92:

Ist λ Eigenwert von A, so ist \overline{λ} Eigenwert von A^{H}.

Beweis: Wegen

\overline{det(A − λ · I 1)} = \overline{det(A^{T} − λ · I 1)} = det(A^{H} − \overline{λ} · I 1)

stimmten die charakteristischen Polynome von A und A^{H} bis auf komplexe Konjugation überein: \overline{p_{A}(λ)} = p_{A^{H}} (\overline{λ}).

Q.E.D.

Satz 12.93:

Sei x⃗ ein Eigenvektor von A zum Eigenwert λ, sei y⃗ ein Eigenvektor von A^{H} zum Eigenwert μ ≠ \overline{λ}. Dann gilt ⟨y⃗, x⃗ ⟩ = 0.

Beweis: Wir betrachten das komplexe Skalarprodukt ⟨a⃗, b⃗ ⟩ = ∑_{i} \overline{a_{i}} ·b_{i} auf dem ℂ^{n}. Es gilt

⟨y⃗, Ax⃗ ⟩ = ⟨y⃗, λ · x⃗ ⟩ = λ · ⟨y⃗, x⃗ ⟩
= ⟨A^{H}y⃗, x⃗ ⟩ = ⟨μ · y⃗, x⃗ ⟩ = \overline{μ} · ⟨y⃗, x⃗ ⟩.

Es folgt

(λ − \overline{μ}) · ⟨y⃗, x⃗ ⟩ = 0,

womit das Skalarprodukt zwischen x⃗ und y⃗ für λ ≠ \overline{μ} verschwinden muss. Q.E.D.

Mit der selben Argumentation wie im obigen Beweis bekommt man im Fall hermitescher Matrizen die wichtige Aussage, dass alle Eigenwerte reell sind:

Satz 12.94:

Alle Eigenwerte hermitescher Matrizen A = A^{H} sind reell.

Beweis: Wir betrachten das komplexe Skalarprodukt ⟨a⃗, b⃗ ⟩ = ∑_{i} \overline{a_{i}} ·b_{i} auf dem ℂ^{n}. Mit Ax⃗ = λ · x⃗ folgt

⟨x⃗, Ax⃗ ⟩ = ⟨x⃗, λ · x⃗ ⟩ = λ · ⟨x⃗, x⃗ ⟩
= ⟨A^{H}x⃗, x⃗ ⟩ = ⟨λ · x⃗, x⃗ ⟩ = \overline{λ} · ⟨x⃗, x⃗ ⟩,

also

(λ − \overline{λ}) · ⟨x⃗, x⃗ ⟩ = 0,

wobei ⟨x⃗, x⃗ ⟩ ≠ 0 gilt, da ein Eigenvektor nicht 0 sein kann. Aus λ = \overline{λ} folgt, dass λ reell ist.

Q.E.D.

Satz 12.95:

Eigenvektoren hermitescher Matrizen A = A^{H} zu verschiedenen Eigenwerten sind orthogonal.

Beweis: Dies ist der Spezialfall von Satz 12.93 für hermitesche Matrizen. Sei Ax⃗ = λ · x⃗, Ay⃗ = μ · y⃗ mit reellen Eigenwerten λ ≠ μ. Wir betrachten das komplexe Skalarprodukt ⟨a⃗, b⃗ ⟩ = ∑_{i} \overline{a_{i}} · b_{i} auf dem ℂ^{n}. Es gilt

⟨y⃗, Ax⃗ ⟩ = ⟨y⃗, λ · x⃗ ⟩ = λ · ⟨y⃗, x⃗ ⟩
= ⟨A^{H}y⃗, x⃗ ⟩ = ⟨μ · y⃗, x⃗ ⟩ = \overline{μ} · ⟨y⃗, x⃗ ⟩ = μ · ⟨y⃗, x⃗ ⟩.

Es folgt

(λ − μ) · ⟨y⃗, x⃗ ⟩ = 0,

womit das Skalarprodukt zwischen x⃗ und y⃗ für λ ≠ μ verschwinden muss. Q.E.D.

Hier die zentrale Besonderheit des Eigenwertproblems für hermitesche Matrizen:

Satz 12.96:

a) Für jeden Eigenwert einer hermiteschen Matrix gilt

1 ≤ geometrische Vielfachheit = algebraische Vielfachheit.

b) Hermitesche Matrizen besitzen eine Basis von orthogonalen Eigenvektoren.

Beweis: Wir beweisen a) und b) simultan für hermitesches A ∈ K^{n×n}. Seien dazu λ_{1}, …, λ_{k} die paarweise unterschiedlichen Eigenwerte mit den geometrischen Vielfachheiten g_{1}, …, g_{k}. Seien v_{j}^{(i)} mit j = 1, …, g_{i} eine orthogonale Basis des Eigenraums E_{λ_{i}} (nehme z.B. irgendeine Basis des Kerns von A−λ_{i}· I 1 und orthogonalisiere sie per Gram-Schmidt (Aufgabe 110, Blatt 13)). Da nach Satz 12.95 die Eigenvektoren zu unterschiedlichen Eigenwerten orthogonal sind, haben wir insgesamt eine Sammlung von g = ∑_{i=1}^{k} g_{i} orthogonalen Eigenvektoren

\underbrace{v_{1}^{(1)}, …, v_{g_{1}}^{(1)}}_{Eigenwert λ_{1}}, \underbrace{v_{1}^{(2)}, …, v_{g_{2}}^{(2)}}_{Eigenwert λ_{2}}, …, \underbrace{v_{1}^{(k)}, …, v_{g_{k}}^{(k)}}_{Eigenwert λ_{k}},

wobei

g = ∑_{i=1}^{k} g_{i} ≤ ∑_{i=1}^{k} n_{i} = n

gilt. Wir wählen weitere n − g Vektoren w⃗_{1}, …, w⃗_{n−g} hinzu, die zusammen mit den Eigenvektoren den K^{n} aufspannen. Nach Orthogonalisierung per Gram-Schmidt (Aufgabe 110, Blatt 13), können wir sie als paarweise orthogonal und orthogonal zu den Eigenvektoren v_{j}^{(i)} annehmen.

Aus diesen insgesamt n Vektoren wird spaltenweise die Matrix

T = [v_{1}^{(1)}, …, v_{g_{1}}^{(1)}, v_{1}^{(2)}, …, v_{g_{2}}^{(2)}, …, v_{1}^{(k)}, …, v_{g_{k}}^{(k)}, w⃗_{1}, …, w⃗_{n−g}]

aufgebaut, die wegen der Orthogonalität der Spalten T^{H}T = I 1 erfüllt (also eine orthogonale Matrix mit T^{−1} = T^{H} ist). Analog zum Beweis von Satz 12.90 betrachten wir die Matrix

Ã = T^{−1}AT,

die mit den selben Argumenten wie im Beweis von Satz 12.90 von der Form

\begin{matrix}g_{1} & g & g + 1 & n \\ ↓ & ↓ & ↓ & ↓ \end{matrix} ; Ã = ( \begin{matrix}λ_{1} & 0 & … & … & … & … & 0 & ∗ & … & ∗ \\ 0 & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & λ_{1} & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & λ_{k} & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & ... & 0 & ⋮ & ... & ⋮ \\ 0 & … & … & … & … & 0 & λ_{k} & ∗ & … & ∗ \\ 0 & … & … & … & … & … & 0 & ∗ & … & ∗ \\ ⋮ & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & … & … & … & … & … & 0 & ∗ & … & ∗ \end{matrix} ) .

sein muss. Wegen Ã^{H} = T^{H}A^{H}(T^{−1})^{H} = T^{−1}AT = Ã ist Ã wieder hermitesch, damit muss Ã speziell von folgender Form sein:

\begin{matrix}g_{1} & g & g + 1 & n \\ ↓ & ↓ & ↓ & ↓ \end{matrix} ; Ã = ( \begin{matrix}λ_{1} & 0 & … & … & … & … & 0 & 0 & … & 0 \\ 0 & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & λ_{1} & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & λ_{k} & ... & ⋮ & ⋮ & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & ... & 0 & ⋮ & ... & ⋮ \\ 0 & … & … & … & … & 0 & λ_{k} & 0 & … & 0 \\ 0 & … & … & … & … & … & 0 & ∗ & … & ∗ \\ ⋮ & ... & ... & ... & ... & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & … & … & … & … & … & 0 & ∗ & … & ∗ \end{matrix} ) .

Das charakteristische Polynom von Ã (das mit dem von A übereinstimmt, siehe den Beweis von Satz 12.90) ist

pÃ(λ) = (λ_{1} − λ)^{g_{1}} · . . . · (λ_{k} − λ)^{g_{k}} · det(S − λ · I 1),

wo S der (symmetrische) Matrixblock der Dimension (n − g) × (n − g) in der rechten unteren Ecke von Ã ist. Vergleich mit

p_{A}(λ) = (λ_{1} − λ)^{n_{1}} · . . . · (λ_{k} − λ)^{n_{k}}

liefert

det(S − λ · I 1) = (λ_{1} − λ)^{n_{1}−g_{1}} · . . . · (λ_{k} − λ)^{n_{k}−g_{k}},

d.h., dieser Block hat einen Eigenwert λ_{i}, falls für mindestens einen Index g_{i} < n_{i} gilt. Dazu gehört ein Eigenvektor (x_{1}, … x_{n−g})^{T} ∈ K^{n−g} des Blocks S, der zu einem Eigenvektor

x⃗ = (0, …, 0, x_{1}, …, x_{n−g})^{T} ∈ K^{n}

von Ã zum Eigenwert λ_{i} erweitert werden kann. Hieraus wird ein Eigenvektor T x⃗ von A, denn

A(T x⃗) = T ÃT^{−1}(T x⃗) = T Ãx⃗ = T λ_{i} · x⃗ = λ_{i} · (T x⃗).

Man überzeugt sich leicht davon, dass der Eigenvektor x⃗ linear unabhängig von den Kernvektoren v_{1}^{(i)}, …, v_{g_{i}}^{(i)} ist, denn nach Konstruktion gilt T^{−1}v_{g_{i}}^{(i)} = (0, …, 0, 1, 0, … 0)^{T}, wo die 1 unter den ersten g Komponenten des Vektors zu finden sind. (Im Gegensatz dazu hat x⃗ mindestens einen von 0 verschiedenen Eintrag in den letzten n−g Komponenten.) Damit haben wir einen Widerspruch zu g_{i} < n_{i}, da wir nun einen weiteren linear unabhängigen Eigenvektor zu λ_{i} gefunden haben.

Q.E.D.

12.7.3 Diagonalisierung und Funktionalkalkül

Der wesentliche Grund, warum man sich für die Eigenwerte und -vektoren von Matrizen interessiert, ist die Tatsache, dass man mit Hilfe dieser ”spektralen Daten“ eine Matrix durch eine ”Ähnlichkeitstransformation“ T^{−1}AT auf Diagonalgestalt bringen kann, was das Hantieren mit der Matrix einfacher macht. Dies läuft darauf hinaus, statt der Standardbasis des K^{n} eine Basis aus Eigenvektoren der Matrix A zu benutzen, um die Vektoren des K^{n} darzustellen.

Satz 12.97: (Diagonalisierung von Matrizen)

Sei A eine reelle oder komplexe n × n-Matrix mit den (eventuell komplexen) Eigenwerten λ_{1}, …, λ_{n} und entsprechenden Eigenvektoren x⃗_{1}, …, x⃗_{n}, also A x⃗_{k} = λ_{k} x⃗_{k}. Sei T = [x⃗_{1}, …, x⃗_{n}] die Matrix, deren Spalten aus diesen Eigenvektoren besteht. Es gilt

A T = T D mit D = diag(λ_{1}, …, λ_{n}) := ( \begin{matrix}λ_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & λ_{n} \end{matrix} ) .

Sind die Eigenvektoren linear unabhängig, so ist T invertierbar, und es folgt

A = T D T^{−1}.

Beweis: Nach Definition der Matrixmultiplikation gilt

A T = A [x⃗_{1}, …, x⃗_{n}] = [A x⃗_{1}, …, A x⃗_{n}].

Mit

T D = [x⃗_{1}, …, x⃗_{n}] ( \begin{matrix}λ_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & λ_{n} \end{matrix} ) = [λ_{1} · x⃗_{1}, …, λ_{n} · x⃗_{n}]

und A x⃗_{k} = λ_{k} · x⃗_{k} folgt A T = T D.

Q.E.D.

Folgerung 12.98:

Mit einer Diagonalisierung A = T D T^{−1} gilt

A^{n} = \underbrace{T D T^{−1}}_{A} \underbrace{T D T^{−1}}_{A} ⋯ \underbrace{T D T^{−1}}_{A} = T D D ⋯ D T^{−1} = T D^{n} T^{−1}.

Die Potenzen von A sind damit auf Potenzen der Diagonalform D von A zurückgeführt, wobei D^{n} sich ohne große Rechnung durch Potenzieren der Diagonalelemente ergibt:

( \begin{matrix}λ_{1} \\ & λ_{2} \\ & & . & . & . \end{matrix} )^{n} = ( \begin{matrix}λ_{1}^{n} \\ & λ_{2}^{n} \\ & & . & . & . \end{matrix} ) .

Bemerkung 12.99: Hat man einen Eigenwert λ_{k} der zu diagonalisierenden Matrix gefunden, so kann man nach 12.97 irgendeinen dazugehörigen Eigenvektor x⃗_{k} benutzen, die entsprechende Spalte von T zu besetzen. Nun sind Eigenvektoren aber nicht eindeutig: ist x⃗_{k} ein Eigenvektor, so ist jedes Vielfaches y⃗_{k} = c_{k} x⃗_{k} wieder ein Eigenvektor zum selben Eigenwert λ_{k}. Es gibt damit viele unterschiedliche Transformationsmatrizen T, während die Diagonalmatrix bis auf Umnummerierung der Eigenwerte eindeutig ist. Wie kann das sein? Antwort: die Transformationsmatrizen unterscheiden sich nur um eine Diagonalmatrix:

T̃ = [y⃗_{1}, …, y⃗_{n}] = [c_{1} x⃗_{1}, …, c_{n} x⃗_{n}] = \underbrace{[x⃗_{1}, …, x⃗_{n}]}_{T} \underbrace{( \begin{matrix}c_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & c_{n} \end{matrix} )}_{C} = T C.

In der Diagonalisierung fällt die diagonale ”Skalierungsmatrix“ C heraus, da die Multiplikation von Diagonalmatrizen kommutativ ist:

A = T̃ D T̃^{−1} = T C D (T C)^{−1} = T C D C^{−1} T^{−1}
= T D C C^{−1} T^{−1} = T D T^{−1}.

Bemerkung 12.100: Da bei der Diagonalisierung die Invertierbarkeit von T wichtig ist, nützt es überhaupt nichts, triviale Eigenvektoren x⃗_{k} = 0 zu betrachten (die ja auch strenggenommen per Definition von Eigenvektoren gar nicht als Eigenvektoren zulässig sind).

Die Aufgabenstellung der Diagonalisierung läuft darauf hinaus, die Eigenvektoren zu allen Eigenwerten zu finden. Sobald man eine Basis von linear unabhängigen Eigenvektoren gefunden hat, hat man die invertierbare Transformationsmatrix T gefunden, welche die betrachtete Matrix auf Diagonalform bringt. Sind alle Eigenwerte verschieden, so existiert immer eine Basis von linear unabhängigen Eigenvektoren. Bei entarteten Eigenwerten (mehrfachen Nullstellen des charakteristischen Polynoms) ist dies jedoch nicht garantiert, und in der Tat gibt es nicht-diagonalisierbare Matrizen (siehe Beispiel 12.91). Symmetrische reelle bzw. hermitesche komplexe Matrizen sind immer diagonalisierbar, selbst wenn die (bei Symmetrie/Hermitzität der Matrix automatisch reellen) Eigenwerte entartet sind.

Beispiel 12.101: Mittels Diagonalisierung können wir für

A = ( \begin{matrix}1 & −\frac{1}{2} \\ 2 & 1 \end{matrix} )

12.7. EIGENWERTE UND -VEKTOREN 289

eine explizite Darstellung von A^{n} für jedes n ∈ ℤ ermitteln. Nach Satz 12.97 sind alle Eigenwerte und –vektoren zu bestimmen. Die Eigenwerte sind die Nullstellen des charakteristischen Polynoms

det(λ I 1 − A) = det ( \begin{matrix}λ − 1 & \frac{1}{2} \\ −2 & λ − 1 \end{matrix} ) = λ^{2} − 2 λ + 2

(hier ist I 1 die 2 × 2-Einheitsmatrix). Nach der Standardformel für die Nullstellen quadratischer Polynome ergeben sich die komplex konjugierten Eigenwerte

λ_{1,2} = 1 ± \sqrt{−1} = 1 ± i.

Die Eigenvektoren zu λ_{1} bzw. λ_{2} findet man, indem man die Kernvektoren von A−λ_{k} I 1 ermittelt, d.h., die Gleichungen (A − λ_{k} I 1) x⃗_{k} = A x⃗_{k} − λ_{k} x⃗_{k} = 0 löst. Mit dem Gauß-Algorithmus 12.64 gefolgt vom Entzerrungsalgorithmus aus Abschnitt 12.5.3 findet man die Lösungen

x⃗_{1} = ( \begin{matrix}i \\ 2 \end{matrix} ) bzw. x⃗_{2} = ( \begin{matrix}1 \\ 2 · i \end{matrix} ) .

Die Transformationsmatrix T wird spaltenweise aus diesen Eigenvektoren aufgebaut, die Inverse wird berechnet:

T = ( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} ) , T^{−1} = ( \begin{matrix}−\frac{i}{2} & \frac{1}{4} \\ \frac{1}{2} & −\frac{i}{4} \end{matrix} ) .

Damit folgt die Diagonalisierung

A = ( \begin{matrix}1 & −\frac{1}{2} \\ 2 & 1 \end{matrix} ) = \underbrace{( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} )}_{T} \underbrace{( \begin{matrix}1 + i & 0 \\ 0 & 1 − i \end{matrix} )}_{D} \underbrace{( \begin{matrix}−\frac{i}{2} & \frac{1}{4} \\ \frac{1}{2} & −\frac{i}{4} \end{matrix} )}_{T^{−1}} .

Dies liefert

A^{n} = \underbrace{( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} )}_{T} \underbrace{\underbrace{( \begin{matrix}(1 + i)^{n} & 0 \\ 0 & (1 − i)^{n} \end{matrix} )}_{D^{n}} \underbrace{( \begin{matrix}−\frac{i}{2} & \frac{1}{4} \\ \frac{1}{2} & −\frac{i}{4} \end{matrix} )}_{T^{−1}}}

= ( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} ) ( \begin{matrix}−\frac{i}{2} · (1 + i)^{n} & \frac{1}{4} · (1 + i)^{n} \\ \frac{1}{2} · (1 − i)^{n} & −\frac{i}{4} · (1 − i)^{n} \end{matrix} )

= ( \begin{matrix}\frac{1}{2} · (1 + i)^{n} + \frac{1}{2} · (1 − i)^{n} & \frac{i}{4} · (1 + i)^{n} − \frac{i}{4} · (1 − i)^{n} \\ −i · (1 + i)^{n} + i · (1 − i)^{n} & \frac{1}{2} · (1 + i)^{n} + \frac{1}{2} · (1 − i)^{n} \end{matrix} ) .

Das Ergebnis muß als Potenz der reellen Matrix A reell sein. Dies ist in dieser Darstellung leider alles andere als offensichtlich. Über die Polardarstellungen

1 ± i = \sqrt{2} · e^{±i· \frac{π}{4}}

ergibt sich mit |1 ± i| = \sqrt{2} und den Polarwinkeln ±\frac{π}{4} :

(1 ± i)^{n} = 2^{n/2} · e^{±n·i· \frac{π}{4}} = 2^{n/2} · ( cos (n · \frac{π}{4} ) ± i · sin (n · \frac{π}{4} )).

Damit folgt

(A^{n})_{11} = \frac{1}{2} · (1 + i)^{n} + \frac{1}{2} · (1 − i)^{n} = 2^{n/2} · cos(n · \frac{π}{4} ),
(A^{n})_{12} = \frac{i}{4} · (1 + i)^{n} − \frac{i}{4} · (1 − i)^{n} = −2^{n/2−1} · sin(n · \frac{π}{4} ),
(A^{n})_{21} = −i · (1 + i)^{n} + i · (1 − i)^{n} = 2^{n/2+1} · sin(n · \frac{π}{4} ),
(A^{n})_{22} = \frac{1}{2} · (1 + i)^{n} + \frac{1}{2} · (1 − i)^{n} = 2^{n/2} · cos(n · \frac{π}{4} ).

Insgesamt erhalten wir also in der Tat eine explizite (und nun recht einfache) reelle Darstellung beliebiger Potenzen von A:

( \begin{matrix}1 & −\frac{1}{2} \\ 2 & 1 \end{matrix} )^{n} = ( \begin{matrix}2^{\frac{n}{2}} · cos(n · \frac{π}{4} ) & −2^{\frac{n}{2} −1} · sin(n · \frac{π}{4} ) \\ 2^{\frac{n}{2} +1} · sin(n · \frac{π}{4} ) & 2^{\frac{n}{2}} · cos(n · \frac{π}{4} ) \end{matrix} ) .

Satz 12.102: (Hamilton-Cayley-Theorem)

Das charakteristische Polynom von A ∈ K^{n×n} sei

p_{A}(λ) = (−1)^{n} · λ^{n} + c_{n−1} · λ^{n−1} + … + c_{1} · λ + c_{0}.

Dann gilt die Matrix-Gleichung

p_{A}(A) = (−1)^{n} · A^{n} + c_{n−1} · A^{n−1} + … + c_{1} · A + c_{0} · I 1 = 0 ∈ K^{n×n}.

Beweis: Für diagonalisierbares A = T DT^{−1} mit D = diag(λ_{1}, …, λ_{n}) ist der Beweis einfach. Mit A^{k} = T D^{k}T^{−1} und D^{k} = diag(λ_{1}^{k}, …, λ_{n}^{k}) folgt

p_{A}(A) = p_{A}(T DT^{−1}) = T p_{A}(D)T^{−1} = T ( \begin{matrix}p_{A}(λ_{1}) & & & & 0 \\ & . & . & . \\ 0 & & & & p_{A}(λ_{n}) \end{matrix} ) T^{−1}

= T ( \begin{matrix}0 & & & & 0 \\ & . & . & . \\ 0 & & & & 0 \end{matrix} ) T^{−1} = ( \begin{matrix}0 & & & & 0 \\ & . & . & . \\ 0 & & & & 0 \end{matrix} ) .

Die Aussage gilt auch für nicht-diagonalisierbare Matrizen A, wobei der Beweis aber deutlich aufwendiger wird (das lassen wir hier).

Q.E.D.

12.7. EIGENWERTE UND -VEKTOREN 291

Für Diagonalmatrizen D = diag(λ_{1}, …, λ_{n}) gilt D^{k} = diag(λ_{1}^{k}, …, λ_{n}^{k}). Man nimmt dies zum Anlass, für beliebige Funktion f : ℝ → ℝ bzw. f : ℂ → ℂ zu definieren: f(D) = diag(f(λ_{1}), …, f(λ_{n})).

Definition 12.103: (Funktionalkalkül)

Für eine Funktionen f : ℝ → ℝ bzw. f : ℝ → ℝ definieren wir die Matrix-Auswertung dieser Funktion für eine diagonalisierbare Matrix A = T DT^{−1} ∈ K^{n×n} mit D = diag(λ_{1}, …, λ_{n}) mittels

f(A) = T f(D)T^{−1} = T ( \begin{matrix}f(λ_{1}) & & & & 0 \\ & . & . & . \\ 0 & & & & f(λ_{n}) \end{matrix} ) T^{−1}.

Beispiel 12.104: Wir betrachten f(x) = e^{x}. Stellt man sich die exp-Funktion als die Potenzreihe

e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + ⋯

vor, so liegt es nahe, die Matrixauswertung für A ∈ K^{n×n} durch

e^{A} = I 1 + A + \frac{1}{2!} · A^{2} + \frac{1}{3!} · A^{3} + … (#)

zu definieren. Für diagonalisierbares A = T DT^{−1} mit D = diag(λ_{1}, …, λ_{n}) stimmt dies mit der obigen Definition 12.103 überein:

e^{A} = I 1 + T DT^{−1} + \frac{1}{2!} · (T DT^{−1})^{2} + \frac{1}{3!} · (T DT^{−1})^{3} + …

= T ( I 1 + D + \frac{1}{2!} · D^{2} + \frac{1}{3!} · D^{3} + …)T^{−1}

= T ( \begin{matrix}1 + λ_{1} + \frac{λ_{1}^{2}}{2!} + … & & & & 0 \\ & . & . & . \\ 0 & & & & 1 + λ_{n} + \frac{λ_{n}^{2}}{2!} + … \end{matrix} ) T^{−1}

= T ( \begin{matrix}e^{λ_{1}} & & & & 0 \\ & . & . & . \\ 0 & & & & e^{λ_{n}} \end{matrix} ) T^{−1}.

Die Definition (#) über die Potenzreihe ist dabei auch für nicht-diagonalisierbares A sinnvoll.

Hier eine Anwendung:

292 KAPITEL 12. LINEARE ALGEBRA Satz 12.105: (dynamische Systeme)

Sei A ∈ K^{n×n} eine konstante Matrix. Die Lösung des Differentialgleichungssystems

\frac{d}{dt} x⃗(t) = A x⃗(t)

ist

x⃗(t) = e^{t·A} x⃗(0).

Beweis: Es gilt

\frac{d}{dt} e^{tA} = \frac{d}{dt} ( I 1 + t · A + \frac{t^{2}}{2!} · A^{2} + \frac{t^{3}}{3!} · A^{3} + …) = A + t · A^{2} + \frac{t^{2}}{2!} · A^{3} + …

= A ( I 1 + t · A + \frac{t^{2}}{2!} · A^{2} + \frac{t^{3}}{3!} · A^{3} + …) = A e^{t·A}.

Damit ist x⃗(t) = e^{t·A} x⃗(0) in der Tat eine Lösung der DGL:

\frac{d}{dt} x⃗(t) = \frac{d}{dt} e^{t·A}x⃗(0) = A e^{tA} x⃗(0) = A x⃗(t).

Q.E.D.

Beispiel 12.106: Betrachte das DGL-System

\frac{dx_{1}}{dt} = x_{1} − \frac{x_{2}}{2} , \frac{dx_{2}}{dt} = 2 · x_{1} + x_{2},

das als

\frac{d}{dt} ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} ) = ( \begin{matrix}1 & −\frac{1}{2} \\ 2 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} )

geschrieben wird. In Beispiel 12.101 war die Diagonalisierung

( \begin{matrix}1 & −\frac{1}{2} \\ 2 & 1 \end{matrix} ) = \underbrace{( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} )}_{T} \underbrace{( \begin{matrix}1 + i & 0 \\ 0 & 1 − i \end{matrix} )}_{D} \underbrace{( \begin{matrix}−\frac{i}{2} & \frac{1}{4} \\ \frac{1}{2} & −\frac{i}{4} \end{matrix} )}_{T^{−1}}

gefunden worden. Die Lösung der DGL ist damit

( \begin{matrix}x_{1}(t) \\ x_{2}(t) \end{matrix} ) = \underbrace{\underbrace{( \begin{matrix}i & 1 \\ 2 & 2 · i \end{matrix} )}_{T} \underbrace{( \begin{matrix}e^{t·(1+i)} & 0 \\ 0 & e^{t·(1−i)} \end{matrix} )}_{e^{t·D}} \underbrace{( \begin{matrix}−\frac{i}{2} & \frac{1}{4} \\ \frac{1}{2} & −\frac{i}{4} \end{matrix} )}_{T^{−1}}}_{e^{t·A}} ( \begin{matrix}x_{1}(0) \\ x_{2}(0) \end{matrix} )

= ( \begin{matrix}cos(t) · e^{t} & −\frac{1}{2} · sin(t) · e^{t} \\ 2 · sin(t) · e^{t} & cos(t) · e^{t} \end{matrix} ) ( \begin{matrix}x_{1}(0) \\ x_{2}(0) \end{matrix} ) ,

12.7. EIGENWERTE UND -VEKTOREN 293

also

x_{1}(t) = cos(t) · e^{t} · x_{1}(0) − \frac{x_{2}(0)}{2} · sin(t) · e^{t},

x_{2}(t) = 2 · sin(t) · e^{t} · x_{1}(0) + x_{2}(0) · cos(t) · e^{t}.