Symmetrische Gruppe

Die symmetrische Gruppe ${\displaystyle S_{n}}$ (${\displaystyle {\mathcal {S}}_{n}}$, ${\displaystyle {\mathfrak {S}}_{n}}$ oder ${\displaystyle \operatorname {Sym} _{n}}$) ist die Gruppe, die aus allen Permutationen (Vertauschungen) einer ${\displaystyle n}$-elementigen Menge besteht. Man nennt ${\displaystyle n}$ den Grad der Gruppe. Die Gruppenoperation ist die Komposition ${\displaystyle \circ }$ (Hintereinanderausführung) der Permutationen; das neutrale Element ist die identische Abbildung. Die symmetrische Gruppe ${\displaystyle S_{n}}$ ist endlich und besitzt die Ordnung ${\displaystyle n!}$. Sie ist für ${\displaystyle n>2}$ nichtabelsch.

Ein Cayleygraph der symmetrischen Gruppe S₄

Verknüpfungstafel der symmetrischen Gruppe S₃
(als Multiplikationstafel der Permutationsmatrizen)

Der Name der Gruppe wurde deshalb so gewählt, weil die Funktionen der Variablen ${\displaystyle x_{1},x_{2},\dotsb ,x_{n}}$, die bei allen Permutationen invariant bleiben, die symmetrischen Funktionen sind.[1]

Notation von Permutationen

Zweizeilenform

Es gibt verschiedene Möglichkeiten, eine Permutation zu notieren. Bildet zum Beispiel eine Permutation ${\displaystyle p}$ das Element ${\displaystyle 1}$ auf ${\displaystyle p_{1}}$, das Element ${\displaystyle 2}$ auf ${\displaystyle p_{2}}$ usw. ab, so kann man hierfür

${\displaystyle p={\begin{pmatrix}1&2&3&\dots \\p_{1}&p_{2}&p_{3}&\dots \end{pmatrix}}}$

schreiben. In dieser sogenannten Zweizeilenform erhält man die inverse Permutation ${\displaystyle p^{-1}}$, indem man die obere und die untere Zeile vertauscht.

Anmerkung: Die Elemente d​er ersten Zeile dürfen a​uch in e​iner anderen Reihenfolge notiert werden.

Zyklenschreibweise

Eine andere wichtige Schreibweise i​st die Zyklenschreibweise:

Sind ${\displaystyle p_{1},p_{2},\ldots p_{k}}$ verschieden, geht ${\displaystyle p_{1}}$ in ${\displaystyle p_{2}}$, ${\displaystyle p_{2}}$ in ${\displaystyle p_{3}}$, ..., ${\displaystyle p_{k}}$ in ${\displaystyle p_{1}}$ über, und bleiben alle anderen Elemente invariant, so schreibt man hierfür

${\displaystyle p={\begin{pmatrix}p_{1}&p_{2}&p_{3}&\dots &p_{k}\end{pmatrix}},}$

und nennt dies einen Zyklus der Länge ${\displaystyle k}$. Zwei Zyklen der Länge ${\displaystyle k}$ beschreiben genau dann die gleiche Abbildung, wenn der eine durch zyklische Vertauschung seiner Einträge ${\displaystyle p_{k}}$ zum anderen wird. Zum Beispiel gilt ${\displaystyle {\begin{pmatrix}1&5&3\end{pmatrix}}={\begin{pmatrix}5&3&1\end{pmatrix}}\neq {\begin{pmatrix}1&3&5\end{pmatrix}}.}$

Jede Permutation kann als Produkt von disjunkten Zyklen geschrieben werden. (Hierbei heißen zwei Zyklen ${\displaystyle {\begin{pmatrix}p_{1}&p_{2}&p_{3}&\dots &p_{k}\end{pmatrix}}}$ und ${\displaystyle {\begin{pmatrix}q_{1}&q_{2}&q_{3}&\dots &q_{l}\end{pmatrix}}}$ disjunkt, wenn ${\displaystyle p_{i}\neq q_{j}}$ für alle ${\displaystyle i}$ und ${\displaystyle j}$ gilt.) Diese Darstellung als Produkt von disjunkten Zyklen ist sogar eindeutig bis auf zyklische Vertauschung der Einträge innerhalb von Zyklen und die Reihenfolge der Zyklen (diese Reihenfolge kann beliebig sein: disjunkte Zyklen kommutieren stets miteinander).

Eigenschaften

Erzeugende Mengen

• Jede Permutation kann als Produkt von Transpositionen (Zweierzyklen) dargestellt werden; je nachdem, ob diese Anzahl gerad- oder ungeradzahlig ist, spricht man von geraden oder ungeraden Permutationen. Unabhängig davon, wie man das Produkt wählt, ist diese Anzahl entweder immer gerade oder immer ungerade und wird durch das Vorzeichen der Permutation beschrieben. Die Menge der geradzahligen Permutationen bildet eine Untergruppe der ${\displaystyle S_{n},}$ die alternierende Gruppe ${\displaystyle A_{n}.}$
• Auch die beiden Elemente ${\displaystyle {\begin{pmatrix}1&2\end{pmatrix}}}$ und ${\displaystyle {\begin{pmatrix}1&2&\dots &n\end{pmatrix}}}$ erzeugen die symmetrische Gruppe ${\displaystyle S_{n}.}$[2] Allgemeiner kann auch ein beliebiger ${\displaystyle n}$-Zyklus zusammen mit einer beliebigen Transposition zweier aufeinanderfolgender Elemente in diesem Zyklus gewählt werden.
• Falls ${\displaystyle n\neq 4}$, lässt sich zu einem beliebigen Element (nicht die Identität) ein Zweites derart wählen, dass beide Elemente die ${\displaystyle S_{n}}$ erzeugen.[3]

Konjugationsklassen

Zwei Elemente d​er symmetrischen Gruppe s​ind genau d​ann zueinander konjugiert, w​enn sie i​n der Darstellung a​ls Produkt disjunkter Zyklen denselben Zyklentyp aufweisen, d​as heißt, w​enn die Anzahlen d​er Einer-, Zweier-, Dreier- usw. -Zyklen übereinstimmen. In dieser Darstellung bedeutet d​ie Konjugation e​ine Umnummerierung d​er Zahlen, d​ie in d​en Zyklen stehen.

Jede Konjugationsklasse der ${\displaystyle S_{n}}$ entspricht daher umkehrbar eindeutig einer Zahlpartition von ${\displaystyle n}$ und die Anzahl ihrer Konjugationsklassen ist gleich dem Wert der Partitionsfunktion an der Stelle ${\displaystyle n,\,P(n).}$

Zum Beispiel liegen die Elemente ${\displaystyle {\begin{pmatrix}1&2&3\end{pmatrix}}{\begin{pmatrix}4&5\end{pmatrix}};{\begin{pmatrix}7&1&2\end{pmatrix}}{\begin{pmatrix}3&4\end{pmatrix}}\in S_{7}}$ in der Konjugationsklasse, die der Zahlpartition ${\displaystyle 7=3+2+1+1}$ von ${\displaystyle 7}$ zugeordnet ist und ${\displaystyle S_{7}}$ hat ${\displaystyle P(7)=15}$ verschiedene Konjugationsklassen.

Normalteiler

Die symmetrische Gruppe ${\displaystyle S_{n}}$ besitzt außer den trivialen Normalteilern ${\displaystyle \{id\}}$ und ${\displaystyle S_{n}}$ nur die alternierende Gruppe ${\displaystyle A_{n}}$ als Normalteiler, für ${\displaystyle n=4}$ zusätzlich noch die Kleinsche Vierergruppe ${\displaystyle V}$.

Die Kommutatorgruppe ${\displaystyle K(S_{n})=[S_{n},S_{n}]={S_{n}}'}$ ist ein Normalteiler, und es ist

${\displaystyle K(S_{n})=A_{n}}$.

Satz von Cayley

Nach dem Satz von Cayley ist jede endliche Gruppe ${\displaystyle G}$ zu einer Untergruppe einer symmetrischen Gruppe ${\displaystyle S_{n}}$ isomorph, deren Grad ${\displaystyle n}$ nicht größer als die Ordnung von ${\displaystyle G}$ ist.

Ferner kann ${\displaystyle S_{n}}$ unter Anhängen der Transposition ${\displaystyle (n+1,n+2)}$ an alle ungeraden Permutationen in die alternierende Gruppe ${\displaystyle A_{n+2}}$ eingebettet werden. Damit ist jede endliche Gruppe auch zu einer Untergruppe einer alternierenden Gruppe isomorph.

Rechenbeispiele

Angelehnt an die Verkettung von Funktionen wird bei der Hintereinanderausführung ${\displaystyle p_{2}\circ p_{1}}$ von zwei Permutationen die zuerst ausgeführte Permutation ${\displaystyle p_{1}}$ rechts vom Verkettungszeichen ${\displaystyle \circ }$ geschrieben. Auf das Ergebnis wird die zweite Permutation ${\displaystyle p_{2}}$ angewandt.

Beispiel:

${\displaystyle {\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}\circ {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4\\3&4&2&1\end{pmatrix}}.}$

In Zyklenschreibweise lautet dies:

${\displaystyle {\begin{pmatrix}2&4\end{pmatrix}}\circ {\begin{pmatrix}1&3&4\end{pmatrix}}={\begin{pmatrix}1&3&2&4\end{pmatrix}}.}$

Zunächst bildet die „rechte“ Permutation ${\displaystyle \scriptstyle {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}\,=\,\scriptstyle {\begin{pmatrix}1&3&4\end{pmatrix}}}$ die ${\displaystyle 1}$ auf die ${\displaystyle 3}$ ab, anschließend bildet die „linke“ Permutation ${\displaystyle \scriptstyle {\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}\,=\,\scriptstyle {\begin{pmatrix}2&4\end{pmatrix}}}$ die ${\displaystyle 3}$ auf die ${\displaystyle 3}$ ab; die gesamte Verkettung bildet also die ${\displaystyle 1}$ auf die ${\displaystyle 3}$ ab, wie rechts vom Gleichheitszeichen als ${\displaystyle \scriptstyle {\begin{pmatrix}1&2&3&4\\3&4&2&1\end{pmatrix}}\,=\,\scriptstyle {\begin{pmatrix}1&3&2&4\end{pmatrix}}}$ hingeschrieben.

Für ${\displaystyle n>2}$ ist die symmetrische Gruppe ${\displaystyle S_{n}}$ nicht abelsch, wie man an folgender Rechnung sieht:

${\displaystyle {\begin{pmatrix}1&2&3&\ldots \\2&3&1&\ldots \end{pmatrix}}\circ {\begin{pmatrix}1&2&3&\ldots \\2&1&3&\ldots \end{pmatrix}}={\begin{pmatrix}1&2&3&\ldots \\3&2&1&\ldots \end{pmatrix}}\ \neq }$

${\displaystyle {\begin{pmatrix}1&2&3&\ldots \\2&1&3&\ldots \end{pmatrix}}\circ {\begin{pmatrix}1&2&3&\ldots \\2&3&1&\ldots \end{pmatrix}}={\begin{pmatrix}1&2&3&\ldots \\1&3&2&\ldots \end{pmatrix}}}$

Siehe auch

• Symmetrische Gruppe vom Grad 3
• Young-Tableau

Einzelnachweise

1. B. L. van der Waerden: Moderne Algebra. 3. verbesserte Auflage. Springer-Verlag, Berlin, Göttingen, Heidelberg 1950, S. 21 (VIII, 292 S.).
2. Vgl. Seite 2 oben in (PDF-Datei (Memento vom 16. Dezember 2011 im Internet Archive))
3. I. M. Isaacs and Thilo Zieschang, “Generating Symmetric Groups,” The American Mathematical Monthly 102, no. 8 (October 1995): 734-739.