Permutation matrix on arvau

Wikipedia / Permutation matrix

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. Pre-multiplying an -row matrix by a permutation matrix , forming , results in permuting the rows of , while post-multiplying an -column matrix , forming , permutes the columns of .

Every permutation matrix P is orthogonal, with its inverse equal to its transpose. Indeed, permutation matrices can be characterized as the orthogonal matrices whose entries are all non-negative.

The two permutation/matrix correspondences

There are two natural one-to-one correspondences between permutations and permutation matrices, one of which works along the rows of the matrix, the other along its columns. Here is an example, starting with a permutation in two-line form at the upper left:

The row-based correspondence takes the permutation otherwise.

The column-based correspondence takes and 0 otherwise. Since the two recipes differ only by swapping i with j.

Permutation matrices permute rows or columns

Multiplying a matrix M on either the left or the right will permute either the rows or columns of M by either or −1. The details are a bit tricky.

by some permutation . Arguing similarly about each of the slots, we find that the output vector is

. is sometimes called taking the alibi viewpoint would take the alias viewpoint.)

Now, suppose that we pre-multiply some n. By the rule for matrix multiplication is

, we have permuted the rows of M themselves by . A similar argument shows that post-multiplying an n-column matrix M permutes its columns by .

, and they permute the rows or columns respectively by −1, instead of by .

The transpose is also the inverse

A related argument proves that, as we claimed above, the transpose of any permutation matrix P also acts as its inverse, which implies that P is invertible. (Artin leaves that proof as an exercise, is then

column of P row of P, implying that P.

Multiplying permutation matrices

Given two permutations of elements and , the product of the corresponding column-based permutation matrices and is given, applies first and then This follows because pre-multiplying some matrix by and then pre-multiplying the resulting product by .

For the row-based matrices, there is a twist: The product of and is given by

with applied before in the composed permutation. This happens because we must post-multiply to avoid inversions under the row-based option, so we would post-multiply first by and then by .

Some people, when applying a function to an argument, write the function after the argument (postfix notation is defined either by

or, more elegantly, by

with applied first. That notation gives us a simpler rule for multiplying row-based permutation matrices:

Matrix group

When for all i, both and are the identity matrix.

There are permutation matrices, since there are is another such correspondence.) By the formulas above, those permutation matrices form a group of order under matrix multiplication, with the identity matrix as its identity element is a subgroup of the general linear group of invertible matrices of real numbers. Indeed, for any field F, where the matrix entries belong to F, but that sum doesn't arise.)

denote the symmetric group, or group of permutations, on {1,2,..., denote the opposite group that takes is a faithful representation that takes .

Doubly stochastic matrices

Every permutation matrix is doubly stochastic. The set of all doubly stochastic matrices is called the Birkhoff polytope, and the permutation matrices play a special role in that polytope. The Birkhoff–von Neumann theorem says that every doubly stochastic real matrix is a convex combination of permutation matrices of the same order, with the permutation matrices being precisely the extreme points (the vertices) of the Birkhoff polytope. The Birkhoff polytope is thus the convex hull of the permutation matrices.

Linear-algebraic properties

Just as each permutation is associated with two permutation matrices, each permutation matrix is associated with two permutations, as we can see by relabeling the example in the big square above starting with the matrix P at the upper right:

So we are here denoting the inverse of C and the inverse of R. We can then compute the linear-algebraic properties of P.

A point is fixed, and the trace of P is the number of such shared fixed points. If the integer k is one of them, then the standard basis vector is an eigenvector of P.

To calculate the complex eigenvalues of P as a composition of disjoint cycles roots of unity. The multiset is then the multiset of eigenvalues of P would give the same result. The multiplicity of any eigenvalue v is the number of i contains v. (Since any permutation matrix is normal and any normal matrix is diagonalizable over the complex numbers, the algebraic and geometric multiplicities of an eigenvalue v are the same.)

From group theory we know that any permutation may be written as a composition of transpositionss. Therefore, any permutation matrix factors as a product of row-switching elementary matrices, each of which has determinant 1. Thus, the determinant of the permutation matrix P is the sign.

Restricted forms

Costas array, a permutation matrix in which the displacement vectors between the entries are all distinct
n-queens puzzle, a permutation matrix in which there is at most one entry in each diagonal and antidiagonal