Permutation/Signum/Einführung/Textabschnitt

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äß Fakt, 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 Fakt.

$◻$

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 Fakt und Fakt.

$◻$

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