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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s