8.4 Die Bruhat-Zerlegung *
Seien \(K\) ein Körper und \(n\ge 1\).
Sei \(B\subset GL_n(K)\) die Teilmenge der invertierbaren oberen Dreiecksmatrizen. Es ist nicht schwer zu sehen, dass \(B\) eine Untergruppe von \(GL_n(K)\) ist: Das Produkt von oberen Dreiecksmatrizen ist eine obere Dreiecksmatrix ist, und das Inverse einer invertierbaren oberen Dreiecksmatrix ist eine obere Dreiecksmatrix. Dass die Einheitsmatrix \(E_n\) in \(B\) liegt, ist offensichtlich.
Die Menge \(U\) aller Matrizen in \(B\), deren Diagonaleinträge sämtlich \(=1\) sind, ist eine Untergruppe.
Wir bezeichnen mit \(W\subset GL_n(K)\) die Untergruppe der Permutationsmatrizen (siehe Definition 8.25).
Sei \(A\in GL_n(K)\). Dann existiert eine Permutationsmatrix \(w\in GL_n(K)\), so dass sich \(A\) in der Form \(b w b^\prime \) mit \(b, b^\prime \in B\) schreiben lässt. Ferner gilt: die Matrix \(w\) ist durch \(A\) eindeutig bestimmt. Außerdem lässt sich bei geeigneter Wahl von \(b\) und \(b^\prime \) erreichen, dass alle Diagonaleinträge von \(b\) gleich \(1\) sind.
Wir können den Satz umformulieren als
Hier schreiben wir
Es gilt
Das Symbol \(\sqcup \) bedeutet, dass es sich um eine disjunkte Vereinigung handelt, das heißt \(GL_n(K) = \bigcup _w UwB\) und \(UwB \cap Uw^\prime B=\emptyset \) für alle \(w\ne w^\prime \). Die Gruppe \(GL_n(K)\) als eine disjunkte Vereinigung zu beschreiben, nennt man auch eine Zerlegung von \(GL_n(K)\). Der Name Bruhat-Zerlegung geht zurück auf den französischen Mathematiker François Bruhat (1929–2007).
Es ist wichtig zu beachten, dass \(b\) und \(b^\prime \) im Satz in der Regel nicht eindeutig bestimmt sind.
I. Existenz der Zerlegung. Wir führen den sogenannten Gauß-Bruhat-Algorithmus durch und bringen \(A\) im ersten Schritt durch geeignete Zeilen- und Spaltenumformungen vom Typ I auf eine Matrix, die in jeder Zeile und in jeder Spalte genau einen Eintrag \(\ne 0\) hat.
Sei \(A=(a_{ij})_{i,j}\in GL_n(K)\). Sei \(i_1\) maximal mit \(a_{i_1,1}\ne 0\). Bringe alle Einträge der ersten Spalte in den Zeilen \(i=1,\dots , i_1-1\) durch geeignete Zeilenumformungen vom Typ I auf \(0\). Danach ist nur noch ein Eintrag in der ersten Spalte vorhanden. Bringe nun alle Einträge der \(i_1\)-ten Zeile in den Spalten \(2, 3, \dots , n\) durch geeignete Spaltenumformungen vom Typ I auf \(0\). Danach ist auch in Zeile \(i_1\) nur noch ein einziger Eintrag (nämlich \(a_{i_1,1}\)) ungleich \(0\).
Bezeichne die Einträge der neuen Matrix wieder mit \(a_{ij}\).
Sei nun \(i_2\) maximal mit \(a_{i_2,2}\ne 0\). Nach dem ersten Schritt ist jedenfalls \(i_2\ne i_1\) (und insbesondere \(a_{i_2,1}=0\)). Bringe alle Einträge der zweiten Spalte in den Zeilen \(i=1,\dots , i_2-1\) durch geeignete Zeilenumformungen vom Typ I auf \(0\). Danach ist nur noch ein Eintrag in der zweiten Spalte vorhanden. Bringe nun alle Einträge der \(i_2\)-ten Zeile in den Spalten \(3, \dots , n\) durch geeignete Spaltenumformungen vom Typ I auf \(0\). Danach ist auch in Zeile \(i_2\) nur noch ein einziger Eintrag (nämlich \(a_{i_2,2}\)) ungleich \(0\).
Fahre entsprechend fort mit den Spalten \(3, \dots , n\). Alle diese elementaren Zeilen- und Spaltenumformungen lassen sich beschreiben durch Multiplikation von \(A\) mit Elementarmatrizen \(E_{ij}(a)\) von links bzw. rechts. Weil wir immer nur Vielfache einer Zeile zu einer darüberliegenden Zeile bzw. Vielfache eine Spalte zu einer davon rechts liegenden Spalte addieren, gilt stets \(i {\lt} j\), d.h. \(E_{ij}(a)\in U\). Es gibt also \(u, u^\prime \in U\), so dass \(uAu^\prime \) in jeder Zeile und jeder Spalte genau einen Eintrag \(\ne 0\) hat. Sei \(d\) die eindeutig bestimmte Diagonalmatrix, so dass \(w:=uAu^\prime d\) eine Permutationsmatrix ist.
Wir setzen \(b:=u^{-1}\in U\), \(b^\prime = d^{-1} (u^\prime )^{-1}\in B\) und haben \(A = bwb^\prime \) wie gewünscht.
II. Eindeutigkeit von \(w\). Sei \(b_1 w b_1^\prime = b_2 v b_2^\prime \), wo \(b_i, b_i^\prime \in B\), \(v,w\in W\). Sei \(\sigma \) die zu \(v\), und \(\tau \) die zu \(w\) gehörige Permutation. Zu zeigen ist \(w=v\). Jedenfalls gilt für \(b:= b_2^{-1}b_1\), \(b^\prime := b_2^\prime (b_1^\prime )^{-1}\):
Vergleiche nun die ersten Spalten dieser Matrizen. Die erste Spalte von \(bw\) ist die \(\tau (1)\)-te Spalte von \(b\). Jedenfalls an der Stelle \(\tau (1)\) befindet sich hier ein Eintrag \(\ne 0\). Die erste Spalte von \(vb^\prime \) ist das \(b^\prime _{11}\)-fache der ersten Spalte von \(v\). Höchstens (und sogar genau) an der Stelle \(\sigma (1)\) befindet sich hier ein Eintrag \(\ne 0\). Es folgt \(\tau (1)\in \{ \sigma (1)\} \), also \(\tau (1)=\sigma (1)\).
Vergleiche nun die zweiten Spalten der Matrizen. Die zweite Spalte von \(bw\) ist die \(\tau (2)\)-te Spalte von \(b\). Jedenfalls an der Stelle \(\tau (2)\) befindet sich hier ein Eintrag \(\ne 0\). Die zweite Spalte von \(vb^\prime \) ist die Summe des \(b^\prime _{12}\)-fachen der ersten und des \(b^\prime _{22}\)-fachen der zweiten Spalte. Höchstens an den Stellen \(\sigma (1)\) und \(\sigma (2)\) befinden sich hier Einträge \(\ne 0\). Es folgt \(\tau (2)\in \{ \sigma (1), \sigma (2)\} \). Da \(\tau \) bijektiv ist und \(\tau (1)=\sigma (1)\), folgt \(\tau (2)=\sigma (2)\).
Induktiv folgt \(\tau =\sigma \), also \(w=v\), wie gewünscht.
Bei der praktischen Durchführung des Algorithmus ist es unter Umständen sinnvoller, die Einträge \(a_{i_\nu , \nu }\) direkt durch Multiplikation der entsprechenden Spalte mit \(a_{i_\nu , \nu }^{-1}\) auf \(1\) zu bringen.
Die Bruhat-Zerlegung ist eng verwandt mit der LR-Zerlegung, die auch (neben der direkten Anwendung des Gauß-Verfahrens) bei der Lösung von Gleichungssystemen in der Praxis eine Rolle spielt (für Gleichungssysteme in der Größenordnung von \(\le 10\, 000\) Gleichungen). Darunter versteht man den folgenden Satz:
Sei \(A\in GL_n(K)\) eine invertierbare Matrix. Dann existieren eine Permutationsmatrix \(P\), eine untere Dreiecksmatrix \(L\) (mit Einsen auf der Diagonale) und eine obere Dreiecksmatrix \(R\), so dass
Wie der Beweis zeigen wird, ist \(P\) genau dieselbe Permutationsmatrix, die auch in der Bruhat-Zerlegung von \(A\) auftritt. (Eine Variante ist, den Satz auf \(w_0A\) anzuwenden; gilt \(w_0A\in Bw_0B\) – in gewissem Sinne der Normalfall – so erhält man dann \(w_0 A = w_0LR\), also \(A=LR\) für eine untere Dreiecksmatrix \(L\) und eine obere Dreiecksmatrix \(R\).)
Sei \(w_0 = P_{\sigma }\), wobei die Permutation \(\sigma \) definiert ist durch \(\sigma (i) = n-i+1\). Dann gilt \(w_0 = w_0^{-1}\) und für eine obere Dreiecksmatrix \(M\) ist \(w_0Mw_0^{-1}\) eine untere Dreiecksmatrix.
Sei nun \(A = bwb^\prime \) mit \(b, b^\prime \in B\), \(w\in W\), die Bruhat-Zerlegung von \(A\). Es folgt dann leicht aus dem Beweis der Bruhat-Zerlegung, dass \(w_0w^{-1}A \in Bw_0 B\) ist, d.h. die Permutationsmatrix in der Bruhat-Zerlegung der Matrix \(w_0w^{-1}A\) ist \(w_0\). Schreiben wir
mit \(L^\prime , R\in B\), so erhalten wir
wir können also \(P:=w\), \(L:=w_0L^\prime w_0\) setzen.
Die LR-Zerlegung heißt manchmal auch LU-Zerlegung und lässt sich auch auf den Fall verallgemeinern, dass \(A\) nicht invertierbar ist (vergleiche [ LM ] Satz 5.4).
Ist \(A\) invertierbar und ein lineares Gleichungssystem \(Ax = b\) gegeben, und ist \(A = PLR\) wie oben die LR-Zerlegung von \(A\), so haben wir für die eindeutig bestimmte Lösung \(x\):
Der Vektor \(b^\prime = P^{-1} b\) entsteht durch Vertauschung der Einträge von \(b\). Der Vektor \(x^\prime = L^{-1} b^\prime \) ist die eindeutige Lösung des linearen Gleichungssystems \(Lx^\prime = b^\prime \), die unmittelbar »abgelesen« werden kann, weil \(L\) eine Dreiecksmatrix ist. Dann ist \(x\) die Lösung des Gleichungssystems \(Rx = x^\prime \), und auch diese lässt sich direkt ablesen, weil \(R\) eine Dreiecksmatrix ist.
Wenn man das Verfahren in der Praxis in Fällen anwendet, die man nicht per Hand lösen kann, sind natürlich Fragen der Effizienz und vor allem der Rechengenauigkeit zu beachten, insbesondere Strategien, um Rundungsfehler zu vermeiden und/oder zu kontrollieren. Diese Aspekte lassen wir hier völlig außer Acht.