What are the necessary and sufficient conditions for 2 permutation matrices to commute? I know disjoint matrices commutes, but it is not a necessary condition (e.g. $P_1=(1,2)(3,4)$ and $P_2=(1,3)(2,4)$ commutes). I want to know the necessary and sufficient condition for permutation matrices which commutes.
Moreover, what is the necessary and sufficient condition under which each pair of $k>2$ permutation matrices commute with each other?