Vorzeichenbehaftete Permutationsmatrix

Matrizenart in der Mathematik

Eine vorzeichenbehaftete Permutationsmatrix ist in der Mathematik eine quadratische Matrix, bei der in jeder Zeile und jeder Spalte genau ein Eintrag plus oder minus eins ist und alle übrigen Einträge null sind. Vorzeichenbehaftete Permutationsmatrizen stellen damit eine Verallgemeinerung gewöhnlicher Permutationsmatrizen dar und sind ein Spezialfall monomialer Matrizen. Sie sind genau die ganzzahligen orthogonalen Matrizen. Die Gruppe der vorzeichenbehafteten Permutationsmatrizen ist isomorph zur Hyperoktaedergruppe, der Symmetriegruppe eines Hyperwürfels oder Kreuzpolytops.

Definition

Bearbeiten

Eine vorzeichenbehaftete Permutationsmatrix ist eine quadratische Matrix, bei der genau ein Eintrag pro Zeile und Spalte   oder   ist und alle anderen Einträge   sind. Hierbei sind im Allgemeinen   und   das Einselement und Nullelement eines zugrunde liegenden Rings  . Jede vorzeichenbehaftete Permutationsmatrix   lässt sich als Produkt

    bzw.    

aus einer normalen Permutationsmatrix   und einer Diagonalmatrix   mit Einträgen   oder   auf der Hauptdiagonalen darstellen.[1] Die beiden Darstellungen sind dabei äquivalent: in der ersten Darstellung entsprechen die Diagonaleinträge von   jeweils den Spalteneinträgen ungleich null von  , in der zweiten Darstellung jeweils den Zeileneinträgen ungleich null; die beiden Permutationsmatrizen stimmen überein.

Beispiel

Bearbeiten

Ein Beispiel für eine vorzeichenbehaftete Permutationsmatrix der Größe   ist

 ,

denn es gilt

 .

Eigenschaften

Bearbeiten

Die Anzahl verschiedener vorzeichenbehafteter Permutationsmatrizen der Größe   ist

 ,

wobei   die Doppelfakultät bezeichnet. Es gibt nämlich   verschiedene Permutationsmatrizen der Größe   und   mögliche Wahlen für die   Vorzeichen.

Das Produkt zweier vorzeichenbehafteter Permutationsmatrizen   ist wieder eine vorzeichenbehaftete Permutationsmatrix, denn es gilt

 ,

wobei   die Diagonalmatrix ist, die aus   durch Zeilen- und Spaltenvertauschungen gemäß der   zugrunde liegenden Permutation entsteht.[1]

Eine vorzeichenbehaftete Permutationsmatrix   ist stets invertierbar. Die Menge der vorzeichenbehafteten Permutationen bildet daher mit der Matrizenmultiplikation als Verknüpfung eine Untergruppe der allgemeinen linearen Gruppe  , spezieller eine Untergruppe der monomialen Gruppe  . Die Inverse einer vorzeichenbehafteten Permutationsmatrix ergibt sich dabei zu

 

und ist demnach gleich ihrer Transponierten. Reelle vorzeichenbehaftete Permutationsmatrizen sind daher orthogonal und ihre Matrizengruppe ist eine Untergruppe der orthogonalen Gruppe  . Diese Untergruppe besteht genau aus den ganzzahligen orthogonalen Matrizen.

Potenzen

Bearbeiten

Ganzzahlige Potenzen vorzeichenbehafteter Permutationsmatrizen sind wieder vorzeichenbehaftete Permutationsmatrizen. Für jede vorzeichenbehaftete Permutationsmatrix   gibt es dabei eine Potenz  , sodass

 

ergibt, wobei   die Einheitsmatrix ist. Das kleinste positive   mit dieser Eigenschaft ist gleich der Ordnung von   in der allgemeinen linearen Gruppe. Stellt die zu   zugehörige Permutation   einen einzelnen Zyklus der Länge   dar und bezeichnet   die Anzahl der Einträge mit Wert   in  , dann gilt für die Ordnung von  

 

Im Allgemeinfall zerfällt die Permutation   in disjunkte Zyklen und die Ordnung von   ist dann gleich dem kleinsten gemeinsamen Vielfachen der Ordnungen der zugehörigen Untermatrizen.

Determinante

Bearbeiten

Die Determinante einer vorzeichenbehafteten Permutationsmatrix   mit Einträgen aus einem kommutativen Ring   ergibt sich nach dem Determinantenproduktsatz zu

 ,

wobei   das Vorzeichen der zu   zugehörigen Permutation   ist und   die Anzahl der Einträge mit Wert   in   ist. Vorzeichenbehaftete Permutationsmatrizen sind demnach unimodular, denn ihre Determinante kann nur die Werte   oder   annehmen.

Verwendung

Bearbeiten

Vorzeichenbehaftete Permutationen

Bearbeiten

Jede vorzeichenbehaftete Permutationsmatrix   entspricht genau einer vorzeichenbehafteten Permutation, also einer Permutation   der Menge  , für die   für   gilt. Die Einträge der zu der Permutation   zugehörigen Matrix   sind dabei gegeben als

 

Die Gruppe der vorzeichenbehafteten Permutationsmatrizen der Größe   ist isomorph zur Hyperoktaedergruppe, der Symmetriegruppe eines Hyperwürfels oder Kreuzpolytops im  -dimensionalen Raum.[2]

Hadamard-Matrizen

Bearbeiten

Eine Hadamard-Matrix ist eine quadratische Matrix mit Einträgen  , bei der alle Zeilen und alle Spalten zueinander orthogonal sind. Das Produkt einer Hadamard-Matrix mit einer vorzeichenbehafteten Permutationsmatrix ergibt wieder eine Hadamard-Matrix. Zwei Hadamard-Matrizen   und   sind dabei äquivalent, wenn es vorzeichenbehaftete Permutationsmatrizen   und   gibt, sodass

 

gilt. Die Äquivalenzklasse einer Hadamard-Matrix ist daher der Orbit einer Gruppenoperation, bei der die Transformationsgruppe das direkte Produkt der Gruppe der vorzeichenbehafteten Permutationen mit sich selbst ist.[1]

Literatur

Bearbeiten
  • Petteri Kaski, Patric R.J. Östergård: Classification Algorithms for Codes and Designs. Springer, 2006, ISBN 3-540-28991-7.
  • Michael Field: Lectures on Bifurcations, Dynamics and Symmetry. CRC Press, 1996, ISBN 0-582-30346-X.

Einzelnachweise

Bearbeiten
  1. a b c Petteri Kaski, Patric R.J. Östergård: Classification Algorithms for Codes and Designs. Springer, 2006, ISBN 3-540-28991-7, S. 63.
  2. Michael Field: Lectures on Bifurcations, Dynamics and Symmetry. CRC Press, 1996, ISBN 0-582-30346-X, S. 12–13.