Permutation Matrices and X_n,a

For each $\sigma \in S_n$, let $M_\sigma$ be the $n \times n$ matrix constructed by the following rule:

$$(M_\sigma)_{ij} = \cases{1 & if $j=\sigma(i)$\cr 0 & otherwise.\cr}$$ (8)

That is, the i^th row of $M_\sigma$ has a 1 in the column $\sigma(i)$ and 0's in all the others. It is easy to verify that $M_\sigma$ is a permutation matrix (as defined in the introduction), and that this rule in fact defines a one-to-one correspondence between S_nand the $n \times n$ permutation matrices. (With $M_\sigma$ defined in this way, a matrix that is left-multiplied by $M_\sigma$ will have its rows permuted according to $\sigma$, and a matrix that is right-multiplied by $M_\sigma$ will have its columns permuted according to the inverse of $\sigma$.)

Using some elementary facts about S_n and the properties of determinants, it is not difficult to show that, if $\sigma$ has a cycle structure of $(C_1,\,C_2,\,\ldots,\,C_n)$, then the characteristic polynomial of $M_\sigma$ is

$$p(\lambda) = \det(M_\sigma- \lambda I) = (-1)^n\prod_{k=1}^n (\lambda^k -1)^{C_k},$$ (9)

which results because every k-cycle in $\sigma$ contributes a factor of $(-1)^k(\lambda^k -1)$ to $p(\lambda)$. The zeros of $\pm(\lambda^k -1)$ are just the k^th roots of unity, which are $1,\,e^{2\pi i/k},\,e^{4\pi i/k},\,\ldots,\,e^{2(k-1)\pi i/k}$