EIGENVALUE ROULETTE AND RANDOM TEST MATRICES

A. EDELMAN

Department of Mathematics University of California Berkeley, CA 94720 edelman@math.berkeley.edu

KEYWORDS. CM5, Eigenvalues, Numerical Linear Algebra, Random Matrix, Roulette, Test Matrix.

1. Random Matrices in Numerical Linear Algebra

Random matrices may not be mentioned in research abstracts, but second only to Matlab, the most widely used tool of numerical linear algebraists is the “random test matrix.” Algorithmic developers in need of guinea pigs nearly always take random matrices with standard normal entries or perhaps close cousins, such as the uniform distribution on [−1, 1]. The choice is highly reasonable: these matrices are generated effortlessly and might very well catch programming errors. What is a mistake is to psychologically link a random matrix with the intuitive notion of a “typical” matrix or the vague concept of “any old matrix.”

In contrast, we argue that “random matrices” are very special matrices. The larger the size of the matrix the more predictable they are because of the central limit theorem. This is the beauty of a random matrix; it has more structure than a fixed matrix. For example, an n by n matrix with normally distributed entries has 2-norm very nearly 2\sqrt{n}, spectral radius \sqrt{n}, and \sqrt{2n/π} real eigenvalues. If you sort and plot the singular values, you will get nearly the same picture each time. These statements are either crude versions of rigorous theorems or empirical evidence (see Edelman [1] for one survey); however, if you perform the experiments on matrices of size n > 50, you will see for yourself that a random matrix has structure. Experiments with the uniform distribution or even the discrete distribution {−1, 1} will yield essentially the same results scaled by the variance.

Recently, we took a closer look at the real eigenvalues of a matrix of standard normals [2, 3]. Since such is matrix is unlikely to be symmetric, one might expect that it would generally have some real and some complex eigenvalues. Plotting normalized eigenvalues λ/\sqrt{n} in the complex plane yields a curious picture. To the right are 2500 dots representing λ/\sqrt{n} for fifty random matrices of size n = 50. What may appear to be a horizontal line segment is in fact, many closely huddled eigenvalues on the real axis. Furthermore, according to Girko’s circular law [4], the normalized complex eigenvalues fall uniformly in the complex unit disk (in the limit as n → ∞). We concentrated our studies on

• p_{n,k}, the probability that an n by n matrix has exactly k real eigenvalues,

• E_{n} = ∑_{k} kp_{n,k}, the expected number of real eigenvalues and,

• the distribution of the real eigenvalues.

The tables below contain a wealth of information regarding the expected number of real eigenvalues of a matrix (from [3]). The reader will notice that if n is even, the expected number is a rational multiple of \sqrt{2}, while if n is odd, it is one more than such a multiple. We consider the CM-5 experiments a simultaneous validation of our theory, the CM-5, and LAPACK. The exact formulas contain the familiar double factorial notation which is the product of odd or even numbers, depending on the argument.

Expected number of real eigenvalues

\begin{matrix}n & E_{n} \\ 1 & 1 & 1.00000 \\ 2 & \sqrt{2} & 1.41421 \\ 3 & 1 + \frac{1}{2} \sqrt{2} & 1.70711 \\ 4 & \sqrt[\frac{11}{8}]{2} & 1.94454 \\ 5 & 1 + \frac{13}{16} \sqrt{2} & 2.14905 \\ 6 & \sqrt[\frac{211}{128}]{2} & 2.33124 \\ 7 & 1 + \frac{271}{256} \sqrt{2} & 2.49708 \\ 8 & \sqrt[\frac{1919}{1024}]{2} & 2.65027 \\ 9 & 1 + \frac{2597}{2048} \sqrt{2} & 2.79332 \\ 10 & \sqrt[\frac{67843}{32768}]{2} & 2.92799 \end{matrix} CM-5 Experiments using LAPACK on 64 processors

n trials experimental E_{n} theoretical E_{n} minutes
80 640  7.6  7.603  1
160 640  10.7  10.569  7
320 640  14.9  14.756  51
640 128  20.8  20.673  82
900 64  24.5  24.427  107

Exact Formulas:

\begin{matrix}E_{n} = \sqrt{2} ∑_{k=0}^{n/2−1} \frac{(4k − 1)!!}{(4k)!!} & n even \\ E_{n} = 1 + \sqrt{2} ∑_{k=1}^{(n−1)/2} \frac{(4k − 3)!!}{(4k − 2)!!} & n odd \end{matrix}

In [2], we prove that a not too small random normally distributed matrix virtually never has all real eigenvalues, despite doctored examples found in elementary linear algebra textbooks. The probability that all the eigenvalues are real is p_{n,n} = 2^{−n(n−1)/4}. We further show that p_{n,k} always has the form r + s\sqrt{2} where r and s are rational numbers with denominators that are powers of 2 and therefore E_{n} has this form also. The expected number of real eigenvalues E_{n}, is shown in [3] to be asymptotically \sqrt{2n/π}. Finally, we show that the real eigenvalues normalized by dividing by \sqrt{n} are asymptotically uniformly distributed on [−1, 1].

2. Eigenvalue Roulette

We conclude with a game for the amusement and edification of our readers. Let A be a random n by n matrix whose elements are independent standard normals. Our proposed game of eigenvalue roulette spins a wheel with the numbers n, n−2, n−4, … down to 0 or 1 with the possible number of real eigenvalues that A might have. As an example the figure to the right is our “wheel” for n = 8. The wheel may be spun (with a tolerance) in Matlab Version 3 by typing

  >> rand('normal');a=rand(8);sum(abs(imag(eig(a)))<.0001)

Payoffs for the game may be made at the reader’s discretion; fair odds, however, for each value on the wheel when n = 8 are as follows [2]:

Probabilities for Eigenvalue Roulette

k  p_{n,k}
8  1/16384  0.00
6  −1/4096 + 3851/262144 \sqrt{2}  0.02
4 53519/131072−11553/262144 \sqrt{2} 0.35
2 −53487/65536+257185/262144 \sqrt{2} 0.57
0 184551/131072−249483/262144 \sqrt{2} 0.06

A game of a similar flavor was proposed for roots of random polynomials in 1938 by Littlewood and Offord [5]. They write

Let the reader place himself at the point of view of A in the following situation. An equation of degree 30 with real coefficients being selected by a referee, A lays B even odds that the equation has not more than r real roots. … What smallest possible value of r will make A safe [from being ruined]?

What makes their game so remarkable is that they did not have the technology to play it!

References

[1] A. Edelman. Eigenvalues and Condition Numbers of Random Matrices, PhD thesis, Department of Mathematics, MIT, 1989.

[2] A. Edelman. The probability that an n by n matrix has k real eigenvalues. In preparation.

[3] A. Edelman, E. Kostlan, M. Shub. How many eigenvalues of a random matrix are real? Submitted to J. Amer. Math. Soc.

[4] V.L. Girko, Circular law, Theory Prob. Appl., 29, pp 694–706, 1984.

[5] J.E. Littlewood, A.C. Offord. On the number of real roots of a random algebraic equation, J. London Math. Soc., 13, pp 288–295, 1938.