Benutzer:SuperAle/Statistik und Permutationsgruppe: Unterschied zwischen den Seiten

In der Gruppentheorie bezeichnet man eine Gruppe von Permutationen einer endlichen Menge M mit der Hintereinanderausführung als Gruppenverknüpfung als Permutationsgruppe. Die Gruppe aller Permutationen von M nennt man ihre symmetrische Gruppe $S(M)$. Die Permutationsgruppen sind somit genau die Untergruppen der symmetrischen Gruppen.

Nach dem Satz von Cayley ist jede endliche Gruppe zu einer Untergruppe der symmetrischen Gruppe, also zu einer Permutationsgruppe isomorph. Insofern „ist“ jede endliche Gruppe eine Permutationsgruppe. Sieht man die endliche Gruppe G als abstrakte algebraische Struktur an, dann sagt man daher genauer: G operiert als Permutationsgruppe auf der Menge M. Damit wird deutlich, dass es sich bei dieser treuen Permutationsdarstellung um eine eindeutige Beschreibung der Gruppenstruktur handelt, neben der auch andere Beschreibungen möglich sind.

Definitionen

Definition durch eine Gruppenoperation

Sei $(G,\cdot )$ eine Gruppe mit dem neutralen Element e. G operiert genau dann als Permutationsgruppe auf M, wenn gilt:

1. M ist eine endliche Menge.
2. G operiert auf M, das bedeutet, dass eine Abbildung $G\times M\rightarrow M,(g,m)\mapsto g\circ m\in M$ existiert, die den Regeln $e\circ m=m,(g\cdot h)\circ m=g\circ (h\circ m)$ für alle $m\in M;\;g,h\in G$ gehorcht.
3. Die Operation $\circ$ ist treu (engl.: faithful), das heißt, es gilt: Ist $g\circ m=h\circ m$ für alle $m\in M$, dann folgt $g=h$. Oder es gilt gleichwertig: $g\circ m=m$ für alle $m\in M$, dann folgt $g=e$.

Eine Gruppenoperation, die nur die 2. und 3. Bedingung erfüllt, heißt treu. G operiert also genau dann als Permutationsgruppe auf M, wenn die Operation treu und M endlich ist. Ein Gruppenoperation, die nur die 1. und 2. Bedingung erfüllt, wird als Permutationsdarstellung (engl.: permutation representation) von G bezeichnet. G operiert also genau dann als Permutationsgruppe auf M, wenn die Gruppenoperation eine treue Permutationsdarstellung ist.

Definition durch einen Gruppenhomomorphismus

Gleichwertige Beschreibung: G operiert genau dann als Permutationsgruppe auf M, falls M eine endliche Menge ist und ein injektiver Gruppenhomomorphismus $\phi :G\rightarrow S(M)$ existiert. Dabei ist $S(M)=\{\alpha \in M^{M}:\;\alpha \;{\text{ist bijektiv}}\}$, also die Menge aller bijektiven Selbstabbildungen der Menge M. Bei dieser Beschreibung ist die Operation $\circ$ aus der ersten Definition durch $g\circ m=(\phi (g))(m)$ gegeben, die Forderung der Injektivität ist gleichwertig zur Forderung, dass die Operation treu sei.

Man beachte, dass bei den hier genannten Definitionen für eine Permutationsgruppe nicht gesondert gefordert werden muss, dass die Gruppe G endlich sei; dies ergibt sich aus der Endlichkeit von M.

Isomorphie als Permutationsgruppen

Für zwei Gruppen G und H, die auf zwei endlichen Mengen M bzw. N als Permutationsgruppen operieren, wird eine Verschärfung des Isomorphiebegriffs definiert: G und H heißen isomorph als Permutationsgruppen genau dann, wenn ein Gruppenisomorphismus $\sigma :G\rightarrow H$ und eine Bijektion $\psi :M\rightarrow N$ existiert, so dass $\psi (g\circ m)=(\sigma (g))\circ \psi (m)$ für alle $g\in G,m\in M$ gilt. Man kann zeigen, dass zwei Gruppen G und H, die auf derselben Menge $M=N=\{1,2,\ldots ,n\}$ treu operieren, genau dann als Permutationsgruppen isomorph sind, wenn ihre durch die Gruppenoperationen bestimmten Bildgruppen $\phi _{1}(G),\phi _{2}(H)<S_{n}$ in der symmetrischen Gruppe $S_{n}$ konjugierte Untergruppen sind, das heißt, wenn sie durch Konjugation mit einem festen Gruppenelement aufeinander abgebildet werden können.

Semiregulär und regulär

• Wenn G auf M als Permutationsgruppe operiert, wird diese Operation genau dann semiregulär und G semireguläre Permutationsgruppe genannt, wenn das einzige Element von G, das irgendein Element von M fixiert, das Einselement von G ist. Formal: $\left(\exists m\in M:g\circ m=m\right)\Rightarrow g=e.$

• Die Operation heißt genau dann regulär und man nennt G genau dann eine reguläre Permutationsgruppe auf M, wenn die Operation semiregulär und transitiv ist. Die Operation heißt transitiv, wenn jedes Element von M durch die Operation auf jedes beliebige andere Element von M abgebildet werden kann. Formal: $\forall m,n\in M\exists g\in G:g\circ m=n.$ Siehe zu weiteren möglichen Transitivitätseigenschaften einer Permutationsgruppe Gruppenoperation#Transitive Gruppenoperation.

Eigenschaften

Die in diesem Abschnitt beschriebenen Eigenschaften finden sich in dem Lehrbuch Design Theory, das in der Literatur genannt ist, triviale Eigenschaften werden hier oder im Abschnitt Beispiele und Gegenbeispiele in diesem Artikel demonstriert.

• Jede endliche Gruppe lässt eine Darstellung als reguläre Permutationsgruppe zu. Eine solche Darstellung ist durch die „Linksmultiplikation“ der Gruppe auf sich gegeben, siehe bei den Beispielen.
• Für jede endliche Gruppe kann auf jeder beliebigen endlichen Menge M eine Permutationsdarstellung als Gruppenoperation erklärt werden, man wähle etwa die triviale Operation $\circ :G\times M\rightarrow M:g\circ m:=m$. Eine treue Permutationsdarstellung erfordert jedoch eine von der Gruppenordnung abhängige Mindestanzahl m an Elementen. Dann existiert für jede natürliche Zahl n, die nicht kleiner als m ist, eine treue Permutationsdarstellung auf jeder Menge mit n Elementen.

• Nur für die triviale Einsgruppe $\{e\}$ ist $m=1$.
• Enthält die Gruppe G ein Element der Ordnung $p^{r}$, wobei $p^{r}$ eine Primzahlpotenz ist, dann ist $m\geq p^{r}$.
• Speziell gilt dann nach den [Sylow-Sätzen]]: Teilt die Primzahl p die Gruppenordnung, dann ist $m\geq p$.

• Sei G eine Gruppe, $H<G$ eine Untergruppe. Wenn G auf M als Permutationsgruppe operiert, dann operiert auch H über die auf diese Untergruppe eingeschränkte Operation als Permutationsgruppe auf M.

• Ist die Operation von H transitiv, dann ist es auch die von G, umgekehrt kann die Operation von G transitiv sein, die eingeschränkte von H aber nicht.
• Ist dagegen die Operation von G semiregulär, dann ist es ebenso die von H, auch hier muss die Umkehrung nicht gelten.

Beispiele und Gegenbeispiele

• Jede endliche Gruppe $(G,\cdot )$ operiert auf sich selbst $(M=G)$ durch die Linksmultiplikation $G\times M\rightarrow M:g\circ m:=g\cdot m$. Diese Operation ist treu und semiregulär (wegen der Kürzungsregel für Gruppen) und transitiv, also operiert jede endliche Gruppe via Linksmultiplikation als reguläre Permutationsgruppe auf der Menge ihrer Elemente und ist damit isomorph zu einer transitiven Untergruppe der symmetrischen Gruppe $S_{n}$, wenn G n Elemente enthält. Die Rechtsmultiplikation führt im Allgemeinen zu einer anderen Einbettung der Gruppe in $S_{n}$, außerdem muss dafür die Gruppenverknüpfung umgekehrt werden: $G\times M\rightarrow M:g\circ m:=m\cdot g$, $G^{\mathrm {op} }:h\cdot ^{\mathrm {op} }g:=g\cdot h,(g,h\in G)$, damit die Rechtsmultiplikation den oben genannten Regeln (2.) für eine Operation von links genügt oder die Regeln müssen für eine Operation von rechts sinngemäß umformuliert werden.

• Die zyklische Restklassengruppe $(\mathbb {Z} /n\mathbb {Z} ,+),n\geq 2$ operiert regulär durch die Linksaddition $g\circ m:=g+m$ auf sich selbst.

• Die symmetrische Gruppe $S_{n}$ mit n Elementen operiert in ihrer Ausgangsdarstellung auf $M=\{1,2,..n\}$ treu und transitiv, aber nur für $n\leq 2$ semiregulär. Auf sich selbst operiert sie aber mit der Linksmultiplikation als reguläre Permutationsgruppe.
• Eine endliche Gruppe G operiert auf sich selbst auch durch Konjugation $g\circ m:=g\cdot m\cdot g^{-1}$. Diese Operation ist aber im Allgemeinen nicht treu. Jede endliche, nichtkommutative, einfache Gruppe operiert jedoch via Konjugation als Permutationsgruppe (also treu) auf sich selbst.
• Die lineare Gruppe $G=\mathrm {GL} (n,q)$ ($n\geq 2,q=p^{r}>1$ Primzahlpotenz) operiert als Permutationsgruppe auf $M=(\mathbb {F} _{q})^{n}$. M ist die endliche Menge der Vektoren in dem n-dimensionalen Vektorraum über dem endlichen Körper $\mathbb {F} _{q}$ mit q Elementen. Die Operation ist transitiv auf $N=M\setminus \{0\}$, aber im Allgemeinen nicht semiregulär.

• Ist $M<(\mathbb {F} _{q})^{n}$ ein echter linearer Teilraum von $(\mathbb {F} _{q})^{n},q,n>1$ und $H<G=\mathrm {GL} (n,q)$ die Untergruppe, die M als Ganzes auf sich selbst abbildet, dann operiert H transitiv, aber nicht als Permutationsgruppe auf $N=M\setminus \{0\}$, denn die Operation ist nicht treu. Dagegen operiert die Faktorgruppe $H/U$, wobei $U=\{u\in H:\forall m\in M:u(m)=m\}$ die Untergruppe von G und U ist, die jedes einzelne Element von N fixiert, in natürlicher Weise transitiv als Permutationsgruppe auf $N$.
• Für einen unendlichen Körper K (zum Beispiel $K=\mathbb {R}$) operiert $\mathrm {GL} (n,K),(n\geq 2)$ zwar treu und transitiv, aber nicht als Permutationsgruppe auf $N=K^{n}\setminus \{0\}$, denn N ist nicht endlich.

• Sei $V_{4}=\{e,(12)(34),(13)(24),(14)(23)\}$ die Kleinsche Vierergruppe als Untergruppe der symmetrischen Gruppe $S_{4}$. $V_{4}$ operiert als reguläre Permutationsgruppe auf $M=\{1,2,3,4\}$.

• Die Gruppe $S_{4}$ enthält 3 weitere, zu $V_{4}$ isomorphe Untergruppen, z.B. $U=\{e,(13),(24),(13)(24)\}$. Da $V_{4}$, wie hier definiert, transitiv auf M operiert, U dagegen nicht (die Bahn von 1 enthält bei der Operation von U nur zwei Elemente), sind die beiden Untergruppen nicht als Permutationsgruppen auf M isomorph. Dagegen ist U zu den anderen beiden (von $V_{4}$ verschiedenen!) Gruppen, die von zwei disjunkten Transpositionen erzeugt werden, isomorph als Permutationsgruppe.

• Die zyklische Gruppe mit 6 Elementen $G\cong C_{6}\cong C_{2}\times C_{3}$ operiert als reguläre Permutationsgruppe via Linksmultiplikation auf sich selbst, das entspricht ihrer üblichen Permutationsdarstellung $G\cong <\xi =(123456)>$ auf $M=\{1,2,3,4,5,6\}$. Sie operiert aber auch als Permutationsgruppe $G\cong <(12)(345)>$ auf der Menge $N=\{1,2,3,4,5\}>$, hier aber nicht transitiv und nicht semiregulär. Die Zahl $m=5$ ist für diese Gruppe die Mindestmächtigkeit für eine Menge, auf der G als Permutationsgruppe operiert. Die eingeschränkte Operation von $H\cong <\xi ^{3}=(14)(25)(36)>$ ist semiregulär, aber nicht transitiv.

Endliche Symmetriegruppen

In der Geometrie treten viele Gruppen auf, die dadurch definiert sind, dass sie eine geometrische Figur als Ganzes auf sich abbilden. Zum Beispiel ist die Gruppe der Bewegungen des dreidimensionalen Anschauungsraums, die den Einheitswürfel (aufgespannt von den drei Standardbasisvektoren) als Ganzes auf sich abbilden, eine typische Symmetriegruppe.

• Die Symmetriegruppe eines (nichtentarteten) Polyeders im Anschauungsraum operiert als Permutationsgruppe auf der (endlichen!) Menge der Eckpunkte des Polyeders.
• Die Symmetriegruppe G einer Kugel im Anschauungsraum operiert transitiv auf der Menge M der Punkte auf der Kugeloberfläche, aber auf keiner Menge $N\subseteq M$ als Permutationsgruppe: Weil die Operation auf M transitiv ist, lässt sie sich nicht für die ganze Symmetriegruppe G auf eine endliche Punktmenge N beschränken. Dagegen kann die Symmetriegruppe des Einheitswürfels als Untergruppe von G aufgefasst werden, wenn man als Kugel die dem Würfel umbeschriebene Kugel wählt, also die Kugel durch alle Eckpunkte des Würfels.
• Die Symmetriegruppe eines gleichseitigen Dreiecks in der reellen Ebene operiert als transitive Permutationsgruppe, aber nicht semiregulär auf der Menge der Eckpunkte des Dreiecks.
• Allgemeiner operiert die Symmetriegruppe G eines regelmäßigen n-Ecks $n\geq 3$ in der Ebene als transitive, nicht semireguläre Permutationsgruppe auf der Menge $\{1,2,\ldots n\}$ der Eckpunkte des n-Ecks. Diese Beschreibung kann für $n\geq 3$ als Definition der Diedergruppe $G=D_{n}$ (als Untergruppe der symmetrischen Gruppe $S_{n}$) benutzt werden.
• Die Symmetriegruppe einer Strecke auf der reellen Geraden (also eines reellen Intervalls $[a,b],a<b$) operiert als reguläre Permutationsgruppe auf deren Randpunkten. Sie ist die zweielementige Gruppe $\{e,s\}$, wobei s die Spiegelung der Geraden an der Intervallmitte $(a+b)/2$ ist.
• Dagegen operiert die Symmetriegruppe H (im oben beschrieben Sinn) einer Strecke im dreidimensionalen Raum nicht treu und daher nicht als Permutationsgruppe auf den Randpunkten der Strecke. Diese Gruppe ist sogar unendlich – man beachte die Drehungen, bei denen die Strecke auf der Achse liegt! Wie in dem Beispiel eines linearen Unterraums in einem endlichen Vektorraum weiter oben muss man zu der Faktorgruppe $H/U$ nach der Untergruppe U der Bewegungen, die jeden Punkt der Strecke auf sich abbilden, übergehen. Damit gelangt man wieder zu einer Gruppe, die zu der im vorigen Beispiel genannten Gruppe isomorph ist. Oft wird diese kanonische Faktorgruppe dann als die Symmetriegruppe (hier: der Strecke) bezeichnet.

Automorphismengruppen endlicher Strukturen

Die strukturerhaltenden, bijektiven Selbstabbildungen endlicher Strukturen, zum Beispiel der endlichen Inzidenzstrukturen, wie der Blockpläne, der endlichen projektiven Ebenen usw. operieren als Permutationsgruppen auf der endlichen Menge M der „Elemente“ der Struktur (für Inzidenzstrukturen $M={\mathfrak {p}}\cup {\mathfrak {B}}$, also die Menge der „Punkte“ zusammen mit der Menge der „Blöcke“). In den wichtigen Fällen, etwa für alle einfachen Blockpläne (also auch für alle „klassischen“ endlichen Geometrien), genügt es, als Menge die Punkt- oder die Blockmenge zu verwenden, da die Automorphismengruppen bereits auf wenigstens einer dieser Mengen treu operiert. Meist wird die Punktmenge verwendet. Die Gruppe aller strukturerhaltenden, bijektiven Selbstabbildungen der Struktur ${\mathcal {I}}$ wird als volle Automorphismengruppe $\mathrm {Aut} ({\mathcal {I}})$ der Struktur, jede ihrer Untergruppen als Automorphismengruppe bezeichnet. Nach Konstruktion operieren diese Gruppen als Permutationsgruppen auf der Menge der Strukturelemente, in den angesprochenen wichtigsten Fällen bereits auf der Punktmenge.

• Die endliche einfache Gruppe $\mathrm {PGL} (3,2)$ operiert als Permutations- und volle Automorhismengruppe transitiv, aber nicht regulär auf der projektiven Fano-Ebene $PG(2,2)$, d.h. konkret auf der Menge ihrer 7 Punkte. Im Artikel Fano-Ebene ist die Struktur dieser Gruppe und die hier beschriebene treue Permutationsdarstellung als Untergruppe der alternierenden Gruppe $A_{7}$ ausführlich dargestellt.
• Die 5 sporadischen Mathieugruppen operieren als Permutations- und volle Automorhismengruppen auf jeweils einem ihnen zugeordneten Wittschen Blockplan - auch hier genügt die Punktmenge für die eindeutige Beschreibung.
• Ein etwas gekünsteltes Beispiel einer Inzidenzstruktur, bei der die volle Automorphismengruppe weder auf der Punkt- noch auf der Blockmenge allein als Permutationsgruppe operiert, ist ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)$ mit den Mengen ${\mathfrak {p}}=\{p_{1},p_{2}\},\;{\mathfrak {B}}=\{B_{1},B_{2}\},\;I=\emptyset ,\;{\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)$. Hier ist die Automorphismengruppe das Erzeugnis $G=\mathrm {Aut} ({\mathcal {I}})=<(p_{1}p_{2}),(B_{1}B_{2})>$, also ist G isomorph zur Kleinschen Vierergruppe $G\cong C_{2}\times C_{2}$. Aber G operiert weder auf der Punkt- noch auf der Blockmenge treu! Die gleichen Aussagen gelten, wenn man für diese Punkt- und Blockmenge die Inzidenz statt durch $I=\emptyset$ durch $I'={\mathfrak {p}}\times {\mathfrak {B}}$ definiert.

Siehe auch

• Die Zyklenstruktur einer Permutationsgruppe wird durch den Zyklenzeiger zusammengefasst.
• Andere eindeutige Beschreibungen einer endlichen Gruppe sind die Verknüpfungstafel oder die Darstellung durch Erzeugende und Relationen, mit letzterer können nicht nur endliche sondern allgemeiner endlich erzeugbare Gruppen beschrieben werden.

→ Siehe für weitere Möglichkeiten, eine endliche Gruppe zu beschreiben, den Artikel Darstellungstheorie (Gruppentheorie)

Literatur

• Michael Artin: Algebra. Birkhäuser, Basel u. a. 1993, ISBN 3-7643-2927-0, Kapitel 1(?!). 
• Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. 2. Auflage. B.I. Wissenschaftsverlag, London/New York/New Rochelle/Melbourne/Sidney 1999, ISBN 0-521-33334-2. 
• Günther Eisenreich: Lexikon der Algebra. Akademie-Verlag, Berlin 1989, ISBN 3-05-500231-8. 
• Thomas W. Hungerford: Algebra. 5. Auflage. Springer, Berlin/Heidelberg/New York 1989, ISBN 0-387-90518-9, Kapitel I Groups. 

Weblinks

• Eric W. Weisstein: Permutation Group. In: MathWorld (englisch).