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.
Theorem 1. For a permutation matrix the following conditions are equivalent.
- 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.
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 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.
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 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.
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).
- 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.