Permutation/Signum/Einführung/Textabschnitt

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 bis auf das Vorzeichen gleichen Differenzen ${}\pm (j-i)$ stehen. Es gibt für das Signum also nur zwei mögliche Werte. Bei ${}\operatorname {sgn} (\pi )=1$ spricht man von einer geraden Permutation und bei ${}\operatorname {sgn} (\pi )=-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.

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 \colon G\longrightarrow H$

heißt Gruppenhomomorphismus, wenn die Gleichheit

${}\psi (g\circ g')=\psi (g)\circ \psi (g')\,$

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

Satz

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

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

${}\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.