Permutation matrix
A permutation matrix is a square matrix derived from the identity matrix by rearranging its rows according to a permutation of the indices, resulting in exactly one entry of 1 in each row and each column, with all other entries being 0.[1] For an n \times n matrix, there are precisely n! such matrices, each corresponding to one of the n! possible permutations of \{[1](/page/1), 2, \dots, n\}.[1] These matrices form a fundamental tool in linear algebra for representing permutations as linear transformations.[2]
Permutation matrices exhibit several key properties that underscore their importance. They are orthogonal, meaning their transpose equals their inverse (P^T = P^{-1}), and thus preserve the Euclidean norm when multiplying vectors.[3] The product of two permutation matrices is another permutation matrix, corresponding to the composition of their associated permutations, and the determinant of a permutation matrix is either +1 or -1, equal to the sign of the permutation (the parity of the number of transpositions needed to achieve it).[3] Left-multiplying a matrix by a permutation matrix permutes its rows, while right-multiplication permutes the columns, making them essential for reordering data in computational algorithms and solving systems of equations.[1]
In broader applications, permutation matrices play a central role in the Leibniz formula for the determinant of a general matrix, where the determinant is expressed as a signed sum over all permutations.[3] They also appear in group theory as representations of the symmetric group S_n and in numerical linear algebra for optimizing matrix factorizations, such as in LU decomposition with partial pivoting.[4] Their binary structure—consisting solely of 0s and 1s—facilitates efficient implementation in computer science for tasks like sorting and graph algorithms.[1]
Definition and Representation
Correspondence to Permutations
A permutation of a finite set is defined as a bijective function \sigma: \{1, \dots, [n](/page/N+)\} \to \{1, \dots, [n](/page/N+)\}, which rearranges the elements of the set while preserving the number of elements.[5] The set of all such bijections forms the symmetric group S_n under composition, which has order n!.[6]
There exists a natural bijection between the elements of the symmetric group S_n and the set of n \times n permutation matrices, where a permutation matrix P_\sigma corresponding to \sigma \in S_n is the square matrix with entries P_{i,j} = [1](/page/1) if \sigma(i) = j and $0 otherwise.[7] This correspondence associates each permutation with a unique matrix that has exactly one $1 in each row and each column, and zeros elsewhere.[7]
For example, with n=3, the identity permutation \sigma = (1,2,3) corresponds to the identity matrix
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}.
The transposition (1\ 2), or \sigma = (2,1,3), corresponds to the matrix
\begin{pmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{pmatrix},
where the $1s in the first two rows and columns are swapped relative to the identity.[7]
To see that the correspondence is a bijection, note that for any \sigma \in S_n, the matrix P_\sigma is uniquely determined by placing a $1 at position (i, \sigma(i)) for each i, ensuring exactly one $1 per row and column since \sigma is bijective. Conversely, any n \times n matrix with exactly one $1 per row and column defines a unique permutation \sigma by setting \sigma(i) = j where the $1 in row i is in column j, and the bijectivity follows from the single $1 per column.[7]
Explicit Matrix Construction
A permutation matrix P corresponding to a permutation \sigma of \{1, 2, \dots, n\} is constructed row-wise by placing a 1 in the i-th row at column \sigma(i), with all other entries in that row being 0, for each i = 1 to n.[8] Mathematically, the entry P_{i,j} is given by
P_{i,j} =
\begin{cases}
1 & \text{if } j = \sigma(i), \\
0 & \text{otherwise}.
\end{cases}
This ensures exactly one 1 per row, positioned according to the permutation mapping.[9]
An equivalent column-wise construction places a 1 in column j at row \sigma^{-1}(j), filling the matrix with 0s elsewhere, which yields the same matrix since the positions satisfy the row-wise condition reciprocally.[10]
In programming contexts, the matrix can be generated algorithmically by initializing an n \times n zero matrix and setting the specified indices to 1. The following pseudocode illustrates this for the row-wise approach:
function permutation_matrix(sigma, n):
P = zeros(n, n) // Initialize n x n matrix with zeros
for i in 1 to n:
j = sigma(i)
P[i, j] = 1
return P
function permutation_matrix(sigma, n):
P = zeros(n, n) // Initialize n x n matrix with zeros
for i in 1 to n:
j = sigma(i)
P[i, j] = 1
return P
This method efficiently produces the matrix in O(n) time, assuming \sigma is provided as an array or function.[11]
For example, consider the 3-cycle permutation \sigma = (1\ 2\ 3), where \sigma(1) = 2, \sigma(2) = 3, \sigma(3) = 1. The resulting 3×3 permutation matrix is
\begin{pmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{pmatrix}.
Each row has a single 1 at the column indicated by \sigma.[11]
The mapping from permutations to permutation matrices is a bijection: no two distinct permutations yield the same matrix. To see this, note that any permutation matrix has exactly one 1 in each row and each column, defining a unique permutation \sigma by \sigma(i) = j where the 1 in row i is at column j. The single 1 per column ensures \sigma is bijective, as the images \sigma(i) are distinct and cover \{1, \dots, n\}. Conversely, any such \sigma produces a valid permutation matrix by the construction above.[12]
Basic Actions and Properties
Permuting Rows, Columns, and Vectors
Permutation matrices serve as linear transformations that rearrange the components of vectors and the entries of matrices according to a specified permutation \sigma. For a vector \mathbf{v} \in \mathbb{R}^n and the permutation matrix P_\sigma associated with \sigma, the action is given by (P_\sigma \mathbf{v})_i = v_{\sigma^{-1}(i)} for each index i = 1, \dots, n. This formula indicates that the i-th component of the transformed vector receives the value from the \sigma^{-1}(i)-th position of the original vector, effectively reordering the entries to reflect the inverse permutation on the indices.[13]
When applied to matrices, permutation matrices enable systematic reordering of rows and columns. Specifically, left-multiplication by P_\sigma permutes the rows of a matrix A \in \mathbb{R}^{m \times n} according to \sigma^{-1}, such that the i-th row of P_\sigma A is the \sigma^{-1}(i)-th row of A. In contrast, right-multiplication A P_\sigma permutes the columns of A by \sigma, where the j-th column of A P_\sigma is the \sigma(j)-th column of A. These operations preserve the structure and dimensions of the matrix while simply exchanging positions.[13]
To illustrate, consider a $2 \times 2 matrix A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} and the transposition \sigma = (1\ 2), which swaps indices 1 and 2, with corresponding P_\sigma = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. Then, P_\sigma A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} c & d \\ a & b \end{pmatrix}, permuting the rows by swapping them. Similarly, A P_\sigma = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} b & a \\ d & c \end{pmatrix}, which swaps the columns of A.
Geometrically, a permutation matrix P_\sigma represents a reordering of the standard basis vectors in the vector space \mathbb{R}^n, mapping e_j to e_{\sigma(j)} for each standard basis vector e_j. This basis reordering is a linear isometry that preserves vector norms and inner products, as permutation matrices are orthogonal.
The appearance of \sigma^{-1} in the vector action formula, rather than \sigma directly, ensures consistency with the intuitive notion of permutation as a relabeling of positions: the value originally at position k moves to \sigma(k), so the value arriving at i originates from \sigma^{-1}(i). This inverse arises naturally from the matrix-vector multiplication, where row indices of P_\sigma select from the input vector.
Orthogonality and the Inverse-Transpose Relation
A permutation matrix P corresponding to a permutation \sigma of \{1, 2, \dots, n\} is defined such that its columns (or rows) are a rearrangement of the standard basis vectors in \mathbb{R}^n. This structure ensures that P is an orthogonal matrix, satisfying P^T P = I_n, where I_n is the n \times n identity matrix and P^T denotes the transpose of P. To verify this, consider the (i,j)-entry of the product P^T P: it equals the dot product of the i-th row of P and the j-th column of P, which is 1 if i = j (since each row and column has exactly one 1) and 0 otherwise (no overlapping 1's in distinct rows and columns).
Since P is orthogonal, its inverse equals its transpose: P^{-1} = P^T. This can be confirmed directly using the permutation representation. The entry (P_\sigma^T)_{i,j} = (P_\sigma)_{j,i} = 1 if and only if \sigma(j) = i, which is equivalent to j = \sigma^{-1}(i). Thus, P_\sigma^T places a 1 in position (i, \sigma^{-1}(i)), meaning P_\sigma^T = P_{\sigma^{-1}}, the permutation matrix for the inverse permutation \sigma^{-1}.
As orthogonal matrices, permutation matrices preserve the Euclidean norm and inner products of vectors, meaning they maintain lengths (\|P \mathbf{x}\| = \|\mathbf{x}\|) and angles between vectors, effectively acting as rotations or reflections within the standard basis of \mathbb{R}^n. For example, consider the n=2 transposition permutation \sigma = (1\ 2), with matrix
P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.
Here, P^T = P, and since P^2 = I_2, it follows that P^{-1} = P, illustrating self-inversality for this transposition.
Multiplication and Composition
Product of Permutation Matrices
The product of two permutation matrices P_\sigma and P_\tau, where \sigma, \tau \in S_n, corresponds to the permutation matrix of the composition \tau \circ \sigma.[14] Specifically, the (i,j)-entry of the product P_\sigma P_\tau is computed as
(P_\sigma P_\tau)_{i,j} = \sum_{k=1}^n (P_\sigma)_{i,k} (P_\tau)_{k,j}.
Since each row and column of a permutation matrix contains exactly one 1, the sum equals 1 if and only if there exists a k such that (P_\sigma)_{i,k} = 1 and (P_\tau)_{k,j} = 1, meaning k = \sigma(i) and j = \tau(k). Thus, j = \tau(\sigma(i)), so the product has a 1 precisely at positions corresponding to the permutation \tau \circ \sigma, where composition is right-to-left (apply \sigma first, then \tau).[14]
This derivation also establishes closure: the product of any two permutation matrices is itself a permutation matrix, as it has exactly one 1 in each row and column.[1] To see this explicitly via basis vectors, note that P_\sigma P_\tau \mathbf{e}_i = P_\sigma (\mathbf{e}_{\tau(i)}) = \mathbf{e}_{\sigma(\tau(i))} = \mathbf{e}_{(\tau \circ \sigma)(i)} for the standard basis \mathbf{e}_i, confirming the action matches P_{\tau \circ \sigma}.[14]
For a concrete example in S_3, consider \sigma = (1\ 2) and \tau = (2\ 3). The matrices are
P_\sigma = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad
P_\tau = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.
Their product is
P_\sigma P_\tau = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix},
which corresponds to \tau \circ \sigma = (1\ 3\ 2), as it maps 1 to 3, 3 to 2, and 2 to 1.[14]
In computational contexts, multiplying permutation matrices implements sequential index permutation, which is efficient for reordering data structures or simulating transformations in algorithms like sorting or graph traversals.[3]
Relation to Permutation Composition
The mapping \sigma \mapsto P_\sigma from the symmetric group S_n (under composition \circ) to the group of n \times n permutation matrices (under matrix multiplication) defines a group isomorphism, as it is a bijective homomorphism that sends the group operation in S_n to matrix multiplication in the codomain.[6] Specifically, for permutations \sigma, \tau \in S_n, the product satisfies P_\tau P_\sigma = P_{\tau \circ \sigma}, thereby interpreting matrix multiplication as the realization of permutation composition within the matrix group.[6] This correspondence preserves the group structure, including the identity element—the identity permutation maps to the identity matrix I_n—and inverses, where P_{\sigma^{-1}} = P_\sigma^{-1}.[6]
The associativity of matrix multiplication directly inherits and mirrors the associativity of permutation composition, ensuring that the isomorphic groups share this fundamental property without alteration.[6] In both settings, the operation is associative: (\rho \circ \tau) \circ \sigma = \rho \circ (\tau \circ \sigma) in S_n, and correspondingly P_\rho (P_\tau P_\sigma) = (P_\rho P_\tau) P_\sigma for the matrices.[6]
This isomorphism provides insight into cycle decompositions of permutations, as the product of permutation matrices reflects the cycle structure of the composed permutation; for instance, disjoint cycles in S_n commute under composition, and their corresponding matrices likewise commute under multiplication.[6][15] If \sigma and \tau consist of disjoint cycles, then \sigma \circ \tau = \tau \circ \sigma, and thus P_\sigma P_\tau = P_\tau P_\sigma, highlighting how the matrix representation preserves combinatorial properties of permutations.[6][15]
The construction yields the defining permutation representation of S_n, which is faithful—meaning the homomorphism is injective—and thus embeds S_n injectively into the general linear group GL_n(\mathbb{R}) via permutation matrices.[6] This representation is canonical for capturing the action of S_n on the standard basis of \mathbb{R}^n, distinguishing it as the standard faithful realization of the symmetric group in matrix form.[6]
Group Structure
Representation of the Symmetric Group
Permutation matrices provide a faithful matrix representation of the symmetric group S_n, the group of all permutations of n elements. Specifically, the map \rho: S_n \to \mathrm{GL}(n, \mathbb{R}) defined by \rho(\sigma) = P_\sigma, where P_\sigma is the permutation matrix associated to \sigma, is an injective group homomorphism. This injectivity follows from the fact that distinct permutations \sigma and \tau produce matrices with 1s in different positions, ensuring \rho(\sigma) \neq \rho(\tau). The image of \rho is precisely the set of all n \times n permutation matrices, which forms a subgroup of the general linear group \mathrm{GL}(n, \mathbb{R}).
This representation acts on the vector space \mathbb{R}^n by permuting the standard basis vectors: for the standard basis \{e_1, \dots, e_n\}, the action satisfies \rho(\sigma) e_i = e_{\sigma(i)}. Thus, it is known as the permutation representation of S_n, where group elements permute the coordinates of vectors in \mathbb{R}^n. The dimension of this representation is n, matching the dimension of \mathbb{R}^n, and the standard basis serves as a natural basis for the module.[16]
The permutation representation is irreducible only for n=1, where S_1 is trivial. For n \geq 2, it is reducible, decomposing as a direct sum of the 1-dimensional trivial representation (spanned by the all-ones vector \sum e_i) and the (n-1)-dimensional standard representation, which is irreducible over \mathbb{R}. This decomposition highlights how the permutation action preserves the subspace orthogonal to the trivial part, consisting of vectors with sum zero.[17]
Historically, permutation matrices and their representations were employed in 19th-century invariant theory by Arthur Cayley and others to study polynomials invariant under linear transformations, including those induced by permutations. In modern contexts, this representation is fundamental in computational group theory, enabling algorithms for group computations via matrix operations in systems like GAP.[16]
For illustration, consider S_3, which has order 6. The permutation matrices correspond to the elements classified by cycle types: the identity (type (1,1,1)), three transpositions (type (2,1)), and two 3-cycles (type (3)). These are:
| Cycle Type | Permutation \sigma | Matrix P_\sigma |
|---|
| (1,1,1) | id: (1)(2)(3) | \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} |
| (2,1) | (12): 2→1,1→2,3→3 | \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} |
| (2,1) | (13): 3→1,1→3,2→2 | \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} |
| (2,1) | (23): 2→3,3→2,1→1 | \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} |
| (3) | (123): 1→2,2→3,3→1 | \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} |
| (3) | (132): 1→3,3→2,2→1 | \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} |
The Permutation Matrix Group
The set of all n \times n permutation matrices, denoted \{P_\sigma \mid \sigma \in S_n\}, forms a group under matrix multiplication that is isomorphic to the symmetric group S_n and thus has order n!.[15] This group is closed under multiplication, as the product of two permutation matrices corresponds to the composition of their associated permutations, and closed under inversion, since the inverse of a permutation matrix is its transpose, which is also a permutation matrix.[19] Furthermore, permutation matrices are orthogonal, satisfying P_\sigma^T P_\sigma = I_n, so the permutation matrix group is a finite subgroup of the orthogonal group O(n).[3]
The conjugacy classes within the permutation matrix group mirror those of S_n, determined by the cycle types of the corresponding permutations.[20] For instance, all transposition matrices, which correspond to 2-cycles and have cycle type (2,1^{n-2}), are conjugate to each other within the group.[21] More generally, two permutation matrices P_\sigma and P_\tau are conjugate if and only if \sigma and \tau share the same cycle structure, partitioning n into cycle lengths.[22]
The center of the permutation matrix group is trivial for n \geq 3, meaning the only matrix that commutes with every element is the identity.[22] Additionally, the commutator subgroup, generated by all commutators [P_\sigma, P_\tau] = P_\sigma P_\tau P_\sigma^{-1} P_\tau^{-1], coincides with the subgroup of even permutation matrices, isomorphic to the alternating group A_n, for n \geq 3.[23]
In computational group theory, the permutation matrix group is implemented efficiently in libraries like GAP and SageMath using strong generating sets and stabilizer chains, enabling algorithms for membership testing, subgroup computation, and conjugacy class enumeration that scale well for n up to hundreds as of 2025.[24][25] These structures exploit the group's faithful permutation representation to minimize storage and runtime for practical applications in symbolic computation.
Doubly Stochastic Matrices
A doubly stochastic matrix is a square matrix with non-negative real entries such that the sum of the entries in each row and each column equals 1.[26] Permutation matrices form the extreme points (vertices) of the convex set of all such matrices, known as the Birkhoff polytope.[26]
The Birkhoff–von Neumann theorem states that every doubly stochastic matrix can be expressed as a convex combination of permutation matrices.[26] Specifically, for an n \times n doubly stochastic matrix D, there exist permutation matrices P_{\sigma_k} (for permutations \sigma_k) and non-negative coefficients \lambda_k with \sum_k \lambda_k = 1 such that
D = \sum_k \lambda_k P_{\sigma_k}.
The number of terms in such a decomposition is at most (n-1)^2 + 1.[26]
This theorem has applications in combinatorial optimization, particularly in solving the assignment problem, where the goal is to find a permutation matrix that minimizes the total cost of assigning tasks to agents.[27] The Hungarian algorithm, a primal-dual method, efficiently computes such an optimal permutation matrix by reducing the problem to finding perfect matchings in a bipartite graph, with solutions corresponding to vertices of the Birkhoff polytope.[27]
For example, consider the average of the identity permutation matrix and the matrix corresponding to the cycle permutation (1\ 2\ 3) for n=3:
P_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad P_2 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.
Their average is
\frac{1}{2} (P_1 + P_2) = \begin{pmatrix} 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \\ 0.5 & 0 & 0.5 \end{pmatrix},
a doubly stochastic matrix with entries of 0.5 along the positions of the cycle and the fixed points.
Restricted Permutation Matrices
Restricted permutation matrices are a subclass of permutation matrices where the positions of the 1's are constrained to avoid certain forbidden locations or substructures, often defined by combinatorial restrictions such as partial orders or pattern avoidance. In the case of restricted positions, a permutation matrix corresponds to a bijection \sigma: \to such that (\sigma(i), i) lies in a prescribed subset B \subseteq \times for all i, ensuring no 1 appears in disallowed entries.[28] More generally, these matrices arise as (0,1)-matrices with exactly one 1 per row and column that avoid specified submatrix patterns, generalizing classical permutation pattern avoidance to broader structural constraints.[29]
A prominent example involves permutation matrices corresponding to linear extensions of a poset, where the 1's in row i and column j are permitted only if i \leq j in the poset order, reflecting order-preserving bijections from the poset to a total order.[30] Another key class consists of pattern-avoiding permutation matrices, such as those avoiding the 321 pattern, which forbid any decreasing subsequence of length 3 in the underlying permutation; these matrices have no 3x3 submatrix matching the anti-diagonal pattern of 1's.[29] In Coxeter groups, particularly the symmetric group, reduced decompositions of permutations impose restrictions on the matrix entries, linking to pattern containment where certain braid relations are avoided in the word representation of the permutation.[31]
The enumeration of restricted permutation matrices frequently yields closed-form combinatorial formulas tied to classical sequences. For instance, the number of 321-avoiding permutation matrices of size n equals the nth Catalan number,
C_n = \frac{1}{n+1} \binom{2n}{n},
reflecting the bijection between such permutations and Dyck paths or balanced parentheses.[32] Similarly, for mobile posets (a subclass including ribbons and d-complete posets), the number of corresponding linear extension matrices is given by n! times the determinant of a hook-length matrix M, where M_{i,j} = 1 / \prod_{x \in P_{i,j}} h(x) for subposets P_{i,j} and hook lengths h(x), providing an exact count via linear algebra.[30] For monotone grid classes—permutations avoiding patterns defined by monotone subsequences in a grid—the asymptotic enumeration follows from generating functions derived from the grid's dimensions.[33]
These matrices find applications in sorting networks, where a network's comparators induce restricted permutations representable as products of permutation matrices with banded or topology-limited 1's, enabling efficient parallel sorting with depth bounded by the graph's sorting number. In the theory of Young tableaux, every n \times n permutation matrix bijects to a pair of generalized Young tableaux of the same shape, with rows non-decreasing and columns strictly increasing, facilitating enumerative connections to symmetric group representations.[34]
Recent developments in algebraic combinatorics highlight restricted permutation matrices in quiver representations, where partial permutation matrices encode dimension vectors and map assignments for type A quivers, aiding the computation of K-polynomials and equivariant cohomology of orbit closures via permutation actions on positroid varieties.[35]
Linear-Algebraic Properties
Determinants, Eigenvalues, and Trace
The determinant of a permutation matrix P_\sigma, where \sigma is a permutation of \{1, \dots, n\}, equals the sign of the permutation, \det(P_\sigma) = \sgn(\sigma), which is either +1 or -1.[36] This sign is given by \sgn(\sigma) = (-1)^k, where k is the number of inversions in \sigma (pairs i < j with \sigma(i) > \sigma(j)), or equivalently the parity of the number of even-length cycles in its cycle decomposition.[3]
To see this, apply the Leibniz formula for the determinant:
\det(A) = \sum_{\pi \in S_n} \sgn(\pi) \prod_{i=1}^n a_{i, \pi(i)},
where S_n is the symmetric group on n elements. For P_\sigma, the entry (P_\sigma)_{i,j} = 1 if j = \sigma(i) and 0 otherwise, so the product \prod_{i=1}^n (P_\sigma)_{i, \pi(i)} = 1 only if \pi(i) = \sigma(i) for all i, i.e., \pi = \sigma. All other terms vanish, leaving \det(P_\sigma) = \sgn(\sigma) \cdot 1 = \sgn(\sigma).[37] For the identity permutation I, \det(P_I) = 1 and \tr(P_I) = n; for a transposition \tau, \det(P_\tau) = -1 and \tr(P_\tau) = n-2.[36]
Permutation matrices for even permutations (those with \sgn(\sigma) = 1) thus have determinant 1, realizing the defining representation of the alternating group A_n.[3]
Permutation matrices are real orthogonal, so P_\sigma^T P_\sigma = I and their eigenvalues \lambda satisfy |\lambda| = 1, lying on the unit circle in the complex plane.[36] More precisely, the eigenvalues arise from the cycle decomposition of \sigma: if \sigma consists of disjoint cycles of lengths k_1, k_2, \dots, the eigenvalues are the k_j-th roots of unity for each cycle, with multiplicity according to the cycle structure.[38] For a single k-cycle, these are e^{2\pi i m / k} for m = 0, 1, \dots, k-1.[38]
The trace of P_\sigma equals the number of fixed points of \sigma, since the diagonal entry (P_\sigma)_{i,i} = 1 if and only if \sigma(i) = i, and 0 otherwise; thus, \tr(P_\sigma) = \sum_{i=1}^n \mathbf{1}_{\sigma(i)=i}.[39] The algebraic multiplicity of the eigenvalue 1 equals the number of cycles in the cycle decomposition of σ, since each cycle contributes exactly one eigenvalue 1.[40]
Permutation matrices encode linear transformations that rearrange the coordinates of vectors according to a given permutation of the standard basis. For a permutation \sigma of \{1, \dots, n\}, the corresponding permutation matrix P_\sigma is defined such that its j-th column is the standard basis vector e_{\sigma(j)}, resulting in P_\sigma x having components (P_\sigma x)_i = x_{\sigma^{-1}(i)} for any vector x \in \mathbb{R}^n.[1] This transformation permutes the entries of x by applying \sigma^{-1} to the indices, effectively reordering the coordinates while acting linearly on the vector space.[1]
Multiplying a matrix A on the left by P_\sigma permutes its rows according to \sigma, whereas right multiplication A P_\sigma permutes the columns. These operations are invertible, with P_\sigma^{-1} = P_{\sigma^{-1}}, and preserve the solution set of linear systems Ax = b since row permutations do not alter the underlying equations.[1] Such permutations are essential for reordering data in computational contexts, such as transforming coordinate systems or basis vectors in linear algebra applications.[1]
In numerical methods, permutation matrices play a key role in Gaussian elimination with partial pivoting to enhance stability. During elimination, if the pivot element in column k is small or zero, a permutation matrix P_k swaps the current row with the row containing the largest absolute value below the pivot, bringing a more suitable element to the diagonal position.[41] The process yields the decomposition PA = [LU](/page/Lu), where P is the product of these permutation matrices, L is unit lower triangular, and U is upper triangular; this avoids division by near-zero elements and bounds error propagation in floating-point arithmetic to roughly machine epsilon times the condition number of A.[41]
Permutation matrices are orthogonal, satisfying P^T P = I, which implies they preserve the Euclidean norm \|Px\| = \|x\| and inner products \langle Px, Py \rangle = \langle x, y \rangle for all vectors x, y. This property positions them as linear isometries, useful in applications requiring undistorted geometric structures, such as coordinate permutations in optimization problems or simulations where spatial relationships must remain intact.