Einschub C : Das Vorzeichen einer Permutation

Für n ∈ IN bezeichne S_{n} die Menge aller Permutationen der n Zahlen 1, 2, …, n. Genaugenommen ist S_{n} = Bij(IN_{n}, IN_{n}) mit IN_{n} := {1, 2, …, n}.

\underline{(C.1) DEF:} Sei π ∈ S_{n}. Ein Zahlenpaar (i, k) ∈ IN_{n} × IN_{n} heißt eine Inversion (oder ein Fehlstand) von π, wenn

i < k und π(i) > π(k)

gilt. Es bezeichne ν(π) die Anzahl der Inversionen von π.

\underline{Beispiel:} Inversionen von π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \end{matrix} ) ∈ S_{5} sind die Paare (1, 4), (2, 4), (3, 4), (3, 5),

d.h. ν(π) = 4.

\underline{(C.2) LEMMA:} Sei π ∈ S_{n}. Dann ist ν(π) die minimale Anzahl der Nachbarschaftsvertauschungen, die erforderlich sind, um aus der Folge π(1), π(2), …, π(n) die natürliche Reihenfolge 1, 2, …, n herzustellen.

\underline{(C.3) DEF:} Das Vorzeichen sign(π) einer Permutation π ∈ S_{n} ist definiert durch

sign(π) := (−1)^{ν(π)}

\underline{(C.4) SATZ:} f : V^{n} ⟶ K sei eine schiefsymmetrische Abbildung und π ∈ S_{n}. Dann gilt für jedes (v_{1}, v_{2}, …, v_{n}) ∈ V^{n}

f(v_{π(1)}, v_{π(2)}, …, v_{π(n)}) = sign(π) · f(v_{1}, v_{2}, …, v_{n})

\underline{Bew:} (Idee) Durch ν(π) Nachbarvertauschungen läßt sich aus v_{π(1)}, v_{π(2)}, …, v_{π(n)} die natürliche Reihenfolge v_{1}, v_{2}, …, v_{n} herstellen. Bei jeder Vertauschung ändert sich das Vorzeichen des Bildes unter f , da f nach Voraussetzung schiefsymmetrisch ist. Damit gilt

f(v_{π(1)}, v_{π(2)}, …, v_{π(n)}) = (−1)^{ν(π)} = sign(π) · f(v_{1}, v_{2}, …, v_{n})

\underline{(C.5) FOLG:} Für π, ρ ∈ S_{n} gilt: sign(π ∘ ρ) = sign(π) · sign(ρ) .

\underline{Bew:} Sei d : V^{n} ⟶ K die eindeutig bestimmte Determinantenform auf V := K^{n} mit d(e_{1}, …, e_{n}) = 1 . Dann ist

\underline{\underline{d(e_{(π∘ρ)(1)}, …, e_{(π∘ρ)(n)})}} = sign(π ∘ ρ) · \underbrace{d(e_{1}, …, e_{n})}_{=1} = \underline{\underline{sign(π ∘ ρ)}}

Auf der anderen Seite ist

\underline{\underline{d(e_{(π∘ρ)(1)}, …, e_{(π∘ρ)(n)})}} = d(e_{π(ρ(1))}, …, e_{π(ρ(n))}) = d(e′_{ρ(1)}, …, e′_{ρ(n)})

wenn man e_{π(k)} =: e′_{k} setzt. Man erhält weiter

d(e′_{ρ(1)}, …, e′_{ρ(n)}) = sign(ρ) · d(e′_{1}, …, e′_{n}) = sign(ρ) · d(e_{π(1)}, …, e_{π(n)}) =

sign(ρ) · sign(π) · \underbrace{d(e_{1}, …, e_{n})}_{=1} = \underline{\underline{sign(ρ) · sign(π)}}

Damit ist die Behauptung bewiesen.

\underline{(C.6) DEF:} Sei n ≥ 2. Eine Permutation τ ∈ S_{n} heißt Transposition, wenn es i, k ∈ IN_{n} mit i ≠ k gibt , so daß gilt: τ(i) = k , τ(k) = i , τ(l) = l (∀ l ∈ IN_{n} \ {i, k}) .

Eine Transposition τ vertauscht also genau 2 Zahlen aus IN_{n} und läßt den Rest unverändert. Außerdem gilt τ ∘ τ = id, d.h. τ^{−1} = τ.

\underline{(C.7) SATZ:} Jede Permutation π ∈ S_{n} (n ≥ 2) läßt sich als Hintereinanderausführung von höchstens n Transpositionen darstellen.

\underline{Bew:} (Idee) Führe Induktion nach n.

\underline{(C.8) DEF:} Eine Permutation π ∈ S_{n} heißt gerade, wenn ν(π) eine gerade Zahl ist, ansonsten ungerade. Mit A_{n} wird die Menge aller geraden Permutationen aus S_{n} bezeichnet.

\underline{BEISPIEL:} Eine Transposition ist immer ungerade.

\underline{(C.9) SATZ:} Eine Permutation π ∈ S_{n} ist genau dann gerade, wenn sich π als Hintereinanderausführung einer geraden Anzahl von Transpositionen darstellen läßt .

\underline{(C.10) SATZ:} a) A_{n} ist eine Untergruppe von (S_{n}, ∘).

b) Für n ≥ 2 gilt |A_{n}| = \frac{1}{2} · n!.

\underline{(C.11) DEF:} (A_{n}, ∘) heißt alternierende Gruppe von n Elementen