A condition number for one eigenvalue

Symmetry is worth more than precision measures the gap between the two cases with one pair of numbers. A symmetric matrix’s eigenvalues obey Weyl’s theorem — a perturbation of size ε moves every eigenvalue by at most ε, with no constant at all. An 8×8 Jordan block with a corner entry moves its eigenvalues like ε^(1/8), so a perturbation at the level of storing the matrix moves the spectrum by 10⁻².

That essay is about the difference between the two cases. This one is about the fact that in the second case the question does not have one answer.

The quantity #

Let λ be a simple eigenvalue of A, with right eigenvector x and left eigenvector y — that is, Ax = λx and yᵀA = λyᵀ, both normalised. Then a perturbation A + εE moves λ by

$$\delta\lambda = \varepsilon\,\frac{y^{\mathsf T} E x}{y^{\mathsf T} x} + O(\varepsilon^2)$$

and the worst case over unit E is ε / |yᵀx|. So the condition number of the eigenvalue is

$$s(\lambda)^{-1} = \frac{1}{|y^{\mathsf T} x|}$$

which, for normalised vectors, is the reciprocal of the cosine of the angle between them.

Two consequences, and both are what the symmetric case hides.

For a symmetric matrix the left and right eigenvectors are the same vector, so the cosine is one and the condition number is one. That is Weyl’s theorem, arrived at from the other direction, and it explains why the symmetric case needs no per-eigenvalue analysis: the answer is one for all of them, always.

In general they are different vectors and the angle between them is a property of that eigenvalue. Nothing forces the angles for different eigenvalues of the same matrix to be similar.

A matrix where the answer is exact #

The claim needs a check against something that was not measured, and this subject rarely supplies one — eigenvalues of a general matrix are exactly the thing there is no closed form for.

Here there is. Take

$$T = \begin{pmatrix} 1 & c \\ 0 & 2 \end{pmatrix}$$

Its right eigenvector for λ = 1 is [1, 0]; its left eigenvector is [1, −c], since the second component of yᵀ(T − I) is cy₁ + y₂. So the cosine is 1/√(1 + c²) and the condition number is √(1 + c²). Doing the same for λ = 2 gives right eigenvector [c, 1], left eigenvector [0, 1], and the same number.

Now conjugate by an orthogonal matrix, and add two decoupled diagonal entries at 5 and 7. An orthogonal similarity does not change the angle between two vectors, so both eigenvalue condition numbers are still exactly √(1 + c²) — while the matrix is a full 4×4 with no visible structure. The decoupled entries have left and right eigenvectors that coincide, so their condition numbers are exactly 1.

One matrix, two condition numbers, both known in closed form. At c = 100 the numbers are 100.005 and 1.

Three routes, and the third is the one that matters #

The figure computes all three and the site asserts all three.

The closed form is √(1 + c²), from the algebra above.

The computed value comes from inverse iteration: solve with the shifted matrix A − (λ + δ)I, giving the right eigenvector, and with its transpose, giving the left one, then take the cosine. This is the standard and slightly alarming way it is done — the system is deliberately near-singular, because the error in the solve lies almost entirely along the eigenvector being sought, which is the one property of a badly conditioned solve anybody ever wants. The two agree to better than 2% at twenty-five values of c across three decades.

The measured value is what a perturbation actually does. Twelve random directions E with ‖E‖_F = 1, at ε = 10⁻⁹; for each, the whole spectrum is recomputed by the real Schur decomposition and the movement of the eigenvalue near 1 is recorded. The worst of the twelve reaches 46.3 at c = 100.

That third number is the one worth being careful about, and it is reported as a fraction rather than as a match. The condition number is a worst case over all perturbation directions, and twelve random directions in a sixteen-dimensional space do not find the worst one. 46 out of a permitted 100.005 is what twelve directions reach; a hundred directions would reach more, and the exact worst case requires the specific rank-one E aligned with yxᵀ.

The site therefore asserts two things rather than one: that the movement is at least a tenth of the condition number, so the number is doing predictive work, and that it never exceeds it, so the bound is a bound. That is the same discipline the condition number is an amplifier applies to the linear-system case, where a random perturbation direction is amplified by 0.29 of κ at the median and 0.76 at the worst of two hundred. The worst case is attained by no particular direction and the typical direction reaches a good fraction of it, which is the honest form of the claim in both places.

Meanwhile the decoupled eigenvalue moves by 0.37 of ε, over the same twelve directions, in the same matrix. That is the whole essay in one comparison.

The cheap diagnostic #

Computing per-eigenvalue condition numbers needs eigenvectors, and eigenvectors are a further computation which can itself be badly conditioned. There is a single number that needs none of them.

Henrici’s departure from normality:

$$\mathrm{dep}(A) = \sqrt{\|A\|_F^2 - \sum_i |\lambda_i|^2}$$

which is zero exactly when A is normal and grows with how far from normal it is. It comes free with the Schur form — it is the norm of the strictly triangular part of T — and it bounds the whole spectrum’s sensitivity collectively.

On the matrix here it comes out at exactly c, which is a pleasant check: the departure from normality of a matrix orthogonally similar to [[1, c], [0, 2]] ⊕ diag(5, 7) is the one entry that makes it non-normal.

Its usefulness and its limitation are the same thing. It is a matrix quantity, so it tells a caller that some eigenvalue may be sensitive and cannot say which, and it cannot distinguish the case where one eigenvalue is terrible and the rest are perfect — which is the case here — from the case where all of them are moderately bad. It is the right thing to print beside a spectrum, and the wrong thing to conclude from.

Why this is not the condition number of the matrix #

A reader arriving from the error field has a condition number already: κ(A) = σ₁/σₙ, which the condition number is an amplifier establishes as the amplification factor for solving Ax = b.

It is the wrong number here and the reason is worth stating, because the two are often conflated.

κ(A) is about the solution of a linear system. The eigenvalue condition number is about the location of an eigenvalue. They are different questions and they can point in opposite directions: an orthogonal matrix has κ = 1 and can have arbitrarily ill-conditioned eigenvalues if it is written in a skewed basis — except that it cannot, because an orthogonal matrix is normal, which is precisely the point. A better example is a matrix with a large κ and perfectly conditioned eigenvalues: diag(1, 10⁻¹⁰) has κ = 10¹⁰ and both eigenvalues at condition number 1.

So a matrix can be hard to solve with and easy to find the eigenvalues of, and the reverse. The quantity that governs the eigenvalue problem is non-normality, and the quantity that governs the linear system is the spread of the singular values, and neither implies anything about the other.

What this means for a computed spectrum #

The practical content is a sentence about what a backward stable eigenvalue routine gives.

The Francis algorithm is backward stable: it returns the exact eigenvalues of A + E with ‖E‖ ≈ u‖A‖. In the symmetric case that ends the discussion, because every eigenvalue has condition number one and the computed values are accurate to u‖A‖.

Here it does not. The computed eigenvalue near 1 is accurate to about u‖A‖ times its own condition number, which at c = 100 is a hundred times worse than the eigenvalues at 5 and 7 from the same run of the same routine on the same matrix. Nothing in the output distinguishes them, and any routine that reported a single accuracy estimate for the spectrum would be wrong about at least half of it.

Which is why LAPACK’s expert drivers return per-eigenvalue condition estimates alongside the eigenvalues, and why the simple drivers do not — and why the difference between the two is worth knowing about before choosing one.

What happens as the angle closes #

The condition number is the reciprocal of a cosine, so it is unbounded, and the way it becomes unbounded is worth following because it connects this essay to the one below it on the ladder.

As c grows, the right eigenvector for λ = 1 stays at [1, 0] and the left one tilts towards [0, −1] — they approach orthogonality, the cosine approaches zero, and the condition number approaches infinity like c. Nothing pathological happens to the matrix on the way: its entries are ordinary, its eigenvalues stay at 1 and 2, and its condition number as a linear system is unremarkable.

The limit is where the essay below this one lives. When the left and right eigenvectors become exactly orthogonal, the eigenvalue is defective — it has algebraic multiplicity greater than its geometric multiplicity — and its condition number is not a large number, it is undefined. The first-order perturbation theory the whole essay rests on breaks down, because there is no first order: a defective eigenvalue of multiplicity m moves like ε^(1/m) rather than like ε.

That is exactly the ε^(1/8) that symmetry is worth more than precision measures on the 8×8 Jordan block. So the two essays are the two regimes of one story, and the join between them is not smooth: the condition number grows without limit as the eigenvectors close, and then the concept stops applying rather than reaching a limiting value.

The practical consequence is a familiar shape. Near-defectiveness cannot be detected by looking at the eigenvalues, because two eigenvalues can be well separated and still have nearly parallel eigenvectors — as they do here, at 1 and 2, with a condition number of 100. It cannot be detected from the matrix’s condition number as a linear system either. What detects it is the departure from normality, or the eigenvectors themselves, and both are things a caller has to ask for.

The other half: eigenvectors are worse #

One more asymmetry, and it is the one most likely to catch somebody out, because it is invisible in everything above.

The condition number of an eigenvalue is 1/|yᵀx|. The condition number of an eigenvector is governed by something else entirely: the separation between its eigenvalue and the rest of the spectrum. A perturbation of size ε rotates the eigenvector by about ε divided by the gap to the nearest other eigenvalue.

So the two sensitivities are controlled by different quantities and can be at opposite extremes in the same matrix. A symmetric matrix has perfectly conditioned eigenvalues always, and its eigenvectors are as badly conditioned as its eigenvalue gaps are small — two nearly equal eigenvalues of a symmetric matrix have eigenvectors that a perturbation can rotate arbitrarily, and there is nothing wrong with that, because any vector in the plane they span is nearly an eigenvector.

Which is a case this site has already met by another route. Rank is a decision is about the same difficulty on the singular value side: individual singular vectors belonging to close singular values are not determined, while the subspace they span is, and the useful output is a subspace rather than a vector. The eigenvector version is the same statement and it has the same resolution — ask for the invariant subspace, which is well conditioned when the group of eigenvalues is separated from the rest, and never ask for a single vector belonging to a cluster.

The Schur form of the form a real matrix can reach is what delivers that, which is the third of the reasons it is a library’s return value rather than an intermediate: its columns span nested invariant subspaces, orthonormally, and the ill-conditioned object is never formed.

What is asserted here #

The computed condition number is the closed form, at twenty-five values of c across three decades, to within 2%. Two routes: one is inverse iteration on a near-singular matrix, the other is √(1 + c²).

The decoupled eigenvalues are exactly one, to 10⁻⁴, throughout — the control without which the rising curve would only be a rising curve.

A perturbation moves the sensitive eigenvalue by at least a tenth of its condition number and by no more than the condition number permits, over twelve directions at every position of the slider.

The departure from normality is the off-diagonal entry, which is the third route and the one that needs no eigenvectors.

And A = ZTZᵀ on every frame, because the spectrum this whole essay is about is read off a factorisation and the site does not draw one without its residual.

A closing note on where the number comes from #

The derivation at the top of this essay is four lines and it is worth reading them once more, because the place the condition number comes from explains its behaviour better than the formula does.

Differentiate Ax = λx with respect to a perturbation: (A + εE)(x + εẋ) = (λ + ελ̇)(x + εẋ). Expand, keep the first-order terms, and left-multiply by yᵀ. The terms in ẋ vanish, because yᵀA = λyᵀ makes yᵀ(A − λI)ẋ zero whatever ẋ is — and that is the whole trick. The left eigenvector is exactly the vector that annihilates the unknown part of the perturbation, which is why it appears and why no other vector would do.

What is left is yᵀEx = λ̇ yᵀx, and dividing gives the formula.

Two things are visible in that derivation and not in the result. First, the sensitivity is a first-order quantity, so it says nothing when the first-order term vanishes — which is the defective case above, where yᵀx is zero and the division is undefined rather than large. Second, the denominator is not a norm of anything: it is an inner product between two vectors that are both determined by the matrix, so it can be small for reasons that have nothing to do with the size of the entries.

That second point is the one worth carrying. A matrix can have small entries, a modest norm, a respectable condition number as a linear system, and an eigenvalue that a perturbation in the fifteenth digit moves in the fourth. There is no quantity a reader can look at on the face of the matrix that predicts it — only the eigenvectors, or the departure from normality, and both have to be asked for.