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.

Linear Algebra and Its Applications, Exercise 1.5.14

Leave a Reply Cancel reply

Archives

Meta

Linear Algebra and Its Applications, Exercise 1.5.14

Share this:

Like this:

Related

Leave a Reply Cancel reply

Archives

Meta