Permutation matrix

Matrices representing permutation of vector elements; with exactly one 1 per row and column

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 and 0s elsewhere. Each such matrix, say P, represents a permutation of m elements and, when used to multiply another matrix, say A, results in permuting the rows (when pre-multiplying, to form PA) or columns (when post-multiplying, to form AP) of the matrix A.

there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the m × m identity matrix, Im, either permute the columns or permute the rows, according to π. Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to the other representation. This article will primarily deal with just one of these representations and the other will only be mentioned when there is a difference to be aware of.

The m × m permutation matrix Pπ = (pij) obtained by permuting the columns of the identity matrix Im, that is, for each i, pij = 1 if j = π(i) and pij = 0 otherwise, will be referred to as the column representation in this article.[1] Since the entries in row i are all 0 except that a 1 appears in column π(i), we may write

Observe that the jth column of the I5 identity matrix now appears as the π(j)th column of Pπ.

The other representation, obtained by permuting the rows of the identity matrix Im, that is, for each j, pij = 1 if i = π(j) and pij = 0 otherwise, will be referred to as the row representation.

The column representation of a permutation matrix is used throughout this section, except when otherwise indicated.

Again, repeated application of this result shows that post-multiplying a matrix M by the permutation matrix Pπ, that is, M Pπ, results in permuting the columns of M. Notice also that

Given two permutations π and σ of m elements, the corresponding permutation matrices Pπ and Pσ acting on column vectors are composed with

The same matrices acting on row vectors (that is, post-multiplication) compose according to the same rule

To be clear, the above formulas use the prefix notation for permutation composition, that is,

If (1) denotes the identity permutation, then P(1) is the identity matrix.

The map Sn → GL(n, Z2) that sends a permutation to its column representation is a faithful representation.

A permutation matrix is itself a doubly stochastic matrix, but it also plays a special role in the theory of these matrices. The Birkhoff–von Neumann theorem says that every doubly stochastic real matrix is a convex combination of permutation matrices of the same order and the permutation matrices are precisely the extreme points of the set of doubly stochastic matrices. That is, the Birkhoff polytope, the set of doubly stochastic matrices, is the convex hull of the set of permutation matrices.[3]

The trace of a permutation matrix is the number of fixed points of the permutation. If the permutation has fixed points, so it can be written in cycle form as π = (a1)(a2)...(ak where σ has no fixed points, then ea1,ea2,...,eak are eigenvectors of the permutation matrix.

From group theory we know that any permutation may be written as a product of transpositions. Therefore, any permutation matrix P factors as a product of row-interchanging elementary matrices, each having determinant −1. Thus, the determinant of a permutation matrix P is the signature of the corresponding permutation.

When a matrix M is multiplied by a permutation matrix P on the left to make PM, the product is the result of permuting the rows of M. As a special case, if M is a column vector, then PM is the result of permuting the entries of M:

When instead M is multiplied by a permutation matrix on the right to make MP, the product is the result of permuting the columns of M. As a special case, if M is a row vector, then MP is the result of permuting the entries of M:

where eai represents the ith basis vector (as a row) for Rj, and where

Now, in performing matrix multiplication, one essentially forms the dot product of each row of the first matrix with each column of the second. In this instance, we will be forming the dot product of each row of this matrix with the vector of elements we want to permute. That is, for example, = (g0,...,g5)T,

So, the product of the permutation matrix with the vector v above, will be a vector in the form (ga1, ga2, ..., gaj), and that this then is a permutation of v since we have said that the permutation form is

So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.