Vorzeichen (Permutation)

Bedeutung und Grunddefinition

Das Vorzeichen, auch Signum, Signatur oder Parität, ist eine Kennzahl einer Permutation. Es hat nur die Werte +1 und −1. Eine Permutation mit Signum +1 heißt gerade, eine mit Signum −1 ungerade.

Für die symmetrische Gruppe Sₙ aller Permutationen von {1,…,n} und eine Permutation π=(π(1),π(2),…,π(n)) gilt: sgn(π)=(-1)^{|inv(π)|}. Dabei ist inv(π) die Menge der Fehlstände. Ein Fehlstand ist ein Paar (i,j) mit i<j, aber π(i)>π(j). |inv(π)| bedeutet die Anzahl dieser Paare. Eine gerade Anzahl von Fehlständen führt also zu +1, eine ungerade zu −1.

Auch Permutationen beliebiger endlicher geordneter Mengen können betrachtet werden; für die mathematische Analyse genügt die Beschränkung auf die ersten n natürlichen Zahlen.

Fehlstände erkennen

Bei π=(1 2 3 4 5 über 4 1 5 2 3) sind die Fehlstände (1,2), (1,4), (1,5), (3,4) und (3,5). Es gibt also fünf Fehlstände und damit sgn(π)=(-1)^5=−1: Die Permutation ist ungerade.

Die identische Permutation id=(1 2 … n über 1 2 … n) besitzt keine Fehlstände. Daher ist sie stets gerade.

Für S₃ ergeben sich als typische Fälle: Die Identität hat Signum +1. Die Permutationen (1 2 3 über 1 3 2) und (1 2 3 über 2 1 3) haben jeweils einen Fehlstand und Signum −1. Die Permutationen (1 2 3 über 2 3 1) und (1 2 3 über 3 1 2) haben jeweils zwei Fehlstände und Signum +1. Die umgekehrte Reihenfolge (1 2 3 über 3 2 1) hat drei Fehlstände und Signum −1.

Produktformel und Verkettung

Das Signum lässt sich auch direkt durch die Produktformel bestimmen: sgn(π)=∏_{1≤i<j≤n} (π(j)−π(i))/(j−i). Weil π bijektiv ist, treten die Differenzen j−i im Zähler und Nenner bis auf ihr Vorzeichen jeweils genau einmal auf. Jeder Fehlstand bewirkt genau einen negativen Faktor.

Für π=(1 2 3 über 3 1 2) erhält man die Faktoren (1−3)/(2−1), (2−3)/(3−1) und (2−1)/(3−2). Nach Umordnung der Differenzen ist ihr Produkt (+1)·(−1)·(−1)=+1. Die zwei Fehlstände (1,2) und (1,3) entsprechen den zwei Vorzeichenwechseln.

Für die Verkettung τ∘π zweier Permutationen gilt die zentrale Regel sgn(τ∘π)=sgn(τ)·sgn(π). Die Reihenfolge der Faktoren der Produktformel ändert sich bei der Verkettung nur; bei vertauschten Zahlen kehren sich Zähler und Nenner zugleich im Vorzeichen um. Daraus folgt: Eine Verkettung ist genau dann gerade, wenn beide beteiligten Permutationen dasselbe Signum haben.

Transpositionen, Zyklen und Matrizen

Eine Transposition τₖₗ mit k<l vertauscht nur k und l und lässt alle übrigen Zahlen fest. Sie hat immer Signum −1. Sie kann durch 2(l−k)−1 Nachbarvertauschungen dargestellt werden; diese Zahl und damit auch ihre Anzahl von Fehlständen ist ungerade. Jede Permutation in Sₙ lässt sich als Verkettung von höchstens n−1 Transpositionen darstellen. Unabhängig von der gewählten Darstellung ist die Zahl der Transpositionen bei geraden Permutationen gerade und bei ungeraden ungerade.

Eine zyklische Permutation der Länge m lässt sich als Verkettung von m−1 Transpositionen schreiben und hat deshalb das Signum (-1)^{m−1}. Sie ist genau dann gerade, wenn m ungerade ist. Zerfällt π eindeutig in s paarweise disjunkte Zyklen der Längen m₁,…,mₛ, so gilt sgn(π)=(-1)^{m₁+…+mₛ−s}. Damit ist π genau dann gerade, wenn die Summe der Zykluslängen minus der Zyklusanzahl gerade ist; gleichwertig muss die Anzahl der Zyklen gerader Länge gerade sein. Eine Permutation ungerader Ordnung ist stets gerade. Einerzyklen dürfen weggelassen werden, ohne dieses Ergebnis zu ändern.

Die Permutation (1 2 3 4 5 6 über 3 6 4 1 5 2) hat die Zyklen (1 3 4)(2 6)(5). Weil 3+2+1−3 ungerade ist, ist sie ungerade.

Zu π gehört die Permutationsmatrix Pπ mit (Pπ)ᵢⱼ=1, falls π(i)=j, und 0 sonst. Es gilt sgn(π)=det(Pπ); ihre Determinante ist also stets +1 oder −1. Praktisch kann man je Spalte die links liegenden Spalten zählen, deren Eins tiefer steht; diese Anzahl heißt Kennmarke. Eine gerade Summe der Kennmarken liefert die Determinante +1, eine ungerade Summe −1.

Gruppeneigenschaften und Anzahl

Für n≥2 gibt es unter den insgesamt n! Permutationen genau gleich viele gerade wie ungerade: #{π∈Sₙ | sgn(π)=+1}=#{π∈Sₙ | sgn(π)=−1}=n!/2.

Die Umkehrung einer Permutation ändert ihr Vorzeichen nicht: sgn(π⁻¹)=sgn(π). Dies folgt auch aus sgn(π⁻¹)·sgn(π)=sgn(id)=1.

Wegen sgn(τ∘π)=sgn(τ)·sgn(π) ist sgn:Sₙ→{+1,−1} ein Gruppenhomomorphismus in die multiplikative Gruppe {+1,−1}, die zyklische Gruppe vom Grad 2. Sein Kern ist die Menge der geraden Permutationen. Sie ist als alternierende Gruppe Aₙ ein Normalteiler von Sₙ. Die ungeraden Permutationen bilden keine Untergruppe, weil die Verkettung zweier ungerader Permutationen gerade ist. Konjugierte Permutationen besitzen dasselbe Signum.

Anwendungen und Verallgemeinerung

Das Vorzeichen wird unter anderem in der Leibniz-Formel für Determinanten, bei antisymmetrischen Funktionen wie alternierenden Multilinearformen, im Lemma von Zolotareff für das Legendre-Symbol und bei erreichbaren Stellungen des 15-Puzzles verwendet. Als anschauliches Beispiel wird die Futurama-Folge „Im Körper des Freundes“ genannt: Bei einer Maschine, die die Seelen zweier Menschen vertauscht, ist unabhängig von Zahl und Beteiligten der vorgenommenen Tausche stets eine ungerade Zahl an Permutationen notwendig, damit alle wieder im eigenen Körper sind.

Für nicht unbedingt bijektive Abbildungen φ:{1,…,n}→{1,…,n} verallgemeinert das Levi-Civita-Symbol ε_{φ₁…φₙ} das Signum. Mit φₖ=φ(k) ist es definiert durch ε_{φ₁…φₙ}=∏_{1≤i<j≤n}(φⱼ−φᵢ)/(j−i). Im Unterschied zum Signum kann es den Wert 0 annehmen: genau dann, wenn φ nicht bijektiv ist. Das Levi-Civita-Symbol wird besonders in der Vektor- und Tensorrechnung, etwa in Relativitätstheorie und Quantenmechanik, verwendet.