Contents

Permutation matrix

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

For example, the permutation matrix corresponding to σ=(1)(2 4 5 3) is

<math>P_\sigma = \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}</math>

and

<math>P_\sigma\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}.</math>

In general, for a permutation σ on n objects, the correponding permutation matrix is an n-by-n matrix Pσ is given by Pσ[i,j]=1 if i=σ(j) and 0 otherwise. We have

<math>P_\sigma\begin{bmatrix}g_1\\ \vdots\\ g_n\end{bmatrix}
=\begin{bmatrix}g_{\sigma(1)}\\ \vdots\\ g_{\sigma(n)}\end{bmatrix}</math>.

Properties:

  1. PσPπ=Pσπ for any two permutations σ and π on n objects.
  2. P(1) is the identity matrix.
  3. Permutation matrices are orthogonal matrix and Pσ-1=Pσ-1.

See also generalized permutation matrix.