- #1
Kastchei
- 2
- 0
Homework Statement
"How many 5x5 permutation matrices are there? Are they linearly independent? Do they span the space of all 5x5 matrices?"
Homework Equations
The Attempt at a Solution
The first two questions are fairly easy. 5! = 120 P matrices. Since dim(space of all 5x5 matrices) = 25, the rank of a matrix of P-matrices would be at most 25; and since we have 120 Ps, the null space has at least dimension = 120 - 25 = 95 > 0, therefore the columns (P-matrices) are not linearly independent.
The question about spanning the space of all 5x5 matrices has me stumped. I assume you could start with the fact that in order to span a 25 dimension space, you have to have a 25 linearly independent vectors in R25, as this is the size of a basis which is a minimal spanning set. So if all 5x5 Ps span the space of 5x5s, then there must be a 25 member subset of those 120 that are linearly independent, which means that the rank of my matrix of 120 matrices would have to be 25 (and thus my column space). How in the world do I find that subset though! It seems plausible that there may be none.
Edit:
I think I figured it out, but it's not particularly elegant - which usually tells me there's a simpler way. If anyone knows of a better proof, please let me know!
If I wrote each matrix as a vertical vector, then I have A, a 25x120 matrix. As discussed above, the column space has to have dimension 25 to span all of R25. That means the left null space has to have dimension = 0 (25 - 25). This means that only the zero vector (in R25) would combine the rows to form 0. In looking at my columns of 25 values each, no matter how I place my original columns, each group of 5 values (going down the column) contains only one 1. The rest are zeros. This comes from the definition of a permutation matrix which has only one 1 in a row/column and 0s elsewhere. Thus the vector y = (1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) will yield yTA = 0 no matter how I write A. The first group of five numbers will contain, in some order, 1*1 + 1*0 + 1*0 + 1*0 + 1*0 = 1. The second group will contain -1*1 + -1*0 + -1*0 + -1*0 + -1*0 = -1. Together these = 0, and the other 15 values also contribute 0 since the rest of y is 0. Therefore, the vector y is in the left null space which means that dim(left null) = m - r = 25 - r > 0 -> r < 25, which means the column space < 25 so it cannot span R25. Phew!
Last edited: