7 Gruppen
7.1 Definition
Eine Gruppe ist ein Paar $(G, \cdot )$ bestehend aus einer Menge $G$ und einer Verknüpfung $G\times G \rightarrow G$, $(g,h)\mapsto g\cdot h$, so dass gilt:
(Assoziativität). Für alle $g,h,j\in G$ gilt: $(g\cdot h)\cdot j = g\cdot (h\cdot j)$.
(Neutrales Element). Es gibt ein Element $e\in G$, so dass für alle $g\in G$ gilt: $e\cdot g = g$, $g\cdot e = g$.
(Inverse Elemente). Für jedes $g\in G$ existiert ein Element $h\in G$ mit $g \cdot h = h \cdot g = e$.
$e$ wie in 2. ist eindeutig bestimmt ($e=ee’=e’$), wie in 3. implizit vorausgesetzt wird. [Könnte Definition ändern.]
Zu jedem $g\in G$ ist das inverse Element $h$ eindeutig bestimmt.
“Rechenregeln”
Abelsche/kommutative Gruppe
Gruppenhomomorphismus, Isomorphismus, Kern, Bild, Untergruppe
Gruppe der Bijektionen einer Menge, symmetrische Gruppe.
$GL_n$ Gruppe aller $K$-VR-Automorphismen von $K^n$.
Identifiziere $S_n$ mit Untergruppe der Permutationsmatrizen in $GL_n$
Symmetriegruppen von geometrischen Objekten (Teilmengen von $\mathbb R^n$).
7.2 Die spezielle lineare Gruppe
Elementarmatrizen $E_ij(a)$, $i\ne j$, $a\in K^\times $: auf der Diagonale überall $1$ und bei $(i,j)$ der Eintrag $a$, alle weiteren Einträge $=0$. Inverses einer Elementarmatrix: $E_{ij}(a)^{-1} = E_{ij}(-a)$.
$SL_n$ ist die von allen Elementarmatrizen erzeugte Untergruppe von $GL_n$.
Sei $A\in GL_n$. Dann existieren $d, d’\in K$ und $B, C\in SL_n$, so dass
(siehe zum Beispiel [ Lo-LA1 ] ).
7.3 Invertieren einer Matrix
Alle elementaren Zeilenumformungen lassen sich durch Multiplikation mit gewissen invertierbaren Matrizen von links beschreiben.
Ist $A\in M_{n\times n}(K)$ eine Matrix, die sich durch elementare Zeilenumformungen in die Einheitsmatrix $E_n$ umformen lässt, so ist $A$ invertierbar, und die inverse Matrix $A^{-1}$ geht aus $E_n$ durch Anwendung derselben Zeilenumformungen hervor.
7.4 Bruhat-Zerlegung
$B\subset GL_n(K)$ die Untergruppe der oberen Dreiecksmatrizen.
Beachte: die Menge $U$ aller Matrizen in $B$, deren Diagonaleinträge sämtlich $=1$ sind, ist eine Untergruppe.
$W\subset GL_n(K)$ die Untergruppe der Permutationsmatrizen.
Sei $A\in GL_n$. Dann existiert eine Permutationsmatrix $w\in GL_n$, so dass sich $A$ in der Form $b w b’$ mit $b, b’\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’$ erreichen, dass alle Diagonaleinträge von $b$ gleich $1$ sind.
Wir können den Satz umformulieren als $GL_n = \sqcup _w UwB$ (disjunkte Vereinigung), wobei $UwB = \{ bwb’;\ b\in U, b’\in B\} $.
Beachte: $b$, $b’$ im Satz sind nicht eindeutig bestimmt.
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, wobei stets $i Wir setzen $b:=u^{-1}\in U$, $b’ = d^{-1} (u’)^{-1}\in B$ und haben $A = bwb’$ wie gewünscht. II. Eindeutigkeit von $w$. Sei $b_1 w b_1’ = b_2 v b_2’$, wo $b_i, b_i’\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’:= b_2’(b_1’)^{-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’$ ist das $b’_{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’$ ist die Summe des $b’_{12}$-fachen der ersten und des $b’_{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.
Sei $B\in GL_n(K)$, sei $w$ die Permutationsmatrix, die zu der Permutation $i \mapsto n+1-i$ gehört, und sei $A=wB$. Sei $A=bwb’$ die Bruhat-Zerlegung von $A$ — mit derselben Permutation $w$. (Dies ist gewissermaßen der Normalfall.) Wir nehmen außerdem an, dass auf der Diagonalen von $b$ nur $1$ stehen. Dann ist $wbw$ eine untere Dreiecksmatrix, auf deren Diagonale nur $1$ stehen. In diesem Fall können wir also $B = (wbw)b’$ als Produkt einer unteren Dreiecksmatrix mit $1$ auf der Diagonale und einer oberen Dreiecksmatrix schreiben. Diese Zerlegung nennt man auch LR-Zerlegung von $B$; sie ist bei der numerischen Behandlung von linearen Gleichungssystemen von Bedeutung.