A *permutation matrix* is a square matrix in which every row and every column contains a single and all the other elements are zero. Such a matrix, say, is orthogonal, that is, , so it is nonsingular and has determinant . The total number of permutation matrices is .

Premultiplying a matrix by reorders the rows and postmultiplying by reorders the columns. A permutation matrix 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 , the reverse identity matrix , and the shift matrix (also called the cyclic permutation matrix), illustrated for by

Pre- or postmultiplying a matrix by reverses the order of the rows and columns, respectively. Pre- or postmultiplying a matrix by 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 is a symmetric Hankel matrix and is a circulant matrix.

An *elementary permutation matrix* differs from in just two rows and columns, and , say. It can be written , where is the th column of . Such a matrix is symmetric and so satisfies , and it has determinant . A general permutation matrix can be written as a product of elementary permutation matrices , where is such that .

It is easy to show that , which means that the eigenvalues of are , where is the th root of unity. The matrix has two diagonals of s, which move up through the matrix as it is powered: for and . The following animated gif superposes MATLAB spy plots of , , â€¦, .

The shift matrix plays a fundamental role in characterizing irreducible permutation matrices. Recall that a matrix is irreducible if there does not exist a permutation matrix such that

where and are square, nonempty submatrices.

For a permutation matrix the following conditions are equivalent.Theorem 1.

- is irreducible.
- There exists a permutation matrix such that
- The eigenvalues of are .

One consequence of Theorem 1 is that for any irreducible permutation matrix , .

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

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

Another notable permutation matrix is the vec-permutation matrix, which relates to , where 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 . A classic result characterizes doubly stochastic matrices in terms of permutation matrices.

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

In coding, memory can be saved by representing a permutation matrix as an integer vector , where is the column index of the within the th row of . 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

- Desmond Higham and Nicholas Higham, MATLAB Guide, third edition, SIAM, 2017.
- Roger A. Horn and Charles R. Johnson, Matrix Analysis, second edition, Cambridge University Press, 2013. My review of the second edition.
- Charles F. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, 1992.
- Fuzhen Zhang, Matrix Theory: Basic Results and Techniques, Springer, 2011.

## 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.