Skip to main content

Subsection 3.1 Permutation matrices

Definition 3.1.53. Permutation matrix.

A permutation matrix has the rows of the identity matrix, \(\boldsymbol{I}_n\) in any order.
  • The simplest permutation matrix is the identity itself:
    \begin{equation*} \boldsymbol{I}_4 = \left[\begin{array}{rrrr} 1 \amp 0 \amp 0 \amp 0\\ 0 \amp 1 \amp 0 \amp 0\\ 0 \amp 0 \amp 1 \amp 0\\ 0 \amp 0 \amp 0 \amp 1 \end{array}\right] = \left[\begin{array}{rrrr} 1 \amp \amp \amp \\ \amp 1 \amp \amp \\ \amp \amp 1 \amp \\ \amp \amp \amp 1 \end{array}\right] \end{equation*}
  • The permutation matrix obtained by interchanging rows 3 and 2 is,
    \begin{equation*} \boldsymbol{P}_{32} = \left[\begin{array}{rrrr} 1 \amp \amp \amp \\ \amp \amp 1 \amp \\ \amp 1 \amp \amp \\ \amp \amp \amp 1 \end{array}\right] \end{equation*}
  • Other permutation matrices are,
    \begin{equation*} \boldsymbol{P}_{12} = \left[\begin{array}{rrrr} \amp 1 \amp \amp \\ 1\amp \amp \amp \\ \amp \amp 1\amp \\ \amp \amp \amp 1 \end{array}\right], \hspace{1cm} \boldsymbol{P}_{43} = \left[\begin{array}{rrrr} 1 \amp \amp \amp \\ \amp 1\amp \amp \\ \amp \amp \amp1 \\ \amp \amp 1 \amp \end{array}\right]. \end{equation*}

Insight 3.1.55. Products of permutation matrices.

Any product between two permutation matrices is itself a permutation.
Consider the following 3 by 3 permutation matrices,
\begin{equation*} \boldsymbol{P}_{31}= \left[\begin{array}{rrr} \amp \amp 1 \\ \amp 1 \amp \\ 1 \amp \amp \end{array}\right], \hspace{1cm} \boldsymbol{P}_{32} = \left[\begin{array}{rrr} 1 \amp \amp \\ \amp \amp 1 \\ \amp 1 \amp \end{array}\right]. \end{equation*}
Their product,
\begin{equation*} \boldsymbol{P}_{31} \boldsymbol{P}_{32}= \left[\begin{array}{rrr} \amp 1\amp \\ \amp \amp 1 \\ 1\amp \amp \end{array}\right] \end{equation*}
<Prev^TopNext>