Symmetrische Gruppe
(als Multiplikationstafel der Permutationsmatrizen)
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 <math>\circ</math> (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 > 2</math> nichtabelsch.
Der Name der Gruppe wurde deshalb so gewählt, weil die Funktionen der Variablen <math>x_1, x_2, \dotsb, x_n</math>, die bei allen Permutationen invariant bleiben, die symmetrischen Funktionen sind.<ref name="Waerden_1950">{{#invoke:Vorlage:Literatur|f}}</ref>
Mitunter findet man auch die Definition der symmetrischen Gruppe <math>S(M)</math> oder <math>\operatorname{Sym}(M)</math> einer beliebigen nicht-leeren Menge <math>M</math>, bestehend aus allen bijektiven Abbildungen der Menge <math>M</math> in sich, zusammen mit der üblichen Komposition von Abbildungen. Die Gruppe <math>S_n</math> ist dann die symmetrische Gruppe von <math>M=\{1,2,...,n\}</math>.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
Notation von Permutationen
Zweizeilenform
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. In dieser sogenannten Zweizeilenform erhält man die inverse Permutation <math>p^{-1}</math>, indem man die obere und die untere Zeile vertauscht.
Anmerkung: Die Elemente der ersten Zeile dürfen auch in einer anderen Reihenfolge notiert werden.
Zyklenschreibweise
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, denn 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><ref>Vgl. Seite 2 oben in (<templatestyles src="Webarchiv/styles.css" />{{#if:20111216075447
| {{#ifeq: 20111216075447 | *
| {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20111216075447}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20111216075447}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: PDF-Datei | {{#invoke:WLink|getEscapedTitle|PDF-Datei}} | {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20111216075447|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf}}
|| {{#if: || }}
}}{{#if: PDF-Datei
| {{#if: {{#invoke:WLink|isBracketedLink|PDF-Datei}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.math.ethz.ch/~wustholz/vieweg-algebra/algebra_4.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}})</ref> 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.<ref>I. M. Isaacs and Thilo Zieschang, “Generating Symmetric Groups,” The American Mathematical Monthly 102, no. 8 (October 1995): 734-739.</ref>
Konjugationsklassen
Zwei Elemente der symmetrischen Gruppe sind genau dann zueinander konjugiert, wenn sie in der Darstellung als Produkt disjunkter Zyklen denselben Zyklentyp aufweisen, das heißt, wenn die Anzahlen der Einer-, Zweier-, Dreier- usw. -Zyklen übereinstimmen. In dieser Darstellung bedeutet die Konjugation eine Umnummerierung der Zahlen, die in den Zyklen 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 <math>7</math> zugeordnet ist, und <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>.
Die Kommutatorgruppe <math>K(S_n) = [S_n,S_n] = {S_n}'</math> ist ein Normalteiler, und es ist
- <math>K(S_n) = A_n</math>.
Satz von Cayley
Nach dem Satz von Cayley ist jede endliche Gruppe <math>G</math> zu einer Untergruppe einer symmetrischen Gruppe <math>S_n</math> isomorph, deren Grad <math>n</math> nicht größer als die Ordnung von <math>G</math> ist.
Ferner kann <math>S_n</math> unter Anhängen der Transposition <math>(n+1,n+2)</math> an alle ungeraden Permutationen in die alternierende Gruppe <math>A_{n+2}</math> 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 <math>p_2 \circ p_1</math> von zwei Permutationen die zuerst ausgeführte Permutation <math>p_1</math> rechts vom Verkettungszeichen <math>\circ</math> geschrieben. Auf das Ergebnis wird die zweite Permutation <math>p_2</math> angewandt.
Beispiel:
- <math>
\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}. </math> In Zyklenschreibweise lautet dies:
- <math>
\begin{pmatrix} 2 & 4 \end{pmatrix} \circ \begin{pmatrix} 1 & 3 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 3 & 2 & 4 \end{pmatrix}. </math>
Zunächst bildet die „rechte“ Permutation <math> \scriptstyle \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} \, = \, \scriptstyle \begin{pmatrix} 1 & 3 & 4 \end{pmatrix} </math> die <math>1</math> auf die <math>3</math> ab, anschließend bildet die „linke“ Permutation <math> \scriptstyle \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2\end{pmatrix} \, = \, \scriptstyle \begin{pmatrix} 2 & 4 \end{pmatrix} </math> die <math>3</math> auf die <math>3</math> ab; die gesamte Verkettung bildet also die <math>1</math> auf die <math>3</math> ab, wie rechts vom Gleichheitszeichen als <math> \scriptstyle \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1\end{pmatrix} \, = \, \scriptstyle \begin{pmatrix} 1 & 3 & 2 & 4 \end{pmatrix} </math> hingeschrieben.
Für <math>n > 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
<references/>