Vorzeichenbehaftete Permutationsmatrix

Eine vorzeichenbehaftete Permutationsmatrix i​st in d​er Mathematik e​ine quadratische Matrix, b​ei der i​n jeder Zeile u​nd jeder Spalte g​enau ein Eintrag p​lus oder m​inus eins i​st und a​lle übrigen Einträge n​ull sind. Vorzeichenbehaftete Permutationsmatrizen stellen d​amit eine Verallgemeinerung gewöhnlicher Permutationsmatrizen d​ar und s​ind ein Spezialfall monomialer Matrizen. Sie s​ind genau d​ie ganzzahligen orthogonalen Matrizen. Die Gruppe d​er vorzeichenbehafteten Permutationsmatrizen i​st isomorph z​ur Hyperoktaedergruppe, d​er Symmetriegruppe e​ines Hyperwürfels o​der Kreuzpolytops.

Definition

Eine vorzeichenbehaftete Permutationsmatrix ist eine quadratische Matrix, bei der genau ein Eintrag pro Zeile und Spalte ${\displaystyle +1}$ oder ${\displaystyle -1}$ ist und alle anderen Einträge ${\displaystyle 0}$ sind. Hierbei sind im Allgemeinen ${\displaystyle 1}$ und ${\displaystyle 0}$ das Einselement und Nullelement eines zugrunde liegenden Rings ${\displaystyle R}$. Jede vorzeichenbehaftete Permutationsmatrix ${\displaystyle S\in R^{n\times n}}$ lässt sich als Produkt

${\displaystyle S=P\cdot D}$   bzw.   ${\displaystyle S=D\cdot P}$

aus einer normalen Permutationsmatrix ${\displaystyle P\in R^{n\times n}}$ und einer Diagonalmatrix ${\displaystyle D\in R^{n\times n}}$ mit Einträgen ${\displaystyle +1}$ oder ${\displaystyle -1}$ auf der Hauptdiagonalen darstellen.[1] Die beiden Darstellungen sind dabei äquivalent: in der ersten Darstellung entsprechen die Diagonaleinträge von ${\displaystyle D}$ jeweils den Spalteneinträgen ungleich null von ${\displaystyle S}$, in der zweiten Darstellung jeweils den Zeileneinträgen ungleich null; die beiden Permutationsmatrizen stimmen überein.

Beispiel

Ein Beispiel für eine vorzeichenbehaftete Permutationsmatrix der Größe ${\displaystyle 3\times 3}$ ist

${\displaystyle S={\begin{pmatrix}0&+1&0\\0&0&-1\\-1&0&0\end{pmatrix}}}$,

denn e​s gilt

${\displaystyle S={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}\cdot {\begin{pmatrix}-1&0&0\\0&+1&0\\0&0&-1\end{pmatrix}}={\begin{pmatrix}+1&0&0\\0&-1&0\\0&0&-1\end{pmatrix}}\cdot {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}}$.

Eigenschaften

Anzahl

Die Anzahl verschiedener vorzeichenbehafteter Permutationsmatrizen der Größe ${\displaystyle n\times n}$ ist

${\displaystyle 2^{n}\cdot n!=(2n)!!=2\cdot 4\cdot \ldots \cdot 2n}$,

wobei ${\displaystyle {}!!}$ die Doppelfakultät bezeichnet. Es gibt nämlich ${\displaystyle n!}$ verschiedene Permutationsmatrizen der Größe ${\displaystyle n\times n}$ und ${\displaystyle 2^{n}}$ mögliche Wahlen für die ${\displaystyle n}$ Vorzeichen.

Produkt

Das Produkt zweier vorzeichenbehafteter Permutationsmatrizen ${\displaystyle S,S'\in R^{n\times n}}$ ist wieder eine vorzeichenbehaftete Permutationsmatrix, denn es gilt

${\displaystyle S\cdot S'=(P\cdot D)\cdot (P'\cdot D')=(P\cdot P')\cdot ({\bar {D}}\cdot D')}$,

wobei ${\displaystyle {\bar {D}}=(P')^{T}\cdot D\cdot P'}$ die Diagonalmatrix ist, die aus ${\displaystyle D}$ durch Zeilen- und Spaltenvertauschungen gemäß der ${\displaystyle P'}$ zugrunde liegenden Permutation entsteht.[1]

Inverse

Eine vorzeichenbehaftete Permutationsmatrix ${\displaystyle S\in R^{n\times n}}$ ist stets invertierbar. Die Menge der vorzeichenbehafteten Permutationen bildet daher mit der Matrizenmultiplikation als Verknüpfung eine Untergruppe der allgemeinen linearen Gruppe ${\displaystyle \operatorname {GL} (n,R)}$, spezieller eine Untergruppe der monomialen Gruppe ${\displaystyle \operatorname {M} (n,R)}$. Die Inverse einer vorzeichenbehafteten Permutationsmatrix ergibt sich dabei zu

${\displaystyle S^{-1}=(P\cdot D)^{-1}=D^{-1}\cdot P^{-1}=D^{T}\cdot P^{T}=(P\cdot D)^{T}=S^{T}}$

und ist demnach gleich ihrer Transponierten. Reelle vorzeichenbehaftete Permutationsmatrizen sind daher orthogonal und ihre Matrizengruppe ist eine Untergruppe der orthogonalen Gruppe ${\displaystyle \operatorname {O} (n)}$. Diese Untergruppe besteht genau aus den ganzzahligen orthogonalen Matrizen.

Potenzen

Ganzzahlige Potenzen vorzeichenbehafteter Permutationsmatrizen sind wieder vorzeichenbehaftete Permutationsmatrizen. Für jede vorzeichenbehaftete Permutationsmatrix ${\displaystyle S\in R^{n\times n}}$ gibt es dabei eine Potenz ${\displaystyle k}$, sodass

${\displaystyle S^{k}=I}$

ergibt, wobei ${\displaystyle I}$ die Einheitsmatrix ist. Das kleinste positive ${\displaystyle k}$ mit dieser Eigenschaft ist gleich der Ordnung von ${\displaystyle S}$ in der allgemeinen linearen Gruppe. Stellt die zu ${\displaystyle P}$ zugehörige Permutation ${\displaystyle \pi }$ einen einzelnen Zyklus der Länge ${\displaystyle n}$ dar und bezeichnet ${\displaystyle m}$ die Anzahl der Einträge mit Wert ${\displaystyle -1}$ in ${\displaystyle D}$, dann gilt für die Ordnung von ${\displaystyle S}$

${\displaystyle \operatorname {ord} (S)={\begin{cases}n&{\text{falls}}~m~{\text{gerade ist,}}\\2n&{\text{falls}}~m~{\text{ungerade ist.}}\end{cases}}}$

Im Allgemeinfall zerfällt die Permutation ${\displaystyle \pi }$ in disjunkte Zyklen und die Ordnung von ${\displaystyle S}$ ist dann gleich dem kleinsten gemeinsamen Vielfachen der Ordnungen der zugehörigen Untermatrizen.

Determinante

Die Determinante einer vorzeichenbehafteten Permutationsmatrix ${\displaystyle S\in R^{n\times n}}$ mit Einträgen aus einem kommutativen Ring ${\displaystyle R}$ ergibt sich nach dem Determinantenproduktsatz zu

${\displaystyle \det(S)=\det(P)\cdot \det(D)=\operatorname {sgn} (\pi )\cdot (-1)^{m}}$,

wobei ${\displaystyle \operatorname {sgn} (\pi )}$ das Vorzeichen der zu ${\displaystyle P}$ zugehörigen Permutation ${\displaystyle \pi }$ ist und ${\displaystyle m}$ die Anzahl der Einträge mit Wert ${\displaystyle -1}$ in ${\displaystyle D}$ ist. Vorzeichenbehaftete Permutationsmatrizen sind demnach unimodular, denn ihre Determinante kann nur die Werte ${\displaystyle +1}$ oder ${\displaystyle -1}$ annehmen.

Verwendung

Vorzeichenbehaftete Permutationen

Jede vorzeichenbehaftete Permutationsmatrix ${\displaystyle S\in R^{n\times n}}$ entspricht genau einer vorzeichenbehafteten Permutation, also einer Permutation ${\displaystyle \pi }$ der Menge ${\displaystyle \{-n,\ldots ,n\}}$, für die ${\displaystyle \pi (-i)=-\pi (i)}$ für ${\displaystyle i=0,\ldots ,n}$ gilt. Die Einträge der zu der Permutation ${\displaystyle \pi }$ zugehörigen Matrix ${\displaystyle S_{\pi }=(s_{ij})}$ sind dabei gegeben als

${\displaystyle s_{ij}={\begin{cases}+1,&{\text{falls }}\pi (i)=j\\-1,&{\text{falls }}\pi (i)=-j\\0,&{\text{sonst.}}\end{cases}}}$

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

Hadamard-Matrizen

Eine Hadamard-Matrix ist eine quadratische Matrix mit Einträgen ${\displaystyle \pm 1}$, 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 ${\displaystyle H_{1}}$ und ${\displaystyle H_{2}}$ sind dabei äquivalent, wenn es vorzeichenbehaftete Permutationsmatrizen ${\displaystyle S}$ und ${\displaystyle T}$ gibt, sodass

${\displaystyle H_{2}=S\cdot H_{1}\cdot T^{-1}}$

gilt. Die Äquivalenzklasse e​iner Hadamard-Matrix i​st daher d​er Orbit e​iner Gruppenoperation, b​ei der d​ie Transformationsgruppe d​as direkte Produkt d​er Gruppe d​er vorzeichenbehafteten Permutationen m​it sich selbst ist.[1]

Literatur

• 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

1. 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.