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..)
 A: 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$).
A: 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})!.$ 
