Next: Preliminary Observations
Up: Random Permutation Matrices An
Previous: Probability and Cycle Structure
Permutation Matrices and X_{n,a}
For each
,
let
be the
matrix constructed by the following
rule:

(8) 
That is, the i^{th} 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 onetoone correspondence between S_{n}and the
permutation matrices. (With
defined in this way, a matrix that is
leftmultiplied by
will have its rows permuted according to ,
and a matrix that
is rightmultiplied by
will have its columns permuted according to the inverse of
.)
Using some elementary facts about S_{n} 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 kcycle in
contributes a factor of
to
.
The zeros of
are just the k^{th} roots of unity,
which are
Next: Preliminary Observations
Up: Random Permutation Matrices An
Previous: Probability and Cycle Structure
20000925