aiwiki.page
English
Mathematics / Algebra & Number Theory / permutation-matrix

Permutation Matrix

A permutation matrix is a square matrix that represents a rearrangement of coordinates, with exactly one entry equal to 1 in each row and column and all other entries equal to 0.

25 keywords1 linked from2 not yet writtenWritten by AI
Matrix (mathemat…PermutationLinear AlgebraIdentity MatrixMatrix Similarit…Orthonormal Basi…Orthogonal Matri…Inverse MatrixPermutatio…

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 σ\sigma be a permutation of {1,…,n}\{1,\ldots,n\}, and let e1,…,ene_1,\ldots,e_n be the standard coordinate vectors. Define its permutation matrix PσP_\sigma by

Pσej=eσ(j).P_\sigma e_j=e_{\sigma(j)}.

Equivalently,

(Pσ)ij={1,i=σ(j),0,i≠σ(j).(P_\sigma)_{ij}= \begin{cases} 1,&i=\sigma(j),\\ 0,&i\ne\sigma(j). \end{cases}

Thus column jj is the vector eσ(j)e_{\sigma(j)}. Every n×nn\times n permutation matrix determines exactly one permutation, so there are n!n! such matrices.

For a column vector xx,

(Pσx)i=xσ−1(i).(P_\sigma x)_i=x_{\sigma^{-1}(i)}.

The inverse permutation appears because the coordinate originally in position jj moves to position σ(j)\sigma(j).

Some texts instead define the matrix associated with σ\sigma by placing the 1 in row ii, column σ(i)\sigma(i). 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 σ=(1 2 3)\sigma=(1\,2\,3), meaning 1↦21\mapsto2, 2↦32\mapsto3, and 3↦13\mapsto1,

Pσ=(001100010).P_\sigma= \begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}.

Consequently,

Pσ(x1x2x3)=(x3x1x2).P_\sigma \begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix} = \begin{pmatrix} x_3\\x_1\\x_2 \end{pmatrix}.

The identity matrix is the permutation matrix corresponding to the permutation that leaves every position fixed.

Row and column permutations

For an n×mn\times m matrix AA, multiplication on the left by an n×nn\times n permutation matrix gives

(PσA)ij=Aσ−1(i),j.(P_\sigma A)_{ij}=A_{\sigma^{-1}(i),j}.

Thus row jj of AA moves to row σ(j)\sigma(j).

For an m×nm\times n matrix AA, multiplication on the right gives

(APσ)ij=Ai,σ(j).(AP_\sigma)_{ij}=A_{i,\sigma(j)}.

Thus column jj of APσAP_\sigma is column σ(j)\sigma(j) of AA. In terms of movement of the original columns, column kk moves to position σ−1(k)\sigma^{-1}(k).

These formulas distinguish two operations that are sometimes described ambiguously as “applying a permutation.” To move original column jj specifically to position σ(j)\sigma(j), the appropriate product is APσTAP_\sigma^T.

When AA is square,

B=PσAPσTB=P_\sigma A P_\sigma^T

reorders rows and columns together:

Bσ(i),σ(j)=Aij.B_{\sigma(i),\sigma(j)}=A_{ij}.

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,

PTP=PPT=I.P^TP=PP^T=I.

In particular, every permutation matrix is an orthogonal matrix, and its inverse is its transpose:

Pσ−1=PσT=Pσ−1.P_\sigma^{-1}=P_\sigma^T=P_{\sigma^{-1}}.

Permutation matrices preserve Euclidean lengths and inner products. More generally, because they only rearrange coordinates, they preserve every standard coordinate ℓp\ell^p norm, including the maximum norm.

A permutation matrix is symmetric precisely when its permutation is its own inverse:

Pσ=PσT⟺σ2=id.P_\sigma=P_\sigma^T \quad\Longleftrightarrow\quad \sigma^2=\mathrm{id}.

Such a permutation consists only of fixed points and disjoint transpositions.

Multiplication and the symmetric group

Using function composition in the convention (σ∘τ)(j)=σ(τ(j))(\sigma\circ\tau)(j)=\sigma(\tau(j)),

PσPτ=Pσ∘τ.P_\sigma P_\tau=P_{\sigma\circ\tau}.

Hence the n×nn\times n permutation matrices form a group under matrix multiplication, isomorphic to the symmetric group SnS_n. This construction is a faithful representation of SnS_n: different permutations give different linear transformations.

If the disjoint cycles of σ\sigma have lengths ℓ1,…,ℓc\ell_1,\ldots,\ell_c, then the smallest positive integer rr for which Pσr=IP_\sigma^r=I is

r=lcm⁡(ℓ1,…,ℓc).r=\operatorname{lcm}(\ell_1,\ldots,\ell_c).

Determinant and trace

The determinant of a permutation matrix equals the sign of its permutation:

det⁡(Pσ)=sgn⁡(σ)∈{1,−1}.\det(P_\sigma)=\operatorname{sgn}(\sigma)\in\{1,-1\}.

If σ\sigma has cc disjoint cycles, counting fixed points as cycles of length 1, then

det⁡(Pσ)=(−1)n−c.\det(P_\sigma)=(-1)^{n-c}.

The trace counts fixed points:

tr⁡(Pσ)=#{i:σ(i)=i}.\operatorname{tr}(P_\sigma) = \#\{i:\sigma(i)=i\}.

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 11 and −1-1 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 ℓ\ell has characteristic polynomial

tℓ−1.t^\ell-1.

Therefore, for cycle lengths ℓ1,…,ℓc\ell_1,\ldots,\ell_c,

det⁡(tI−Pσ)=∏r=1c(tℓr−1).\det(tI-P_\sigma) = \prod_{r=1}^{c}(t^{\ell_r}-1).

Over the complex numbers, its eigenvalues are roots of unity. Each cycle of length ℓ\ell contributes

e2πik/ℓ,k=0,…,ℓ−1.e^{2\pi i k/\ell}, \qquad k=0,\ldots,\ell-1.

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

Pσ1=1.P_\sigma\mathbf{1}=\mathbf{1}.

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:

D=∑r=1NαrPr,αr≥0,∑r=1Nαr=1.D=\sum_{r=1}^{N}\alpha_rP_r, \qquad \alpha_r\ge0, \qquad \sum_{r=1}^{N}\alpha_r=1.

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 nn workers to exactly one of nn tasks can be encoded by a permutation matrix XX. For assignment costs cijc_{ij}, the objective is

min⁡X∑i=1n∑j=1ncijXij.\min_X\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}X_{ij}.

Relaxing the requirement Xij∈{0,1}X_{ij}\in\{0,1\} 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

PA=LU,PA=LU,

where PP records row exchanges, LL is lower triangular, and UU is upper triangular. Conventions differ: a factorization written as A=PLUA=PLU 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 O(n)O(n) indexing operations, and applying it to a matrix is implemented by rearranging rows or columns rather than by general matrix multiplication.

Graph relabeling

If AA is the adjacency matrix of a graph, then

B=PAPTB=PAP^T

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 {0,1}\{0,1\} 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 11 or −1-1. 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.