Every eigenvalue real, and a test that says so

A symmetric matrix has real eigenvalues, and the fact is so familiar that it is easy to forget it is a theorem about a class rather than an observation about a computation. Nothing has to be measured; symmetry is checkable by inspection, and realness follows.

A quadratic eigenvalue problem with symmetric coefficients has no such guarantee. The damped chain in the field’s first essay has M, C and K all symmetric and positive definite, and its eigenvalues are complex whenever the damping is light — which is what makes the physical thing oscillate. Symmetry buys nothing here.

There is a class in which realness comes back as a property, and it comes with three things this site wants: a certificate that is a factorisation, a boundary with a closed form, and a failure at the boundary that has nothing to do with conditioning.

The class, and the test that is a Cholesky #

Q is hyperbolic when M, C and K are symmetric with M positive definite and

(xᵀCx)² > 4(xᵀMx)(xᵀKx)   for every x ≠ 0.

Written that way it is useless as a test: it quantifies over every vector in the space, and no finite computation checks it directly. The usable form is a theorem about definiteness —

Q is hyperbolic exactly when there is a real μ at which Q(μ) is negative definite.

— and that is one symmetric matrix and one Cholesky. The factorisation completes or it does not. A completed one is a certificate anybody can re-check for the cost of a factorisation; a failed one at every μ is the negative answer.

It is the same routine when symmetry is not enough uses as the test for definiteness and the same one that stops at a constraint row in the saddle-point field. Here it is doing a third job: proving something about a polynomial by factorising one of its values.

The certificate does two things #

The μ that proves the spectrum is real also locates the gap. Measured at n = 8 with β = 8: the sixteen eigenvalues split into eight above the certificate and eight below, with a gap of 0.48 between the two groups. At β = 12 the split is the same and the gap is 1.27; at n = 10 with β = 9, ten and ten, gap 0.456.

That is not luck and it is not an extra computation. The two groups of a hyperbolic quadratic are called primary and secondary, they are separated by an interval, and Q is negative definite exactly on the interior of that interval. So one Cholesky answers two questions — is the spectrum real, and where does it divide — and the second answer is the one a method needs in order to ask for “the n eigenvalues nearest zero” and mean something by it.

The boundary, located twice #

For the chain with C = βK the quantifier collapses. In the basis of K’s eigenvectors the condition becomes β²κ > 4 for every stiffness eigenvalue κ, so the binding constraint is the smallest κ, and the critical damping is

β* = 2/√κ_min = 1/sin(π/2(n+1)),

exactly. At n = 8 that is 5.758770483143636.

Now locate the same boundary by bisection on the certificate: at each trial β, scan for a μ at which −Q(μ) has a Cholesky, and keep the half where one exists. Forty-four bisections later the answer is 5.75877048314, agreeing with the sine to thirteen digits. At n = 4 it is 3.2360679775 against 3.2360679775, and at n = 12, 8.29622981056.

Neither route computes an eigenvalue. One is a closed form from a trigonometric identity; the other is a factorisation that either completes or does not, asked forty-four times. That is this site’s two-routes habit applied to a boundary rather than to a value, and it is the strongest form of it available: the two computations have no arithmetic in common at all.

One detail from building it is worth keeping, because it is the kind of thing that would otherwise be silently wrong. The certificate is found by scanning μ, and as β approaches β* the window of μ that works closes like the square root of the margin. A scan of fixed resolution therefore reports “not hyperbolic” slightly before the true boundary — measured at n = 4, a critical β of 3.23617 against a true 3.23607, wrong in the fifth digit and looking perfectly convergent. The repair is a golden-section refinement inside the scan’s best bracket, and with it the two routes agree to thirteen digits instead of four.

An integer, read two ways #

A hyperbolic quadratic offers something else that this site collects: an integer answer, available from a factorisation rather than from a spectrum.

The number of negative eigenvalues of Q(μ) — an inertia, and therefore an integer — counts eigenvalues relative to μ. It is exactly the device an eigenvalue count that cannot be slightly wrong uses for a symmetric matrix, carried to a matrix that depends on the shift.

And it does not mean the same thing on the two sides of the gap.

μ to the right of the gap    eigenvalues above μ = ν(μ)
μ to the left of the gap     eigenvalues above μ = 2n − ν(μ)

Measured at n = 8, β = 8: at μ = −12 the negative count is 5 and eleven eigenvalues lie above; at μ = −0.3 the count is 8 and eight lie above. A reader who takes the first rule everywhere gets 5 where the answer is 11 — not slightly wrong, and not an accuracy question at all. The count is exact on both sides. What is wrong is the reading, and the reading needs the gap, which the certificate has already located for the price of the Cholesky that proved the spectrum was real.

Seven of twelve shifts tested disagree under the naive reading. That is the interesting failure rate: not one in a hundred, which would look like an edge case, but more than half, which is what a rule that is simply the wrong rule looks like.

What happens at the boundary #

Set β to exactly β* and the smallest mode’s two eigenvalues coincide. A double root of a quadratic is the classical place where accuracy halves, and here the loss can be measured against a closed form rather than argued about.

At β = β*(1 + ε), the pair’s separation is 0.9823 √ε — the same constant to four digits over twelve decades of ε, which is the square-root law measured rather than quoted. And the computed spectrum’s worst relative error against the closed form runs

ε = 10⁻²    8.9·10⁻¹⁵
ε = 10⁻⁶    5.3·10⁻¹³
ε = 10⁻¹⁰   1.1·10⁻¹⁰
ε = 0       3.7·10⁻⁸

Eight digits gone at the boundary, which is √u times a small constant.

And nothing is ill conditioned. κ(K) is 32.16 at every stop of that sweep — it does not move at all, since β does not appear in K. The coefficients are integers. The matrices are symmetric and well scaled, ‖M‖, ‖C‖ and ‖K‖ are within a factor of thirty of each other, and there is no condition number anywhere in the problem above a hundred.

What is unbounded is the derivative of the map from a coefficient to a double root. Near a simple root, moving a coefficient by ε moves the root by O(ε); near a double root it moves it by O(√ε), so a rounding of size u produces an error of size √u whatever else is true. That is not the condition number of a matrix and it is not a defect of an algorithm: it is a property of the question, and it is the reason the condition number is an amplifier is a statement about simple eigenvalues and has to be, since at a repeated one the amplifier is infinite.

The site has met the same shape once, from the matrix side: a condition number for one eigenvalue ends at a defective matrix, where the sensitivity stops being a number. What is new here is that the approach to it is a slider — the damping — so the halving of the digits can be watched arriving, with a closed form available at every stop including the one where the two eigenvalues are genuinely equal.

What the class rules out, and what it does not #

It is worth being exact about the boundary of the claim, because “the eigenvalues are real” is a strong-sounding sentence and it does less than it sounds like.

Hyperbolicity gives realness and the split into two groups. It says nothing about the eigenvalues being well separated: the primary group of a long chain is crowded near zero, and at n = 8 with β = 8 its eight members span 0.1255 to 0.1476 — a spread of twenty per cent across eight numbers, with neighbouring pairs a thousandth apart. Any method that wants an individual eigenvector out of that group is subject to the same gap arithmetic the gap decides the eigenvector sets out, and the class does not help.

It says nothing about conditioning either. A hyperbolic quadratic can be as badly scaled as any other, and the whole of the previous three essays applies to it unchanged — indeed the overdamped family is exactly what those essays measure on, because their measurements need real eigenvectors.

And it says nothing about the physics being sensible. Overdamped means every mode returns to rest without oscillating, which for a real structure usually means the model has been given far more damping than the thing it describes. The class is a mathematical convenience that occurs in practice — a heavily damped isolator, a lubricated bearing — rather than the common case.

How the certificate is actually found #

The scan deserves one paragraph of description, since the essay leans on it twice.

λ_max(Q(μ)) is a continuous function of μ, negative exactly on the gap. So the certificate is found by minimising it: a coarse geometric scan over sixty values of μ spanning four decades, then a golden-section refinement inside the bracket containing the scan’s best point, then one Cholesky at the refined μ to produce the certificate itself. Fifty refinement steps take the bracket to the rounding level, which is far more than needed except at the boundary — and the boundary is exactly where the whole thing is being used, which is why the refinement is not optional.

The refinement is also what makes the bisection above honest. Without it, the two routes to β* disagree in the fifth digit and the disagreement is in the direction that looks like agreement: the certificate route reports a slightly larger critical damping, which is what a reader would expect from a conservative test. Convergent-looking, plausible, and wrong. The failure was found by the closed form and by nothing else, which is the argument for having one.

Why the class is worth having #

Three practical things follow, and they are why this is a field’s essay rather than a curiosity.

A method can be told the spectrum is real before it starts. An eigensolver that knows its answers are real can work in real arithmetic throughout, which is a factor of two to four, and can use bisection and inertia counts rather than a general iteration — which is where the integer above earns its keep.

The gap gives a shift. “Compute the n eigenvalues nearest zero” is a well-posed request for a hyperbolic problem, because the two groups are separated and the certificate says where. For a general quadratic it is not: the eigenvalues are scattered in the plane and nearest has to be defined.

And the boundary is a design constraint. A structure at exactly critical damping is a structure whose modes are computed to eight digits instead of sixteen, and the loss cannot be repaired by scaling, by a better linearisation or by a better solver. The only repairs are more precision or a formulation that solves for the pair rather than the roots — which is a real trade, priced in buying the accuracy back, and it is the sort of thing worth knowing before the model is built rather than after.

The other quadratic classes, briefly #

Hyperbolic is one of a small family of classes defined by what their spectra are forced to do, and naming the neighbours puts it in place.

Overdamped is hyperbolic with K positive definite as well, which is the case here: every eigenvalue is then real and negative, so every mode decays and none of them oscillates. Hyperbolic without that allows a positive eigenvalue, which is a mode that grows.

Gyroscopic is the opposite corner: M and K symmetric positive definite with C skew-symmetric, which is what a rotating system produces. Its eigenvalues are purely imaginary and come in quadruples, so nothing decays and everything oscillates — the exact reverse of overdamped, and the same kind of statement: a property of the class, not an outcome of a computation.

Palindromic is a different axis again, and it has its own essay two doors along: there the constraint is not on where the eigenvalues are but on how they pair, and the pairing turns out to be where half the accuracy is.

What the three have in common is worth the sentence. In each case a structural property of the coefficients forces a property of the spectrum, and in each case the interesting numerical question is not whether the property holds — it does, as algebra — but whether a computation on those coefficients returns something that has it. For hyperbolicity the answer is yes and the certificate is cheap. For palindromic structure the answer is no, and what to do about it is the surprise.

At other settings #