## 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 .

This entry was posted in linear algebra and tagged , , , . Bookmark the permalink.