next up previous
Next: Preliminary Observations Up: Random Permutation Matrices An Previous: Probability and Cycle Structure

   
Permutation Matrices and Xn,a

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

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

That is, the ith 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 Snand 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 Sn 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

\begin{displaymath}p(\lambda) = \det(M_\sigma- \lambda I) = (-1)^n\prod_{k=1}^n (\lambda^k -1)^{C_k},
\end{displaymath} (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 kth roots of unity, which are $1,\,e^{2\pi i/k},\,e^{4\pi i/k},\,\ldots,\,e^{2(k-1)\pi i/k}$
next up previous
Next: Preliminary Observations Up: Random Permutation Matrices An Previous: Probability and Cycle Structure

2000-09-25