Signum einer Permutation

Motivation

Eine Permutation $\pi$ einer Menge $\{1, \dots, n\}$ ist eine bijektive Abbildung dieser Menge auf sich selbst. Jede Permutation lässt sich als Produkt von Transpositionen (Vertauschungen zweier Elemente) schreiben — auf viele Arten, aber die Parität der Anzahl solcher Transpositionen ist eindeutig. Das Signum $\operatorname{sgn}(\pi) \in \{+1, -1\}$ fasst genau diese Parität zusammen: $+1$ für eine gerade, $-1$ für eine ungerade Permutation.

Das Signum ist allgegenwärtig: Es definiert die Determinante über die Leibniz-Formel, die alternierende Gruppe $A_n$ (Kern der Signum-Abbildung) und das Vorzeichen in zahllosen kombinatorischen Identitäten.

Formale Definition

Schreibe $\pi$ in Einzeilen-Notation, also als Liste der Bilder $\big(\pi(1), \pi(2), \dots, \pi(n)\big)$ . Klassisch ist das Signum über die Fehlstände (Inversionen) definiert:

\operatorname{sgn}(\pi) \coloneqq \prod_{1 \le i < j \le n} \frac{\pi(i) - \pi(j)}{i - j} = (-1)^{\#\{(i,j)\,:\, i < j,\ \pi(i) > \pi(j)\}}.

Praktischer — und der Weg, den dieser Rechner geht — ist die Zykelzerlegung. Jede Permutation zerfällt eindeutig in disjunkte Zykel. Ist $z$ ihre Anzahl (Fixpunkte zählen als 1-Zykel), so gilt

\operatorname{sgn}(\pi) = (-1)^{\,n - z}.

Der Exponent $k = n - z$ ist die minimale Anzahl von Transpositionen, deren Produkt $\pi$ ergibt: Ein Zykel der Länge $\ell$ ist ein Produkt von $\ell - 1$ Transpositionen, und die Längen aller Zykel summieren sich zu $n$ .

Durchgerechnetes Beispiel

Wir nehmen $\pi = (2, 1, 3)$ in Einzeilen-Notation — also $\pi(1) = 2$ , $\pi(2) = 1$ , $\pi(3) = 3$ (die Vorbelegung des Rechners oben).

Zykel finden. Start bei $1$ : $1 \mapsto 2 \mapsto 1$ schließt den Zykel $(1\ 2)$ . Es bleibt $3$ : $3 \mapsto 3$ ist der Fixpunkt $(3)$ . Also

\pi = (1\ 2)(3), \qquad z = 2.

Signum berechnen. Mit $n = 3$ und $z = 2$ :

\operatorname{sgn}(\pi) = (-1)^{\,n - z} = (-1)^{\,3 - 2} = (-1)^{1} = -1.

$\pi$ ist also ungerade — was man auch direkt sieht: $\pi = (1\ 2)$ ist eine einzige Transposition.

Häufige Fehler

Fixpunkte vergessen: In $z$ zählen alle Zykel mit, auch 1-Zykel. Lässt man Fixpunkte weg, wird der Exponent $n - z$ falsch.
Einzeilen- vs. Zykel-Notation verwechselt: $(2, 1, 3)$ als Einzeilen-Notation ist die Permutation mit $\pi(1) = 2$ — nicht der Zykel $(2\ 1\ 3)$ .
Keine gültige Permutation: Jede Zahl $1, \dots, n$ muss genau einmal vorkommen. Doppelte oder fehlende Werte ergeben keine Permutation — der Rechner weist solche Eingaben ab.
Parität mit Wert verwechselt: Das Signum ist immer $+1$ oder $-1$ , nie der Exponent selbst.