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.

1 Response to Linear Algebra and Its Applications, Review Exercise 1.20

Pingback: Linear Algebra and Its Applications, Review Exercise 1.20 | My …