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

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 bis auf das Vorzeichen gleichen Differenzen $\pm (j-i)$ stehen. Der Faktor $r-s$ im Zähler wird von $\pm ({\pi }^{-1}(r)-{\pi }^{-1}(s))$ aus getroffen. Es gibt für das Signum also nur zwei mögliche Werte. Bei  $\mathrm{sgn}(\pi )=1$  spricht man von einer geraden Permutation und bei  $\mathrm{sgn}(\pi )=-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.

Das Signum ist ein Gruppenhomomorphismus im Sinne der folgenden Definition.

Definition

Es seien $(G,\circ ,e_G)$ und $(H,\circ ,e_H)$ Gruppen. Eine Abbildung

$\psi :G⟶H$

heißt Gruppenhomomorphismus, wenn die Gleichheit

$\psi (g\circ g^{\prime })=\psi (g)\circ \psi (g^{\prime })$

für alle  $g,g^{\prime }\in G$  gilt.

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

Das Signum einer Transposition

ist $-1$.

Beweis

Die Transposition $\tau$ vertausche die beiden Zahlen  $k<\ell$.  Wenn  $k+1<\ell$,  und wenn $\rho$ die Transposition der Nachbarn $k$ und $k+1$ und $\tilde{\tau }$ die Transposition von $k+1$ und $\ell$ bezeichnet, so besteht die Beziehung

$\tau =\rho \circ \tilde{\tau }\circ \rho ,$

was man direkt auf den relevanten Elementen $k,k+1,\ell$ überprüfen kann. Aufgrund der Homomorphieeigenschaft gilt also  $\mathrm{sgn}(\tau )=\mathrm{sgn}(\tilde{\tau })$.  Daher genügt es, die Aussage für Transpositionen zu beweisen, die zwei benachbarte Elemente vertauschen. Solche Transpositionen haben aber nur einen Fehlstand, und somit folgt die Aussage aus Lemma 18.10 (Lineare Algebra (Osnabrück 2024-2025)).

$◻$

Korollar

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)).

$◻$

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

$\mathrm{sgn}(\pi )=\{\begin{array}{c}1,\text{ falls }r\text{ gerade ist},\\ -1,\text{ falls }r\text{ ungerade ist}.\end{array}$

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

$\phi :I⟶\{1,\dots ,n\}.$

Die Permutation $\pi$ auf $I$ definiert auf $\{1,\dots ,n\}$ die Permutation  ${\pi }^{\prime }=\phi \pi {\phi }^{-1}$.  Sei  $\pi ={\tau }_1\cdots {\tau }_r$  eine Darstellung als Produkt von $r$ Transpositionen auf $I$. Dann gilt

${\pi }^{\prime }=\phi \pi {\phi }^{-1}=\phi {\tau }_1\cdots {\tau }_r{\phi }^{-1}=\phi {\tau }_1{\phi }^{-1}\phi {\tau }_2{\phi }^{-1}\phi \cdots {\phi }^{-1}\phi {\tau }_r{\phi }^{-1}={{\tau }_1}^{\prime }{{\tau }_2}^{\prime }\cdots {{\tau }_r}^{\prime }$

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

Die alternierende Gruppe

Für $n\ge 2$ ist die Signumsabbildung $\mathrm{sgn}:S_n\to \{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:=\{\sigma \in S_n\mid \mathrm{sgn}(\sigma )=1\}$

der geraden Permutationen die alternierende Gruppe.

Die alternierende Gruppe besitzt ($n\ge 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 Zyklendarstellung)

$\mathrm{id},⟨1,2⟩⟨3,4⟩,⟨1,3⟩⟨2,4⟩,⟨1,4⟩⟨2,3⟩$

bilden darin eine kommutative Untergruppe $V$, in der jedes Element $\ne \mathrm{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 =⟨1,2⟩⟨3,4⟩$ und $\tau =⟨1,2,3⟩$ mit dem Inversen ${\tau }^{-1}=⟨1,3,2⟩$. Wir erhalten

$⟨1,2,3⟩⟨1,2⟩⟨3,4⟩⟨1,3,2⟩=⟨1,4⟩⟨2,3⟩,$

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 Dreierzyklus

$N=⟨2,3,4⟩,⟨1,4,3⟩,⟨1,2,4⟩,⟨1,3,2⟩$

und andererseits die dazu inversen Dreierzyklus

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

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\ge 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\ne 0,\ne 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=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \dots & a_{nn}\end{array}\right)$

heißt

$detM=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )a_{1\sigma (1)}\cdots a_{n\sigma (n)}$

die Determinante von $M$.

Der Satz von Cayley

Arthur Cayley (1821-1895)

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

$L_g:G⟶G,x⟼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 $\mathrm{Perm}(G)$ die Gruppe der Bijektionen auf $G$.

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

$G⟶\mathrm{Perm}(G),g⟼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=\mathrm{id}$. Dann ist aber sofort

$g=ge=L_g(e)=\mathrm{id}(e)=e.$

$◻$

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.

$◻$

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,\dots ,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

$0\mapsto 1,1\mapsto 2,2\mapsto 3,\dots ,n-2\mapsto n-1,n-1\mapsto 0.$

Das ist also ein Zyklus der Ordnung $n$. Das Element $k$ geht auf die $k$-fache Hintereinanderausführung dieses Zyklus.

<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)