Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 9

Das Signum einer Permutation

Definition

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

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

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

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

Die durch das Signum gegebene Zuordnung

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

ist ein Gruppenhomomorphismus.

Beweis

Zunächst ist das Signum wirklich gleich ${}1$ oder ${}-1$ . Dies beruht darauf, dass sowohl im Zähler als auch im Nenner der Definition des Signums zu jedem Indexpaar ${}i\leq j$ die positive oder die negative Differenz ${}\pm (i-j)$ vorkommt.

Seien zwei Permutationen ${}\sigma$ und ${}\tau$ gegeben. Dann ist

{}{\begin{aligned}\operatorname {sgn} (\sigma \circ \tau )&=\prod _{i<j}{\frac {(\sigma \circ \tau )(j)-(\sigma \circ \tau )(i)}{j-i}}\\&={\left(\prod _{i<j}{\frac {(\sigma \circ \tau )(j)-(\sigma \circ \tau )(i)}{\tau (j)-\tau (i)}}\right)}\prod _{i<j}{\frac {\tau (j)-\tau (i)}{j-i}}\\&={\left(\prod _{i<j,\,\tau (i)<\tau (j)}{\frac {\sigma (\tau (j))-\sigma (\tau (i))}{\tau (j)-\tau (i)}}\right)}{\left(\prod _{i<j,\,\tau (i)>\tau (j)}{\frac {\sigma (\tau (j))-\sigma (\tau (i))}{\tau (j)-\tau (i)}}\right)}\,\operatorname {sgn} (\tau )\\&={\left(\prod _{i<j,\,\tau (i)<\tau (j)}{\frac {\sigma (\tau (j))-\sigma (\tau (i))}{\tau (j)-\tau (i)}}\right)}{\left(\prod _{i<j,\,\tau (i)>\tau (j)}{\frac {\sigma (\tau (i))-\sigma (\tau (j))}{\tau (i)-\tau (j)}}\right)}\,\operatorname {sgn} (\tau )\\&=\prod _{k<\ell }{\frac {\sigma (\ell )-\sigma (k)}{\ell -k}}\operatorname {sgn} (\tau )\\&=\operatorname {sgn} (\sigma )\operatorname {sgn} (\tau ).\end{aligned}}

\Box

Lemma

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

Bemerkung

Es sei ${}I$ eine beliebige Menge mit ${}n$ Elementen, die nicht geordnet sein muss, und sei ${}\pi$ eine Permutation auf ${}I$ . Dann kann man nicht von Fehlständen sprechen und die Definition des Signums ist nicht direkt anwendbar. Man kann sich jedoch an Lemma 9.12 orientieren, um das Signum auch in dieser leicht allgemeineren Situation zu erklären. Dazu schreibt man ${}\pi$ als Produkt von ${}r$ Transpositionen und definiert

{}\operatorname {sgn} (\pi )={\begin{cases}1\,,{\text{ falls }}r{\text{ gerade ist}}\,,\\-1\,,{\text{ falls }}r{\text{ ungerade ist}}\,.\end{cases}}\,

Um einzusehen, dass dies wohldefiniert ist, betrachtet man eine Bijektion

\varphi \colon I\longrightarrow {\{1,\ldots ,n\}}.

Die Permutation ${}\pi$ auf ${}I$ definiert auf ${}{\{1,\ldots ,n\}}$ die Permutation ${}\pi '=\varphi \pi \varphi ^{-1}$ . Sei ${}\pi =\tau _{1}\cdots \tau _{r}$ eine Darstellung als Produkt von ${}r$ Transpositionen auf ${}I$ . Dann gilt

{}\pi '=\varphi \pi \varphi ^{-1}=\varphi \tau _{1}\cdots \tau _{r}\varphi ^{-1}=\varphi \tau _{1}\varphi ^{-1}\varphi \tau _{2}\varphi ^{-1}\varphi \cdots \varphi ^{-1}\varphi \tau _{r}\varphi ^{-1}=\tau _{1}'\tau _{2}'\cdots \tau _{r}'\,

mit ${}\tau _{j}'=\varphi \tau _{j}\varphi ^{-1}$ . Dies sind ebenfalls Transpositionen, sodass die Parität von ${}r$ durch das Signum von ${}\pi '$ festgelegt ist.

Die alternierende Gruppe

Für ${}n\geq 2$ ist die Signumsabbildung ${}\operatorname {sgn} \colon S_{n}\rightarrow \{1,-1\}$ ein surjektiver Gruppenhomomorphismus, da ja Transpositionen auf ${}-1$ abgebildet werden. Der Kern dieses Homomorphismus besteht aus allen geraden Permutationen und ist ein Normalteiler in der Permutationsgruppe ${}S_{n}$ . Diese Untergruppe bekommt einen eigenen Namen.

Definition

Zu ${}n\in \mathbb {N}$ heißt die Untergruppe

{}A_{n}:={\left\{\sigma \in S_{n}\mid \operatorname {sgn} (\sigma )=1\right\}}\,

der geraden Permutationen die alternierende Gruppe.

Die alternierende Gruppe besitzt ( ${}n\geq 2$ ) den Index zwei, die beiden Nebenklassen sind die geraden Permutationen und die ungeraden Permutationen.

Für ${}n=1,2$ ist die alternierende Gruppe die triviale Gruppe. Für ${}n=3$ ist ${}A_{3}=\mathbb {Z} /(3)$ . Die Gruppe ${}A_{4}$ ist isomorph zur Tetraedergruppe.

Beispiel

Wir betrachten die alternierende Gruppe ${}A_{4}$ . Die vier Permutationen (in Zykeldarstellung)

\operatorname {id} ,\,\langle 1,2\rangle \langle 3,4\rangle ,\,\langle 1,3\rangle \langle 2,4\rangle ,\,\langle 1,4\rangle \langle 2,3\rangle

bilden darin eine kommutative Untergruppe ${}V$ , in der jedes Element ${}\neq \operatorname {id} \,$ die Ordnung ${}2$ besitzt. Sie ist isomorph zur Kleinschen Vierergruppe. Es handelt sich sogar um einen Normalteiler vom Index drei. Um dies einzusehen verwenden wir Lemma 7.8 und betrachten exemplarisch ${}\sigma =\langle 1,2\rangle \langle 3,4\rangle$ und ${}\tau =\langle 1,2,3\rangle$ mit dem Inversen ${}\tau ^{-1}=\langle 1,3,2\rangle$ . Wir erhalten

\langle 1,2,3\rangle \langle 1,2\rangle \langle 3,4\rangle \langle 1,3,2\rangle =\langle 1,4\rangle \langle 2,3\rangle ,

was wieder zu ${}V$ gehört. Die Restklassengruppe ${}A_{4}/V$ muss isomorph zu ${}\mathbb {Z} /(3)$ sein, die beiden anderen (neben ${}V$ ) Nebenklassen sind einerseits die Dreierzykel

{}N=\langle 2,3,4\rangle ,\,\langle 1,4,3\rangle ,\,\langle 1,2,4\rangle ,\,\langle 1,3,2\rangle \,

und andererseits die dazu inversen Dreierzykel

\langle 2,4,3\rangle ,\,\langle 1,3,4\rangle ,\,\langle 1,4,2\rangle ,\,\langle 1,2,3\rangle .

Wenn man einen Tetraeder mit nummerierten Ecken anschaut, so entsprechen diese beiden Nebenklassen den Dritteldrehungen im Uhrzeigersinn oder entgegen dem Uhrzeigersinn um die Seiteneckachsen, wobei die Drehrichtung dadurch festgelegt ist, dass man auf den Eckpunkt schaut (welche Orientierung zu welcher Nebenklasse gehört, hängt dabei von der Nummerierung der Ecken ab).

Die Gruppe ${}A_{4}$ besitzt also einen nicht-trivialen Normalteiler. Sie ist damit unter den alternierenden Gruppen eine Ausnahme. Es gilt nämlich, und das werden wir hier nicht beweisen, dass die alternierenden Gruppen ${}A_{n}$ , ${}n\geq 5$ einfach sind im Sinne der folgenden Definition.

Definition

Eine Gruppe heißt einfach, wenn sie genau zwei Normalteiler enthält (nämlich sich selbst und die triviale Gruppe).

Für eine Primzahl ${}p$ sind die zyklischen Gruppen ${}\mathbb {Z} /(p)$ der Ordnung ${}p$ einfach, da es in diesen Gruppen aufgrund des Satzes von Lagrange überhaupt nur die triviale und die ganze Gruppe als Untergruppe gibt. In einer nicht kommutativen einfachen Gruppe gibt es im Allgemeinen sehr viele Untergruppen, aber eben keine nicht-trivialen Normalteiler. Die einfachen Gruppen sind in gewissem Sinne die einfachsten Bausteine für alle endlichen Gruppen. Die nicht einfachen Gruppen sind in einem gewissen Sinn „zusammengesetzt“, da es dort dann einen echten Normalteiler ${}N\subset G$ , ${}N\neq 0,\neq G$ gibt und damit auch eine Restklassengruppe ${}G/N=Q$ . Die Gruppe ${}G$ ist dann aus den kleineren Gruppen ${}N$ und ${}Q$ irgendwie „zusammengebastelt“, wobei allerdings ${}N$ und ${}Q$ nicht die Struktur von ${}G$ festlegen. Die Klassifikation aller einfachen endlichen Gruppen war ein schwieriges Problem der Gruppentheorie und ist inzwischen (seit ca. ${}1980$ ) gelöst.

Die Determinante

Wir erinnern noch kurz an die Determinante, die aus der Anfängervorlesung bekannt ist. Mittels Permutationen und deren Signa kann man eine geschlossene Definition für die Determinante geben. Zur Berechnung sind aber rekursive Verfahren sinnvoller.

Definition

Zu einer ${}n\times n$ - Matrix

{}M={\begin{pmatrix}a_{11}&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}\end{pmatrix}}\,

heißt

{}\det M=\sum _{\sigma \in S_{n}}\operatorname {sgn} (\sigma )a_{1\sigma (1)}\cdots a_{n\sigma (n)}\,

die Determinante von ${}M$ .

Der Satz von Cayley

Zu einer Gruppe ${}G$ und einem Element ${}g\in G$ nennt man die Abbildung

L_{g}\colon G\longrightarrow G,\,x\longmapsto gx

die Linksmultiplikation mit ${}g$ . Das ist in aller Regel kein Gruppenhomomorphismus, allerdings ist es eine bijektive Abbildung der Menge ${}G$ in sich. Dieser Zusammenhang wird nun kurz thematisiert.

Lemma

Es sei ${}G$ eine Gruppe und ${}\operatorname {Perm} \,(G)$ die Gruppe der Bijektionen auf ${}G$ .

Dann ist die Abbildung, die einem Gruppenelement die Linksmultiplikation zuordnet, also

$G\longrightarrow \operatorname {Perm} \,(G),\,g\longmapsto L_{g},$

ein injektiver Gruppenhomomorphismus.

Beweis

Die Linksmultiplikation ist eine Bijektion auf ${}G$ , da aus ${}gx=gy$ durch Multiplikation von links mit ${}g^{-1}$ sofort ${}x=y$ folgt. Wegen ${}ex=x$ geht das neutrale Element auf die Identität. Ferner ist für jedes ${}x\in G$

{}L_{g{\tilde {g}}}(x)=(g{\tilde {g}})x=g({\tilde {g}}x)=g(L_{\tilde {g}}(x))=L_{g}(L_{\tilde {g}}(x))=(L_{g}L_{\tilde {g}})(x)\,,

was ${}L_{g{\tilde {g}}}=L_{g}L_{\tilde {g}}$ bedeutet. Daher ist die Zuordnung ein Gruppenhomomorphismus. Zum Nachweis der Injektivität verwenden wir das Kernkriterium. Es sei also ${}L_{g}=\operatorname {id} \,$ . Dann ist aber sofort

{}g=ge=L_{g}(e)=\operatorname {id} \,(e)=e\,.

\Box

Satz

Jede Gruppe lässt sich als Untergruppe einer Permutationsgruppe realisieren. Jede endliche Gruppe lässt sich als Untergruppe einer endlichen Permutationsgruppe realisieren.

Beweis

Dies folgt sofort aus Lemma 5.12.

\Box

Bemerkung

Es gilt sogar, dass mit Ausnahme der Identität jede Linksmultiplikation fixpunktfrei ist. D.h. die Untergruppe der Permutationen, die isomorph zur vorgegebenen Gruppe ist, besitzt außer der Identität nur fixpunktfreie Abbildungen. Dies folgt aus ${}gx=L_{g}(x)=x$ durch Multiplikation mit ${}x^{-1}$ von rechts.

Beispiel

Es sei ${}G=\mathbb {Z} /(n)$ eine zyklische Gruppe, repräsentiert durch die Elemente ${}\{0,1,\ldots ,n-1\}$ . Das Einselement ${}1$ erzeugt die Gruppe, das muss dann auch für die zu ${}G$ isomorphe Untergruppe von ${}S_{n}$ gelten. Die Linksaddition mit ${}1$ ist die Zuordnung