## Linear Algebra and Its Applications, Exercise 1.5.14

Exercise 1.5.14. Find all possible 3 by 3 permutation matrices, along with their inverses.

Answer: The identity matrix I is the first possible permutation matrix, corresponding to not doing a row exchange at all; it is its own inverse: $I = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix}$ $I \cdot I = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$

The permutation matrix $P_{12}$ exchanges rows 1 and 2: $P_{12} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix}$

A second exchange of rows 1 and 2 returns both rows to their original position, so $P_{12}$ is its own inverse: $P_{12}P_{12} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$

The permutation matrix $P_{13}$ exchanges rows 1 and 3: $P_{13} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix}$

A second exchange of rows 1 and 3 returns both rows to their original position, so $P_{13}$ is also its own inverse: $P_{13} P_{13} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$

The permutation matrix $P_{23}$ exchanges rows 2 and 3: $P_{23} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix}$

As with $P_{12}$ and $P_{13}$ (and for similar reasons) $P_{23}$ is also its own inverse: $P_{23} P_{23} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$

We can generate a fifth permutation matrix by exchanging rows 1 and 3 and then exchanging rows 2 and 3; this is equivalent to multiplying $P_{23}$ by $P_{13}$: $P_5 = P_{23} P_{13} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix}$

(Note that the order of multiplication is important here; since by convention we apply permutation matrices to the left, we put $P_{13}$ on the right and then multiply it by $P_{23}$ on the left.) The resulting matrix sends row 1 to row 2, row 2 to row 3, and row 3 to row 1.

We can generate a sixth permutation matrix by reversing the exchanges used in creating the previous permutation matrix; in other words, we first exchange rows 2 and 3, and then subsequently exchange rows 1 and 3. This is equivalent to multiplying $P_{13}$ by $P_{23}$: $P_6 = P_{13} P_{23} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix}$

The resulting matrix sends row 1 to row 3, row 2 to row 1, and row 3 to row 2, reversing the effect of the fifth permutation matrix. The fifth and sixth matrices are therefore inverses of each other: $P_5 P_6 = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$ $P_6 P_5 = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = I$

In permuting the rows of a 3 by 3 matrix, we have three possible choices for row 1 of the permuted matrix. (In other words, row 1 of the permuted matrix could be set to row 1, row 2, or row 3 of the original matrix.) Having made that choice, we have two choices remaining for row 2 of the permuted matrix. (For example, if we set row 1 of the permuted matrix to be row 3 of the original matrix, then row 2 of the permuted matrix could be set to either row 1 or row 2 of the original matrix.)

Having made the first two choices, there is only one choice remaining for row 3 of the permuted matrix. (For example, if we set row 1 of the permuted matrix to be row 3 of the original matrix and row 2 of the permuted matrix to be row 1 of the original matrix, then row 3 of the permuted matrix must be set to row 2 of the original matrix.) There are thus 3 times 2 times 1 or 6 possible ways to permute the rows of a 3 x 3 matrix. (This is a special case of the general result that there are n times n-1 times n-2 … times 2 times 1 or $n!$ ways to permute n items.)

We have found six 3 by 3 permutation matrices: $I = \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} \quad P_{12} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \quad P_{13} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix}$ $P_{23} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \quad P_5 = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \quad P_6 = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix}$

This therefore completes the set of all possible 3 x 3 permutation matrices.

Extra credit: From above we have six 3 by 3 permutation matrices: I, $P_{12}$, $P_{13}$, $P_{23}$, $P_5$ (equal to $P_{23}P_{13}$), and $P_6$ (equal to $P_{13}P_{23}$). There are 36 possible products of the six matrices (six possible choices for the left factor, and six for the right). We already know that IA = AI = A for any matrix A. We also know that any of $P_{12}$, $P_{13}$, and $P_{23}$ times itself equals I, since each of these three matrices is its own inverse. Finally, we know that $P_{23}P_{13}$ equals $P_5$, $P_{13}P_{23}$ equals $P_6$, and $P_5 P_6$ equals $P_6 P_5$ equals I.

What about other products? We have $P_{12} P_{13} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = P_6$

and $P_{13} P_{12} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = P_5$

We also have $P_{12} P_{23} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = P_5$

and $P_{23} P_{12} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = P_6$

We then have $P_{13} P_{23} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = P_6$

and $P_{23} P_{13} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = P_5$

We next find the products of $P_5$ and $P_6$ with $P_{12}$, $P_{13}$, and $P_{23}$ respectively. We start by multiplying by $P_5$ on the left: $P_5 P_{12} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = P_{13}$ $P_5 P_{13} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = P_{23}$ $P_5 P_{23} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = P_{12}$

and then on the right: $P_{12} P_5 = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} = P_{23}$ $P_{13} P_5 = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} = P_{12}$ $P_{23} P_5 = \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix} = P_{13}$

We can then use the results above to compute products involving $P_6$ by taking advantage of the fact that $P_6$ is the inverse of $P_5$: $P_5 P_{12} = P_{13} \Rightarrow P_6 P_5 P_{12} = P_6 P_{13} \Rightarrow I P_{12} = P_6 P_{13} \Rightarrow P_6 P_{13} = P_{12}$ $P_5 P_{13} = P_{23} \Rightarrow P_6 P_5 P_{13} = P_6 P_{23} \Rightarrow I P_{13} = P_6 P_{23} \Rightarrow P_6 P_{23} = P_{13}$ $P_5 P_{23} = P_{12} \Rightarrow P_6 P_5 P_{23} = P_6 P_{12} \Rightarrow I P_{23} = P_6 P_{12} \Rightarrow P_6 P_{12} = P_{23}$ $P_{12} P_5 = P_{23} \Rightarrow P_{12} P_5 P_6 = P_{23} P_6 \Rightarrow P_{12} I = P_{23} P_6 \Rightarrow P_{23} P_6 = P_{12}$ $P_{13} P_5 = P_{12} \Rightarrow P_{13} P_5 P_6 = P_{12} P_6 \Rightarrow P_{13} I = P_{12} P_6 \Rightarrow P_{12} P_6 = P_{13}$ $P_{23} P_5 = P_{13} \Rightarrow P_{23} P_5 P_6 = P_{13} P_6 \Rightarrow P_{23} I = P_{13} P_6 \Rightarrow P_{13} P_6 = P_{23}$

Finally, we multiply $P_5$ and $P_6$ by themselves: $P_5 P_5 = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = P_6$ $P_6 P_6 = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} = P_5$

So the product of any two of the six 3 x 3 permutation matrices is itself one of the six permutation matrices. The following multiplication table summarizes the results above: $\setlength\arraycolsep{0.2em}\begin{array}{cccccccc}\times&\vline& I&P_{12}&P_{13}&P_{23}&P_5&P_6 \\ \hline I&\vline&I&P_{12}&P_{13}&P_{23}&P_5&P_6 \\ P_{12}&\vline&P_{12}&I&P_6&P_5&P_{23}&P_{13} \\ P_{13}&\vline&P_{13}&P_5&I&P_6&P_{12}&P_{23} \\ P_{23}&\vline&P_{23}&P_6&P_5&I&P_{13}&P_{12} \\ P_5&\vline&P_5&P_{13}&P_{23}&P_{12}&P_6&I \\ P_6&\vline&P_6&P_{23}&P_{12}&P_{13}&I&P_5 \end{array}$

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition , Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books .

This entry was posted in linear algebra. Bookmark the permalink.