The Number of Eigenvalues at $e^{i\theta }$

When random points are chosen uniformly on the unit 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 order to gain some insight into this problem, define a random variable $Z_{n,\theta}$ to be the number of eigenvalues of $\sigma \in S_n$ equal to $e^{i\theta }$. The variable $Z_{n,\theta}$ is already well understood; see, for example, [1], [2]. Presented here is a brief explanation of what happens to the mean of $Z_{n,\theta}$ as $n\rightarrow\infty$.

First consider the case when $\theta=0$. Every cycle in a permutation $\sigma$ produces the eigenvalue 1, so the number of eigenvalues at $\theta=0$ will equal the total number of cycles in $\sigma$. Recall that the number of cycles in $\sigma$ is the sum of all the values of C_k in the cycle structure. Thus,

$$Z_{n,0} = \sum_{k=1}^n C_k,$$ (14)

and the mean of Z_n,0 is

$$E\left[Z_{n,0}\right] = \sum_{k=1}^n E[C_k] = \sum_{k=1}^n {1 \over k}.$$ (15)

For large n, this sum can be approximated by $\ln n$, resulting in

$$E\left[Z_{n,0}\right] = \ln n + O(1).$$ (16)

Similar reasoning can be used to see that in general, if $\theta=2\pi p/q$ with p and qrelatively prime, then

$$E\left[Z_{n,\theta}\right] = {1 \over q} \ln n + O(1).$$ (17)

If $\theta$ is an irrational multiple of $2\pi$, then no eigenvalues can occur there, so $Z_{n,\theta}=0$ for all n in this case. This behavior is quite different from the uniform case.