In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. Permutation matrices are the matrix representation of permutations.

Definition

---

Given a permutation π of m elements

$\backslash pi\; :\; \backslash lbrace\; 1,\; \backslash ldots,\; m\; \backslash rbrace\; \backslash to\; \backslash lbrace\; \backslash pi(1),\; \backslash ldots,\; \backslash pi(m)\; \backslash rbrace$

the permutation matrix P_π with m elements is defined as

$P\_\{\backslash pi\}\; :=\; \backslash begin\{bmatrix\}$

\mathbf{e}_{\pi(1)} \\ \vdots \\ \mathbf{e}_{\pi(m)} \\ \end{bmatrix}

with e_i being the i-th vector in the identity matrix.

Properties

---

Given two permutations π and σ of m elements and the corresponding permutation matrices P_π and P_σ

$P\_\{\backslash pi\}\; P\_\{\backslash sigma\}\; =\; P\_\{\backslash pi\; \backslash circ\; \backslash sigma\}$

As permutation matrices are orthogonal matrices the inverse matrix exists and can be written as

$P\_\{\backslash pi\}^\{-1\}\; =\; P\_\{\backslash pi^\{-1\}\}$

The multiplication of a permutation matrix P_π with a vector g will permute the entries of the vector.

$P\_\backslash pi\; \backslash mathbf\{g\}$

= \begin{bmatrix} \mathbf{e}_{\pi(1)} \\ \vdots \\ \mathbf{e}_{\pi(n)} \end{bmatrix}

\begin{bmatrix} g_1 \\ \vdots \\ g_n \end{bmatrix} = \begin{bmatrix} g_{\pi(1)} \\ \vdots \\ g_{\pi(n)} \end{bmatrix}

Notes

---

P₍₁₎ is the identity matrix. This is clear if one views the permutation matrix of a permutation σ, as the permutation of the rows or columns of the identity matrix.

A permutation matrix is a stochastic matrix; in fact doubly stochastic. One can show that every doubly stochastic matrix is a convex combination of permutation matrices of the same size, giving permutation matrices a characterisation as the set of extreme points.

The product of a matrix M with a permutation matrix P on the right (PM) permutes the rows of M, likewise, on the left (MP), permutes the columns of M.

Since the map S_n → A ⊂ GL(n, Z₂) is a faithful representation, we have the following:

• There are n! n-by-n permutation matrices, so |S_n| = |A| = n!.
• The n-by-n permutation matrices form a group under matrix multiplication with the identity matrix as the identity element, as S_n is.

The trace of a permutation matrix is the number of fixed points of the permutation. If the permutation has fixed points, so it can be written as (a₁)(a₂)...(a_n)q where q has no fixed points, then e₁,e₂,...,e_n are eigenvectors of the permutation matrix.

From group theory we know that any permutation may be written as a product of transpositions. Therefore, any permutation matrix P factors as a product of row-interchanging elementary matrices, each having determinant −1. Thus the determinant of a permutation matrix P is just the signature of the corresponding permutation.

Examples

---

The permutation matrix P_π corresponding to the permutation π=(1)(2 4 5 3) is

$P\_\backslash pi$

= \begin{bmatrix} \mathbf{e}_{\pi(1)} \\ \mathbf{e}_{\pi(2)} \\ \mathbf{e}_{\pi(3)} \\ \mathbf{e}_{\pi(4)} \\ \mathbf{e}_{\pi(5)} \end{bmatrix} = \begin{bmatrix} \mathbf{e}_{1} \\ \mathbf{e}_{4} \\ \mathbf{e}_{2} \\ \mathbf{e}_{5} \\ \mathbf{e}_{3} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}

and given a vector g

$P\_\backslash pi\; \backslash mathbf\{g\}$

= \begin{bmatrix} \mathbf{e}_{\pi(1)} \\ \mathbf{e}_{\pi(2)} \\ \mathbf{e}_{\pi(3)} \\ \mathbf{e}_{\pi(4)} \\ \mathbf{e}_{\pi(5)} \end{bmatrix}

\begin{bmatrix} g_1 \\ g_2 \\ g_3 \\ g_4 \\ g_5 \end{bmatrix} = \begin{bmatrix} g_1 \\ g_4 \\ g_2 \\ g_5 \\ g_3 \end{bmatrix}

Solving for P

---

The question of "if I have two matrices A and B, how can I find P?" is answerable through the use of eigenvalue decomposition which yields:

$A\; =\; Q\; \backslash Lambda\; Q^\{-1\}$

where $\backslash Lambda$ is a diagonal matrix of eigenvalues and $Q$ is the matrix of eigenvectors.

The permutation matrix $P$ relates $A$ and $B$ by

$B\; =\; P\; A\; P^\{-1\}$

Since the eigenvalues of $A$ and $B$ are the same then we can write $Q\_B\; =\; P\; Q\_A$. From this we see that the elements of an eigenvector are transformed through $P$.

Example

Given the two matrices

$$

A = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 0 & 1.5 \\ 2 & 1.5 & 0 \end{bmatrix}

$$

B = \begin{bmatrix} 0 & 1 & 1.5 \\ 1 & 0 & 2 \\ 1.5 & 2 & 0 \end{bmatrix}

and the transformation matrix that changes $A$ into $B$ is

$$

P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

which says that the first & second row as well as the first & second column of $A$ have been swapped to yield $B$ (and visual inspection confirms this).

After finding the eigenvalues of both $A$ and $B$ and diagonalizing them into a diagonal matrix is

$$

\Lambda = \begin{bmatrix} -2.09394 & 0 & 0 \\ 0 & 0.9433954 & 0 \\ 0 & 0 & 3.037337 \end{bmatrix}

and the $Q\_A$ matrix of eigenvectors for $A$ is

$$

Q_A = \begin{bmatrix} -0.60130 & 0.54493 & 0.58437 \\ -0.25523 & -0.82404 & 0.50579 \\ 0.75716 & 0.15498 & 0.63458 \end{bmatrix}

and the $Q\_B$ matrix of eigenvectors for $B$ is

$$

Q_B = \begin{bmatrix} -0.25523 & -0.82404 & -0.50579 \\ -0.60130 & 0.54493 & -0.58437 \\ 0.75716 & 0.15498 & -0.63458 \end{bmatrix}

Comparing the first eigenvector (i.e., the first column) of both we can write the first column of $P$ by noting that the first element ($Q\_\{A(1,1)\}\; =\; -0.60130$) matches the second element ($Q\_\{B(2,1)\}$), thus we put a 1 in the second element of the first column of $P$. Repeating this procedure, we match the second element ($Q\_\{A(2,1)\}$) to the first element ($Q\_\{B(1,1)\}$), thus we put a 1 in the first element of the second column of $P$; and the third element ($Q\_\{A(3,1)\}$) to the third element ($Q\_\{B(3,1)\}$), thus we put a 1 in the third element of the third column of $P$.

The resulting $P$ matrix is:

$$

P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

And comparing to the $P$ matrix from above, we find they are the same.

Explanation

---

A permutation matrix will always be in the form

$\backslash begin\{bmatrix\}$

\mathbf{e}_{a_1} \\ \mathbf{e}_{a_2} \\ \vdots \\ \mathbf{e}_{a_j} \\ \end{bmatrix} where e_ai represents the ith basis vector (as a row) for R^j, and where

$\backslash begin\{bmatrix\}$

1 & 2 & \ldots & j \\ a_1 & a_2 & \ldots & a_j\end{bmatrix} is the permutation form of the permutation matrix.

Now, in performing matrix multiplication, one essentially forms the dot product of each row of the first matrix with each column of the second. In this instance, we will be forming the dot product of each column of this matrix with the vector with elements we want to permute. That is, for example, if we call this vector v = (g₀,...,g₅)^T,

e_ai·v=g_ai

So, the product of the permutation matrix with the vector v above, will be a vector in the form (g_a1, g_a2, ..., g_aj), and that this then is a permutation of v since we have said that the permutation form is

$\backslash begin\{bmatrix\}$

1 & 2 & \ldots & j \\ a_1 & a_2 & \ldots & a_j\end{bmatrix} So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.

Generalization

---

The sum of the values in each column or row in a permutation matrix adds up to exactly 1. A possible generalization of permutation matrices are matrices where the values of each column and row add up to a number c.

For example in the following matrix M each column or row adds up to 5.

$M\; =$

\begin{bmatrix} 5 & 0 & 0 & 0 & 0 \\ 0 & 3 & 2 & 0 & 0 \\ 0 & 0 & 0 & 5 & 0 \\ 0 & 1 & 2 & 0 & 2 \\ 0 & 1 & 1 & 0 & 3 \end{bmatrix}

A matrix of this sort can be decomposed into permutation matrices as

$M\; =\; c\_1\; P\_1\; +\; \backslash cdots\; +\; c\_t\; P\_t$

with

$\backslash sum\_\{i=1\}^\{t\}\; c\_i\; =\; c.$

See also

---

• Alternating sign matrix
• Generalized permutation matrix

Matrices | Permutations

Permutationsmatrix | Matrice de permutation | Matrice permutativa | Ma trận hoán vị