Given two Permutation Matrices, $P_1$ and $P_2$, when is $P_1P_2 = P_2P_1$?

Question

I've been working on Gilbert Strang's Linear Algebra book. This question came up in exercises but the solution wasn't satisfying. I've tried working intuitively, as well as rigorously but didn't get to an answer. One of the things I've noticed is that if Permutation matrices swap different rows of matrices, then the order should not matter, but does that imply that $3$x$3$ permutation matrices wouldn't have this property? (If we exclude the Identity matrix, cause it's a degenerate case.) And does this also imply that if $P_1%$ and $P_2$ exchange any common row, and $P_1 \neq P_2$, then $P_1P_2\neq P_2P_1$?

Answer 1

Lets say P_1 exchanges a th row with b th row and P_2 exchanges b th row with c th row note that a,b,c are different and a <b <c. Then the matrix can be shown with rows M = R_i R_1,R_2,...,a,...,b,...,c,...,R_n P_1 M =R_1,...,b,...,a,...,c,...,R_n P_2P_1 M=R_1,...,b,...,c,...,a,...,R_n P_2 M=R_1,...,a,...,c,...,b,...,R_n P_1P_2 M=R_1,...,c,...,a,...,b,...,R_n

As you can see P_1 P_2 M is not equal to P_2P_1 M unless a th row = b th row = c th row and in our situation M=I all rows are different so your statement is true

Answer 2

If we use cycle notation then swapping row $x$ with row $y$ would be represented by the transposition $(x,y)$. If you have two permutations that permute the same row and are unequal, they will be of the form $(x,y)$ and $(y,z)$ with $x \neq z$. We can then calculate $(x,y)(y,z)=(x,y,z)$ and $(y,z)(x,y) = (x,z,y)$ and so they do not commute because $(x,y,z) \neq (x,z,y)$.