# Permutation matrices that commute

Just simple question:

Can anyone provide a list of types of permutation matrices that commute (with the matrices of the same type)?

for one, I can think of rotation matrix... (Oh, wait. it isn't really permutation matrix..)

-
Not sure what you exactly mean by the same type. But it is easy to see that permutation matrices commute if and only if the corresponding permutations commute. So you can ask an equivalent question: When do permutations commute? – Martin Sleziak Nov 9 '12 at 7:45
Are you asking about commutative subgroups of the group of all permutation matrices of a given size (equivalently of the corresponding symmetric group)? That would be very hard to do exhaustively, given that any finite (abelian) group can be embdded in a symmetric group, in many ways. – Marc van Leeuwen Nov 9 '12 at 12:25

Conjugation of one permutation by another leaves the cycle structure unchanged, but permutes the letters in the cycles according to the second permutation. So a permutation $\sigma$ that commutes with $\pi$ must map each cycle of $\pi$ to a cycle of $\pi$ (with the same length, of course). For example, the permutations of $6$ letters that commute with $(123)(456)$ will either map $(123)$ and $(456)$ to themselves or interchange them. They are determined by what they do to $1$ and $4$. Thus there are $6 \times 3 = 18$ possibilities, including the identity (maps $1 \to 1$ and $4 \to 4$) and $(162435)$ (maps $1 \to 6$ and $4 \to 3$).
In general, if a permutation $\sigma$ has a disjoint cycle decomposition with $n_{i}$ $i$-cycles for each $i$, then $C_{S_{n}}(\sigma)$ has the structure $\prod_{i} (C_{i} \wr S_{n_{i}}$, where $C_{i}$ is the cyclic group of order $i$ generated by one of the $i$-cycles of $\sigma$(viewed as an element of $S_{i}$). The wreath product $\wr$ is a standard group theoretic construction, and $|C_{i} \wr S_{n_{i}}|= i^{n_{i}} (n_{i})!.$