Die Elementarmatrizen

Wir zeigen nun, dass der Invertierungsalgorithmus korrekt ist: Er eignet sich als Test auf Invertierbarkeit und er produziert im invertierbaren Fall das Inverse der Ausgangsmatrix. Hierzu führen wir spezielle Matrizen ein, mit deren Hilfe wir die elementaren Zeilenoperationen als Matrizenmultiplikation von links darstellen können.

Definition (Elementarmatrix, Additionstyp, Multiplikationstyp)

Seien 1 ≤ i, j ≤ 3 und λ  ∈  ℝ. Dann ist W_ij(λ)  ∈  ℝ^3 × 3 definiert als die Matrix, die mit der Einheitsmatrix E₃ übereinstimmt, aber an der Stelle (i, j) den Eintrag λ besitzt. Eine solche Matrix W heißt eine Elementarmatrix, falls

W = W_ij(λ) mit λ  ∈  ℝ, i ≠ j, oder (Additionstyp)

W = W_ij(λ) mit λ  ∈  ℝ*, i = j.(Multiplikationstyp)

Die Matrix W_ij(λ) entsteht, indem wir den Eintrag der Einheitsmatrix an der Stelle (i, j) mit dem Skalar λ überschreiben. Befindet sich der neue Eintrag außerhalb der Hauptdiagonalen, so erhalten wir einen Additionstyp. Wird eine Eins der Diagonale durch λ ≠ 0 ersetzt, so erhalten wir einen Multiplikationstyp. Die Namensgebung wird erklärt durch:

(1)	Ist A  ∈  ℝ^3 × 3 und W = W_ij(λ) ein Additionstyp, so ist WA die Matrix, die entsteht, wenn wir das λ-Fache der j-ten Zeile zur i-ten Zeile von A addieren.

(2)	Ist A  ∈  ℝ^3 × 3 und W = W_ii(λ) ein Multiplikationstyp, so ist WA die Matrix, die entsteht, wenn wir die i-te Zeile von A mit λ multiplizieren.

Beispiel

W₂₃(5) = $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 5 \\ 0 & 0 & 1 \end{matrix} )$ , W₂₃(5) $( \begin{matrix} 1 & 1 & 2 \\ 0 & - 2 & - 1 \\ 1 & 2 & 1 \end{matrix} )$ = $( \begin{matrix} 1 & 1 & 2 \\ 5 & 8 & 4 \\ 1 & 2 & 1 \end{matrix} )$

W₃₂(5) = $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{matrix} )$ , W₃₂(5) $( \begin{matrix} 1 & 1 & 2 \\ 0 & - 2 & - 1 \\ 1 & 2 & 1 \end{matrix} )$ = $( \begin{matrix} 1 & 1 & 2 \\ 0 & - 2 & 1 \\ 1 & - 8 & - 4 \end{matrix} )$

Für die Multiplikation AW einer Matrix A mit einer Elementarmatrix W von rechts gelten analoge Aussagen für die Spalten von A. Für einen Additionstyp W vertauschen sich dabei die Indizes, sodass AW entsteht, indem wir das λ-Fache der i-ten Spalte zur j-ten Spalte von A addieren.

Eine Elementarmatrix ist invertierbar und ihr Inverses ist wieder eine Elementarmatrix:

(1)	Das Inverse eines Additionstyps W_ij(λ) ist W_ij(−λ).

(2)	Das Inverse eines Multiplikationstyps W_ii(λ) ist W_ii(1/λ).

Den Invertierungsalgorithmus können wir nun so beschreiben: Gegeben A, versuchen wir, Elementarmatrizen L₁, …, L_k zu finden, sodass

(+) L_k … L₁ A = E₃.

Gelingt dies, so ist

B = L_k … L₁ = A⁻¹.

Denn es gilt B A = L_k … L₁ A = E₃ nach (+), und aus B A B = E₃ B = B und der Invertierbarkeit von B folgt A B = B⁻¹ B A B = B⁻¹ B = E₃. Wegen

B = B E₃ = L_k … L₁ E₃

erzeugt unser Algorithmus im invertierbaren Fall also das Inverse von A in der parallel ausgeführten Zeilenmanipulation von E₃. Mit obigen Notationen gilt

A₀ = A, A₁ = L₁ A₀, A₂ = L₂ A₁ = L₂ L₁ A, …

B₀ = E₃, B₁ = L₁ B₀ = L₁, B₂ = L₂ B₁ = L₂ L₁, …

Wird eine Nullzeile oder Nullspalte erzeugt, so ist die Matrix

A_k = L_k … L₁ A

nicht invertierbar. Da alle L_i invertierbar sind, ist notwendig A singulär. Damit ist die Korrektheit des Algorithmus vollständig bewiesen.

Unsere Überlegungen zeigen (angewendet auf B = A⁻¹), dass jede invertierbare Matrix A als ein Produkt von Elementarmatrizen dargestellt werden kann:

Satz (Zerlegung einer invertierbaren Matrix in Elementarmatrizen)

Sei A  ∈  ℝ^3 × 3 invertierbar. Dann gibt es ein k ≥ 1 und Elementarmatrizen L₁, …, L_k mit A = L_k … L₁.

Dieser bemerkenswerte Satz gilt analog auch für höhere Dimensionen.

Bemerkung: Deterministische Version des Invertierungs-Algorithmus

Wir haben bei unserer Formulierung des Algorithmus keine Strategie vorgegeben, wie der Versuch der Umwandlung von A in E₃ durchzuführen ist. Es gibt verschiedene Möglichkeiten, dies zu organisieren. Eine deterministische Version erhalten wir zum Beispiel, indem wir solange wie möglich (1) A Spalte für Spalte unterhalb der Hauptdiagonalen ausräumen, (2) A Spalte für Spalte oberhalb der Hauptdiagonalen ausräumen, (3) die Diagonale normieren. Alternativ können wir die Spalten von A auch gleich unter- und oberhalb der Diagonale ausräumen und dabei auch die Normierung der Diagonaleinträge durchführen.