next up previous
Next: Background About Permutations and Up: Random Permutation Matrices An Previous: Random Permutation Matrices An

Introduction

A permutation matrix is any $n \times n$ matrix that has exactly one 1 in each row and column, with all other entries being 0. Here is an example of a $6 \times 6$ permutation matrix:

\begin{displaymath}P = \pmatrix{0 &0 &1 &0 &0 &0 \cr
0 &0 &0 &0 &0 &1 \cr
0 &0...
...&0 &0 &0 &0 &0 \cr
0 &0 &0 &0 &1 &0 \cr
0 &1 &0 &0 &0 &0 \cr}\end{displaymath}

All the eigenvalues of a permutation matrix lie on the (complex) unit circle, and one might wonder how these eigenvalues are distributed when permutation matrices are chosen at random (that is, uniformly from the set of all $n \times n$ permutation matrices). Some work has already been done in studying the eigenvalues of permutation matrices. Diaconis and Shahshahani [3] looked at the trace (sum of the eigenvalues), and Wieand [5],[4] investigated the number of eigenvalues that lie in a fixed arc of the unit circle. In both cases, the asymptotic behavior for large n was determined.

Roughly speaking, the number of eigenvalues that lie in a fixed interval on the unit circle will be proportional to the size of the interval and to the dimension n of the matrix. In this paper, the goal will be to allow n to increase while decreasing the size of the interval, so that the number of eigenvalues lying in it should remain fairly constant on average. In particular, we look at the number of eigenvalues Xn,a lying in the interval $I_n = \left(e^{2 \pi i a},\,e^{2 \pi i(a + l/n)}\right]$


next up previous
Next: Background About Permutations and Up: Random Permutation Matrices An Previous: Random Permutation Matrices An

2000-09-25