Linear Algebra and Its Applications, Review Exercise 2.20

Review exercise 2.20. Consider the set of all 5 by 5 permutation matrices. How many such matrices are there? Are the matrices linearly independent? Do the matrices span the set of all 5 by 5 matrices?

Answer: An example member of this set is

$\begin{bmatrix} 1&0&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&0&1 \\ 0&1&0&0&0 \\ 0&0&0&1&0 \end{bmatrix}$

Note that for any such permutation matrix each row has the value 1 in one column and the value 0 in all other columns. Also note that if a given row has a 1 in a given column then no other row can have a 1 in that column.

This allows us to calculate the number of permutation matrices as follows: For the first row we have five columns in which to put a 1. Having chosen a 1 column for the first row, we then have four choices for the column to contain a 1 in the second row (because we can’t put it in the same column as in the first row). Having chosen the 1 columns for the first two rows we have three choices for the 1 column in the third row, and having chosen the 1 columns for the first three rows we have two choices for the 1 column in the fourth row. Finally, having chosen the 1 columns for the first four rows there is only one choice for the 1 column in the fifth row.

The number of 5 by 5 permutation matrices is therefore

$5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 = 5!$

(In general the number of $n$ by $n$ permutation matrices is $n!$ .)

The set of 5 by 5 matrices has dimension $5 \cdot 5 = 25$ . Since the number of 5 by 5 permutation matrices is greater than 25 the set of permutation matrices cannot be linearly independent.

Does the set of 5 by 5 permutation matrices span the space of all 5 by 5 matrices? One way to address this question is to first look at the set of 3 by 3 permutation matrices, of which there are $3! = 6$ matrices. A linear combination of such matrices looks as follows:

$c_1 \begin{bmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} + c_2 \begin{bmatrix} 1&0&0 \\ 0&0&1 \\ 0&1&0 \end{bmatrix}$

$+ c_3 \begin{bmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{bmatrix} + c_4 \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&0 \end{bmatrix}$

$+ c_5 \begin{bmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{bmatrix} + c_6 \begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix}$

$= \begin{bmatrix} c_1+c_2&c_3+c_4&c_5+c_6 \\ c_3+c_5&c_1+c_6&c_2+c_4 \\ c_4+c_6&c_2+c_5&c_1+c_3 \end{bmatrix}$

Notice that for each row in the resulting matrix the sum of the entries in the row is the same, namely $c_1+c_2+c_3+c_4+c_5+c_6$ .

Now consider the set of 5 by 5 permutation matrices $P_i$ and consider forming a linear combination of those matrices; this produces a matrix

$A = c_1P_1 + c_2P_2 + \cdots + c_{120}P_{120}$

$= \sum_{i=1}^{120} c_iP_i$

for some arbitrary set of scalars $c_i$ .

Consider an arbitrary row of $A$ . Of the 120 5 by 5 permutation matrices there are 24 permutation matrices that have the value 1 in column 1, so the entry for column 1 in that row of $A$ will be the sum of the 24 scalars $c_i$ that multiply those matrices. Similarly, there is a different set of 24 permutation matrices that have a 1 in column 2, so the entry for column 2 in that row of $A$ will be the sum of the different 24 scalars $c_i$ that multiply those matrices. Continuing in this way for columns 3 through 5, we see that each scalar $c_i$ contributes to the value of one and only one column in that row of $A$ , and that (as in the 3 by 3 case) the sum of the entries for all columns in that row is equal to the sum of the 120 scalars, or $\sum_{i = 1}^{120} c_i$ .

We chose an arbitrary row, so this same argument applies to all rows of $A$ : the sum of the entries for all columns in each row of $A$ is equal to the same value $\sum_{i = 1}^{120} c_i$ .

There are matrices for which the sum of the entries in each row is not equal, for example the matrix

$B = \begin{bmatrix} 1&0&0&0&1 \\ 0&1&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \end{bmatrix}$

for which the sum of the entries in the first row is 2 and the sum of the entries in all other rows is 1. The matrix $B$ cannot be expressed as a linear combination of the 5 by 5 permutation matrices (otherwise the sum of the entries in each row of $B$ would be the same), and thus the set of 5 by 5 permutation matrices does not span the space of all 5 by 5 matrices.

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.

Buy me a snack to sponsor more posts like this!

Linear Algebra and Its Applications, Review Exercise 2.20

Leave a Reply Cancel reply

Archives

Meta

Linear Algebra and Its Applications, Review Exercise 2.20

Share this:

Like this:

Related

Leave a Reply Cancel reply

Archives

Meta