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

# Permutation Matrices and Xn,a

For each , let be the matrix constructed by the following rule: (8)

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

Using some elementary facts about Sn and the properties of determinants, it is not difficult to show that, if has a cycle structure of , then the characteristic polynomial of is (9)

which results because every k-cycle in contributes a factor of to . The zeros of are just the kth roots of unity, which are    Next: Preliminary Observations Up: Random Permutation Matrices An Previous: Probability and Cycle Structure

2000-09-25