Permutation matrix

Permutation matrix of the permutation (3,5,8,1,7,4,2,6). The red dots show the entries.

A permutation or permutation matrix is in mathematics a matrix where exactly in each row and each column an entry is one, and all other entries are zero. Every permutation matrix corresponds exactly to one permutation of a finite set of numbers. If a permutation matrix is multiplied by a vector , the components of the vector are swapped according to this permutation. Permutation matrices are orthogonal , double-stochastic and integer unimodular . The set of permutation matrices of fixed size forms a subgroup of the general linear group with the matrix multiplication . Permutation matrices are used in linear algebra , combinatorics and cryptography , among others .

definition

A permutation matrix is ​​a square matrix in which exactly one entry per row and column is the same and all other entries are the same . In general, and are the one element and zero element of an underlying ring (in practice mostly the real numbers ). Each permutation matrix of size corresponds exactly to one permutation of the numbers from to . The permutation matrix belonging to a permutation ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle n\times n}$ ${\displaystyle (\pi (1),\ldots ,\pi (n))}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle \pi \in S_{n}}$

${\displaystyle P_{\pi }=(p_{ij})\in R^{n\times n}}$

then has as entries

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

If exactly two numbers are exchanged with one another through the permutation , then one also calls an exchange matrix . If the -th canonical unit vector is a row vector, then the permutation matrix can also be passed through ${\displaystyle \pi }$ ${\displaystyle P_{\pi }}$ ${\displaystyle e_{i}}$ ${\displaystyle i}$ ${\displaystyle P_{\pi }}$

${\displaystyle P_{\pi }={\begin{pmatrix}e_{\pi (1)}\\\vdots \\e_{\pi (n)}\end{pmatrix}}}$

represent. Occasionally, however, the reverse variant is also found in the literature, in which the unit vectors are put together in columns, whereby the permutation matrices are correspondingly transposed . In the following, however, the more common first variant is used.

example

The one to the permutation

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\4&2&1&5&3\\\end{pmatrix}}\in S_{5}}$

associated permutation matrix is

${\displaystyle P_{\pi }={\begin{pmatrix}e_{4}\\e_{2}\\e_{1}\\e_{5}\\e_{3}\end{pmatrix}}={\begin{pmatrix}0&0&0&1&0\\0&1&0&0&0\\1&0&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{pmatrix}}\in R^{5\times 5}}$.

After the number is mapped onto the number through the permutation, for example , the fifth row of is found in the third column. ${\displaystyle \pi }$ ${\displaystyle 5}$ ${\displaystyle 3}$ ${\displaystyle P_{\pi }}$ ${\displaystyle 1}$

application

If a permutation matrix is multiplied by a given column vector , the result is the matrix-vector product ${\displaystyle v=(v_{1},\ldots ,v_{n})^{T}}$

${\displaystyle P_{\pi }\cdot v={\begin{pmatrix}e_{\pi (1)}\\\vdots \\e_{\pi (n)}\end{pmatrix}}\cdot {\begin{pmatrix}v_{1}\\\vdots \\v_{n}\end{pmatrix}}={\begin{pmatrix}v_{\pi (1)}\\\vdots \\v_{\pi (n)}\end{pmatrix}}}$

a new column vector whose entries have been swapped according to the permutation . For example , then the matrix-vector product with the above example permutation matrix gives the column vector ${\displaystyle \pi }$ ${\displaystyle v=(v_{1},v_{2},v_{3},v_{4},v_{5})^{T}}$

${\displaystyle P_{\pi }\cdot v={\begin{pmatrix}0&0&0&1&0\\0&1&0&0&0\\1&0&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{pmatrix}}\cdot {\begin{pmatrix}v_{1}\\v_{2}\\v_{3}\\v_{4}\\v_{5}\end{pmatrix}}={\begin{pmatrix}v_{4}\\v_{2}\\v_{1}\\v_{5}\\v_{3}\end{pmatrix}}.}$

If a matrix is ​​multiplied by a permutation matrix from the left, the rows of the matrix are swapped according to the permutation. Conversely, the multiplication of a row vector with the transposed permutation matrix results in a row vector with elements swapped according to the permutation , that is ${\displaystyle \pi }$

${\displaystyle v^{T}\cdot P_{\pi }^{T}={\begin{pmatrix}v_{1}&\ldots &v_{n}\end{pmatrix}}\cdot {\begin{pmatrix}e_{\pi (1)}^{T}&\ldots &e_{\pi (n)}^{T}\end{pmatrix}}={\begin{pmatrix}v_{\pi (1)}&\ldots &v_{\pi (n)}\end{pmatrix}}}$.

For the above example one obtains

${\displaystyle v^{T}\cdot P_{\pi }^{T}={\begin{pmatrix}v_{1}&v_{2}&v_{3}&v_{4}&v_{5}\end{pmatrix}}\cdot {\begin{pmatrix}0&0&1&0&0\\0&1&0&0&0\\0&0&0&0&1\\1&0&0&0&0\\0&0&0&1&0\end{pmatrix}}={\begin{pmatrix}v_{4}&v_{2}&v_{1}&v_{5}&v_{3}\end{pmatrix}}.}$

If a matrix is ​​multiplied from the right with the transposed permutation matrix, the columns of the matrix are swapped according to the permutation.

properties

Group table of the 3! = 6 permutations of a 3-element set. The product of two permutation matrices is again a permutation matrix.

Positions of the 6 dies in the group table above. Only the unit matrices are symmetrical to the main diagonal, so the symmetrical group is not Abelian. These are also permutation matrices, hence the drawn cycles.

Inverse

Permutation matrices are always invertible , the inverse of a permutation matrix being its transpose. The transposed matrix is ​​the permutation matrix of the inverse permutation , so it applies

${\displaystyle P_{\pi }^{-1}=P_{\pi }^{T}=P_{\pi ^{-1}}}$.

Real permutation matrices are therefore always orthogonal and have full rank . ${\displaystyle n}$

product

The product of two permutation matrices is again a permutation matrix which corresponds to the execution of the associated permutations one after the other . The permutation matrix of the successive execution of two permutations results in ${\displaystyle \pi ,\sigma \in S_{n}}$

${\displaystyle P_{\pi \circ \sigma }=P_{\sigma }\cdot P_{\pi }}$.

The figure thus represents an antihomomorphism . The set of permutation matrices together with the matrix multiplication form a group , namely a subgroup of the general linear group . Each permutation matrix can be represented as a product of elementary row-interchanging matrices. ${\displaystyle \pi \mapsto P_{\pi }}$ ${\displaystyle \mathrm {GL} (n,R)}$

Potencies

Integer powers of permutation matrices are again permutation matrices. For every permutation matrix there is a power such that ${\displaystyle P_{\pi }}$ ${\displaystyle k}$

${\displaystyle P_{\pi }^{k}=I}$

where is the identity matrix . The smallest positive with this property is equal to the order of in the general linear group. This order is equal to the least common multiple of the lengths of the disjoint cycles of . ${\displaystyle I}$ ${\displaystyle k}$ ${\displaystyle P_{\pi }}$ ${\displaystyle \pi }$

Determinant

The determinant of a permutation matrix is ​​either or and corresponds to the sign of the associated permutation: ${\displaystyle +1}$ ${\displaystyle -1}$

${\displaystyle \det(P_{\pi })=\operatorname {sgn} (\pi )}$.

A permutation matrix over the whole numbers is therefore an integer unimodular matrix . The trace of an integer permutation matrix corresponds to the number of fixed points of the permutation.

Eigenvalues

The eigenvalues ​​of a real permutation matrix are not necessarily all real, but they lie on the complex unit circle . If the lengths of the cycles are a permutation , then the eigenvalues ​​of the associated permutation matrix are the complex roots of unit ${\displaystyle l_{1},\ldots ,l_{s}}$ ${\displaystyle \pi }$ ${\displaystyle P_{\pi }}$

${\displaystyle \lambda _{jk}=e^{2\pi ik/l_{j}}}$

for and . A real permutation matrix accordingly has the eigenvalue , where and are coprime if the underlying permutation has at least one cycle whose length is divisible by . The multiplicity of this eigenvalue then corresponds to the number of such cycles. A real permutation matrix therefore always has the eigenvalue with a multiplicity equal to the total number of cycles of the underlying permutation. ${\displaystyle j=1,\ldots ,s}$ ${\displaystyle k=1,\ldots ,l_{j}}$ ${\displaystyle e^{2\pi ik/m}}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle 1}$ ${\displaystyle s}$

Norms

Since real permutation matrices are orthogonal, the following applies to their spectral norm

${\displaystyle \|P_{\pi }\|_{2}=1}$.

For the column and row sum norm of a real permutation matrix it also results

${\displaystyle \|P_{\pi }\|_{1}=\|P_{\pi }\|_{\infty }=1}$.

A real permution matrix is ​​therefore a double-stochastic matrix . According to Birkhoff's and von Neumann's theorem , a square matrix is ​​double-stochastic if and only if it is a convex combination of permutation matrices.

Special cases

• The permutation matrix of identical permutation is the identity matrix .
• A permutation matrix is symmetric if and only if the underlying permutation is itself inverse .
• If a permutation matrix has a block structure , then the underlying permutation can be represented as the sum of permutations .

use

	a	b	c	d	e	f	G	H
8th									8th
7th									7th
6th									6th
5									5
4th									4th
3									3
2									2
1									1
	a	b	c	d	e	f	G	H

Eight rooks that do not attack each other on a chessboard

Permutation matrices are used, among other things:

• in linear algebra as elementary matrices in Gaussian elimination for the solution of linear systems of equations
• in combinatorics in the matrix representation of permutation groups
• in cryptography as components of block encryption methods

In chess mathematics , the permutation matrices are precisely the solution to the problem of distributing rooks on a chessboard of the size so that no rooks attack each other. More difficult to solve is the queens problem , where the rooks are replaced by queens who can attack diagonally. The solutions to the queens problem are also permutation matrices. ${\displaystyle n}$ ${\displaystyle n\times n}$

generalization

→ Main article : Monomial matrix

A generalized permutation matrix or monomial matrix is ​​a square matrix in which exactly one entry per row and column is not equal . Monomial matrices have the representation ${\displaystyle G\in R^{n\times n}}$ ${\displaystyle 0}$

${\displaystyle G=P\cdot D}$,

where is an ordinary permutation matrix and a diagonal matrix whose diagonal entries are all unequal . The regular monomial matrices together with the matrix multiplication as a link form the monomial group , a further subgroup of the general linear group . Special monomial matrices are signed permutation matrices in which there is exactly one entry or in each row and each column and all other entries are ${\displaystyle P\in R^{n\times n}}$ ${\displaystyle D\in R^{n\times n}}$ ${\displaystyle 0}$ ${\displaystyle \operatorname {M} (n,R)}$ ${\displaystyle \operatorname {GL} (n,R)}$ ${\displaystyle +1}$ ${\displaystyle -1}$ ${\displaystyle 0}$

See also

• Levi Civita symbol
• Rothe diagram
• Irreducible matrix
• Cyclic matrix

literature

• Siegfried Bosch: Linear Algebra . Springer, 2006, ISBN 3-540-29884-3 .
• Jörg Liesen, Volker Mehrmann: Linear Algebra . Springer, 2012, ISBN 978-3-8348-8290-5 .

Individual evidence

1. ^ Jörg Liesen, Volker Mehrmann: Lineare Algebra . Springer, 2011, p. 45 .
2. ^ Siegfried Bosch : Linear Algebra . Springer, 2006, p. 275 .

Web links

• Eric W. Weisstein : Permutation Matrix . In: MathWorld (English).
• Wkbj79: Permutation Matrix . In: PlanetMath . (English)