What Is a Permutation Matrix?

A permutation matrix is a square matrix in which every row and every column contains a single 1 and all the other elements are zero. Such a matrix, P say, is orthogonal, that is, P^TP = PP^T = I_n, so it is nonsingular and has determinant \pm 1. The total number of n\times n permutation matrices is n!.

Premultiplying a matrix by P reorders the rows and postmultiplying by P reorders the columns. A permutation matrix P that has the desired reordering effect is constructed by doing the same operations on the identity matrix.

Examples of permutation matrices are the identity matrix I_n, the reverse identity matrix J_n, and the shift matrix K_n (also called the cyclic permutation matrix), illustrated for n = 4 by

\notag   I_4 = \begin{bmatrix}   1 & 0 & 0 & 0  \\   0 & 1 & 0 & 0  \\   0 & 0 & 1 & 0  \\   0 & 0 & 0 & 1 \end{bmatrix}, \qquad   J_4 = \begin{bmatrix}   0 & 0 & 0 & 1  \\   0 & 0 & 1 & 0  \\   0 & 1 & 0 & 0  \\   1 & 0 & 0 & 0 \end{bmatrix}, \qquad   K_4 = \begin{bmatrix}   0 & 1 & 0 & 0  \\   0 & 0 & 1 & 0  \\   0 & 0 & 0 & 1  \\   1 & 0 & 0 & 0 \end{bmatrix}.

Pre- or postmultiplying a matrix by J_n reverses the order of the rows and columns, respectively. Pre- or postmultiplying a matrix by K_n shifts the rows or columns, respectively, one place forward and moves the first one to the last position—that is, it cyclically permutes the rows or columns. Note that J_n is a symmetric Hankel matrix and K_n is a circulant matrix.

An elementary permutation matrix P differs from I_n in just two rows and columns, i and j, say. It can be written P = I_n - (e_i-e_j)(e_i-e_j)^T, where e_i is the ith column of I_n. Such a matrix is symmetric and so satisfies P^2 = I_n, and it has determinant -1. A general permutation matrix can be written as a product of elementary permutation matrices P = P_1P_2\dots P_k, where k is such that \det(P) = (-1)^k.

It is easy to show that \det(\lambda I - K_n) = \lambda^n - 1, which means that the eigenvalues of K_n are 1, w, w^2, \dots, w^{n-1}, where w = \exp(2\pi\mathrm{i}/n) is the nth root of unity. The matrix K_n has two diagonals of 1s, which move up through the matrix as it is powered: K_n^i \ne I for i< n and K_n^n = I. The following animated gif superposes MATLAB spy plots of K_{64}, K_{64}^2, …, K_{64}^{64} = I_{64}.

shift_powers.gif

The shift matrix K_n plays a fundamental role in characterizing irreducible permutation matrices. Recall that a matrix A\in\mathbb{C}^{n\times n} is irreducible if there does not exist a permutation matrix P such that

\notag         P^TAP = \begin{bmatrix} A_{11} & A_{12} \\                                    0   & A_{22}                  \end{bmatrix},

where A_{11} and A_{22} are square, nonempty submatrices.

Theorem 1. For a permutation matrix P \in \mathbb{R}^{n \times n} the following conditions are equivalent.

  • P is irreducible.
  • There exists a permutation matrix Q such that Q^{-1}PQ = K_n
  • The eigenvalues of P are 1, w, w^2, \dots, w^{n-1}.

One consequence of Theorem 1 is that for any irreducible permutation matrix P, \mathrm{rank}(P - I) = \mathrm{rank}(K_n - I) = n-1.

The next result shows that a reducible permutation matrix can be expressed in terms of irreducible permutation matrices.

Theorem 2. Every reducible permutation matrix is permutation similar to a direct sum of irreducible permutation matrices.

Another notable permutation matrix is the vec-permutation matrix, which relates A\otimes B to B\otimes A, where \otimes is the Kronecker product.

A permutation matrix is an example of a doubly stochastic matrix: a nonnegative matrix whose row and column sums are all equal to 1. A classic result characterizes doubly stochastic matrices in terms of permutation matrices.

Theorem 3 (Birkhoff). A matrix is doubly stochastic if and only if it is a convex combination of permutation matrices.

In coding, memory can be saved by representing a permutation matrix P as an integer vector p, where p_i is the column index of the 1 within the ith row of P. MATLAB functions that return permutation matrices can also return the permutation in vector form. Here is an example with the MATLAB lu function that illustrates how permuting a matrix can be done using the vector permutation representation.

>> A = gallery('frank',4), [L,U,P] = lu(A); P
A =
     4     3     2     1
     3     3     2     1
     0     2     2     1
     0     0     1     1
P =
     1     0     0     0
     0     0     1     0
     0     0     0     1
     0     1     0     0
>> P*A
ans =
     4     3     2     1
     0     2     2     1
     0     0     1     1
     3     3     2     1
>> [L,U,p] = lu(A,'vector'); p
p =
     1     3     4     2
>> A(p,:)
ans =
     4     3     2     1
     0     2     2     1
     0     0     1     1
     3     3     2     1

For more on handling permutations in MATLAB see section 24.3 of MATLAB Guide.

Notes

For proofs of Theorems 1–3 see Zhang (2011, Sec. 5.6). Theorem 3 is also proved in Horn and Johnson (2013, Thm. 8.7.2).

Permutations play a key role in the fast Fourier transform and its efficient implementation; see Van Loan (1992).

References

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/index-of-what-is-articles/ and in PDF form from the GitHub repository https://github.com/higham/what-is.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s