Inhalt

2.5 Die symmetrische Gruppe

Wir bezeichnen mit \(S_n\) die symmetrische Gruppe »auf \(n\) Buchstaben«, also die Gruppe der Bijektionen \(\{ 1,\dots , n\} \stackrel{\sim }{\smash {\longrightarrow }\rule{0pt}{0.4ex}}\{ 1,\dots , n\} \). Aus der Linearen Algebra kennen wir den Begriff des \(r\)-Zykels, Definition LA1.8.36.

Satz 2.52 Zerlegung in disjunkte Zykel

Jede Permutation \(\sigma \in S_n\) lässt sich als Produkt von Zykeln der Ordnung \({\gt} 1\) und mit paarweise disjunkten Trägern schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.

Beweis

»Anschaulich« ist die Sache einigermaßen klar, siehe Ergänzung LA1.8.38. Überlegen Sie selbst einmal, wie Sie einen formalen Beweis organisieren würden. Dies ist auch ein gutes Beispiel eines Satzes, der in vielen (Algebra-)Büchern bewiesen wird, und wo der Beweis teils auf ziemlich unterschiedliche Weise aufgeschrieben wurde – vergleichen Sie einige Beweise (zum Beispiel [ Bo-A ]  5.3 Satz 1 (ii), [ JS ] Kap. I Satz 3.3 (a), [ Lo ] Kap. 15, [ ] Prop. 1.3.6) und schreiben Sie am Ende »den für Sie selbst besten Beweis« auf.

Sei \(G = \langle \sigma \rangle \) die von \(\sigma \) erzeugte zyklische Gruppe. Dann operiert \(G\) auf \(\{ 1, \dots , n\} \). Wir bezeichnen mit \(B_1,\dots , B_r\) diejenigen Bahnen von \(G\) auf \(\{ 1, \dots , n\} \), die mehr als ein Element haben. Sei \(b_i\in B_i\) jeweils ein fixiertes Element und sei \(n_i = \# B_i\). Für \(1 \le m {\lt} n_i\) gilt dann \(\sigma ^m(b_i)\ne b_i\), denn sonst hätte \(B_i\) höchstens \(m\) Elemente. Es folgt

\[ B_i = \{ b_i, \sigma (b_i), \sigma ^2(b_i), \dots , \sigma ^{n_i-1}(b_i)\} \]

(die Inklusion \(\supseteq \) ist klar, und mit dem vorher gegebenen Argument sieht man leicht, dass die Elemente auf der rechten Seite paarweise verschieden sind, so dass beide Seiten gleich viele Elemente haben), und dass \(\sigma ^{n_i}(b_i) = b_i\) gilt. Wenn wir mit \(\pi _i\) den Zykel \((b_i, \sigma (b_i), \sigma ^2(b_i), \dots , \sigma ^{n_i-1}(b_i))\) bezeichnen, erhalten wir mit

\[ \sigma = \pi _1\cdots \pi _r \]

eine Zerlegung von \(\sigma \) als Produkt von Zykeln mit disjunkten Trägern.

Zur Eindeutigkeit beobachten wir zunächst, dass die in so einer Zerlegung auftretenden Zykel bijektiv den Bahnen von \(\sigma \) entsprechen müssen, die mehr als ein Element haben, weil die Träger dieser Zykel nach Voraussetzung disjunkt sind. Fixieren wir eine dieser Bahnen, etwa \(B\), so stimmen die Einschränkung von \(\sigma \) und des der Bahn entsprechenden Zykel als Abbildungen \(B\to B\) überein, und folglich sind die einzelnen Zykel in der Zerlegung eindeutig bestimmt.

Bei der Eindeutigkeitsaussage ist zu beachten, dass sich die Eindeutigkeit eines Zykels auf die Eindeutigkeit als Permutation, nicht auf die Schreibweise bezieht, zum Beispiel gilt \((1234)=(2341)=(3412)=(4123)\).

Jeder Permutation \(\sigma \) können wir ihr Signum oder Vorzeichen \(\operatorname{sgn}(\sigma )\in \{ 1, -1\} \) zuordnen. Die Signumabbildung \(S_n\to \{ 1, -1\} \) ist ein Gruppenhomomorphismus.

Definition 2.53

Wir schreiben \(A_n = \operatorname{Ker}(\operatorname{sgn})\) und nennen diesen Normalteiler von \(S_n\) die alternierende Gruppe.

Satz 2.54 Satz von Cayley

Sei \(G\) eine Gruppe, und sei \(\operatorname{Bij}(G)\) die Gruppe der bijektiven Abbildungen \(G\to G\) (mit der Verkettung von Abbildungen als Verknüpfung). Für \(g\in G\) liegt die Abbildung \(m_g\colon G\to G\), \(x\mapsto gx\), in \(\operatorname{Bij}(G)\) und die Abbildung

\[ G\to \operatorname{Bij}(G),\quad g\mapsto m_g, \]

ist ein injektiver Gruppenhomomorphismus.

Insbesondere gilt: Jede endliche Gruppe ist isomorph zu einer Untergruppe einer symmetrischen Gruppe.

Beweis

Für \(g\in G\) definiert die Vorschrift \(x\mapsto gx\) eine Abbildung \(m_g\colon G\to G\) (dies ist kein Gruppenhomomorphismus, wenn \(g\) nicht das neutrale Element von \(G\) ist). Die Abbildung \(m_g\) ist bijektiv, denn ist \(h\in G\) das inverse Element zu \(g\), so ist \(m_h\) die Umkehrabbildung von \(m_g\).

Wir erhalten eine Abbildung \(G\to \operatorname{Bij}(G)\), \(g\mapsto m_g\). Diese Abbildung ist ein Gruppenhomomorphismus, denn für Elemente \(g, h\in G\) gilt:

\[ m_{h'}(x) = (gh)x = g(hx)=m_g(m_{h}(x)) = (m_g\circ m_{h})(x). \]

(Dieser Gruppenhomomorphismus ist genau derjenige, der der Wirkung von \(G\) auf sich selbst durch Multiplikation von links entspricht.)

Zudem ist die Abbildung \(g\to m_g\) injektiv. Es genügt dafür zu zeigen, dass nur das neutrale Element von \(G\) auf das neutrale Element von \(S_n\) abgebildet wird. Aber wenn \(m_g = \operatorname{id}\) die Identitätsabbildung ist, dann folgt \(gx = x\) für alle \(x\in G\), und diese Eigenschaft charakterisiert das neutrale Element von \(G\).

Der Zusatz folgt, weil für eine endliche Gruppe mit \(n\) Elementen jede Bijektion zwischen \(G\) und der Menge \(\{ 1,\dots , n\} \) einen Gruppenisomorphismus \(\operatorname{Bij}(G) \stackrel{\sim }{\smash {\longrightarrow }\rule{0pt}{0.4ex}}S_n\) induziert.

Ergänzung 2.55 Konjugationsklassen der symmetrischen Gruppe

Die Zykelzerlegung gibt auch Aufschluss über die Konjugationsklassen in der symmetrischen Gruppe \(S_n\), also über die Bahnen unter der Konjugationsoperation von \(S_n\) auf sich selbst, oder noch anders gesagt über die Äquivalenzklassen in \(S_n\) bezüglich der Äquivalenzrelation

\[ g\sim g'\quad \Longleftrightarrow \quad \text{es existiert}\ h\ \text{mit}\ g' = hgh^{-1}. \]

Die Konjugationsklassen zu verstehen, gibt oft sehr interessante Informationen über die Struktur einer Gruppe und ist insbesondere in der Darstellungstheorie (siehe Ergänzungsabschnitt 8.5.2) von Bedeutung.

Für \(\sigma \in S_n\) mit Zerlegung \(\sigma = \pi _1\cdots \pi _r\) in Zykel der Ordnung \({\gt} 1\) mit disjunkten Trägern nennen wir das absteigend geordnete Tupel der Ordnungen der Zykel \(\pi _i\), ergänzt um Einsen (je eine \(1\) für jedes Element \(\{ 1,\dots , n\} \), das von \(\sigma \) auf sich selbst abgebildet wird) den Zykeltyp von \(\sigma \). Zum Beispiel hat

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 1 & 8 & 2 & 5 & 9 & 3 & 6 & 7 \end{pmatrix} = (142)(38697) \]

den Zykeltyp \((5,3,1)\). Die Ergänzung um Einsen (sozusagen für die \(1\)-Zykel, die wir in der Zykelzerlegung nicht hinschreiben) hat zur Folge, dass für jedes \(\sigma \in S_n\) die Summe aller Einträge des Zykeltyps gleich \(n\) ist.

Dann gilt der folgende Satz:

Satz 2.56

Permutationen \(\sigma , \tau \in S_n\) sind genau dann zueinander konjugiert, wenn sie denselben Zykeltyp haben.

Siehe  [ Soe ] Abschnitt 5.5.