next up previous
Next: Description of Xn,a when Up: Preliminary Observations Previous: Random Independent Points on

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 Ck in the cycle structure. Thus,

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

and the mean of Zn,0 is

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

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

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

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

\begin{displaymath}E\left[Z_{n,\theta}\right] = {1 \over q} \ln n + O(1).
\end{displaymath} (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.


next up previous
Next: Description of Xn,a when Up: Preliminary Observations Previous: Random Independent Points on

2000-09-25