The middle eigenvectors come back exact

Balanced is not symmetric computed the eigenvalues of the Sylvester–Kac matrix, a tridiagonal matrix of small integers whose eigenvalues are the integers from $-(n-1)$ to $n-1$ in steps of two, and measured every digit an eigensolver lost against those integers. The losses followed first-order perturbation theory, the middle of the spectrum lost the most, and at order 112 the solver returned complex eigenvalues for a spectrum of integers. It ended with three questions, and the last was about eigenvectors. They are known exactly too — the matrix’s own three-term recurrence produces them in integers, as Krawtchouk polynomials — and the prediction was that “the eigenvectors of the middle eigenvalues are lost before the eigenvalues are, since an eigenvector’s sensitivity carries the gap to the neighbouring eigenvalue as well as the non-normality, and the gap here is only two.”

The reasoning is the textbook one, and the gap decides the eigenvector measured it on a symmetric matrix: an eigenvector’s perturbation is a sum over the other eigenvalues of terms divided by the distance to each, so a small gap makes a sensitive eigenvector. A non-normal matrix multiplies each term by how far its left and right eigenvectors are from parallel. On the Kac matrix both are bad in the middle of the spectrum.

Measured, it is not the middle that is lost, and the first measurement that seems to say it is was measuring the starting vector.

Exact eigenvectors in integers #

The matrix of order $n$ has zeros on its diagonal, $1, 2, \ldots, n-1$ above it and $n-1, \ldots, 1$ below. For an eigenvalue $\lambda$, row $k$ of $Ax = \lambda x$ reads $(n-k)\,x_{k-1} + (k+1)\,x_{k+1} = \lambda x_k$, so the eigenvector can be written down from $x_0 = 1$ and $x_1 = \lambda$ one entry at a time. In BigInt arithmetic, with the factorials cleared, every entry is an exact rational, and each is rounded to a double once, at the end. That is the reference: for every eigenvalue at every order from 16 to 80, a vector correct to the last bit.

The computed eigenvectors are made the way an eigensolver makes them once it has the eigenvalues: inverse iteration with the shifted matrix $A - \hat\lambda I$, where $\hat\lambda$ is the Francis iteration’s own eigenvalue — wrong by whatever it is wrong by — three solves from a starting vector, normalised. Two errors are measured against the exact vector: the componentwise one, the worst relative error of any entry after matching the scale at the largest, and the normwise one, the distance between the two unit vectors.

The all-ones start, and what it seems to show #

The obvious starting vector is the vector of ones, and from it the prediction looks right.

At order 80 one of the two middle eigenvectors comes back wrong by half normwise — not an eigenvector of anything nearby — while the middle eigenvalues are wrong by $6 \cdot 10^{-6}$, five digits still correct against a gap of two. At order 64 it is wrong by $4 \cdot 10^{-3}$ against an eigenvalue error of $9 \cdot 10^{-7}$. The eigenvector is going faster than the eigenvalue, as predicted.

But only one of the pair. The other middle eigenvector is correct to $10^{-16}$ at every order, including 80. A perturbation argument cannot produce that: $\lambda = 1$ and $\lambda = -1$ have the same condition number, the same gaps on both sides and, by the matrix’s symmetry, errors of the same size. Something in the computation treats them differently, and the only thing the computation contains besides the matrix and the eigenvalue is the starting vector.

Across the whole spectrum at order 80 the eigenvectors alternate: one exact to $10^{-15}$, the next wrong — wholly wrong in the middle, a little wrong further out, exact again near the ends. The alternation is in the starting vector, and it can be checked exactly. The component of the ones vector along the eigenvector of $\lambda$ is proportional to the sum of the entries of the left eigenvector of $\lambda$, which satisfies its own recurrence and is also exact in rationals. That sum is zero, exactly, for every eigenvalue with $\lambda \equiv n - 3 \pmod 4$, and nonzero for every eigenvalue with $\lambda \equiv n - 1 \pmod 4$ — every other eigenvalue, checked in rational arithmetic at orders 16, 40 and 64.

So for half the spectrum, inverse iteration from the ones vector is asked to grow a direction the start does not contain. It can, because rounding puts a trace of it in at about $10^{-16}$, and each solve multiplies that trace by $1/|\hat\lambda - \lambda|$ against everything else. When the eigenvalue is accurate to fourteen digits, three solves are plenty. When it is accurate to six, the trace has grown by $10^{18}$ and the neighbours’ components, which the start does contain and which each solve shrinks only by a factor of about two, are still competitive. The eigenvector that comes back is a mixture, and how wrong it is tracks the eigenvalue’s error — not because the eigenvector is sensitive but because the starting vector was blind to it.

That account makes a number, and the number can be checked. If the trace starts at about $10^{-16}$ and each of three solves multiplies it by $1/\delta$, where $\delta$ is the eigenvalue’s error, while multiplying the nearest neighbours’ components by about a half, the missed eigenvector should come back wrong by about $10^{16}(\delta/2)^3$ normwise, until that reaches one and the vector is simply something else. For the missed middle eigenvectors, $|\lambda| \le 9$, wherever that estimate lies between $10^{-12}$ and a tenth, the measured error is within a factor of a hundred of it, on all twenty such eigenvectors at orders 48 to 72: $9 \cdot 10^{-8}$ measured against $2 \cdot 10^{-8}$ estimated at order 56, $4 \cdot 10^{-3}$ against $8 \cdot 10^{-4}$ at 64, $8 \cdot 10^{-4}$ against $10^{-3}$ at 72. A cube is a steep function. Halve the eigenvalue’s error and the miss falls eightfold; add a fourth solve and it falls by another factor of $2/\delta$, which at order 80 is three hundred thousand. The same three solves that are plenty at order 40 are not enough at 80, and the eigenvalue’s accuracy decides which, though not in the way the prediction said: through the speed at which inverse iteration can build a direction it was not given, not through the eigenvector’s sensitivity.

The ones vector is not an exotic choice; it is what a program reaches for when it has no reason to prefer a direction, and for the Kac matrix it is itself a left eigenvector — every column sums to $n - 1$ — which is the first sign that it carries the matrix’s structure rather than none. The exact sums say which structure: a parity that splits the spectrum in two.

From a random start, the middle is the best of the spectrum #

Started from a vector of independent normal entries, which has a component along every eigenvector, the picture inverts. The middle eigenvalues lose digits at the rate the earlier essay measured — $2 \cdot 10^{-14}$ at order 16, $10^{-6}$ at 64, $3 \cdot 10^{-5}$ at 80. The middle eigenvectors, componentwise, are exact to $10^{-14}$ at every order through 72 and to $5 \cdot 10^{-12}$ at 80. At the order where the middle eigenvalues have lost eleven digits, the middle eigenvectors have lost none that matter.

That is not a contradiction of perturbation theory; it is perturbation theory applied to the right perturbation. The eigenvalue error is the Francis iteration’s: it applied an orthogonal similarity whose rounding is a backward error of order $u\|A\|$, and a backward error that size moves a sensitive eigenvalue by up to its condition number times it. Inverse iteration does not inherit that backward error. It works with the exact matrix — the Kac matrix’s integers are held exactly — and asks for the null vector of $A - \hat\lambda I$, which for any shift nearer $\lambda$ than its neighbours is the eigenvector of $\lambda$ itself. The eigenvalue error enters only as the shift, and a shift wrong by $10^{-5}$ still picks out the right eigenvector by a factor of $2 \cdot 10^{5}$ per solve. What remains is the solve’s own rounding, and the next figure says how big that is.

Lost at the ends, in the smallest entries #

The dial shows each order’s whole spectrum, and the shape is the same at every order: eigenvalue errors peak in the middle, eigenvector errors climb towards the ends. At order 64 the worst eigenvector is $\lambda = 61$, wrong by 2.5 in its smallest entries and by $9 \cdot 10^{-16}$ normwise. At 80, $\lambda = -77$, wrong by $1.5 \cdot 10^{5}$ componentwise and $10^{-15}$ normwise. Normwise, every eigenvector of every order is correct to $2 \cdot 10^{-13}$ or better.

The dashed line is the explanation. A Krawtchouk vector near the end of the spectrum has entries that rise from one at the first coordinate to something like a binomial coefficient in the middle and fall back to one at the last. For $\lambda = 61$ at order 64 they span 16.8 decades; for $\lambda = -77$ at order 80, 21.6. A solve that is normwise backward stable returns every entry with an absolute error of about $u$ times the largest, and an entry twenty decades below the largest has a relative error of $10^{20}u$. The middle eigenvectors’ entries span only one and a half decades at order 16 and eleven at order 80, so their smallest entries keep five or more digits even by that accounting, and in fact keep almost all of them.

Over all 432 eigenvectors the componentwise error is at most three times $u \cdot 10^{\text{span}}$. The span is a property of the exact answer, computed before any floating-point arithmetic is done, and it predicts the loss to within a factor of three in the worst case and bounds it in every case. Nothing about the eigenvalue’s condition number or its gap enters. The end eigenvectors are lost because they are the hardest vectors to write down in floating point, not because they are hard to compute; an answer that is known met the same distinction on the Hilbert matrix, where most of the error was the conversion of the data into doubles before any algorithm ran.

The extreme eigenvectors, $\lambda = \pm(n-1)$, are exceptions that prove it. Their entries are binomial coefficients, all of one sign or alternating, and they span the most decades of all — 22.7 at order 80 — yet they come back exact. Their eigenvalues are the best-conditioned in the spectrum, and their entries are all of one sign or strictly alternating, so no entry is formed by cancellation; why the solve keeps their smallest entries to full relative accuracy, when it does not for their neighbours, is not established here.

What the prediction should have been about #

The prediction treated “the eigenvector” as one quantity with one sensitivity. There are at least three, and on this matrix they part company completely. The eigenvalue’s error is a property of the eigenvalue algorithm’s backward error and the eigenvalue’s condition number. The eigenvector’s normwise error, given an exact matrix and a reasonable shift, is a property of the solve and is at rounding level for every eigenvector here. The eigenvector’s componentwise error is a property of the exact vector’s dynamic range. The middle of the Kac spectrum is the worst place for the first and the best place for the third.

A condition number for one eigenvalue is the right instrument for the first, and the condition number is an amplifier the general statement behind it: it amplifies a backward error, and only the computations that commit that backward error pay for it. Inverse iteration on the exact matrix does not commit it. A route that computed eigenvectors from the Schur form instead — back substitution in the triangular factor, then the orthogonal transformation — would inherit the Francis iteration’s backward error, and on that route the prediction might well hold; that is the comparison this page does not make.

The trap with the ones vector is worth a sentence of its own because it looked like confirmation. An experiment that reproduces a prediction for a reason other than the predicted one is worse than one that fails, because nothing prompts a second look. Here the prompt was an asymmetry the theory could not produce: two eigenvalues with identical conditioning, one eigenvector exact and one destroyed. An estimate that can be fooled and columns that steer a random start are the condition-estimation versions of the same lesson — a structured start sees only what its structure allows — and a random start is the cheap repair in both.

Restarting is a filter measured the eigenvalue side of a starting vector’s role, where the start’s components along each eigenvector decide what a Krylov method finds first. Inverse iteration is the extreme case: one direction amplified, everything else suppressed, and a direction with a zero coefficient is found only through rounding, at a speed set by the shift.

The practical consequence is a rule that costs nothing. Inverse iteration should never start from a vector chosen for its simplicity on a structured matrix, because simplicity is itself structure, and the matrix may share it. A random start is not a refinement; it is the assumption the convergence argument for inverse iteration makes, written into the computation. On this matrix the reason is visible in one picture: the comb of the all-ones figure, where every second eigenvector is computed from nothing but rounding.

The second consequence is about reporting. A computed eigenvector of a non-normal matrix should come with two accuracies, not one. Normwise, every eigenvector here is good to $2 \cdot 10^{-13}$; componentwise, the worst at order 80 has not one correct digit in its smallest entry. Which of the two matters depends on what the vector is for — a direction, a mode shape, a probability distribution — and on the Kac matrix, whose eigenvector for the largest eigenvalue is the binomial distribution of the Ehrenfest urn, the small entries are the probabilities of the rare states.

What nine orders do not settle #

Every eigenvector here comes from three steps of inverse iteration with a dense LU solve; a production code that computes eigenvectors from the Schur form, or by inverse iteration on the reduced Hessenberg matrix rather than on $A$, starts from a matrix that already carries the eigenvalue algorithm’s rounding, and the results above would not transfer. The orders stop at 80 because the eigenvalue computation at the larger orders the earlier essay reached is slow in this setting and produces complex eigenvalues past 104. Every order measured is a multiple of eight, so the spectrum never contains zero; at an odd order the middle eigenvalue is zero itself, its eigenvector’s parity class is fixed by the order, and whether the all-ones start sees it is a question the parity rule above answers but the measurements here do not check. And the random start is one draw per order, not repeated.

Still open: the Schur-form route, and left eigenvectors #

Eigenvectors from the Schur form. Back substitution in the computed quasi-triangular factor and multiplication by the accumulated orthogonal transformation is how LAPACK computes eigenvectors, and it inherits the similarity’s backward error. The prediction with a sign is that on that route the middle eigenvectors’ normwise error grows like the middle eigenvalues’ error divided by the gap — about $10^{-5}$ at order 80 — so that the earlier essay’s prediction holds there and fails here, and the difference between the two routes is the whole of the answer.

The left eigenvectors. The left eigenvectors satisfy the transpose’s recurrence and are exact rationals too, and they are what an eigenvalue’s condition number is built from. The prediction is that their componentwise errors from a random start are bounded by the same three units of roundoff times their own span, and that the product of the left and right spans — not either alone — predicts the eigenvalue condition numbers the earlier essay computed, to within a factor of ten.