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:

$$P = \pmatrix{ 0 &0 &1 &0 &0 &0 \cr 0 &0 &0 &0 &0 &1 \cr 0 &0 &0 &1 &0 &0 \cr 1 &0 &0 &0 &0 &0 \cr 0 &0 &0 &0 &1 &0 \cr 0 &1 &0 &0 &0 &0 \cr}$$

Such a matrix is called a permutation matrix because it is obtained by permuting the rows or columns of the identity matrix. (This yields a one-to-one correspondence between the set of $n \times n$ permutation matrices and the set of permutations on $n$ elements. One can verify that multiplying a vector by a permutation matrix permutes the elements of the vector accordingly.) Every permutation matrix is unitary. This implies that the eigenvalues of any permutation matrix all 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 [1] looked at the trace (sum of the eigenvalues), and Wieand [6], [5] 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 length of the interval and to the dimension $n$ of the matrix. In this project, the idea was 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, for fixed positive constants $a$ and $\ell$, we looked at the number of eigenvalues $X_{n,a}$ lying in the half-open interval $I_n = \left(e^{2 \pi i a}, e^{2 \pi i(a +\ell/n)}\right]$ when an $n \times n$ permutation matrix is chosen at random, and we found the limit of the mean of $X_{n,a}$ as $n\rightarrow\infty$ for certain values of $a$ (including all rational points and certain "well-behaved" irrational points).