## Linear Algebra and Its Applications, Review Exercise 1.20

Review exercise 1.20. The set of $n$ by $n$ permutation matrices constitute a group.

(a) How many 4 by 4 permutation matrices are there? How many $n$ by $n$ permutation matrices are there?

(b) For the group of 3 by 3 permutation matrices, what does $k$ have to be in order for $P^k = I$ for all matrices P in the group?

Answer: (a) A permutation matrix has a single 1 entry in each row (with all the other entries in that row being zero) and each row must have that single 1 entry in a different column.

If we construct a 4 by 4 permutation matrix, we have 4 choices for the column in which the 1 entry can be in the first row. Having chosen that column, we have only 3 choices for the column having the 1 entry in the second row (because we cannot choose the same column as in the first row). Having chosen the columns in which the 1 entry is placed in rows 1 and 2, we then have only 2 choices for the column in row 3, and then only 1 choice for the column in row 4 (all the other columns already having been used). The number of possible 4 by 4 permutation matrices is therefore $4 \cdot 3 \cdot 2 \cdot 1 = 24$.

Similarly, for the group of $n$ by $n$ permutation matrices we have $n$ choices for where to put the 1 entry in row 1, $n-1$ choices for where to put the 1 entry in row 2, $n-2$ choices for where to put the 1 entry in row 3, and so on until we have only 1 choice for where to put the 1 entry in row $n$. The number of possible $n$ by $n$ permutation matrices is therefore $n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1 = n!$.

(b) There are $3!$ or six 3 by 3 permutation matrices, of which one is the identity matrix $I$ for which $I^k = I$ for any $k \ge 1$.

Of the remaining five 3 by 3 permutation matrices, three do simple row exchanges:

• exchange row 1 and row 2
• exchange row 1 and row 3
• exchange row 2 and row 3

For each of these matrices repeating the operation reverses the effect of the exchange, so we have $P^2 = I$. We then also have $P^4 = P^2P^2 = I \cdot I = I$ and in general $P^k = I$ for any even $k$.

The remaining two 3 by 3 permutation matrices do forward and reverse shifts of rows:

• move row 1 to row 2, row 2 to row 3, and row 3 to row 1
• move row 1 to row 3, row 2 to row 1, and row 3 to row 2

Applying each of these permutation matrices three times shifts all rows back into their original places, so we have $P^3 = I$. We then have $P^6 = P^3P^3 = I \cdot I = I$, and in general $P^k = I$ for any $k$ that is a multiple of 3.

Combining the results above, we see that $k = 6$ is the smallest $k$ for which $P^k = I$ for all 3 by 3 permutation matrixes $P$.

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.