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

Permutationsgruppen

Definition Referenznummer erstellen

Zu einer Menge ${}M$ nennt man die Menge

${}\operatorname {Aut} \,(M)=\operatorname {Perm} \,(M)={\left\{\varphi :M\longrightarrow M\mid \varphi {\text{ bijektiv}}\right\}}\,$

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

Eine bijektive Selbstabbildung ${}\varphi \colon M\rightarrow M$ nennt man auch eine Permutation. Für eine endliche Menge ${}I=\{1,\ldots ,n\}$ schreibt man ${}S_{n}=\operatorname {Perm} \,(I)$. Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.

Lemma Referenznummer erstellen

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

Dann besitzt die Permutationsgruppe ${}\operatorname {Perm} \,(M)\cong S_{n}$ genau ${}n!$ Elemente.

Beweis

Es sei ${}M={\{1,\ldots ,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.

$\Box$

Lemma Referenznummer erstellen

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

Dann gibt es eine natürliche injektive Abbildung

$\operatorname {Perm} \,(N)\longrightarrow \operatorname {Perm} \,(M),\,\sigma \longmapsto {\tilde {\sigma }},$

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

Mittels dieser Abbildung ist ${}\operatorname {Perm} \,(N)$ eine Untergruppe von ${}\operatorname {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 ${}\operatorname {Perm} \,(N)$ und der Menge der Permutationen auf ${}M$, die ${}M\setminus N$ fest lassen. Diese Permutationen bilden eine Untergruppe.

$\Box$

Zykeldarstellung für Permutationen

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

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

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\leq j<k$, verschieden sind. Ist ${}y=\sigma ^{j}(x)$, so durchläuft auch ${}\sigma ^{i}(y)$ dieselbe Teilmenge aus ${}M$.

Definition Referenznummer erstellen

Es sei ${}M$ eine endliche Menge und ${}\pi$ eine Permutation auf ${}M$. Man nennt ${}\pi$ einen Zykel der Ordnung ${}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),\ldots ,\pi ^{r-1}(z)\}$ ist, so schreibt man einfach

${}\pi =\langle z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\rangle \,.$

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

Definition Referenznummer erstellen

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 Zykel mit der Zyklendarstellung ${}\langle x,y\rangle$, wenn die Transposition die Punkte $x$ und $y$ vertauscht.

Lemma Lemma Anhang 3.6 ändern

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 ${}{\#\left(M\right)}=1$ ist nichts zu zeigen, sei also ${}{\#\left(M\right)}\geq 2$. Die Identität ist das leere Produkt aus Transpositionen. Es sei also ${}\pi$ nicht die Identität, und sei ${}\pi (x)=y\neq 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'=M\setminus \{y\}$. Nach Induktionsvoraussetzung gibt es dann Transpositionen ${}\tau _{j}$ auf ${}M'$ mit ${}\pi \tau =\prod _{j}\tau _{j}$ auf ${}M'$. Dies gilt dann auch auf ${}M$, und daher ist ${}\pi ={\left(\prod _{j}\tau _{j}\right)}\tau$.

$\Box$

Satz Referenznummer erstellen

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}$ Zykel der Ordnung ${}\geq 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},\ldots ,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\leq i\leq k$, sei ${}\sigma _{i}$ der Zykel 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\neq 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\neq 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.

$\Box$

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

Definition Referenznummer erstellen

Es sei ${}M$ eine endliche Menge und ${}\sigma$ eine Permutation auf ${}M$. Es seien ${}Z_{1},\ldots ,Z_{k}$ die Wirkungsbereiche der Zyklen von ${}\sigma$ mit ${}n_{i}={\#\left(Z_{i}\right)}$. Es sei ${}x_{i}\in Z_{i}$ und ${}Z_{i}=\{x_{i},\sigma (x_{i}),\ldots ,\sigma ^{n_{i}-1}(x_{i})\}$. Dann nennt man

$\langle x_{1},\sigma (x_{1}),\ldots ,\sigma ^{n_{1}-1}(x_{1})\rangle \langle x_{2},\sigma (x_{2}),\ldots ,\sigma ^{n_{2}-1}(x_{2})\rangle \cdots \langle x_{k},\sigma (x_{k}),\ldots ,\sigma ^{n_{k}-1}(x_{k})\rangle$

die Zyklendarstellung von ${}\sigma$.

Das Signum einer Permutation

Definition Referenznummer erstellen

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

${}\operatorname {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 ${}\operatorname {sgn} (\sigma )=1$ spricht man von einer geraden Permutation und bei ${}\operatorname {sgn} (\sigma )=-1$ von einer ungeraden Permutation.

Definition Referenznummer erstellen

Es sei ${}M={\{1,\ldots ,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 Referenznummer erstellen

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

Dann ist das Signum von ${}\pi$ gleich

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

Beweis

Wir schreiben

${}{\begin{aligned}\operatorname {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)\not \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)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k},\end{aligned}}$

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

$\Box$

Beispiel Referenznummer erstellen

Wir betrachten die Permutation

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

mit der Zyklendarstellung

$\langle 1,2,4,5,3,6\rangle .$

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äß Fakt *****, und die Permutation ist ungerade.

Satz Referenznummer erstellen

Die durch das Signum gegebene Zuordnung

$S_{n}\longrightarrow \{1,-1\},\,\pi \longmapsto \operatorname {sgn} (\pi ),$

ist ein Gruppenhomomorphismus.

Beweis

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

${}{\begin{aligned}\operatorname {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)}\,\operatorname {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)}\,\operatorname {sgn} (\rho )\\&=\prod _{k<\ell }{\frac {\pi (\ell )-\pi (k)}{\ell -k}}\operatorname {sgn} (\rho )\\&=\operatorname {sgn} (\pi )\operatorname {sgn} (\rho ).\end{aligned}}$

$\Box$

Lemma Referenznummer erstellen

Es sei ${}M={\{1,\ldots ,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

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

Beweis

Die Transposition ${}\tau$ vertausche die beiden Zahlen ${}k<\ell$. Dann ist

${}{\begin{aligned}\operatorname {sgn} (\tau )&=\prod _{i<j}{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{i<j,\,i,j\neq k,\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j\neq \ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i\neq k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{j>k,\,j\neq \ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i\neq k,\,i<\ell }{\frac {k-i}{\ell -i}}\cdot {\frac {k-\ell }{\ell -k}}\\&=\prod _{j>\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i<k}{\frac {k-i}{\ell -i}}\cdot \prod _{k<j<\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{k<i<\ell }{\frac {k-i}{\ell -i}}\cdot (-1)\\&=-1.\end{aligned}}$

Die letzte Gleichung ergibt sich daraus, dass im ersten und im zweiten Produkt alle Zähler und Nenner positiv sind und dass im dritten und im vierten Produkt die Zähler negativ und die Nenner positiv sind, sodass sich diese (wegen der gleichen Indexmenge) Minuszeichen wegkürzen.

Die Aussage folgt dann aus der Homomorphieeigenschaft.

$\Box$