Vorzeichenbehaftete Permutationsmatrix

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

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

$S=P\cdot D$   bzw.   $S=D\cdot P$

aus einer normalen Permutationsmatrix $P\in R^{n\times n}$ und einer Diagonalmatrix $D\in R^{n\times n}$ mit Einträgen $+1$ oder $-1$ auf der Hauptdiagonalen darstellen. Die beiden Darstellungen sind dabei äquivalent: in der ersten Darstellung entsprechen die Diagonaleinträge von $D$ jeweils den Spalteneinträgen ungleich null von $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 $3\times 3$ ist

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

denn es gilt

$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 $n\times n$ ist

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

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

Produkt

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

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

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

Inverse

Eine vorzeichenbehaftete Permutationsmatrix $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 $\operatorname {GL} (n,R)$, spezieller eine Untergruppe der monomialen Gruppe $\operatorname {M} (n,R)$. Die Inverse einer vorzeichenbehafteten Permutationsmatrix ergibt sich dabei zu

$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 $\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 $S\in R^{n\times n}$ gibt es dabei eine Potenz $k$, sodass

$S^{k}=I$

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

$\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 $\pi$ in disjunkte Zyklen und die Ordnung von $S$ ist dann gleich dem kleinsten gemeinsamen Vielfachen der Ordnungen der zugehörigen Untermatrizen.

Determinante

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

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

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

Verwendung

Vorzeichenbehaftete Permutationen

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

$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 $n\times n$ ist isomorph zur Hyperoktaedergruppe, der Symmetriegruppe eines Hyperwürfels oder Kreuzpolytops im $n$-dimensionalen Raum.

Hadamard-Matrizen

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

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

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.

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.