Vorzeichen (Permutation)

wichtige Kennzahl von Permutationen
(Weitergeleitet von Gerade Permutation)

Das Vorzeichen, auch Signum, Signatur oder Parität genannt, ist in der Kombinatorik eine wichtige Kennzahl von Permutationen. Das Signum einer Permutation kann die Werte oder annehmen, wobei man im ersten Fall von einer geraden und im zweiten Fall von einer ungeraden Permutation spricht.

Es gibt mehrere Möglichkeiten, gerade und ungerade Permutationen zu charakterisieren. So ist eine Permutation genau dann gerade, wenn die Anzahl der Fehlstände in der Permutation gerade ist. Jede Permutation lässt sich auch als Verkettung endlich vieler Transpositionen darstellen und ist genau dann gerade, wenn die Anzahl der dabei benötigten Transpositionen gerade ist. Eine Permutation kann zudem auch in Zyklen zerlegt werden und ist genau dann gerade, wenn die Anzahl der Zyklen gerader Länge gerade ist. Das Signum einer Permutation ist auch gleich der Determinante der zugehörigen Permutationsmatrix.

Das Signum ist als Abbildung ein Gruppenhomomorphismus von der symmetrischen Gruppe der Permutationen in die multiplikative Gruppe über der Menge . Ein wichtiges Einsatzbeispiel des Signums ist die Leibniz-Formel für Determinanten.

Definition

Bearbeiten

Ist   die symmetrische Gruppe aller Permutationen der Menge  , dann wird das Vorzeichen einer Permutation   durch

 

definiert, wobei

 

die Menge der Fehlstände der Permutation ist.

  steht für die Mächtigkeit (Anzahl der Elemente) von  .

Ist das Vorzeichen  , so nennt man die Permutation   gerade, ist es  , nennt man sie ungerade.

Allgemeiner können auch Permutationen beliebiger endlicher geordneter Mengen betrachtet werden, für die mathematische Analyse kann man sich jedoch auf die ersten   natürlichen Zahlen beschränken.

Beispiele

Bearbeiten
Permutationen in S3
Permutation Fehlstände Signum
  +1
  (2,3) −1
  (1,2) −1
  (1,3),(2,3) +1
  (1,2),(1,3) +1
  (1,2),(1,3),(2,3) −1

Die Fehlstände der Permutation

 

sind   und  , somit ist

 

und damit die Permutation ungerade. Die identische Permutation

 

ist immer gerade, denn sie weist keine Fehlstände auf. Die nebenstehende Tabelle führt alle Permutationen der Länge drei mit ihren zugehörigen Vorzeichen auf.

Darstellung als Produkt

Bearbeiten

Produktformel

Bearbeiten

Das Vorzeichen einer Permutation der ersten   natürlichen Zahlen kann auch durch die Produktformel

 

dargestellt werden. Aufgrund der Bijektivität einer Permutation tritt hierbei jeder Term   für   bis auf gegebenenfalls das Vorzeichen je einmal im Zähler und einmal Nenner eines Bruchs auf. Jeder Fehlstand führt dabei zu genau einem negativen Vorzeichen.

Beispiel

Das Signum der Permutation

 

ist durch

 

gegeben. Die beiden Fehlstände   und   führen dabei zu jeweils einem Vorzeichenwechsel.

Verkettungseigenschaft

Bearbeiten

Für das Signum einer Verkettung zweier Permutationen   gilt aufgrund der Produktdarstellung:

 

Der letzte Schritt folgt daraus, dass in dem Produkt über   die gleichen Faktoren, wie in dem Produkt über   vorkommen, nur in anderer Reihenfolge. Für zwei durch   vertauschte Zahlen   kehrt sich dabei sowohl im Nenner und im Zähler das Vorzeichen um. Demnach ist die Verkettung zweier Permutationen genau dann gerade, wenn beide Permutationen das gleiche Signum aufweisen.

Weitere Darstellungen

Bearbeiten

Darstellung über die Zahl der Transpositionen

Bearbeiten
 
Umwandlung zwischen geraden und ungeraden Permutationen durch Transpositionen

Eine Transposition   mit   ist eine Permutation, die lediglich die zwei Zahlen   und   vertauscht, das heißt   auf   sowie   auf   abbildet und die übrigen Zahlen festlässt. Für das Signum einer Transposition gilt

 ,

denn jede Transposition lässt sich als Verkettung einer ungeraden Zahl von Nachbarvertauschungen der Form   durch

 

darstellen. Hierbei wird zunächst die Zahl   durch sukzessive Nachbarvertauschungen an die Stelle   gebracht und dann die Zahl   von der Stelle   durch sukzessive Nachbarvertauschungen an die Stelle  . Nachdem jede dieser Nachbarvertauschungen genau einen Fehlstand erzeugt, ist die Gesamtzahl der Fehlstände einer Transposition

 

und damit immer ungerade. Jede Permutation   lässt sich nun als Verkettung von höchstens   Transpositionen darstellen. Jede dieser Transpositionen vertauscht dabei jeweils die kleinste Zahl  , für die   gilt, mit derjenigen Zahl  , für die   gilt. Ist   die Anzahl der dabei benötigten Transpositionen, dann gilt aufgrund der Verkettungseigenschaft

 .

Es gibt natürlich noch weitere Möglichkeiten, eine Permutation als Verkettung von Transpositionen darzustellen. Handelt es sich dabei aber um eine gerade Permutation, dann ist die Zahl der benötigten Transpositionen immer gerade, handelt es sich um eine ungerade Permutation immer ungerade.

Beispiel

Die Permutation

 

lässt sich durch

 

darstellen und ist damit gerade. Eine weitere Darstellung von   als Verkettung von Transpositionen wäre etwa  .

Darstellung über die Zahl und Länge der Zyklen

Bearbeiten
Durch die Hintereinanderausführung einer Permutation (rot) mit einer Vertauschung (blau) erhöht sich die Anzahl der Zyklen um eins, wenn die vertauschten Elemente innerhalb eines Zyklus liegen (links) und sie verringert sich um eins, wenn sie in verschiedenen Zyklen liegen (rechts).

Eine zyklische Permutation   ist eine Permutation, die die Zahlen   zyklisch vertauscht, das heißt   auf   abbildet,   auf   bis hin zu   auf   und die übrigen Zahlen festlässt. Eine zyklische Permutation der Länge zwei entspricht gerade einer Transposition zweier Zahlen. Jede zyklische Permutation der Länge   kann als Verkettung von   Transpositionen geschrieben werden:

 .

Da Transpositionen ungerade sind, ist das Signum einer zyklischen Permutation der Länge   aufgrund der Verkettungseigenschaft

 .

Eine zyklische Permutation ist also genau dann gerade, wenn ihre Länge ungerade ist. Jede Permutation   lässt sich nun eindeutig als Verkettung von   zyklischen Permutationen mit paarweise disjunkten Zyklen darstellen. Sind   die Längen dieser Zyklen, dann gilt aufgrund der Verkettungseigenschaft

 .

Das Signum kann daher direkt aus dem Zyklentyp der Permutation abgelesen werden. Eine Permutation ist demnach genau dann gerade, wenn die Summe der Längen der einzelnen Zyklen minus der Anzahl der Zyklen gerade ist. Da Zyklen ungerader Länge das Signum nicht verändern, ist eine Permutation genau dann gerade, wenn die Anzahl der Zyklen gerader Länge gerade ist. Nachdem sich die Ordnung einer Permutation aus dem kleinsten gemeinsamen Vielfachen ihrer Zyklenlängen ergibt, ist eine Permutation mit ungerader Ordnung stets gerade.

Beispiel

Die Permutation

 

zerfällt in drei disjunkte Zyklen, in Zyklenschreibweise

 .

Da die Summe   ungerade ist, ist die Permutation ebenfalls ungerade. Einerzyklen können in der Zyklenschreibweise und bei der Zählung auch weggelassen werden, ohne die Summe und damit das Signum zu verändern.

Darstellung über die Determinante der Permutationsmatrix

Bearbeiten

Ist   die zu der Permutation   zugehörige Permutationsmatrix mit Einträgen

 

dann entspricht das Signum von   gerade der Determinante von  , also

 .

Die Determinante einer Permutationsmatrix ist entweder +1 oder −1. Die folgende Methode zur Bestimmung der Determinante ist auch für große Matrizen praktikabel. Dazu wird für jede Spalte S der Matrix die Anzahl der Spalten ermittelt, die in der Matrix links von S stehen und bei denen die Eins tiefer steht als in S; diese Anzahl heißt Kennmarke. Ist die Summe der Kennmarken eine gerade Zahl dann ist die Determinante eins, sonst minus eins.[1]

Beispiel

Die zur Permutation

 

zugehörige Permutationsmatrix ist

 ,

deren Determinante sich nach der Regel von Sarrus zu

 

ergibt. Die Kennmarken lauten:

Spalte 1 2 3
Zeilennummer 2 3 1
Kennmarke 0 0 2

Die Summe der Kennmarken ist gerade, was obiges Ergebnis bestätigt.

Weitere Eigenschaften

Bearbeiten

Mächtigkeiten

Bearbeiten

Es gibt genau   verschiedene Permutationen der Menge  . Für   wird die Menge aller Permutationen durch die geraden und ungeraden Permutationen in zwei gleich große Hälften geteilt, denn es gibt gleich viele Möglichkeiten, die Vorzeichen im Zähler der Produktformel so zu wählen, dass das Produkt positiv bzw. negativ ist. Für die Mächtigkeit dieser beiden Mengen gilt demnach

 .

Aus diesem Grund spricht man hier neben dem Signum auch von der Parität (von lateinisch paritas ‚Gleichheit‘) einer Permutation.

Inverse Permutationen

Bearbeiten

Für das Signum der inversen Permutation   von   gilt:

 .

Durch Invertierung ändert sich also das Signum einer Permutation nicht, was mit der Verkettungseigenschaft auch direkt über

 

ersichtlich ist.

Signum-Homomorphismus

Bearbeiten

Aufgrund der Verkettungseigenschaft stellt die Abbildung

 

einen Gruppenhomomorphismus von der symmetrischen Gruppe   in die multiplikative Gruppe   dar (dies ist gerade die zyklische Gruppe vom Grad 2). Diese Eigenschaft wird in der Theorie der Determinanten, beispielsweise der Leibniz-Formel verwendet. Der Kern dieses Homomorphismus ist die Menge der geraden Permutationen. Sie bildet einen Normalteiler von  , die alternierende Gruppe  . Die Menge der ungeraden Permutationen bildet jedoch keine Untergruppe von  , denn die Verkettung zweier ungerader Permutationen ergibt eine gerade Permutation.

Konjugierte Permutationen besitzen dasselbe Signum, wie aus den Eigenschaften des Signum-Homomorphismus folgt. Ist nämlich  , dann gilt für alle  

 .

Verwendung

Bearbeiten

Das Vorzeichen von Permutationen wird unter anderem in folgenden Bereichen verwendet:

Ein sehr anschauliches Beispiel findet sich in der Futurama-Folge "Im Körper des Freundes". Der Charakter "Professor Farnsworth" erfindet darin eine Maschine, welche die Seelen zweier Menschen vertauscht (sodass die Seele von Person A im Körper von Person B ist und die Seele von Person B im Körper von Person A). Unabhängig von der Zahl der vorgenommenen Tausche (und wie viele Personen daran beteiligt waren), ist stets eine ungerade Zahl an Permutationen notwendig, damit jeder wieder in seinem eigenen Körper ist.[2]

Verallgemeinerung

Bearbeiten

Eine Verallgemeinerung des Signums für nicht notwendigerweise bijektive Abbildungen   ist das Levi-Civita-Symbol  , das mit der Notation   für   wie das Signum über

 

definiert werden kann. Im Unterschied zum Signum kann das Levi-Civita-Symbol jedoch auch den Wert   annehmen, was genau dann der Fall ist, wenn die Abbildung   nicht bijektiv ist. Das Levi-Civita-Symbol wird insbesondere in der Vektor- und Tensorrechnung in Anwendungen wie der Relativitätstheorie und der Quantenmechanik verwendet.

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. R. Zurmühl, S. Falk: Matrizen und ihre Anwendungen 1. Grundlagen, Für Ingenieure, Physiker und Angewandte Mathematiker. Springer, Berlin u. a. 1997, ISBN 3-540-61436-2, S. 57.
  2. Burkard Polster: The parity of permutations and the Futurama theorem. Abgerufen am 21. Juni 2019.