Permutation matrix

A permutation matrix or Vertauschungsmatrix is in mathematics, a matrix in which exactly one entry in each row and in each column one and all other entries are zero. Each permutation corresponds exactly to a permutation of a finite set of numbers. Is a permutation matrix is multiplied with a vector, the components of the vector are reversed in accordance with this permutation. Permutation matrices are orthogonal, doubly - stochastic and integer unimodular. The set of permutation matrices of fixed size forms with the matrix multiplication is a subgroup of the general linear group. Permutation matrices are used inter alia in linear algebra, combinatorics, and cryptography.

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 equal. Here, in general, and the unit element, and a zero element underlying ring ( in practice usually the real numbers ). Each permutation of size corresponds exactly to a permutation of the numbers up. The associated to a permutation permutation matrix

Then as entries

Be the permutation exactly two numbers reversed, also referred to as Vertauschungsmatrix. If the -th canonical unit vector as a row vector, then the permutation matrix can also be

Represent. Occasionally, however, finds in the literature, the reverse variant in which the unit vectors are columns composed, so that the permutation matrices are transposed accordingly. In the following, however, the more common first variant is used.

Example

The to the permutation

Corresponding permutation matrix is

For example, after the number is mapped to the number by the permutation, can be found in the fifth line of the third in the column.

Application

Is a permutation matrix is multiplied with a given column vector, then yields the matrix-vector product

A new column vector whose entries were reversed according to the permutation. Is, for example, then the matrix-vector product of the above example results in the column vector permutation

Similarly, the multiplication of a row vector by a permutation matrix again yields a row vector with a correspondingly permuted elements. If a permutation matrix from left multiplied by another matrix, then the rows of the matrix are permuted according to the permutation. Is a permutation matrix of right multiplied by a matrix, the columns of the matrix instead be interchanged.

Properties

Inverse

Permutation matrices are orthogonal matrices, therefore there exists a unique inverse, namely the permutation matrix of the inverse permutation, and we have:

Permutation therefore always have full rank.

Product

The permutation matrix of the sequential execution of two permutations is given by

The set of permutation matrices thus forms together with the matrix multiplication is a group, one subgroup of the general linear group. Each permutation can be represented as a product of elementary matrices zeilenvertauschenden.

Determinant

The determinant of a permutation matrix is either or and corresponds to the sign of the corresponding permutation:

A permutation matrix over the integers is therefore an integer unimodular matrix. The trace of a permutation is the number of fixed points of the permutation.

Standardize

For the column and row sum norm of a permutation matrix is obtained

A Permutionsmatrix is thus a doubly stochastic matrix. By the theorem of Birkhoff and von Neumann, a square matrix is exactly then double - stochastic if it is a convex combination of permutation matrices.

Special cases

• The permutation of the identical permutation is the identity matrix.
• A permutation matrix is symmetric if the underlying permutation is self-inverse.
• Assigns a permutation a Blockstuktur on, then can the underlying permutation written as the sum of permutations.

Use

Permutation matrices may be used, among other things:

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

In the chess mathematics permutation just make the solutions to the problem of distributing towers on a chessboard of size such that no attack towers against each other. More difficult to resolve is the women's issue in which the towers are replaced by women and its solutions are also permutation matrices.