\documentstyle[11pt,fleqn,nato]{article}

\begin{document}
\vspace*{3cm}

\noindent
{\bf EIGENVALUE ROULETTE AND RANDOM TEST MATRICES}
\bigskip

\begin{quote}
 A. EDELMAN\\
 {\it Department of Mathematics \\ University of California
     \\  Berkeley, CA 94720 \\  edelman@math.berkeley.edu}
\end{quote}
\bigskip

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

\section{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
{\it 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{2 n/\pi}$ 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 \cite{edelman-t} 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  
\cite{edelman-p,EKS}. 
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
%%%\linebreak \newpage \noindent \parbox{3.0in}{
\linebreak \newpage \noindent \parbox{2.8in}{
eigenvalues 
$\lambda/\sqrt{n}$ 
in the complex plane yields a curious picture.
To the right are
2500 dots representing
$\lambda/\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
\cite{girko}, the normalized complex eigenvalues
fall uniformly in the complex unit disk (in the limit
as $n\rightarrow \infty$).

We concentrated our studies on\\
\hspace*{.2in}
$\bullet$ $p_{n,k}$, the probability that an $n$ by $n$
matrix has exactly $k$ real eigenvalues, \\
\hspace*{.2in}
$\bullet$ $E_n=\sum_k kp_{n,k}$, the expected number of real eigenvalues and,\\
\hspace*{.2in}
$\bullet$  the distribution of the real eigenvalues.\\
}


 \input{psfig}
 \vspace{-.2in}
 \begin{center}~
 \hspace*{-1in}
 \psfig{figure=edelman_fig1.ps,height=3.5in}
 \end{center}
 \vspace{-3.7in}

\smallskip

The tables below 
contain a wealth of information
regarding the expected number of real eigenvalues
of a matrix (from \cite{EKS}).  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.
\bigskip

\begin{center}
{\bf Expected number of real eigenvalues}
\end{center}

\hspace*{-.2in}
\parbox{2in}{
\begin{center}
\begin{tabular}{|r|c|r|} \hline
$n$ & $E_n$ & \\ \hline
\rule[-2mm]{0cm}{6mm}
1&$1$ & 1.00000\\ \hline
\rule[-2mm]{0cm}{6mm}
2&$ \sqrt{2}$ & 1.41421\\ \hline
\rule[-2mm]{0cm}{6mm}
3&$1+{1\over 2} \sqrt{2}$ & 1.70711\\ \hline
\rule[-2mm]{0cm}{6mm}
4&${{11}\over 8} \sqrt{2}$ & 1.94454\\ \hline
\rule[-2mm]{0cm}{6mm}
5&$1+{{13}\over {16}} \sqrt{2}$ & 2.14905\\ \hline
\rule[-2mm]{0cm}{6mm}
6&${{211}\over {128}} \sqrt{2}$ & 2.33124\\ \hline
\rule[-2mm]{0cm}{6mm}
7&$1+{{271}\over {256}} \sqrt{2}$ & 2.49708\\ \hline
\rule[-2mm]{0cm}{6mm}
8&${{1919}\over {1024}} \sqrt{2}$ & 2.65027\\ \hline
\rule[-2mm]{0cm}{6mm}
9&$1+{{2597}\over {2048}} \sqrt{2}$ & 2.79332\\ \hline
\rule[-2mm]{0cm}{6mm}
10&${{67843}\over {32768}} \sqrt{2}$ &2.92799\\ \hline
\end{tabular}
\end{center}
}
\parbox{4in}{
\begin{center}
CM-5 Experiments using
LAPACK on 64 processors \\*[2mm]
\begin{tabular}{|c|c|r|r|r|} \hline
$n$ & trials & {\small experimental $E_n$} & {\small theoretical $E_n$}
 & {\small minutes} \\
\hline 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 \\ \hline
\end{tabular}
\vspace{0.1in}

Exact Formulas:\\*[2mm]
\vspace{0.04in}
\begin{tabular}{|c|c|} \hline
${\displaystyle  E_n= \sqrt{2} \sum_{k=0}^{n/2-1} \frac{(4k-1)!!}{(4k)!!}}$
& $n$ even  \rule[-.2cm]{0cm}{1cm} \\ \hline
${\displaystyle  E_n= 1+\sqrt{2} \sum_{k=1}^{(n-1)/2} \frac{(4k-3)!!}{(4k-2)!!}}$ &
$n$ odd  \rule[-.2cm]{0cm}{1cm}\\ \hline
\end{tabular}
\end{center}}

\bigskip

In \cite{edelman-p}, 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 \cite{EKS}
to be asymptotically $\sqrt{2n/\pi}$.  
Finally, we show that the real eigenvalues
normalized by dividing by $\sqrt{n}$ are  asymptotically uniformly
distributed on $[-1,1]$.

\section{Eigenvalue Roulette}

\parbox{4.37in}{
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,\ldots$ 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 
\linebreak
}


\smallskip

\vspace{-0.1in}
\parbox{5.0in}{
\noindent
\verb+>> rand('normal');a=rand(8);sum(abs(imag(eig(a)))<.0001)+
}


 \vspace{-2.5in}
 \input{psfig}
 \begin{center}~
 \hspace*{-0.5in}
 \psfig{figure=edelman_fig2.ps,height=2.5in}
 \end{center}
 \vspace{-0.1in}

\bigskip

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 \cite{edelman-p}:
\begin{center}
Probabilities for Eigenvalue Roulette\\
\begin{tabular}{|c|c|l|}\hline
$k$ &$ p_{n,k}$ &\\ \hline
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\\ \hline
\end{tabular}
\end{center}

\bigskip

A game of a  similar flavor was proposed for roots of random polynomials
in 1938 by Littlewood and Offord \cite{LO}. They write
\vspace{-.1in}
\begin{quote}
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. $\ldots$ What smallest possible
value of $r$ will make A safe [from being ruined]?
\end{quote}
\vspace{-.1in}
What makes their game so
remarkable is that they did not have the technology to play it!

%%%\vspace{-0.19in}


\begin{thebibliography}{9}

\bibitem{edelman-t}
A. Edelman.
{\it Eigenvalues and Condition Numbers of Random Matrices},
PhD thesis, Department of Mathematics, MIT, 1989.

\bibitem{edelman-p}
A. Edelman.
The probability that an $n$ by $n$ matrix has $k$ real eigenvalues.
In preparation.

\bibitem{EKS} A. Edelman, E. Kostlan, M. Shub. How many eigenvalues
of a random matrix are real?  Submitted to {\it J. Amer. Math. Soc.}

\bibitem{girko}
V.L.~Girko,
Circular law,
{\sl Theory Prob. Appl.}, {\bf 29}, pp 694--706, 1984.

\bibitem{LO}
J.E. Littlewood, A.C. Offord. On the number of real roots of
a random algebraic equation,
{\sl J. London Math. Soc.}, {\bf 13}, pp 288--295, 1938.

\end{thebibliography}

\end{document}
 

================== RFC 822 Headers ==================
Message-Id: <9211160900.AA03048@sartre.esat.kuleuven.ac.be>
Received: by sartre.esat.kuleuven.ac.be Mon, 16 Nov 92 10:00:52 +0100
Date: Mon, 16 Nov 92 10:00:49 +0100
X-Mts: smtp
