Kurs:Körper- und Galoistheorie (Osnabrück 2011)/Permutationsgruppen/Textabschnitt

Permutationsgruppen

Definition

Zu einer Menge $M$ nennt man die Menge

$\mathrm{Aut}(M)=\mathrm{Perm}(M)=\{\phi :M⟶M\mid \phi \text{ bijektiv}\}$

der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu $M$.

Eine bijektive Selbstabbildung $\phi :M\to M$ nennt man auch eine Permutation. Für eine endliche Menge $I=\{1,\dots ,n\}$ schreibt man $S_n=\mathrm{Perm}(I)$. Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.

Lemma

Es sei $M$ eine endliche Menge mit $n$ Elementen.

Dann besitzt die Permutationsgruppe  $\mathrm{Perm}(M)\cong S_n$  genau $n!$ Elemente.

Beweis

Es sei  $M=\{1,\dots ,n\}$.  Für die $1$ gibt es $n$ mögliche Bilder, für $2$ gibt es noch $n-1$ mögliche Bilder, für $3$ gibt es noch $n-2$ mögliche Bilder, usw. Daher gibt es insgesamt

$n(n-1)(n-2)\cdots 2\cdot 1=n!$

mögliche Permutationen.

$◻$

Lemma

Es sei $M$ eine Menge und $N\subseteq M$ eine Teilmenge.

Dann gibt es eine natürliche injektive Abbildung

$\mathrm{Perm}(N)⟶\mathrm{Perm}(M),\sigma ⟼\tilde{\sigma },$

wobei $\tilde{\sigma }$ auf $N$ gleich $\sigma$ und auf $M\setminus N$ die Identität ist.

Mittels dieser Abbildung ist $\mathrm{Perm}(N)$ eine Untergruppe von $\mathrm{Perm}(M)$.

Beweis

Offenbar ist die Abbildung wohldefiniert. Sie ist injektiv, da aus  $\tilde{\sigma }=\tilde{\tau }$  sofort folgt, dass  $\sigma =\tau$  ist. Die Abbildung liefert eine Bijektion zwischen $\mathrm{Perm}(N)$ und der Menge der Permutationen auf $M$, die $M\setminus N$ fest lassen. Diese Permutationen bilden eine Untergruppe.

$◻$

Zyklendarstellung für Permutationen

Sei $M$ eine endliche Menge, $\sigma \in \mathrm{Perm}(M)$ eine Permutation und  $x\in M$.  Dann kann man die Folge

${\sigma }^0(x)=\mathrm{id}(x)=x,{\sigma }^1(x)=\sigma (x),{\sigma }^2(x),{\sigma }^3(x)\dots ,$

betrachten. Da $M$ endlich ist, gibt es eine Wiederholung ${\sigma }^i(x)={\sigma }^j(x)$ mit $i<j$. Durch Multiplikation mit ${\sigma }^{-i}$ sieht man, dass es ein minimales $k\in {\mathbb{N}}_{+}$ gibt mit ${\sigma }^k(x)={\sigma }^0(x)=x$, und dass alle ${\sigma }^j(x)$ für $j$, $1\le j<k$, verschieden sind. Ist $y={\sigma }^j(x)$, so durchläuft auch ${\sigma }^i(y)$ dieselbe Teilmenge aus $M$.

Definition

Es sei $M$ eine endliche Menge und $\pi$ eine Permutation auf $M$. Man nennt $\pi$ einen Zyklus der Ordnung $r$ (oder der Länge $r$), wenn es eine $r$-elementige Teilmenge  $Z\subseteq M$  derart gibt, dass $\pi$ auf $M\setminus Z$ die Identität ist und $\pi$ die Elemente aus $Z$ zyklisch vertauscht. Wenn  $Z=\{z,\pi (z),{\pi }^2(z),\dots ,{\pi }^{r-1}(z)\}$  ist, so schreibt man einfach

$\pi =⟨z,\pi (z),{\pi }^2(z),\dots ,{\pi }^{r-1}(z)⟩.$

Dabei kann man statt $z$ jedes andere Element aus $Z$ als Anfangsglied nehmen. Die Menge $Z$ heißt auch der Wirkungsbereich des Zyklus, und die (geordnete) Auflistung heißt die Wirkungsfolge des Zyklus.

Definition

Eine Transposition auf einer endlichen Menge $M$ ist eine Permutation auf $M$, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.

Eine Transposition ist also ein besonders einfacher Zyklus mit der Zyklendarstellung $⟨x,y⟩$, wenn die Transposition die Punkte $x$ und $y$ vertauscht.

Lemma

Jede Permutation auf einer endlichen Menge $M$

kann man als Produkt von Transpositionen schreiben.

Beweis

Wir beweisen die Aussage durch Induktion über die Anzahl der Menge $M$. Für  $\mathrm{\#}\left(M\right)=1$  ist nichts zu zeigen, sei also  $\mathrm{\#}\left(M\right)\ge 2$.  Die Identität ist das leere Produkt aus Transpositionen. Es sei also $\pi$ nicht die Identität, und sei  $\pi (x)=y\ne x$.  Es sei $\tau$ die Transposition, die $x$ und $y$ vertauscht. Dann ist $y$ ein Fixpunkt von $\pi \tau$, und man kann $\pi \tau$ auffassen als eine Permutation auf  $M^{\prime }=M\setminus \{y\}$.  Nach Induktionsvoraussetzung gibt es dann Transpositionen ${\tau }_j$ auf $M^{\prime }$ mit  $\pi \tau =\prod _j{\tau }_j$  auf $M^{\prime }$. Dies gilt dann auch auf $M$, und daher ist  $\pi =\left(\prod _j{\tau }_j\right)\tau$. 

$◻$

Satz

Es sei $M$ eine endliche Menge und $\sigma$ eine Permutation auf $M$.

Dann gibt es eine Darstellung

$\sigma ={\sigma }_1\cdots {\sigma }_k,$

wobei die ${\sigma }_i$ Zyklen der Ordnung $\ge 2$ sind mit disjunkten Wirkungsbereichen.

Dabei ist die Darstellung bis auf die Reihenfolge eindeutig.

Beweis

Es sei $F$ die Fixpunktmenge von $\sigma$ und es seien $Z_1,\dots ,Z_k$ diejenigen Teilmengen von $M$ mit mindestens zwei Elementen derart, dass $\sigma$ die Elemente aus jedem $Z_i$ zyklisch vertauscht. Dann ist $M$ die disjunkte Vereinigung aus $F$ und den $Z_i$. Zu $i$, $1\le i\le k$, sei ${\sigma }_i$ der Zyklus auf $M$, der auf $M\setminus Z_i$ die Identität ist und auf $Z_i$ mit $\sigma$ übereinstimmt. Wir behaupten

$\sigma ={\sigma }_1\cdots {\sigma }_k.$

Um dies einzusehen, sei  $x\in M$  beliebig. Bei  $x\in F$  ist $x$ ein Fixpunkt für alle ${\sigma }_i$ und daher kommt links und rechts wieder $x$ raus. Es sei also $x$ kein Fixpunkt der Permutation. Dann gehört  $x\in Z_i$  für genau ein $i$. Für alle $j\ne i$ ist $x$ ein Fixpunkt von ${\sigma }_j$. Da

$y=\sigma (x)$

ebenfalls zu $Z_i$ gehört, ist auch $y$ ein Fixpunkt von ${\sigma }_j$ für alle  $j\ne i$.  Wendet man daher die rechte Seite auf $x$ an, so wird $x$ auf $x$ abgebildet bis man zu ${\sigma }_i$ kommt. Dieses bildet $x$ auf $y$ ab und die folgenden ${\sigma }_j$ bilden $y$ auf $y$ ab, sodass die rechte Seite insgesamt $x$ auf $y$ schickt und daher mit $\sigma$ übereinstimmt.

$◻$

Aufgrund von diesem Satz können wir allgemein eine Zyklendarstellung für eine beliebige Permutation definieren.

Definition

Es sei $M$ eine endliche Menge und $\sigma$ eine Permutation auf $M$. Es seien $Z_1,\dots ,Z_k$ die Wirkungsbereiche der Zyklen von $\sigma$ mit  $n_i=\mathrm{\#}\left(Z_i\right)$.  Es sei  $x_i\in Z_i$  und  $Z_i=\{x_i,\sigma (x_i),\dots ,{\sigma }^{n_i-1}(x_i)\}$.  Dann nennt man

$⟨x_1,\sigma (x_1),\dots ,{\sigma }^{n_1-1}(x_1)⟩⟨x_2,\sigma (x_2),\dots ,{\sigma }^{n_2-1}(x_2)⟩\cdots ⟨x_k,\sigma (x_k),\dots ,{\sigma }^{n_k-1}(x_k)⟩$

die Zyklendarstellung von $\sigma$.

Das Signum einer Permutation

Definition

Es sei  $M=\{1,\dots ,n\}$  und sei $\pi$ eine Permutation auf $M$. Dann heißt die Zahl

$\mathrm{sgn}(\pi )=\prod _{i<j}\frac{\pi (j)-\pi (i)}{j-i}$

das Signum (oder das Vorzeichen) der Permutation $\pi$.

Das Signum ist $1$ oder $-1$, da im Zähler und im Nenner die positive oder die negative Differenz $\pm (i-j)$ steht. Es gibt für das Signum also nur zwei mögliche Werte. Bei $\mathrm{sgn}(\sigma )=1$ spricht man von einer geraden Permutation und bei $\mathrm{sgn}(\sigma )=-1$ von einer ungeraden Permutation.

Definition

Es sei  $M=\{1,\dots ,n\}$  und sei $\pi$ eine Permutation auf $M$. Dann heißt ein Indexpaar

$i<j$

ein Fehlstand von $\pi$, wenn  $\pi (i)>\pi (j)$  ist.

Lemma

Es sei  $M=\{1,\dots ,n\}$  und sei $\pi$ eine Permutation auf $M$. Es sei  $k=\mathrm{\#}\left(F\right)$  die Anzahl der Fehlstände von $\pi$.

Dann ist das Signum von $\pi$ gleich

$\mathrm{sgn}(\pi )=(-1{)}^k.$

Beweis

Wir schreiben

$\begin{array}{cc}\mathrm{sgn}(\pi )& =\prod _{i<j}\frac{\pi (j)-\pi (i)}{j-i}\\ & =\prod _{(i,j)\in F}\frac{\pi (j)-\pi (i)}{j-i}\prod _{(i,j)\in ̸F}\frac{\pi (j)-\pi (i)}{j-i}\\ & =(-1{)}^k\prod _{(i,j)\in F}\frac{\pi (i)-\pi (j)}{j-i}\prod _{(i,j)\in ̸F}\frac{\pi (j)-\pi (i)}{j-i}\\ & =(-1{)}^k,\end{array}$

da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.

$◻$

Beispiel

Wir betrachten die Permutation

$x$	$1$	$2$	$3$	$4$	$5$	$6$
$\sigma (x)$	$2$	$4$	$6$	$5$	$3$	$1$

mit der Zyklendarstellung

$⟨1,2,4,5,3,6⟩.$

Die Fehlstände sind

$(1,6),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6),$

es gibt also $9$ Stück davon. Das Signum ist also  $(-1{)}^9=-1$  gemäß Lemma 18.10 (Lineare Algebra (Osnabrück 2024-2025)), und die Permutation ist ungerade.

Satz

Die durch das Signum gegebene Zuordnung

$S_n⟶\{1,-1\},\pi ⟼\mathrm{sgn}(\pi ),$

ist ein Gruppenhomomorphismus.

Beweis

Es seien zwei Permutationen $\pi$ und $\rho$ gegeben. Dann ist

$\begin{array}{cc}\mathrm{sgn}(\pi \circ \rho )& =\prod _{i<j}\frac{(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{j-i}\\ & =\left(\prod _{i<j}\frac{(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{\rho (j)-\rho (i)}\right)\prod _{i<j}\frac{\rho (j)-\rho (i)}{j-i}\\ & =\left(\prod _{i<j,\rho (i)<\rho (j)}\frac{\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}\right)\left(\prod _{i<j,\rho (i)>\rho (j)}\frac{\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}\right)\mathrm{sgn}(\rho )\\ & =\left(\prod _{i<j,\rho (i)<\rho (j)}\frac{\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}\right)\left(\prod _{i<j,\rho (i)>\rho (j)}\frac{\pi (\rho (i))-\pi (\rho (j))}{\rho (i)-\rho (j)}\right)\mathrm{sgn}(\rho )\\ & =\prod _{k<\ell }\frac{\pi (\ell )-\pi (k)}{\ell -k}\mathrm{sgn}(\rho )\\ & =\mathrm{sgn}(\pi )\mathrm{sgn}(\rho ).\end{array}$

$◻$

Lemma

Es sei  $M=\{1,\dots ,n\}$  und sei $\pi$ eine Permutation auf $M$. Es sei

$\pi ={\tau }_1\cdots {\tau }_r$

als ein Produkt von $r$ Transpositionen geschrieben.

Dann gilt für das Signum die Darstellung

$\mathrm{sgn}(\pi )=(-1{)}^r.$

Beweis

Dies folgt aus Lemma 18.14 (Lineare Algebra (Osnabrück 2024-2025)) und Satz 18.13 (Lineare Algebra (Osnabrück 2024-2025)).

$◻$

Pdf-Version