1 Definition and basic properties

Permutation matrices are square matrices that encode rearrangements of coordinates. They arise by taking an identity matrix and permuting either its rows or its columns. Because of this construction, they retain the sparsity and simplicity of the identity matrix while recording a specific permutation of positions.

1.1 Formal definition

A permutation matrix is an \(n \times n\) matrix \(P\) whose entries are all either 0 or 1, and in which each row and each column contains exactly one entry equal to 1. Equivalently, \(P\) is obtained from the identity matrix \(I_n\) by permuting rows or columns.

Such a matrix represents a bijection on the set \(\{1,2,\dots,n\}\). If the 1 in row \(i\) is located in column \(\sigma(i)\), then \(P\) corresponds to the permutation \(\sigma\).

1.2 Relation to the identity matrix

The identity matrix is the simplest permutation matrix, corresponding to the trivial permutation that leaves every index fixed. Any permutation matrix can be viewed as a rearranged identity matrix, so it differs from \(I_n\) only by the placement of the 1s. This makes permutation matrices a natural algebraic way to represent reordering without changing values.

1.3 Row and column structure

Each row of a permutation matrix contains a single 1 and the rest zeros, so no two rows can have the 1 in the same column. The same holds for columns. This structure implies that the matrix is very sparse and that its nonzero pattern uniquely determines the permutation.

1.4 Binary matrix characterization

Permutation matrices are binary matrices with a stronger condition than mere 0-1 entries. Not every binary matrix qualifies; the row and column constraints are essential. In fact, a binary matrix is a permutation matrix precisely when it has exactly one 1 in each row and each column.

2 Construction and examples

Permutation matrices can be built in several equivalent ways, depending on whether one begins with a permutation of row indices or column indices. Small cases are often used to illustrate the connection between matrices and coordinate rearrangements.

2.1 From permutations of rows

Starting from the identity matrix, one may swap rows according to a chosen permutation. The resulting matrix remains square and binary, but the 1s move to new positions. This construction is commonly used in linear algebra when row operations are represented in matrix form.

2.2 From permutations of columns

A permutation matrix may also be produced by permuting the columns of the identity matrix. This yields the same class of matrices as row permutations, since column permutations of \(I_n\) produce matrices with one 1 in each row and column. The two descriptions are closely related through transposition.

2.3 Small matrix examples

Small permutation matrices provide concrete illustrations of the general definition. They are especially useful for visualizing how permutations act on coordinates.

2.3.1 2×2 permutation matrices

For \(n=2\), there are two permutation matrices:

\[ \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}, \qquad \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}. \]

The second matrix swaps the two coordinates, while the first leaves them unchanged.

2.3.2 3×3 permutation matrices

For \(n=3\), there are six permutation matrices, corresponding to the six permutations of three elements. One example is

\[ \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}, \]

which sends the first row position to the second, the second to the third, and the third to the first. Each possible arrangement of three 1s, one in each row and column, gives a distinct matrix.

3 Algebraic properties

Permutation matrices have several important algebraic features that make them useful in theory and computation. Many of these follow directly from the fact that they simply rearrange coordinates.

3.1 Invertibility

Every permutation matrix is invertible. Since it represents a bijection on basis positions, its action can always be reversed. The inverse is again a permutation matrix, corresponding to the inverse permutation.

3.2 Transpose and inverse

For a permutation matrix \(P\), the transpose equals the inverse:

\[ P^T = P^{-1}. \]

This occurs because transposing swaps rows and columns, reversing the permutation encoded by the matrix. As a consequence, permutation matrices are orthogonal over the real numbers.

3.3 Determinant

The determinant of a permutation matrix is either \(1\) or \(-1\). Its value depends on whether the associated permutation is even or odd. Thus the determinant records the parity of the permutation.

3.4 Eigenvalues and trace

The trace of a permutation matrix equals the number of fixed points of the associated permutation, because the diagonal entries are 1 exactly where an index is left unchanged. Its eigenvalues are roots of unity, with the spectrum determined by the cycle structure of the permutation. In particular, repeated application of the matrix eventually returns to the identity when the permutation has finite order.

4 Action on vectors and matrices

Permutation matrices act by reordering coordinates. This makes them a convenient tool for expressing row and column rearrangements in compact matrix notation.

4.1 Left multiplication and row permutations

When a permutation matrix multiplies another matrix on the left, it permutes the rows of that matrix. This is one reason permutation matrices are used to represent row exchanges in elimination procedures. Left multiplication by \(P\) does not change the row content, only its order.

4.2 Right multiplication and column permutations

When a permutation matrix multiplies a matrix on the right, it permutes the columns. This operation reorganizes the column structure without altering the entries themselves. The effect is dual to left multiplication.

4.3 Effect on basis vectors

If \(e_i\) denotes a standard basis vector, then multiplying by a permutation matrix sends \(e_i\) to another basis vector. In this way, the matrix acts as a coordinate relabeling operator. Every column of a permutation matrix is itself a standard basis vector, reflecting this behavior.

4.4 Effect on matrix factorization

Permutation matrices often appear in factorizations of matrices, especially when rows must be reordered to continue an algorithm. They can be inserted into decompositions to record pivoting steps or to separate structural reordering from other matrix components. This helps preserve exact algebraic information about the transformation process.

5 Group-theoretic interpretation

Permutation matrices provide a matrix representation of permutations and connect linear algebra with group theory. They give a concrete realization of the symmetric group inside the group of invertible matrices.

5.1 Correspondence with permutations

Each permutation matrix corresponds to one and only one permutation of \(n\) elements. This gives a bijection between the set of \(n \times n\) permutation matrices and the symmetric group \(S_n\). The matrix entries encode the same information as the permutation written in one-line notation.

5.2 Multiplication and composition

The product of two permutation matrices is again a permutation matrix. Under the correspondence with permutations, matrix multiplication matches composition of permutations. Thus the algebra of permutation matrices mirrors the group operation on permutations.

5.3 Symmetric group representation

The set of all \(n \times n\) permutation matrices forms a faithful representation of the symmetric group \(S_n\). Faithfulness means distinct permutations produce distinct matrices. This representation allows permutation action to be studied using matrix methods.

6 Applications

Permutation matrices are used throughout applied and computational linear algebra. Their main role is to represent rearrangements efficiently and precisely.

6.1 Gaussian elimination

During Gaussian elimination, rows are often swapped to place a suitable pivot in position. A permutation matrix records these row interchanges succinctly. This notation is especially useful when describing the elimination process in a structured algebraic form.

6.2 LU decomposition with pivoting

In LU decomposition with pivoting, a permutation matrix is included to capture the row reordering needed for numerical stability. The factorization is commonly written in the form \(PA = LU\), where \(P\) stores the pivot pattern. This allows the decomposition to account for row exchanges without losing information about the original matrix.

6.3 Combinatorics

Permutation matrices offer a matrix-based way to study permutations in combinatorics. They can be used to encode permutation statistics, fixed points, and cycle behavior. Their sparse structure also makes them useful in counting arguments and in visual descriptions of rearrangements.

6.4 Numerical linear algebra

In numerical computation, permutation matrices help organize algorithms that depend on row or column reordering. They are particularly valuable for maintaining stability, preserving sparsity patterns, and tracking pivot choices. Because they are orthogonal and exact 0-1 matrices, they are inexpensive to manipulate.

Permutation matrices are closely related to several other matrix classes and operators. These related objects generalize or reinterpret the same basic idea of rearrangement.

7.1 Doubly stochastic matrices

Doubly stochastic matrices have nonnegative entries with each row and each column summing to 1. Every permutation matrix is doubly stochastic, but not every doubly stochastic matrix is a permutation matrix. The latter may contain fractional entries rather than only 0s and 1s.

7.2 Generalized permutation matrices

Generalized permutation matrices allow each row and column to have exactly one nonzero entry, but that entry may be any nonzero scalar rather than just 1. They extend permutation matrices by combining a permutation pattern with diagonal scaling.

7.3 Permutation operators

Permutation operators are linear maps that reorder coordinates in a vector space. A permutation matrix is the matrix representation of such an operator in the standard basis. The operator viewpoint is especially useful in abstract linear algebra and functional analysis.

7.4 Permutation graphs

Permutation graphs are graphs associated with permutations, often constructed from the relative order of elements. While distinct from permutation matrices, they share the same combinatorial origin. Both structures capture rearrangement data in different mathematical settings.