Signed permutation matrix

In mathematics, a signed permutation matrix is a square matrix in which exactly one entry is plus or minus one in each row and each column and all other entries are zero. Signed permutation matrices thus represent a generalization of ordinary permutation matrices and are a special case of monomial matrices . They are exactly the integer orthogonal matrices . The group of signed permutation matrices is isomorphic to the hyperoctahedral group , the symmetry group of a hypercube or cross polytope .

definition

A signed permutation matrix is ​​a square matrix in which exactly one entry per row and column is or and all other entries are. In general, and are the one element and zero element of an underlying ring . Every signed permutation matrix can be used as a product ${\displaystyle +1}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle S\in R^{n\times n}}$

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

from a normal permutation matrix and a diagonal matrix with entries or on the main diagonal . The two representations are equivalent: in the first representation the diagonal entries of each correspond to the column entries not equal to zero from , in the second representation the line entries not equal to zero in each case; the two permutation matrices agree. ${\displaystyle P\in R^{n\times n}}$ ${\displaystyle D\in R^{n\times n}}$ ${\displaystyle +1}$ ${\displaystyle -1}$ ${\displaystyle D}$ ${\displaystyle S}$

example

An example of a signed permutation matrix of magnitude is ${\displaystyle 3\times 3}$

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

because it applies

${\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}}}$.

properties

number

The number of different signed permutation matrices of magnitude is ${\displaystyle n\times n}$

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

where denotes the double faculty . Namely, there are different permutation matrices of magnitude and possible choices for the signs. ${\displaystyle {}!!}$ ${\displaystyle n!}$ ${\displaystyle n\times n}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$

product

The product of two signed permutation matrices is again a signed permutation matrix, because it holds ${\displaystyle S,S'\in R^{n\times n}}$

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

where is the diagonal matrix that results from swapping rows and columns according to the underlying permutation . ${\displaystyle {\bar {D}}=(P')^{T}\cdot D\cdot P'}$ ${\displaystyle D}$ ${\displaystyle P'}$

Inverse

A signed permutation matrix is always invertible . The set of signed permutations therefore forms a subgroup of the general linear group , more specifically a subgroup of the monomial group, with the matrix multiplication as a link . The inverse of a signed permutation matrix is ​​given by ${\displaystyle S\in R^{n\times n}}$ ${\displaystyle \operatorname {GL} (n,R)}$ ${\displaystyle \operatorname {M} (n,R)}$

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

and is therefore equal to her transpose . Real signed permutation matrices are therefore orthogonal and their matrix group is a subgroup of the orthogonal group . This subgroup consists exactly of the integer orthogonal matrices. ${\displaystyle \operatorname {O} (n)}$

Potencies

Integer powers of signed permutation matrices are again signed permutation matrices. For every signed permutation matrix there is a power such that ${\displaystyle S\in R^{n\times n}}$ ${\displaystyle k}$

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

where is the identity matrix . The smallest positive with this property is equal to the order of in the general linear group. If the associated permutation represents a single cycle of length and denotes the number of entries with a value in , then the order of ${\displaystyle I}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle \pi }$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle -1}$ ${\displaystyle D}$ ${\displaystyle S}$

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

In the general case, the permutation breaks down into disjoint cycles and the order of is then equal to the smallest common multiple of the orders of the associated sub-matrices . ${\displaystyle \pi }$ ${\displaystyle S}$

Determinant

The determinant of a signed permutation matrix with entries from a commutative ring arising after the determinants product set to ${\displaystyle S\in R^{n\times n}}$ ${\displaystyle R}$

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

where is the sign of the associated permutation and the number of entries with value in . Signed permutation matrices are therefore unimodular , because their determinant can only take the values or . ${\displaystyle \operatorname {sgn} (\pi )}$ ${\displaystyle P}$ ${\displaystyle \pi }$ ${\displaystyle m}$ ${\displaystyle -1}$ ${\displaystyle D}$ ${\displaystyle +1}$ ${\displaystyle -1}$

use

Signed permutations

Each signed permutation corresponds exactly to a signed permutation , that is a permutation of the amount for which to apply. The entries of the matrix belonging to the permutation are given as ${\displaystyle S\in R^{n\times n}}$ ${\displaystyle \pi }$ ${\displaystyle \{-n,\ldots ,n\}}$ ${\displaystyle \pi (-i)=-\pi (i)}$ ${\displaystyle i=0,\ldots ,n}$ ${\displaystyle \pi }$ ${\displaystyle S_{\pi }=(s_{ij})}$

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

The group of signed permutation matrices of size is isomorphic to the hyperoctahedral group , the symmetry group of a hypercube or cross polytope in -dimensional space. ${\displaystyle n\times n}$ ${\displaystyle n}$

Hadamard matrices

A Hadamard matrix is a square matrix with entries in which all rows and all columns are orthogonal to one another. The product of a Hadamard matrix with a signed permutation matrix again gives a Hadamard matrix. Two Hadamard matrices and are equivalent if there are signed permutation matrices and such that ${\displaystyle \pm 1}$ ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle S}$ ${\displaystyle T}$

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

applies. The equivalence class of a Hadamard matrix is ​​therefore the orbit of a group operation in which the transformation group is the direct product of the group of signed permutations with itself.

literature

• Petteri Kaski, Patric RJ Ö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 .

Individual evidence

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