5. Umformungen mit Elementarmatrizen
Seien K ein Körper, n ≥ 1 und A ∈ GL(n, K).
Umformung mit Additionstypen: Diagonalisierung
Es gibt Additionstypen L1, …, Lk derart, dass Lk … L1A eine Diagonalmatrix ist. Analog gibt es Additionstypen R1, …, Rk derart, dass A R1 … Rk diagonal ist.
Umformung mit Additions- und Multiplikationstypen: Invertierung
Es gibt Additionstypen L1, …, Lk und Multiplikationstypen Mℓ, …, M1 derart, dass
Mℓ … M1 Lk … L1 A = En.
Analoges gilt für die Multiplikation von rechts.
Umformung mit unteren Additionstypen und Permutationen: LR-Zerlegung
Es gibt Additionstypen L1, …, Lk und eine Permutationsmatrix P mit
(a) | Li ist eine untere Dreiecksmatrix für alle i. |
(b) | Lk … L1 A P = R mit einer oberen Dreiecksmatrix R. |
Für die untere Dreiecksmatrix L = (Lk … L1)−1 gilt dann
A P = L R (LR-Zerlegung)
Jede invertierbare Matrix kann also nach einer geeigneten Spaltenvertauschung als Produkt einer unteren und einer oberen Dreiecksmatrix geschrieben werden.
Die Ergebnisse lassen sich durch verschiedene Strategien des Ausräumens der Matrix A beschreiben. Hierbei spielen die Einträge auf der Diagonale eine wichtige Rolle:
Sei B die durch das Ausräumen der Spalten 1, …, i − 1 unterhalb der Diagonale produzierte Matrix. Ist bii ≠ 0, so räumen wir unterhalb von (i, i) mit Hilfe von unteren Dreiecksmatrizen Wki(λ), k > i, aus. Ist bii = 0, so haben wir zwei Möglichkeiten:
(1) | Wir bringen einen Eintrag bki ≠ 0, k > i, unterhalb von (i, i) an die Stelle (i, i) (Multiplikation mit einer oberen Dreiecksmatrix Wik(λ) von links). |
(2) | Wir bringen einen Eintrag bij ≠ 0, i < j, rechts von (i, i) an die Stelle (i, i) (Multiplikation mit einer Transpositionsmatrix Pij von rechts). |
Die erste Version führt zu einer oberen Dreiecksmatrix Lm … L1 A. Analoges Ausräumen oberhalb der Diagonale liefert die Diagonalisierung. Höchstens n Multiplikationen mit Multiplikationstypen Mi verwandeln die Diagonalmatrix schließlich in En.
Die zweite Version ergibt die LR-Zerlegung. Sie benötigt im Allgemeinen eine Permutation der Spalten (Umbenennung der Variablen), kommt dafür aber mit unteren Dreiecksmatrizen Li aus. Die LR-Zerlegung ist beim numerischen Lösen von linearen Gleichungssystemen von Interesse.