Eigenvalues vs. Independent Points on the Circle

Plotting the eigenvalues of a random $n \times n$ permutation matrix can be compared with plotting $n$ points chosen independently and uniformly from the set of all points on the unit circle. When points are chosen at random according to the uniform distribution on the circle, the probability of picking any particular point $e^{i\theta}$ is 0. The eigenvalues of permutation matrices, however, occur only at certain values of $\theta$, so the probability of choosing one of these points is positive, while the probability for any other point is 0.

In particular, if $e^{i\theta}$ is an eigenvalue of an $n \times n$ permutation matrix, then $\theta$ must be a rational number with denominator no greater than $n$. It is known (see, for example, Goncharov [2], or Shepp and Lloyd [4]) that the average number of eigenvalues at a point $e^{2\pi i p/q}$ on the unit circle (where $p$ and $q$ are relatively prime integers) grows as ${1\over q}\ln n + O(1)$. (It will be useful to keep these facts in mind for some of the discussions in the following sections.) This behavior is quite different from the uniform case, which must be interpreted in terms of some interval on the circle rather than at individual points.

When $n$ points are chosen independently and uniformly, the fraction of points landing in a given interval will, on average, equal the ratio of the length of the interval to the circumference of the circle. By defining $I_n$ (as in the introduction) to have a length of $2\pi \ell/n$, the average number of points landing in the interval $I_n$, if picked independently, would have the constant value $\ell$, regardless of the value of $n$. In fact, the number of points landing in the interval has a binomial distribution with parameters $(n,\ell/n)$, and the distribution converges to Poisson with parameter $\ell$ as $n\rightarrow\infty$. One goal of this project was to investigate how the distribution of eigenvalues landing in $I_n$ might compare with the distribution of points in this simpler situation.