Symmetrische Gruppe - LinkFang.de





Symmetrische Gruppe


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

Notation, Zyklenschreibweise

Es gibt verschiedene Möglichkeiten, eine Permutation zu notieren. Bildet zum Beispiel eine Permutation [math]p[/math] das Element [math]1[/math] auf [math]p_1[/math], das Element [math]2[/math] auf [math]p_2[/math] usw. ab, so kann man hierfür

[math] p = \begin{pmatrix} 1 & 2 & 3 & \dots \\ p_1 & p_2 & p_3 & \dots \end{pmatrix} [/math]

schreiben. (Es ist nicht unbedingt gefordert, dass die Zahlen in der oberen Zeile geordnet sind.) In dieser Schreibweise erhält man die inverse Permutation [math]p^{-1}[/math], indem man die obere und die untere Zeile vertauscht.

Eine andere wichtige Schreibweise ist die Zyklenschreibweise:

Sind [math]p_1,p_2,\ldots p_k[/math] verschieden, geht [math]p_1[/math] in [math]p_2[/math], [math]p_2[/math] in [math]p_3[/math], ..., [math]p_k[/math] in [math]p_1[/math] über, und bleiben alle anderen Elemente invariant, so schreibt man hierfür

[math] p = \begin{pmatrix} p_1 & p_2 & p_3 & \dots & p_k \end{pmatrix}, [/math]

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

Jede Permutation kann als Produkt von disjunkten Zyklen geschrieben werden. (Hierbei heißen zwei Zyklen [math]\begin{pmatrix} p_1 & p_2 & p_3 & \dots & p_k \end{pmatrix}[/math] und [math]\begin{pmatrix} q_1 & q_2 & q_3 & \dots & q_l \end{pmatrix}[/math] disjunkt, wenn [math]p_i\neq q_j[/math] für alle [math]i[/math] und [math]j[/math] 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 [math]S_n[/math], die alternierende Gruppe [math]A_n[/math].
  • Auch die beiden Elemente [math]\begin{pmatrix} 1 & 2 \end{pmatrix}[/math] und [math]\begin{pmatrix} 1 & 2 & \dots & n\end{pmatrix}[/math] erzeugen die symmetrische Gruppe [math]S_n[/math].[1] Allgemeiner kann auch ein beliebiger [math]n[/math]-Zyklus zusammen mit einer beliebigen Transposition zweier aufeinanderfolgender Elemente in diesem Zyklus gewählt werden.
  • Falls [math]n\neq 4[/math] lässt sich zu einem beliebigen Element (nicht die Identität) ein Zweites derart wählen, dass beide Elemente die [math]S_n[/math] erzeugen.[2]

Konjugationsklassen

Zwei Elemente der symmetrischen Gruppe sind genau dann zueinander konjugiert, wenn sie in der Darstellung als Produkt disjunkter Zyklen denselben Zykeltyp aufweisen, das heißt, wenn die Anzahl der Einer-, Zweier-, Dreier- usw. -Zyklen übereinstimmen. In dieser Darstellung bedeutet die Konjugation eine Umnummerierung der Zahlen, die in den Zykeln stehen.

Jede Konjugationsklasse der [math]S_n[/math] entspricht daher umkehrbar eindeutig einer Zahlpartition von [math]n[/math] und die Anzahl ihrer Konjugationsklassen ist gleich dem Wert der Partitionsfunktion an der Stelle [math]n,\, P(n).[/math]

Zum Beispiel liegen die Elemente [math]\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[/math] in der Konjugationsklasse die der Zahlpartition [math]7=3+2+1+1[/math] von 7 zugeordnet ist und die [math]S_7[/math] hat [math]P(7)=15[/math] verschiedene Konjugationsklassen.

Normalteiler

Die symmetrische Gruppe [math]S_n[/math] besitzt außer den trivialen Normalteilern [math]\{id\}[/math] und [math]S_n[/math] nur die alternierende Gruppe [math]A_n[/math] als Normalteiler, für [math]n = 4[/math] zusätzlich noch die Kleinsche Vierergruppe [math]V[/math].

Satz von Cayley

Nach dem Satz von Cayley ist jede endliche Gruppe [math]G[/math] zu einer Untergruppe der symmetrischen Gruppe [math]S_n[/math] isomorph, wobei [math]n[/math] nicht größer als die Ordnung von [math]G[/math] ist.

Rechenbeispiele

Die Verkettung zweier Permutationen [math]p_1[/math] und [math]p_2[/math] wird als [math]p_2 \circ p_1[/math] geschrieben: zuerst wird die Permutation [math]p_1[/math] ausgeführt, dann wird auf das Ergebnis die Permutation [math]p_2[/math] angewandt (die Operationen sind von rechts nach links zu lesen).

Beispiel:

[math] \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4\end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2\end{pmatrix}. [/math]

In Zyklenschreibweise lautet dies:

[math] \begin{pmatrix} 1 & 2 & 3 \end{pmatrix}\circ \begin{pmatrix} 1 & 3 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 4 \end{pmatrix}. [/math]

Zunächst bildet die „rechte“ Permutation die 4 auf die 1 ab, anschließend bildet die „linke“ Permutation die 1 auf die 2 ab; die gesamte Verkettung bildet also die 4 auf die 2 ab.

Für [math]n \gt 2[/math] ist die symmetrische Gruppe [math]S_n[/math] nicht abelsch, wie man an folgender Rechnung sieht:

[math] \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 [/math]
[math]\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} [/math]

Siehe auch

Einzelnachweise

  1. Vgl. Seite 2 oben in (PDF-Datei (Memento vom 16. Dezember 2011 im Internet Archive))
  2. I. M. Isaacs and Thilo Zieschang, “Generating Symmetric Groups,” The American Mathematical Monthly 102, no. 8 (October 1995): 734-739.

Kategorien: Permutationstheorie | Endliche Gruppe

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Symmetrische Gruppe (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.