Permutation Matrix¶

Definition¶

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

Interpretation¶

A permutation matrix reorders: multiplying by it permutes the entries of a vector, or the rows or columns of a matrix, without changing any value. It is the identity matrix with its rows put in a different order.

A 4 by 4 permutation matrix with one 1 in each row and column, multiplying the vector (x1, x2, x3, x4) to give its entries reordered as (x2, x4, x1, x3).

Row $1$ of the figure's $\boldsymbol{P}$ has its $1$ in column $2$ , so the first entry of $\boldsymbol{P}\boldsymbol{x}$ is $x_2$ ; rows $2$ , $3$ and $4$ pick $x_4$ , $x_1$ and $x_3$ . Row $i$ says which entry of $\boldsymbol{x}$ is copied into position $i$ , and column $j$ says where $x_j$ goes: column $1$ has its $1$ in row $3$ , so $x_1$ moves to position $3$ .

The matrix product $\boldsymbol{P}\boldsymbol{A}$ applies the same reordering to the rows of $\boldsymbol{A}$ , and $\boldsymbol{A}\boldsymbol{P}$ reorders its columns. A reordering is undone by the transpose: $\boldsymbol{P}^{\top}\boldsymbol{P}=\boldsymbol{I}$ $I$ , so the inverse is $\boldsymbol{P}^{-1}=\boldsymbol{P}^{\top}$ $P^{⊤}$ . The determinant is $1$ when the reordering can be made with an even number of swaps and $-1$ otherwise; the figure's $\boldsymbol{P}$ is three swaps, so its determinant is $-1$ .

The $n\times n$ permutation matrices correspond to the $n!$ elements of the symmetric group $S_n$ . Swapping two rows, an elementary row operation, is multiplication on the left by a permutation matrix; the LU decomposition $\boldsymbol{P}\boldsymbol{A}=\boldsymbol{L}\boldsymbol{U}$ records its row swaps this way.

A common slip is to take $\boldsymbol{P}^{-1}=\boldsymbol{P}$ $P$ . This holds for a single swap such as $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ , but applying the figure's $\boldsymbol{P}$ twice gives $(x_4,x_3,x_2,x_1)$ , not $\boldsymbol{x}$ .

Key Results¶

The identity matrix is a permutation matrix.
The product of two permutation matrices is a permutation matrix.

Examples¶

$\begin{pmatrix}0&1\\1&0\end{pmatrix}$ swaps two rows when multiplied on the left.
$\boldsymbol{I}_3$ represents the permutation that changes nothing.

Prerequisites¶

Matrix

Sources¶

Math II: Linear Algebra · Week 5

Last updated: 20 October 2026 03:02