7.3 Das Vorzeichen einer Permutation

Definition (Vorzeichen, gerade, ungerade, alternierende Gruppe)

Seien n ≥ 1 und S_n die Gruppe der Permutationen auf { 1, …, n }. Dann ist die Vorzeichenfunktion sgn : S_n → { −1, 1 } definiert durch

sgn(σ) = ∏_{1 ≤ i < j ≤ n} ^{σ(j) − σ(i)}_j − i für alle σ  ∈  S_n.

Wir nennen sgn(σ) das Vorzeichen oder Signum der Permutation σ. Eine Permutation σ heißt gerade, falls sgn(σ) = 1, und ungerade, falls sgn(σ) = −1. Wir setzen:

A_n = { σ  ∈  S_n | sgn(σ) = 1 }. (alternierende Gruppe)

Permutationen und ihre Vorzeichen spielen in der Theorie der Determinanten eine wichtige Rolle. Wir werden im nächsten Abschnitt Determinantenfunktionen mit Hilfe von Permutationen explizit definieren. In diesem Abschnitt treffen wir die nötigen algebraischen Vorbereitungen.

Aufgrund der Bijektivität einer Permutation σ : { 1, …, n } → { 1, …, n } gilt

{ { i, j } | 1 ≤ i < j ≤ n } = { { σ(i), σ(j) } | 1 ≤ i < j ≤ n }.

Hieraus liest man ab, dass der Zähler und der Nenner des Produkts

∏_{1 ≤ i < j ≤ n} ^{σ(j) − σ(i)}_j − i

abgesehen von den Vorzeichen dieselben Faktoren enthalten. Damit ist sgn(σ)  ∈  { −1, 1 }. Nennen wir ein Paar (i, j) mit i < j einen Fehlstand von σ, falls σ(i) > σ(j), so gilt also:

Ist k die Anzahl der Fehlstände von σ, so ist sgn(σ) = (−1)^k.

Beispiele

(1)	Die Permutation (1, …, n) hat keine Fehlstände und damit das Vorzeichen (−1)⁰ = 1.

(2)	Die Permutation σ = (2, 3, …, n, 1) hat die Fehlstände (1, n), …, (n − 1, n). Damit ist sgn(σ) = (−1)^n − 1.

(3)	Die Permutation σ = (n, …, 1) hat n (n − 1)/2 Fehlstände. Gilt n ≡ 0 mod(4) oder n ≡ 1 mod(4), so ist sgn(1) = 1. Andernfalls ist sgn(n) = −1.

(4)	Ist τ  ∈  S_n die Transposition, die i < j vertauscht, so enthält die Produktformel der Definition von sgn(τ) genau einen Faktor −1 und sonst nur Einsen. Damit ist sgn(τ) = −1.

Homomorphie der Vorzeichenfunktion

Für alle π, σ  ∈  S_n gilt sgn(π ∘ σ) = sgn(π) sgn(σ). Die Abbildung sgn : S_n → { −1, 1 } ist also ein Gruppenhomomorphismus. Speziell gilt sgn(σ⁻¹) = sgn(σ)⁻¹ für alle σ  ∈  S_n. Weiter ist A_n = Kern(sgn), sodass A_n ein Normalteiler von S_n ist.

Hieraus ergeben sich neue Möglichkeiten zur Berechnung des Vorzeichens. Ist σ  ∈  S_n beliebig, so können wir ausgehend von (1, 2, …, n) durch Anwendung von Transpositionen oder der Identität Permutationen der Form

(σ(1), …), (σ(1), σ(2), …), …, (σ(1), …, σ(n)) (schrittweises Einstellen der Werte)

erzeugen. Damit ist jede Permutation das Produkt von höchstens n − 1 Transpositionen (σ(n) ist automatisch richtig, wenn alle anderen Werte richtig sind). Da jede Transposition das Vorzeichen −1 besitzt, erhalten wir:

Ist σ = τ_k ∘ … ∘ τ₁ mit Transpositionen τ_i, so ist sgn(σ) = (−1)^k.

Ein σ  ∈  S₁₂ mit vier Bahnen. Es gilt

sgn(σ) = (−1)^12 − 4 = 1.

Eine anschauliche Analyse liefert die Zerlegung einer Permutation in Zyklen.

Ist σ  ∈  S_n und i  ∈  { 1, …, n }, so können wir aufgrund der Injektivität von σ die Bahn

B(i) = { i, σ(i), σ²(i), …, σ^k(i) = i }

bilden. Die Permutation π mit π(j) = σ(j) für j  ∈  B(i) und σ(j) = j für j  ∉  B(i) heißt der von i erzeugte Zyklus von σ. Jede Permutation ist das Produkt ihrer (untereinander kommutierenden) Zyklen. Hat eine Bahn B genau k Elemente, so hat der zugehörige Zyklus das Vorzeichen (−1)^k − 1 (vgl. Beispiel (2)). Da sich die Bahnlängen zu n aufsummieren, gilt:

Hat σ  ∈  S_n genau m Bahnen, so ist sgn(σ) = (−1)^n − m.

Beispiele

(1)	Die Permutation (1, …, n) hat die Bahnen { 1 }, …, { n } und damit das Vorzeichen (−1)^n − n = 1. Die Zyklen der Bahnen sind jeweils die Identität.

(2)	σ = (2, 3, …, n, 1) hat nur die eine Bahn { 1, 2, …, n }, sodass sgn(σ) = (− 1)^n − 1.

(3)	σ = (7, …, 1) hat die Bahnen { 1, 7 }, { 2, 6 }, { 3, 5 }, { 4 }, sodass sgn(σ) = −1.

(4)	Die Transposition, die i und j vertauscht, hat die Bahnen { i, j } und { k } mit k  ∈  { 1, …, n } − { i, j }. Das Vorzeichen ist also (−1)^{n − (n − 1)} = −1.