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₍₁₎ is the identity matrix.
3. Permutation matrices are orthogonal matrix and P_σ^-1=P_σ^-1.

See also generalized permutation matrix.