Vorzeichenbehaftete Permutationsmatrix

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.

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]

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.

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.

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.

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]

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 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]