In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. Pre-multiplying an -row matrix by a permutation matrix , forming , results in permuting the rows of , while post-multiplying an -column matrix , forming , permutes the columns of .
Every permutation matrix P is orthogonal, with its inverse equal to its transpose: <math>P^{-1}=P^\mathsf{T}</math>.
The two permutation/matrix correspondences
There are two natural one-to-one correspondences between permutations and permutation matrices, one of which works along the rows of the matrix, the other along its columns. Here is an example, starting with a permutation in two-line form at the upper left:
:<math>\begin{matrix}
\pi\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
R_\pi\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
C_\pi\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\pi^{-1}\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}</math>
The row-based correspondence takes the permutation to the matrix <math>R_\pi</math> at the upper right. The first row of <math>R_\pi</math> has its 1 in the third column because <math>\pi(1)=3</math>. More generally, we have <math>R_\pi=(r_{ij})</math> where <math>r_{ij}=1</math> when <math>j=\pi(i)</math> and <math>r_{ij}=0</math> otherwise.
The column-based correspondence takes to the matrix <math>C_\pi</math> at the lower left. The first column of <math>C_\pi</math> has its 1 in the third row because <math>\pi(1)=3</math>. More generally, we have <math>C_\pi=(c_{ij})</math> where <math>c_{ij}</math> is 1 when <math>i=\pi(j)</math> and 0 otherwise. Since the two recipes differ only by swapping i with j, the matrix <math>C_\pi</math> is the transpose of <math>R_\pi</math>; and, since <math>R_\pi</math> is a permutation matrix, we have <math>C_\pi=R_\pi^\mathsf{T}=R_\pi^{-1}</math>. Tracing the other two sides of the big square, we have <math>R_{\pi^{-1=C_\pi=R_\pi^{-1}</math> and <math>C_{\pi^{-1=R_\pi</math>.
Permutation matrices permute rows or columns
Multiplying a matrix M by either <math>R_\pi</math> or <math>C_\pi</math> on either the left or the right will permute either the rows or columns of M by either or <sup>−1</sup>. The details are a bit tricky.
To begin with, when we permute the entries of a vector <math>(v_1,\ldots,v_n)</math> by some permutation , we move the <math>i^\text{th}</math> entry <math>v_i</math> of the input vector into the <math>\pi(i)^\text{th}</math> slot of the output vector. Which entry then ends up in, say, the first slot of the output? Answer: The entry <math>v_j</math> for which <math>\pi(j)=1</math>, and hence <math>j=\pi^{-1}(1)</math>. Arguing similarly about each of the slots, we find that the output vector is
:<math> \big(v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\ldots,v_{\pi^{-1}(n)}\big),</math>
even though we are permuting by <math>\pi</math>, not by <math>\pi^{-1}</math>. Thus, in order to permute the entries by <math>\pi</math>, we must permute the indices by <math>\pi^{-1}</math>.)
Now, suppose that we pre-multiply some n-row matrix <math>M=(m_{i,j})</math> by the permutation matrix <math>C_\pi</math>. By the rule for matrix multiplication, the <math>(i,j)^\text{th}</math> entry in the product <math>C_\pi M</math> is
:<math display=block>\sum_{k=1}^n c_{i,k}m_{k,j},</math>
where <math>c_{i,k}</math> is 0 except when <math>i=\pi(k)</math>, when it is 1. Thus, the only term in the sum that survives is the term in which <math>k=\pi^{-1}(i)</math>, and the sum reduces to <math>m_{\pi^{-1}(i),j}</math>. Since we have permuted the row index by <math>\pi^{-1}</math>, we have permuted the rows of M themselves by .
Linear-algebraic properties
Just as each permutation is associated with two permutation matrices, each permutation matrix is associated with two permutations, as we can see by relabeling the example in the big square above starting with the matrix P at the upper right:
:<math>\begin{matrix}
\rho_P\colon\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}
& \longleftrightarrow &
P\colon\begin{pmatrix}
0&0&1&0\\
0&1&0&0\\
0&0&0&1\\
1&0&0&0\end{pmatrix}\\[5pt]
\Big\updownarrow && \Big\updownarrow\\[5pt]
P^{-1}\colon\begin{pmatrix}
0&0&0&1\\
0&1&0&0\\
1&0&0&0\\
0&0&1&0\end{pmatrix}
& \longleftrightarrow &
\kappa_P\colon\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}\end{matrix}</math>
So we are here denoting the inverse of C as <math>\kappa</math> and the inverse of R as <math>\rho</math>. We can then compute the linear-algebraic properties of P from some combinatorial properties that are shared by the two permutations <math>\kappa_P</math> and <math>\rho_P=\kappa_P^{-1}</math>.
A point is fixed by <math>\kappa_P</math> just when it is fixed by <math>\rho_P</math>, and the trace of P is the number of such shared fixed points. (Since any permutation matrix is normal and any normal matrix is diagonalizable over the complex numbers,