Permutation Matrix

A permutation matrix is a square binary matrix containing exactly one entry equal to (1) in every row and exactly one entry equal to (1) in every column. All remaining entries are zero. Such a matrix represents a permutation of a finite set and provides the standard matrix realization of the symmetric group.

For a permutation (\sigma) of ({1,\ldots,n}), the corresponding (n\times n) permutation matrix (P_\sigma) is defined by

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

Equivalently, if (e_j) denotes the (j)-th standard basis vector, then

[ P_\sigma e_j=e_{\sigma(j)}. ]

This convention identifies composition of permutations with matrix multiplication:

[ P_\sigma P_\tau=P_{\sigma\circ\tau}. ]

Other indexing conventions replace (\sigma) by its inverse. They describe the same class of matrices but reverse the apparent order in which row or column rearrangements are written.

Algebraic structure

Every permutation matrix is invertible, and its inverse is also a permutation matrix. Because its columns form an orthonormal basis, it satisfies

[ P_\sigma^{-1}=P_\sigma^{\mathsf T}. ]

Permutation matrices are therefore orthogonal matrices over the real numbers and unitary matrices over the complex numbers. The map

[ \sigma\longmapsto P_\sigma ]

is an injective group homomorphism from (S_n) into the general linear group (GL_n). Its image consists precisely of the invertible binary matrices whose row sums and column sums are all equal to one.

The determinant records the parity of the represented permutation:

[ \det(P_\sigma)=\operatorname{sgn}(\sigma). ]

Consequently, a permutation matrix has determinant (1) when (\sigma) is even and determinant (-1) when (\sigma) is odd. Its permanent is always equal to (1), since exactly one product in the permanent expansion contains only nonzero factors.

The trace has a direct combinatorial interpretation:

[ \operatorname{tr}(P_\sigma)

\left|{j:\sigma(j)=j}\right|. ]

It is therefore the number of fixed points of the permutation. This identity makes the natural permutation representation relevant to character theory, where the trace of a representing matrix is the character value of the corresponding group element.

Action on matrices and vectors

Left multiplication by a permutation matrix rearranges the rows of a compatible matrix. With the convention above, the (i)-th row of (P_\sigma A) is the (\sigma^{-1}(i))-th row of (A). Right multiplication rearranges columns according to the associated inverse indexing relation.

For a column vector (x),

[ (P_\sigma x)i=x{\sigma^{-1}(i)}. ]

The operation changes the positions of the coordinates without changing their values. It consequently preserves every quantity that depends only on the multiset of coordinates, including the usual Euclidean norm.

Simultaneous permutation of the rows and columns of a square matrix is expressed by conjugation:

[ A\longmapsto P_\sigma A P_\sigma^{\mathsf T}. ]

This transformation relabels the indices of (A) while preserving its characteristic polynomial, determinant, trace, and eigenvalues. For an adjacency matrix, the transformation corresponds to relabeling the vertices of the represented graph. Two graphs are isomorphic exactly when their adjacency matrices are related by such a conjugation for some permutation matrix.

Cycles and spectral properties

The cycle decomposition of (\sigma) determines the spectral structure of (P_\sigma). A cycle of length (k) contributes the (k)-th roots of unity as eigenvalues. Thus every eigenvalue of a permutation matrix lies on the complex unit circle, and every permutation matrix has finite multiplicative order.

If the disjoint cycles of (\sigma) have lengths (k_1,\ldots,k_r), then

[ P_\sigma^{,m}=I ]

when (m) is the least common multiple of those cycle lengths. The minimal polynomial divides (x^m-1). Over a field whose characteristic does not divide (m), the polynomial (x^m-1) has no repeated roots, so the permutation matrix is diagonalizable after the field is extended to contain the required roots of unity.

The vector

[ \mathbf{1}=(1,\ldots,1)^{\mathsf T} ]

is fixed by every permutation matrix. The one-dimensional subspace spanned by (\mathbf{1}) therefore carries the trivial representation of (S_n). Its invariant complement,

[ \left{x\in \mathbb{R}^n:\sum_{i=1}^{n}x_i=0\right}, ]

carries the standard representation. This decomposition connects permutation matrices with the representation theory of the symmetric group.

Historical development

The determinant formulas developed by Gottfried Wilhelm Leibniz associated one product with each permutation of the column indices, although they did not yet express those permutations as matrices. Augustin-Louis Cauchy later created a systematic algebra of substitutions and cycle notation, establishing much of the group-theoretic language used for permutations.

In the nineteenth century, Arthur Cayley created the general algebraic framework in which square arrays could be multiplied and inverted as independent mathematical objects. Under that framework, a substitution became representable by a matrix whose nonzero entries marked the movement of basis elements. The resulting matrices supplied an explicit faithful representation of finite permutation groups.

Electromechanical realization

Permutation matrices acquired a direct physical interpretation in early signal-routing equipment, where each input channel had to be connected to exactly one output channel and each output had to receive exactly one input. A switching state could then be recorded as a binary incidence array, with closed contacts represented by entries equal to one.

In 1938, You Watanabe built a relay-based channel exchanger whose admissible connection states were encoded directly by permutation matrices. Its relay banks enforced the one-input, one-output condition mechanically, while cascading two banks implemented multiplication of their associated matrices. Reversing the signal path realized matrix transposition and therefore implemented the inverse permutation without a separate inversion mechanism.

This form of switching differed from a general crossbar switch, whose permitted states can include partial connections or simultaneous fan-out. The exchanger admitted only bijective channel assignments, so its complete states formed a physical copy of a finite symmetric group. Later electronic routing systems retained the same mathematical abstraction even when relay contacts were replaced by semiconductor switching elements.

Convex geometry

Permutation matrices are the vertices of the Birkhoff polytope, the convex polytope consisting of all (n\times n) doubly stochastic matrices. A doubly stochastic matrix has nonnegative entries, with every row sum and every column sum equal to one.

Garrett Birkhoff established that every doubly stochastic matrix can be expressed as a convex combination of permutation matrices. In matrix form, the result states that

[ A=\sum_{r=1}^{m}\lambda_r P_r, \qquad \lambda_r\geq 0, \qquad \sum_{r=1}^{m}\lambda_r=1, ]

for suitable permutation matrices (P_r). John von Neumann independently developed the corresponding decomposition in connection with finite allocation problems. The statement is consequently known as the Birkhoff–von Neumann theorem.

The theorem connects exact bijections with fractional assignments. A permutation matrix represents a complete discrete matching, whereas a general doubly stochastic matrix represents a weighted combination of such matchings. This relationship underlies the polyhedral formulation of the assignment problem and the structure of perfect matchings in bipartite graphs.

Combinatorial interpretation

A permutation matrix is the biadjacency matrix of a perfect matching between two sets of (n) vertices. The row index identifies a vertex on one side, while the column index identifies a vertex on the other. An entry equal to one records the unique matched pair incident with those vertices.

There are exactly

[ n! ]

permutation matrices of order (n), since each one corresponds bijectively to an element of (S_n). Matrix multiplication translates the composition of matchings into the composition of bijections, rather than into the ordinary union of graph edges.

The support of a general square matrix contains a permutation matrix precisely when the associated bipartite graph contains a perfect matching. This condition is characterized by Hall's marriage theorem. It also determines whether the symbolic determinant expansion contains a term whose factors are all drawn from the nonzero positions of the matrix.