A permutation matrix is a square matrix whose entries are all 0 or 1, with exactly one 1 in each row and each column. It represents a permutation of a finite set as a linear transformation that rearranges coordinates. Multiplying a matrix by a permutation matrix reorders its rows or columns without changing their entries. Permutation matrices connect linear algebra with combinatorics and group theory, and are widely used in numerical computation, graph algorithms, and optimization.
Definition and conventions
Let be a permutation of , and let be the standard coordinate vectors. Define its permutation matrix by
Equivalently,
Thus column is the vector . Every permutation matrix determines exactly one permutation, so there are such matrices.
For a column vector ,
The inverse permutation appears because the coordinate originally in position moves to position .
Some texts instead define the matrix associated with by placing the 1 in row , column . That convention gives the transpose of the matrix defined here. Both conventions describe the same collection of matrices, but formulas involving composition and coordinate movement depend on which convention is chosen.
Example
For the cycle , meaning , , and ,
Consequently,
The identity matrix is the permutation matrix corresponding to the permutation that leaves every position fixed.
Row and column permutations
For an matrix , multiplication on the left by an permutation matrix gives
Thus row of moves to row .
For an matrix , multiplication on the right gives
Thus column of is column of . In terms of movement of the original columns, column moves to position .
These formulas distinguish two operations that are sometimes described ambiguously as “applying a permutation.” To move original column specifically to position , the appropriate product is .
When is square,
reorders rows and columns together:
This is a similarity transformation, corresponding to a relabeling of coordinates.
Algebraic properties
Transpose, inverse, and orthogonality
The columns of a permutation matrix are distinct standard coordinate vectors, so they form an orthonormal basis. Therefore,
In particular, every permutation matrix is an orthogonal matrix, and its inverse is its transpose:
Permutation matrices preserve Euclidean lengths and inner products. More generally, because they only rearrange coordinates, they preserve every standard coordinate norm, including the maximum norm.
A permutation matrix is symmetric precisely when its permutation is its own inverse:
Such a permutation consists only of fixed points and disjoint transpositions.
Multiplication and the symmetric group
Using function composition in the convention ,
Hence the permutation matrices form a group under matrix multiplication, isomorphic to the symmetric group . This construction is a faithful representation of : different permutations give different linear transformations.
If the disjoint cycles of have lengths , then the smallest positive integer for which is
Determinant and trace
The determinant of a permutation matrix equals the sign of its permutation:
If has disjoint cycles, counting fixed points as cycles of length 1, then
The trace counts fixed points:
These statements concern permutation matrices over the real or complex numbers. The same 0–1 construction works over other fields, although in characteristic 2 the scalars and coincide.
Cycle structure and eigenvalues
Reordering the coordinate basis to group together the elements of each cycle puts a permutation matrix into block-diagonal form, with one block for each cycle.
A cycle of length has characteristic polynomial
Therefore, for cycle lengths ,
Over the complex numbers, its eigenvalues are roots of unity. Each cycle of length contributes
Every permutation matrix is diagonalizable over the complex numbers. It need not be diagonalizable over the real numbers because some eigenvalues may be nonreal.
The eigenvalue 1 has multiplicity equal to the number of cycles. Its eigenvectors are precisely the vectors whose coordinates are constant on each cycle. In particular, the all-ones vector always satisfies
Doubly stochastic matrices and assignment problems
A doubly stochastic matrix is a square matrix with nonnegative real entries whose rows and columns each sum to 1. Every permutation matrix is doubly stochastic, but a general doubly stochastic matrix can have fractional entries.
The Birkhoff–von Neumann theorem states that every doubly stochastic matrix is a convex combination of permutation matrices:
Equivalently, the permutation matrices are exactly the extreme points of the set of doubly stochastic matrices.
This result underlies the assignment problem. Assigning each of workers to exactly one of tasks can be encoded by a permutation matrix . For assignment costs , the objective is
Relaxing the requirement to nonnegativity, while retaining unit row and column sums, gives a linear program with the same optimal value. An optimal permutation matrix always exists, although fractional matrices may also be optimal when there are ties.
Computational applications
Numerical linear algebra
Permutation matrices record pivoting and reordering operations. In Gaussian elimination with row pivoting, a common form of LU decomposition is
where records row exchanges, is lower triangular, and is upper triangular. Conventions differ: a factorization written as may use the inverse permutation instead.
For a sparse matrix, row and column reorderings can substantially affect storage and the number of additional nonzero entries created during factorization. Permutations change the arrangement of entries, not the entries themselves.
Software usually stores a permutation as an index array rather than as a dense matrix. Applying it to a vector takes indexing operations, and applying it to a matrix is implemented by rearranging rows or columns rather than by general matrix multiplication.
Graph relabeling
If is the adjacency matrix of a graph, then
is the adjacency matrix of the same graph with relabeled vertices. Two finite graphs with the same number of vertices are isomorphic exactly when their adjacency matrices are related in this way for some permutation matrix.
Permutation similarity preserves eigenvalues, but equal adjacency spectra alone do not establish that two graphs are isomorphic.
Related matrix classes
A partial permutation matrix has entries in and at most one 1 in each row and column. It may be rectangular and can describe an incomplete one-to-one assignment.
A signed permutation matrix replaces the 1 entries of a permutation matrix by independently chosen or . Such a matrix remains orthogonal but can change coordinate signs as well as positions.
A monomial matrix has exactly one nonzero entry in each row and column, with the nonzero entries not necessarily equal to 1. It combines a coordinate permutation with independent nonzero coordinate scalings. Unlike a permutation matrix, a general monomial matrix need not preserve lengths.