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/√κₘᵢₙ = 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. It is also, exactly, a number that has already appeared in this essay under another name, which is the next section. 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.

Two square roots, and they are one interval #

This essay has now described a square-root law twice, in sections that do not refer to each other.

The first was a nuisance: as β approaches β* the window of μ that works closes like the square root of the margin, which is why a fixed grid reports the wrong boundary and why the scan needs a golden-section refinement inside it. The second was a property of the question: the pair’s separation is 0.9823 √ε, the classical halving of digits at a double root.

They are the same interval, and the constant is the same constant.

Q(μ) is negative definite exactly where every mode is. In the basis of K’s eigenvectors each mode contributes the quadratic μ² + βκμ + κ, which is negative between its two roots, so the certificate’s window is the intersection of n intervals. The binding one is the mode with the smallest margin — the same mode the closed form for β* is derived from — and its two roots are the pair that collides at the boundary. So the window’s width is the colliding pair’s separation, and there is nothing to prove about the coincidence beyond noticing it.

Measured at n = 8, over six decades:

Three columns and one number. And neither square root is asymptotic: the window’s width is √margin exactly, not to leading order, at every stop — which is a stronger statement than “closes like” and is the kind that a gate can hold.

The fourth column is the one that has practical content and was not measured before. The certificate is found by minimising the largest eigenvalue of Q(μ), so what the scan is hunting for is a well, and a well has a depth as well as a width. The depth is margin ⁄ 4, exactly, at n = 4, 8 and 12 — which vanishes linearly in the margin while the width vanishes as its square root. At ε = 10⁻⁶ the window is a thousandth wide and the well is two ten-millionths deep. So the difficulty near the boundary is not that the window is hard to land in; it is that once landed in, the thing that distinguishes it from its surroundings is a linear quantity being read by an eigensolver. That is why the refinement is on μ rather than on a tolerance, and why the failure mode is a certificate that cannot be found rather than one found in the wrong place.

One correction falls out of the same table. The constant 0.9823 is √(margin ⁄ ε), and it is a property of the chain length, not of the law: 1.748 at n = 4, 0.9823 at n = 8, 0.682 at n = 12 — a factor of two and a half across three sizes, against 2.5% across six decades of ε at each of them. Twelve decades of ε hold it fixed, which is what makes it a square-root law; three values of n move it, which is what makes it a constant of this chain.

assertTheWindowAndTheSeparationAreOneInterval holds all four columns, at three chain lengths: that the window is the separation, that both are √margin, that the certificate the scan returns lies inside the window, that the depth is a quarter of the margin, and that the constant is flat in ε and not in n.

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.

And the scan is scanning for something with a closed-form location, which the sweep shows and the description above does not.

μ is exactly proportional to β. At β = 7, 10, 14 and 20 the certificate is at −0.4222, −0.6031, −0.8443 and −1.206, and dividing through gives −0.06031 at every one of the four — the same five digits, not a trend. The scan is therefore searching four decades for a point whose position is 0.0603 β, and on this family a single Cholesky at that μ would produce the certificate with no scan at all.

Two cautions before that is used as a shortcut. The proportionality is a property of this chain — the constant 0.0603 carries its mass and stiffness in it, and nothing above derives it, so on another family the scan is still the honest way to find μ. And the gap is not proportional: 0.48, 0.9861, 1.539, 2.31 against β = 7, 10, 14, 20 divides to 0.069, 0.099, 0.110, 0.116, still climbing at the far end. So the location of the certificate scales and the room around it does not, which means the scan can be cheapened by a good starting point and cannot be replaced by one — the refinement is still doing the work at the boundary, where the gap is closing to nothing.

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.