The highest point on the sphere is an eigenvalue

Discs drawn from the rows fence every eigenvalue of a square matrix, cheaply and coarsely. For one class of matrices there is a description that is neither cheap nor coarse, because it is exact. When the matrix is symmetric, its eigenvalues are not only the roots of a polynomial. They are the heights of the peaks, pits and passes of a function on the unit sphere.

The function is the quadratic form, $x^{\mathsf T}Ax$, evaluated at unit arrows $x$. Its highest value is the largest eigenvalue, its lowest value is the smallest, and each eigenvalue in between is reached at a saddle point: it is the lowest of a family of highest values. Lord Rayleigh used the first half of this in 1877 to estimate the pitch of vibrating strings and plates; Ernst Fischer in 1905 and Richard Courant in 1920 stated the whole of it.

The payoff is not only a new description of old numbers. A description of eigenvalues as extremes turns questions about them into questions about maximising over smaller or larger sets, and those have answers by inspection. The main one is Cauchy’s interlacing theorem: take a symmetric matrix, delete one row and the matching column, and each eigenvalue of the smaller matrix lies between two neighbouring eigenvalues of the original. No formula for the roots of a polynomial could ever deliver that.

Round the circle once #

Take the symmetric matrix that forced its eigenvectors to be perpendicular,

$$A = \begin{pmatrix} 2 & 0.8 \\ 0.8 & 1.4 \end{pmatrix},$$

and send a unit arrow $x = (\cos\theta, \sin\theta)$ once round the circle, recording $x^{\mathsf T}Ax$ at every angle.

The curve rises to $2.554$ at $34.7°$ and falls to $0.846$ at $124.7°$. Those two numbers are the eigenvalues, and those two angles are the eigenvectors. The peak and the pit are a right angle apart, which is the spectral theorem turning up as a fact about where a smooth curve has its extremes.

The reason is one line once the arrow is written in the eigenvectors’ own coordinates. If $x = c_1v_1 + c_2v_2$ with $v_1, v_2$ perpendicular unit eigenvectors, then $c_1^2 + c_2^2 = 1$ and

$$x^{\mathsf T}Ax = \lambda_1 c_1^2 + \lambda_2 c_2^2.$$

That is a weighted average of the two eigenvalues, with weights $c_1^2$ and $c_2^2$ that are never negative and add up to one. A weighted average can never exceed the largest thing being averaged, and it equals it only when all the weight is on that thing. So the form is at most $\lambda_1$, reaches it exactly when $x = \pm v_1$, and by the same argument is at least $\lambda_2$ and reaches that at $\pm v_2$. The same sentence works in any dimension: in $n$ dimensions the form is a weighted average of $n$ eigenvalues, and its range over the unit sphere is exactly the interval from the smallest to the largest.

The quantity $x^{\mathsf T}Ax / x^{\mathsf T}x$, which is the form at the unit arrow pointing along $x$, is called the Rayleigh quotient. It is a height function on the sphere, and the claim of this essay is that everything about a symmetric matrix’s eigenvalues can be read from its landscape.

Flat at the top, which is why guesses work #

The curve in the figure is flat at its peak, as every smooth curve is at a maximum. That innocent observation has a consequence which made Rayleigh’s name in acoustics.

Suppose the arrow is not exactly the eigenvector but misses it by a small angle $\varepsilon$. Then $c_2 = \sin\varepsilon$ and the form is $\lambda_1 - (\lambda_1 - \lambda_2)\sin^2\varepsilon$. The error in the eigenvalue is proportional to $\varepsilon^2$, not to $\varepsilon$. An arrow that is wrong by a tenth gives an eigenvalue wrong by a hundredth. At a peak, a small sideways step barely changes the height.

Rayleigh exploited this for problems where the matrix is infinite: a vibrating string, a drumhead, a beam. The lowest natural frequency squared is the minimum of a quotient of energies, kinetic against potential, over all shapes the object could take. Guess the shape crudely and put it into the quotient. For a string pinned at both ends the true shape of the fundamental is half a sine wave; guess a parabola, $x(1-x)$, instead. The quotient gives $\int_0^1 (1-2x)^2\,dx \big/ \int_0^1 x^2(1-x)^2\,dx = \tfrac13 \big/ \tfrac1{30} = 10$, against the true value $\pi^2 = 9.87$. A shape visibly different from the right one produces a frequency correct to two-thirds of one per cent, and — because the true value is a minimum — the estimate is always too high, never too low. Engineers still size bridges and aircraft wings this way, because a guess of the shape is easy and the error it leaves is squared.

The flatness is also the reason the peak is hard to locate from the curve while its height is easy to read. The same second-order behaviour that forgives a bad arrow when estimating the eigenvalue makes the eigenvector expensive to pin down — the height tells almost nothing about which of many nearby arrows produced it. A method that wants eigenvectors has to work harder than one that only wants eigenvalues.

A circle that cannot see half the matrix #

The weighted-average argument used symmetry at one point: it needed perpendicular eigenvectors to write $x$ in. Remove the symmetry and something odder happens, because the form cannot tell a matrix from its own symmetric part.

Any matrix splits as $A = S + K$, with $S = (A + A^{\mathsf T})/2$ symmetric and $K = (A - A^{\mathsf T})/2$ antisymmetric. For any arrow, $x^{\mathsf T}Kx = 0$ — an antisymmetric matrix turns every arrow to a perpendicular direction, so the shadow of the result on the arrow itself is nothing. So $x^{\mathsf T}Ax = x^{\mathsf T}Sx$ for every $x$, and the circle sees $S$ and only $S$.

The matrix in the figure has complex eigenvalues $1.25 \pm 0.968i$: it turns as well as stretches. The curve knows nothing of that. It peaks at $2.041$ and bottoms at $0.459$, which are the eigenvalues of the symmetric half, and it would draw the identical curve for every matrix with that symmetric half — including symmetric matrices, rotations plus a stretch, anything. The rotational part of a map is invisible to a quantity that measures how much each arrow is pushed along itself.

So the variational description is a genuinely symmetric phenomenon, not a property of eigenvalues in general. What survives for an arbitrary matrix is weaker: the values the form takes, allowing complex arrows, fill a convex region of the plane containing every eigenvalue, and that region is often much larger than the eigenvalues need. It is a different fence from Gershgorin’s discs, and it is exact only in the symmetric case.

The middle eigenvalue is a saddle #

The largest eigenvalue is a maximum and the smallest a minimum. In three dimensions there is a third, and it is neither: it is the height of a mountain pass. Two ways of describing a pass give the same number, and each is worth having.

The first: the middle eigenvalue $\lambda_2$ is the largest value of the form on the plane perpendicular to the top eigenvector. Removing the top direction leaves a smaller sphere, and on it the highest point is the next eigenvalue down. That is true but circular as a way of finding $\lambda_2$, since it needs $v_1$ first.

The second is the one Courant and Fischer made into a principle, and it needs no eigenvector at all. Pick any direction $u$ and look at the plane perpendicular to it. That plane’s great circle has a highest point. Call its height $f(u)$. Now let $u$ range over every direction and take the smallest $f(u)$ can be. That minimum of maxima is exactly $\lambda_2$.

The map shows why. Wherever $u$ points, its perpendicular plane meets the plane spanned by $v_1$ and $v_2$ in at least a line, and on that line the form is a weighted average of $\lambda_1$ and $\lambda_2$, hence at least $\lambda_2$ — so $f(u) \ge \lambda_2$ everywhere. At $u = v_1$ the plane perpendicular to $u$ is spanned by $v_2$ and $v_3$, where the form never exceeds $\lambda_2$, so the bound is attained. The figure measures this rather than trusting it: the lowest value found on a 4,050-cell grid, refined off the grid, agrees with $1.829$ to a millionth.

The other extreme of the map is a surprise the formula makes obvious once seen. Every plane that contains $v_1$ reaches $\lambda_1$ on it, so $f$ equals the top eigenvalue on the whole great circle of directions perpendicular to $v_1$ — not at a point but along a curve. The landscape of $f$ is two pits joined by a ridge that runs all the way round.

In $n$ dimensions the statement generalises by counting constraints. The $k$-th largest eigenvalue is the minimum, over all choices of $k-1$ directions to be perpendicular to, of the maximum of the form on what is left. No eigenvector appears in the statement. That is its power: it describes each eigenvalue by an optimisation over subspaces, and optimisations over subspaces can be compared with one another by asking which is over a bigger set.

Delete a row and a column #

The comparison that matters most is the simplest one. Let $B$ be the matrix obtained from a symmetric $A$ by deleting its last row and last column. The form of $B$ is the form of $A$ restricted to arrows whose last coordinate is zero — a sphere one dimension smaller, sitting inside the original sphere as a slice.

The largest value on a slice cannot exceed the largest value on the whole, so $\lambda_1(B) \le \lambda_1(A)$. That half is easy. The other half uses the min–max principle: the slice is itself “perpendicular to one direction”, namely the last coordinate axis, so its maximum is one of the $f(u)$ values whose minimum is $\lambda_2(A)$, and therefore $\lambda_1(B) \ge \lambda_2(A)$. The same argument, one count further along, gives the whole theorem:

$$\lambda_1(A) \ge \lambda_1(B) \ge \lambda_2(A) \ge \lambda_2(B) \ge \cdots \ge \lambda_{n-1}(B) \ge \lambda_n(A).$$

The eigenvalues of the smaller matrix sit in the gaps between the larger one’s, one to each gap. Augustin-Louis Cauchy proved it in 1829, long before anyone called these things eigenvalues, and it is still the first tool anyone reaches for when a symmetric matrix is compared with a piece of itself.

Stacking the deletions gives a triangle, and each row nests into the gaps of the row above. The corner entry $2$ must lie between the two eigenvalues of the top-left $2\times2$ block, which must straddle the three of the $3\times3$ block, and so on up to the whole. It is a fence of a much finer kind than Gershgorin’s: not a region round each eigenvalue but a chain of inequalities tying every eigenvalue of every block to its neighbours.

The pattern turned out to be the key step in a problem that had resisted nearly thirty years of attack. Hao Huang’s 2019 proof of the sensitivity conjecture needed a set of more than half the corners of a cube to contain a corner with many neighbours in the set, and the whole argument is interlacing applied to a cleverly signed adjacency matrix: the matrix has half its eigenvalues equal to $\sqrt n$, and a large enough block of it cannot escape one of them. The theorem that essay used and did not draw is the one in the figure.

A chain that loses a mass #

Interlacing has a physical reading that makes it feel inevitable. Six equal masses in a line, joined by equal springs, with the two ends fixed to walls, vibrate in six patterns, and the squares of their frequencies are the eigenvalues of the matrix with $2$ down the diagonal and $-1$ on either side. That matrix is also the second difference, the discrete form of the operator whose eigenfunctions are the sine waves of a Fourier series.

Deleting the last row and column is clamping the last mass to the wall, which shortens the chain by one. Every frequency of the shorter chain lies between two neighbouring frequencies of the longer one. Here the numbers have a closed form — the $n$-mass chain’s squared frequencies are $2 - 2\cos\big(k\pi/(n+1)\big)$ — and the interlacing is visible in it: the angles $k\pi/7$ and $k\pi/6$ alternate round the half-circle. But the theorem does not need the closed form, and it holds equally for a chain with unequal masses and springs, where no formula exists.

The same nesting is what makes the remainders that count the roots work for tridiagonal matrices. The characteristic polynomials of the leading blocks of a chain matrix satisfy a three-term recurrence, their roots interlace from one to the next, and so their signs at any number $x$ form a Sturm sequence: the number of sign changes counts the eigenvalues below $x$. That count, run by bisection, is how eigenvalues of large tridiagonal matrices are still located in practice — one sign pattern at a time, with no polynomial ever written down.

Adding a piece of rank one #

Deleting a row is one way of changing a matrix by a small amount. Adding a rank-one piece $t\,vv^{\mathsf T}$, with $t \ge 0$, is another, and it too has an interlacing theorem. The form changes by $t(v\cdot x)^2$, which is never negative, so every value of the form goes up or stays put, and so does every min–max, and so every eigenvalue: nothing goes down. But the addition is zero on the whole plane perpendicular to $v$, and a min–max that is allowed to avoid one direction can avoid it. So each eigenvalue rises by at most the gap to the one above it.

The picture shows both halves: the curves climb, the lower three flatten out under the dashed lines of their neighbours’ starting values, and only the top one is free to climb for ever — which it does at a rate approaching $|v|^2$, since for large $t$ the added piece dominates and its one non-zero eigenvalue is $t|v|^2$. The total rise is fixed by the trace, and the figure checks that it comes out at exactly $t|v|^2$ at every sample.

The scatter matrix of a data set — the sum, over the observations, of each centred observation’s outer product with itself — grows by exactly such a piece whenever an observation is added. So one new observation, however extreme, raises the spread along every direction, and raises each of the ordered spreads by no more than the gap to the next: an outlier can drag the leading direction a long way and cannot reorder the rest. That is why a single wild measurement shows up in the first principal component and hardly anywhere else.

What the landscape cannot show #

Every picture here lives in two or three dimensions, and the theorems that matter live in many.

The min–max over subspaces cannot be drawn above three dimensions. The map of $f(u)$ needs a sphere of directions, which is a surface in three dimensions and a three-dimensional manifold in four. The statement for the $k$-th eigenvalue minimises over sets of $k - 1$ directions, which form a space nobody can picture. The figures show the case $k = 2$, $n = 3$, and trust the algebra for the rest.

The interlacing triangle shows one nesting, and there are many. Deleting the last row is one choice of slice out of infinitely many. The theorem holds for every slice — every restriction to a hyperplane, not just coordinate ones — and a drawing of five nested leading blocks cannot show that it did not depend on the choice.

Nothing here survives the loss of symmetry. The unsymmetric figure shows the circle failing to see a complex pair; it cannot show how badly interlacing fails in general, because there is nothing to interlace. The corner entry of $\begin{pmatrix} 0 & 1 \\ -1 & 0\end{pmatrix}$ is $0$, and the eigenvalues are $\pm i$: there is no gap for the $0$ to sit in, and no sense in which it should.

Further out: sums of symmetric matrices #

Deleting a row and adding a rank-one piece are the two smallest changes, and both give interlacing. The general question — given the eigenvalues of two symmetric matrices, which eigenvalues can their sum have? — was posed by Hermann Weyl in 1912, who gave the first inequalities, and by Alfred Horn in 1962, who conjectured a complete list. The answer is a finite set of linear inequalities defined recursively, and it was proved only in 1999, by Allen Knutson and Terence Tao, using a combinatorial device of hexagonal honeycombs. A question that begins with the weighted average in the first section ends in some of the deepest combinatorics of the century.

Sideways: the singular values of any matrix — the axes of the ellipse a circle is sent to — are the square roots of the eigenvalues of the symmetric matrix $A^{\mathsf T}A$, so everything here applies to them. Deleting a column of a data matrix moves each singular value into the gap below it, which is why a decomposition computed from data that has lost a measurement is still close to the one computed from all of it. And the Laplacian of a graph is symmetric, so the matrix whose minors count spanning trees has its eigenvalues interlace whenever a vertex is removed — the root of a whole subject that reads a graph’s shape off its spectrum.

Eigenvalues as the heights of a landscape #

For a symmetric matrix, the form $x^{\mathsf T}Ax$ on the unit sphere has its highest value at the largest eigenvalue and its lowest at the smallest, and every eigenvalue in between is a minimum of maxima over slices of the sphere. The first fact is a weighted average; the second, the Courant–Fischer principle, describes each eigenvalue without mentioning any eigenvector.

From that description come the facts no formula could supply. An eigenvalue estimated from a guessed shape is accurate to second order in the guess, which is why engineering runs on Rayleigh’s method. Deleting a row and column of a symmetric matrix leaves eigenvalues that interlace the original’s, one to each gap; clamping a mass of a vibrating chain does the same to its frequencies; and adding a rank-one positive piece pushes every eigenvalue up by no more than the gap above it. None of it applies to an unsymmetric matrix, whose circle sees only its symmetric half.

When a quantity can be written as the best value of something, every comparison between such quantities becomes a comparison between the sets being searched — and the smaller set can never do better.