Eigenvalues that keep their distance

A symmetric matrix always has real eigenvalues and perpendicular directions to stretch along. Nothing in that theorem says where the eigenvalues go, and for a particular matrix they go wherever its entries put them. Fill the matrix with random numbers instead, independently and with no structure at all, and ask the same question of the result. The answer is not “anywhere”. The eigenvalues of a large random symmetric matrix keep their distance from one another, far more evenly than any set of independent points could, and the evenness is a theorem rather than an accident.

The figure below sets sixty-one consecutive eigenvalues from the middle of one random 400 × 400 matrix beside sixty-one points dropped independently on a line of the same length. Every entry of the matrix was an independent Gaussian number. Nothing was arranged.

Independent points clump. That is not a defect of the sample; it is what independence means, since the position of one point says nothing about where the next will land, and a gap of any small size is as likely as the arithmetic of a uniform draw allows. The eigenvalues are spread more like the teeth of a comb. Their gaps vary about half as much as the independent points’ do, and near-collisions are rare. Something in passing from entries to eigenvalues has made the levels avoid one another, and the rest of this essay is what that something is and what it does at every scale of the spectrum.

A semicircle out of nothing but independence #

The first question is the coarse one: over the whole spectrum, how are the eigenvalues spread? The matrices here have Gaussian entries, with variance one off the diagonal and two on it — the Gaussian orthogonal ensemble, named for the fact that its distribution is unchanged by any rotation of the coordinates. An $n \times n$ matrix of this kind has eigenvalues of size about $\sqrt n$, and dividing by $\sqrt n$ puts every size on one scale.

The result is Eugene Wigner’s semicircle, $\sqrt{4 - x^2}/2\pi$ on the interval from −2 to 2. Wigner found it in 1955 while looking for a model of the energy levels of heavy atomic nuclei, whose Hamiltonians were far too complicated to write down; his bet was that a matrix with random entries, respecting only the symmetry the physics demands, would reproduce the statistics of the levels if not the levels themselves. The bet paid off, and the semicircle was the first of its returns.

The proof runs through moments, and it is a counting argument. The average of $x^{2k}$ over the eigenvalues is $\operatorname{tr}(A^{2k})/n$ divided by the right power of $n$, and the trace of a power is a sum over closed walks of length $2k$ through the indices of the matrix. Because the entries are independent with mean nought, only walks that use every step at least twice survive the average, and among those, the ones that dominate as $n$ grows trace out a tree and come back. Trees of that kind are counted by the Catalan numbers, and the Catalan numbers are exactly the even moments of the semicircle. Nothing in the argument used the Gaussian shape of the entries — only their independence, mean and variance — so any such matrix gives the same semicircle. That insensitivity has a name, universality, and it is the reason random matrices are useful at all. It is the matrix version of what the bell curve does for sums of coin flips: the details of each ingredient are washed out, and only their mean and spread survive into the answer.

The same counting, applied to a rectangular matrix of random numbers, gives the spread of its singular values — the axes of the ellipse it makes of a circle — and the answer, found by Vladimir Marchenko and Leonid Pastur in 1967, is a different curve with the same origin. It is the reason a covariance matrix estimated from fewer samples than variables has eigenvalues spread far wider than the true ones, even when every true variance is one.

The same curve has turned up elsewhere for different reasons. The first coordinate of a random rotation’s quaternion is spread by exactly this semicircle, because a slice of the three-sphere grows like a square root. Here there is no sphere; the curve comes from trees.

Discs drawn too large by the square root of the size #

There is an older way to say where eigenvalues lie, and the random matrices show exactly how blunt it is. Gershgorin’s discs put every eigenvalue within a disc around a diagonal entry, with radius the sum of the sizes of the other entries in its row. For a random $n \times n$ matrix of this kind, each row’s off-diagonal entries have average size $\sqrt{2/\pi}$, so every disc has radius about $0.8\,n$. The eigenvalues actually lie within $2\sqrt n$. For a thousand-square matrix the discs allow eigenvalues as large as eight hundred, and the largest is about sixty-three.

The discs are not wrong, only pessimistic, and the reason is signs. Gershgorin’s bound adds the sizes of the entries, as though every one of them pushed the same way; the eigenvalue sees the entries with their signs, and a thousand random signs mostly cancel, leaving a sum of order $\sqrt n$ rather than $n$. The directions a map leaves alone are made from the entries jointly, and for a random matrix the joint effect is the square-root cancellation of a random walk, not the worst-case sum. The semicircle’s edge at $2\sqrt n$ is that cancellation measured exactly.

Why two eigenvalues avoid each other #

The semicircle says how dense the eigenvalues are and nothing about how they sit next to one another. The repulsion visible in the first figure is a different fact, and it can be seen completely in a two-by-two matrix.

A symmetric matrix $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ has eigenvalues $\tfrac12\left(a + c \pm \sqrt{(a - c)^2 + 4b^2}\right)$, so the gap between them is $\sqrt{(a - c)^2 + 4b^2}$. That is a distance in a plane, the plane with coordinates $a - c$ and $2b$, and the two eigenvalues coincide only at a single point of that plane — where $a = c$ and $b = 0$. One coincidence is not enough. Two independent numbers have to vanish together.

With Gaussian entries the point $(a - c, 2b)$ is a symmetric Gaussian cloud in the plane, and the chance that it lands within $s$ of the centre is proportional to the area of a disc of radius $s$ — proportional to $s^2$ for small $s$. The gap’s density is therefore a Rayleigh law, $(s/4)e^{-s^2/8}$ for these variances, which is nought at a gap of nought and rises linearly from there. Its mean is $2\sqrt{\pi/2} \approx 2.507$; the forty thousand matrices in the figure give 2.511.

A diagonal matrix has no $b$, and then the gap is $|a - c|$, the distance from the centre along a line. A line has no area to speak of, the chance of a gap under $s$ is proportional to $s$ itself, and the density is largest at nought. The whole difference between the two curves in the figure, the one vanishing at nought and the other peaking there, is the difference between one condition and two.

For larger symmetric matrices the count grows. A repeated eigenvalue of a real symmetric matrix costs two conditions; of a complex Hermitian matrix, three, because the off-diagonal entry has two real parts; of a quaternion matrix, five. Freeman Dyson’s threefold way of 1962 sorted random matrices by exactly this count, and it reappears as the exponent of the repulsion: the gap density near nought grows like $s$, $s^2$ or $s^4$.

Curves that veer instead of crossing #

The same count says something about matrices that change smoothly rather than randomly. Let a symmetric matrix depend on one parameter $t$. Its eigenvalues trace curves as $t$ moves, and the question is whether two curves can cross.

For a diagonal matrix the eigenvalues are the diagonal entries, and two straight lines with different slopes cross. Add any small symmetric coupling between the entries and the crossings vanish. Each near miss is a small two-by-two problem embedded in the large one: as the two curves approach, the matrix restricted to their two directions has a gap $\sqrt{(a - c)^2 + 4b^2}$ in which $a - c$ passes through nought as $t$ moves but the coupling $b$ generally does not. One parameter can arrange one coincidence and almost never two.

John von Neumann and Wigner stated this in 1929 as the non-crossing rule for quantum energy levels: as a molecule’s geometry changes along one coordinate, levels of the same symmetry repel and avoid each other, and only levels that a symmetry keeps from interacting — forcing $b = 0$ exactly — may cross. The diagonal family on the left is the case of perfect symmetry, where every coupling is forbidden. The picture also explains the eigenvalue landscapes of the min–max description, in which every eigenvalue is a saddle height: two saddles merging needs two things to happen at once.

A random matrix is, in effect, a matrix that has been pushed around in every direction at once, and its levels have had every opportunity to veer apart. That is the intuition behind the comb in the first figure, and the next figure measures it in a large spectrum.

The gaps in a large spectrum #

To compare gaps in different parts of the semicircle, where the eigenvalues are packed at different densities, each gap is divided by the local average gap, a step called unfolding. After it every part of the spectrum has average spacing one, and the shape of the spacing distribution can be read directly.

Independent points have exponentially distributed gaps, with density $e^{-s}$: largest at nought, so that nearly nine per cent of gaps are under a tenth of the average. The eigenvalues’ gaps rise from nought like a straight line, exactly as the two-by-two matrix said, and fewer than one in a hundred are under a tenth of the average.

In 1956, with no exact theory for large matrices, Wigner guessed that the large-matrix spacing law would look like the two-by-two one rescaled to mean one, $(\pi s/2)e^{-\pi s^2/4}$, and the guess is still called Wigner’s surmise. It is not exactly right. The exact law for large matrices was found by Michel Gaudin and Madan Lal Mehta in the early 1960s as a determinant of an integral operator, and it differs from the surmise by at most a few per cent of its height — small enough that the histogram here cannot tell them apart in shape, though the variance of the gaps, 0.298 against the surmise’s $4/\pi - 1 = 0.273$, shows the difference.

The surmise’s success says that the repulsion is essentially local. Two neighbouring eigenvalues feel each other as though they were alone in a two-by-two matrix, and the remaining hundreds act mainly to set the scale.

Counting eigenvalues in a window #

Local repulsion has a global consequence. If every eigenvalue keeps its neighbours at a distance, the whole sequence cannot bunch or thin out much over long stretches either, and the number of eigenvalues in a long window should hardly vary.

For independent points the count in a window is Poisson, and its variance equals its mean: a window holding thirty-two points on average typically holds between twenty-six and thirty-eight. For the eigenvalues the variance grows only like the logarithm of the window, $(2/\pi^2)\log L$ plus a constant, and a window of thirty-two holds thirty-two give or take one. Dyson and Mehta worked out this number variance in 1963, and the measurements sit on their curve at every window from one gap to thirty-two.

A crystal lattice, with points exactly one unit apart, would have a count that never varies by more than one. The spectrum is nearly that rigid. The physical picture Dyson gave is a gas of charged particles on a line, every pair repelling with an energy equal to minus the logarithm of their distance, all held in by a parabolic wall: the joint density of the eigenvalues of these matrices is exactly the Boltzmann weight of such a gas, $\prod_{i<j}|\lambda_i - \lambda_j|\, e^{-\sum \lambda_i^2/4}$, and the product of distances is the repulsion written as a formula. The factor $|\lambda_i - \lambda_j|$ to the first power is the same one-power that made the two-by-two gap density vanish linearly.

Where the spectrum ends #

The semicircle says the eigenvalues fill $[-2\sqrt n, 2\sqrt n]$, but a finite matrix has a largest eigenvalue that need not sit at the edge exactly. How far it strays, and how quickly it settles, is a question about the extreme rather than the bulk, and it has an answer of its own.

Two numerical facts make the larger sizes possible. Ioana Dumitriu and Alan Edelman showed in 2002 that a symmetric matrix with only three non-zero diagonals — Gaussian numbers down the middle and the square roots of chi-squared variables beside them — has eigenvalues with exactly the same joint law as the full random matrix. And the largest eigenvalue of such a matrix can be found by bisection, counting how many eigenvalues lie below a trial value from a single pass down the diagonal, without computing the others. Together they turn a ten-thousand-square matrix into a calculation of a few milliseconds, and the figure checks the tridiagonal model against a hundred and fifty full matrices before trusting it.

The largest eigenvalue approaches the edge from below and its spread shrinks like $n^{-2/3}$ in these units — a factor of about two for every eightfold increase in size, far faster than the $n^{-1/2}$ an average of independent quantities would give. Craig Tracy and Harold Widom found the limiting shape of the fluctuations in 1994 and 1996, and their law has mean −1.2065 and standard deviation 1.2680 after scaling. At $n = 10{,}000$ that predicts 1.9974 ± 0.0027, and the two hundred matrices give 1.9975 ± 0.0028. The Tracy–Widom law has since turned up far from matrices — in the longest increasing run in a random shuffle, in the height of a growing crystal surface — wherever a maximum is taken over strongly correlated quantities. The same edge governs graphs. For the adjacency matrix of a random graph in which every point has $d$ neighbours, the eigenvalues fill a curve of their own, the Kesten–McKay law, and Joel Friedman proved in 2008 that all but the trivial top eigenvalue lie within a hair of $\pm 2\sqrt{d - 1}$. That gap below the top is what sets how fast a random walk forgets its start, and it is why random regular graphs mix about as fast as any graph of their degree can.

What a sample of matrices cannot settle #

Every number on this page is measured on finitely many finite matrices, and two different kinds of claim sit behind them. The semicircle, the Rayleigh law for two-by-two gaps, the non-crossing rule and the Tracy–Widom limit are theorems; the figures show them emerging and check them, and could not have established them. The agreement of six thousand gaps with the surmise to a few per cent says nothing about whether the surmise is exact — it is not, and the histogram is too coarse to show why.

Universality is the subtler limitation. All the matrices here have Gaussian entries, and the statement that the local statistics are the same for other entries — independent coin flips, say — was conjectured by Wigner, Dyson and Mehta and proved only around 2010, by László Erdős, Benjamin Schlein and Horng-Tzer Yau and independently by Terence Tao and Van Vu. The figures cannot show it, because they never left the Gaussian case.

And the unfolding step that makes gaps comparable used the semicircle as the local density. For a finite matrix that is an approximation, and its error is part of every measured gap; it is why only the middle half of each spectrum is used, where the semicircle is flattest and the approximation best.

Still open: why chaos sounds like a random matrix #

The surprising part of the story is where these statistics turn up. In 1972 Hugh Montgomery, studying the zeros of the Riemann zeta function, found a formula for how pairs of zeros are spaced; over tea at Princeton, Dyson recognised it as the pair correlation of the eigenvalues of random Hermitian matrices. Andrew Odlyzko’s computations of millions of zeros at enormous heights later matched the zeros that count the primes to random-matrix spacing statistics with startling precision. Why the zeros of a function defined by the primes should behave like the eigenvalues of a random matrix is not known; Montgomery’s conjecture itself remains unproved.

The other surprise is in physics. In 1984 Oriol Bohigas, Marie-Joya Giannoni and Charles Schmit conjectured that the energy levels of any quantum system whose classical motion is chaotic — a particle bouncing in a stadium-shaped room, say — follow random-matrix statistics, while systems with orderly classical motion follow independent-point statistics instead. Overwhelming numerical evidence supports it. No proof exists, for any particular chaotic system, that its spacing distribution is the random-matrix one, and the conjecture is one of the central open problems connecting classical chaos to quantum mechanics.

Distance kept by counting conditions #

A tie between two eigenvalues of a symmetric matrix costs two conditions, not one. For a random matrix that makes a small gap rare in proportion to its square; for a matrix moving with one parameter, it turns every crossing into a near miss; for the whole spectrum, it produces the comb, the rigid count and the sharp edge. The semicircle is a separate fact, about trees in a sum over walks, and the two together describe a large random symmetric matrix completely enough that its eigenvalues have become a model for anything whose levels repel — nuclei, chaotic billiards and, for reasons nobody understands, the zeros of the zeta function.