# Strang, Introd. to Linear Algebra, Section 3.5, Problem 41: Visualizing independence of five of the permutation matrices

Write the $$3$$ by $$3$$ identity matrix as a combination of the other five permutation matrices! Then show that those five matrices are linearly independent.

The six permutation matrices are

$$P_1=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}$$ $$P_2=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}$$ $$P_3=\begin{bmatrix} 1&0&0\\ 0&0&1\\ 0&1&0 \end{bmatrix}$$ $$P_4=\begin{bmatrix} 0&0&1\\ 0&1&0\\ 1&0&0 \end{bmatrix}$$ $$P_5=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}$$ $$P_6=\begin{bmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}$$

By trial and error I was able to figure out that $$P_1=P_2+P_3+P_4-P_5-P_6$$

It is also relatively easy to show that $$P_2,...,P_6$$ are linearly independent. If we assume there is a combination

$$c_2P_2+...c_6P_6=0$$

The lefthand side is the matrix

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

And we obtain as the only solution $$c_2=...=c_6=0$$.

When I looked at the solution manual, the above was correct but they also added what seems to be a more intuitive way of seeing that five of the matrices are independent. Here is the solution manual solution

The six $$P$$'s are dependent. Those five (ie the ones in the picture above) are independent: the 4th has $$P_{11}=1$$ and cannot be a combination of the others. Then the 2nd cannot be (from $$P_{32}=1$$) and also 5th ($$P_{32}=1$$). Continuing, a nonzero combination of all five could not be zero.

I don't quite get what he is trying to say in this solution. In fact, it seems to be an issue of bad writing on the part of the authors of the snippet above more than anything else.

$$P_2$$, $$P_3$$, and $$P_4$$ (as I defined them initially) each have an entry that is $$1$$ for them and $$0$$ for the other four matrices.

In fact, these three matrices together give us a matrix of ones. To get from this ones matrix to identity, six off-main-diagonal ones have to become zero, and these are precisely the six entries that are present in $$P_5+P_6$$.

My question is how to interpret the apparent "intuitive" argument showing independence of five of the permutation matrices?

• Indeed, "an issue of bad writing on the part of the authors of the snippet above more than anything else". Dec 24, 2022 at 21:31

I agree that it isn't well-written, but I see what they're going for, and give or take a typo (or possibly transcription error), what they say is correct.

They point out that in all these permutations except $$P_3 = \pmatrix{1&&\\&&1\\&1&},$$ the top-left entry is $$0$$. So, if we form any linear combination of these matrices, the top-left entry of the final result will depend only on the coefficient of the above matrix. In fact, it will be equal to the coefficient of the above matrix! So, if our linear combination comes to the $$0$$ matrix, we can quickly see that the coefficient of this particular matrix will be $$0$$.

Note, your own calculation reveals the same thing, but perhaps with more calculation: $$\begin{pmatrix} \color{red}{c_3}&c_2+c_5& c_4+c_6\\ c_2+c_6&c_4&c_3+c_5\\ c_4+c_5 &c_3+c_6&c_2 \end{pmatrix}.$$ When this matrix is the $$0$$ matrix, we can very quickly see that $$c_3$$, the coefficient of the above matrix (which you called $$P_3$$) must be $$0$$. It's the same observation with less redundant computation.

We can even see that this same strategy will work for $$P_4$$ and $$P_2$$, looking at the middle and bottom left entries respectively. However, this is not what the author has done (and I'm really not sure why).

Since we know that the $$c_3$$ coefficient must be $$0$$, we can essentially eliminate $$P_3$$ from the linear combination. In other words, if we can throw away $$P_3$$ and prove the linear independence of $$P_2, P_4, P_5, P_6$$, then we get the linear independence of $$P_2, P_3, P_4, P_5, P_6$$.

And this is what the author does, taking the same technique with $$P_2, P_4, P_5, P_6$$, and considering the bottom-middle and middle-right entries. Only $$P_6$$ and $$P_5$$ respectively have $$1$$s there, once we've eliminated $$P_3$$. The same logic that eliminated $$P_3$$ allows us to eliminate $$P_5$$ and $$P_6$$.

In terms of your calculations, once we've determined that $$c_3$$ must be $$0$$, our matrix equation becomes: $$\begin{pmatrix} 0&c_2+c_5& c_4+c_6\\ c_2+c_6&c_4&\color{red}{c_5}\\ c_4+c_5 &\color{red}{c_6}&c_2 \end{pmatrix} = \begin{pmatrix} 0&0&0 \\ 0&0&0 \\ 0&0&0 \end{pmatrix},$$ and we can easily see $$c_5 = c_6 = 0$$.

You can see how you might continue in the same vein. There's nothing fundamentally different about this method of determining independence. Essentially, it amounts to solving the system of equations before you've even written out the system of equations!