An estimate that does not move

The tropical roots of a quadratic matrix polynomial are three numbers and a comparison. Take the Frobenius norms ‖M‖, ‖C‖ and ‖K‖ of the coefficients, form the max-plus polynomial max(log‖M‖ + 2x, log‖C‖ + x, log‖K‖), and read off its corners: they are ‖K‖/‖C‖ and ‖C‖/‖M‖ when ‖C‖² > ‖M‖‖K‖, and √(‖K‖/‖M‖) twice when it is not. Three passes over the coefficients, one comparison, no factorisation — and what comes back is offered as an estimate of where the 2n eigenvalues lie, available before any of them has been computed.

The scaling that buys ten orders measures how well they do it on an overdamped chain of masses, and the answer is lopsided. The large root divided by the largest modulus is 0.961, 0.948, 0.944 and 0.943 at n = 4, 8, 16 and 32. The small root divided by the smallest modulus is 5.36, 17.08, 60.83 and 229.6 over the same four sizes: a factor growing like n².

That is where the account usually stops, and it carries a reading inside it. “Growing like n²” describes an estimate that gets worse — an approximation whose error term is quadratic in the size, whose accuracy therefore decays as the problem grows, which is how nearly every first-order bound in this subject behaves. Under that reading the discrepancy is a property of the estimator, and the repair is a sharper estimator.

A discrepancy that grows has two possible authors and they are separately measurable. Either the estimate is degrading, or the estimate is standing still and the quantity it estimates is walking away from it. The two produce the same ratios and call for opposite responses: the first is a bound to be tightened, the second is a bound that was never a function of the thing that moved. The measurement that separates them is the estimate’s own value at several sizes, which the ratio does not report because a ratio has divided it out.

The estimate is the thing holding still #

Taken on the same family at C = 6M + 0.5K and carried to sixty-four masses, the small tropical root ‖K‖/‖C‖ is

n            4          8         16         32         64
‖K‖/‖C‖   0.333755   0.341040   0.344618   0.346392   0.347275

It rises monotonically and it rises by 4.05 per cent across a sixteen-fold range of sizes. It is not converging slowly to something far away; it is converging quickly to 0.348155, which the next section derives.

The smallest modulus of the actual spectrum, over the same five sizes, is 6.2325·10⁻², 1.9968·10⁻², 5.6649·10⁻³, 1.5086·10⁻³ and 3.8921·10⁻⁴. That is a fall by a factor of 160.1. The ratio of the two columns is 5.355, 17.08, 60.83, 229.6 and 892.3, and the arithmetic is not subtle: 892.3 is 5.355 multiplied by 160.1 for the spectrum and by a further 1.0405 for the estimate. Of the factor of 166.6 the ratio picks up between the smallest chain and the largest, 160.1 is the modulus falling and 1.04 is the estimate rising to meet it.

The good half behaves the same way, which is the part that makes this an explanation rather than a coincidence. The large tropical root ‖C‖/‖M‖ runs 7.02673 → 7.03507, a movement of 0.12 per cent, and the largest modulus runs 7.31437 → 7.46318, a movement of 2.0 per cent. Two quantities that barely move have a ratio that barely moves, and the estimate is called accurate. The same estimate against a quantity that falls by 160 has a ratio that grows by 160, and it is called inaccurate. Neither description is about the estimator’s quality. Both are about whether the thing being estimated happened to be constant in the size.

The largest eigenvalue of the stiffness matrix says why the top end is the easy one. It is 4sin²(nπ/2(n + 1)), which is 3.61803 at n = 4 and 3.99766 at n = 64 and converges to 4, so the top of this spectrum is bounded and settles. The largest modulus that follows from it is 7.31437, 7.41663, 7.45068, 7.46053 and 7.46318, and those are the closed form and the measurement agreeing to six digits at every size. The spectrum has a ceiling and no floor. A constant estimate tracks the ceiling because the ceiling is constant and misses the floor because the floor is not, and it is the same estimate in both readings.

So the sentence to replace is not “the estimate degrades like n²”. It is: the estimate is constant in n, the smallest modulus is not, and the ratio reports the difference. A degrading estimate can be tightened. A constant one cannot be tightened into a function of a variable it does not contain.

Why every ratio of these three norms is constant #

The reason the estimate cannot move is available in closed form, and it needs no eigenvalue at all. The chain’s coefficients are the identity for M, the tridiagonal (−1, 2, −1) matrix for K, and C = αM + βK. Their Frobenius norms are therefore exactly

‖M‖ = √n          ‖K‖ = √(6n − 2)          ‖C‖ = √((α + 2β)²n + 2β²(n − 1))

— the first because every diagonal entry is one, the second because K has n entries of 2 and 2(n − 1) entries of −1, so the sum of squares is 4n + 2(n − 1). At α = 6 and β = 0.5 the third is √(49.5n − 0.5). The measured norms agree with all three closed forms to every digit printed: 2.00000, 4.69042 and 14.0535 at n = 4, and 8.00000, 19.5448 and 56.2805 at n = 64.

Every one of the three has the shape √(an + b) with |b| ≤ 2. Each is therefore √(an) corrected by a factor of 1 + O(1/n), and a ratio of two of them is a constant corrected by 1 + O(1/n). The limits are exact: ‖K‖/‖C‖ → √(6/49.5) = 0.348155 and ‖C‖/‖M‖ → √49.5 = 7.03562. The measured values at n = 64 are 0.347275 and 7.03507, which is the O(1/n) correction at n = 64 and nothing else.

Both tropical roots are ratios of these three norms. That is not an incidental feature of the formula, it is what the formula is: a corner of a max-plus polynomial is a difference of logarithms, which is a ratio. So on any family whose coefficients grow at a common rate — and a coefficient built by scattering the same small stencil down a longer diagonal always does — the tropical roots are constant in the size by construction, before anything is known about the spectrum.

The condition for that to fail is easy to state, and stating it says where such an estimate would come alive. A ratio of two norms moves with the size only if the two grow at different rates, so the corners of a max-plus polynomial carry information about n exactly when the coefficient norms do not share a growth rate. The overdamped chain is the opposite case by construction: M is the identity, K is the same three numbers repeated down a longer diagonal, and C is a fixed linear combination of the two. Whatever lengthening the chain does to one of the three it does to all three, and every difference of logarithms survives it unchanged.

Nothing about the damping disturbs this. C = αM + βK is a linear combination of two matrices that both carry the √n, so it carries it too, at every α and β. The figure above at α = 100 and the one below at β = 4 are the same claim tested at the two ends of the parameter range: the level of the small curve changes, its slope does not.

This is also why the row scaling that fixes badly measured units is a different device with a different job. That one repairs a matrix whose rows are in mismatched units, which is a statement about the spread of the entries. Here the entries are in one unit already and the spread is fine; what is missing is a quantity no norm contains.

What does move, and it is a minimum #

The chain is built so that M, C and K commute, so its 2n eigenvalues are the roots of n scalar quadratics — one for each eigenvalue κ of K:

λ² + (α + βκ)λ + κ = 0

and the eigenvalues of K are known exactly, at 4sin²(kπ/2(n + 1)) for k = 1 … n. The smallest is 4sin²(π/2(n + 1)), which behaves like π²/(n + 1)² and is 3.8197·10⁻¹ at n = 4 and 2.3355·10⁻³ at n = 64.

At α = 6 and β = 0.5 every mode is overdamped, so both roots of each quadratic are real, and the one nearest the origin is close to −κ/(α + βκ). At κ = 2.3355·10⁻³ that formula gives 3.8918·10⁻⁴ against a measured smallest modulus of 3.8921·10⁻⁴ — four digits — and at n = 4 it gives 6.1697·10⁻² against 6.2325·10⁻², within one per cent. So the small end of this spectrum is κ_min divided by a number near α, and it falls like (n + 1)⁻² because κ_min does.

That is the whole of the mismatch. A Frobenius norm is a sum over every entry and is therefore a statement about the large end of a matrix; κ_min is a minimum over a spectrum. No arrangement of ‖M‖, ‖C‖ and ‖K‖ contains 4sin²(π/2(n + 1)), so no arrangement of them can fall like (n + 1)⁻². The estimator is not being sloppy about a quantity it can see; it is silent about a quantity it was never handed.

One matrix carries both numbers, which is the sharpest way to put the omission. The stiffness matrix’s own condition number κ_max/κ_min is 9.47214, 32.1634, 116.461, 440.689 and 1711.66 at the five sizes: that is the quantity here that genuinely grows like n². Its Frobenius norm over the same sizes is 4.69042, 6.78233, 9.69536, 13.7840 and 19.5448, growing like √n. Both are functions of the same n eigenvalues, one of them rises by a factor of 181 across the range and the other by a factor of 4.17, and it is the second that the estimate is handed.

The same shape appears wherever this subject asks a question about a minimum with an instrument built out of maxima. Small compared to what is the symmetric eigenvalue version, where relative accuracy in the small eigenvalues is exactly what a norm-wise backward error declines to promise, and the numbers below the smallest one is the arithmetic’s own version, where the bottom of a format is described by quantities that all live at its top.

The exponent is not two either #

If the discrepancy were the estimate degrading, the exponent in the growth would be a property of the estimator and would be the same wherever the estimator is used. It is not, and the spread is wide enough to read.

Fitting the slope of log(small root ÷ smallest modulus) against log n from n = 4 to n = 64 gives 1.845 at (α, β) = (6, 0.5), 1.852 at (6, 0.2), 1.768 at (6, 4) and 1.852 at (100, 1). At (1, 0.5) it is 2.022, which is above two. None of these is 2, and the settings that produce them differ only in the two damping coefficients.

The reason the split-case numbers sit below two is that the two O(1/n) corrections do not cancel: the estimate is rising by four per cent across the range while the modulus is falling like (n + 1)⁻² rather than n⁻². Both effects shrink with n, so the exponent should approach two from below, and it does. Measured over the last doubling alone, from n = 32 to n = 64, the slopes are 1.958, 1.959, 1.951 and 1.959 — the same four settings, half a per cent apart, and none of them at two.

So “n²” is a limit, correctly derived, describing a regime that begins somewhere past the sizes drawn. Between four masses and sixty-four it predicts a growth of 256 against a measured 166.6, so quoting it as a description of the computation overstates the discrepancy by a factor of 1.54. That is the smaller of the two errors. Quoting it as an account of why the ratio grows is the one this essay is about, and it is not off by half — it names the wrong quantity entirely.

Where the power changes entirely #

The formula has two branches and the test that chooses between them is ‖C‖² > ‖M‖‖K‖: two distinct corners when it holds, one double corner at √(‖K‖/‖M‖) when it does not. That double corner is exactly the γ the standard scaling uses, so the non-split case is the one where prediction and repair collapse into the same number.

Setting α to zero puts the chain there. With C = βK the test becomes β²‖K‖ > ‖M‖, and at β = 0.5 it fails at every size drawn. Both tropical roots are then γ = (6 − 2/n)^(1/4), which is 1.53141 at n = 4 and 1.56304 at n = 64, converging to 6^(1/4) = 1.56508 — a movement of 2.1 per cent, the same kind of near-constancy as before, for the same reason.

What changes is the spectrum. With no viscous damping the low modes of the chain are underdamped: the quadratic λ² + βκλ + κ = 0 has complex roots whenever β²κ < 4, and the modulus of a complex conjugate pair is the square root of the product of the roots, which is √κ exactly. So the smallest modulus is √κ_min rather than κ_min divided by anything, and the measured values confirm it to every digit: 6.1803·10⁻¹, 3.4730·10⁻¹, 1.8454·10⁻¹, 9.5164·10⁻² and 4.8327·10⁻² at n = 4 … 64, against √(4sin²(π/2(n + 1))) = 6.1803·10⁻¹, 3.4730·10⁻¹, 1.8454·10⁻¹, 9.5164·10⁻² and 4.8327·10⁻².

A square root halves an exponent. The smallest modulus now falls like 1/n instead of 1/n², the estimate is as constant as ever, and the discrepancy therefore grows like n. The fitted slope from n = 4 to n = 64 is 0.927, and over the last doubling it is 0.980. Same estimator, same family, one coefficient set to zero, and the published exponent is wrong by a factor of two.

The one place the case test does depend on the size #

An essay claiming the estimate knows nothing about n owes the place where that is not quite true, and there is one. The test ‖C‖² > ‖M‖‖K‖ is a comparison of three numbers, and when α > 0 those numbers all carry the same √n and the comparison is independent of the size to within the same O(1/n). At α = 0 the leading powers do not cancel: the test reduces to β²√(6 − 2/n) > 1, so the boundary sits at

β* = (6 − 2/n)^(−1/4) = 0.652994, 0.645778, 0.642315, 0.640618, 0.639778

at n = 4, 8, 16, 32 and 64, falling to 6^(−1/4) = 0.638943. That is a band of width 2.2 per cent in β, and inside it the same family is non-split at small sizes and split at large ones. At β = 0.645 the roots are a double corner at n = 4 and n = 8 and two distinct corners from n = 16 onwards.

The consequence is worth stating because it is the sharpest form of the whole finding. Inside that band, growing the problem does not change the estimate much and does not change the spectrum’s shape at all — but it changes which formula is used, and therefore which power the discrepancy grows at. A caller who fitted an exponent on chains of four and eight masses and extrapolated would be fitting 1 and predicting 2. Outside the band, at any α > 0, the test is a fact about the damping and the extrapolation is safe. This is the kind of boundary an estimate that can be fooled is also about: cheap, usually right, and with one direction it cannot see.

What follows for anything that uses these numbers #

A sharper bound is not the repair. Every improvement available to a norm-based estimator is an improvement to a number that is already constant in n to within four per cent. The gap it would have to close is a factor of 892 at sixty-four masses and it grows without limit, so no constant factor closes it at every size. What would close it is a different input — the smallest eigenvalue of K, or a cheap lower bound on it — and that is a different computation, not a better bound.

The scaling is untouched by any of this. γ = √(‖K‖/‖M‖) is the geometric mean of the two tropical roots and is a ratio of norms like everything else here, and it moves 2 per cent between n = 4 and n = 64. That is not a defect, because balancing a polynomial’s coefficients is a question about the largest entries of each of them, which is precisely what a norm answers. The device buying ten orders of accuracy works for the same reason the prediction half-fails, and the two facts are one fact seen from two sides.

Two tropical roots twenty decades apart are a different situation. When the corners really are widely separated a single change of variable cannot put both groups near one, and the repair is a second scaling or a division rather than a sharper estimate; a spectrum that comes in reciprocal pairs is the family where that bites. On the chain the two corners are a factor of about twenty-one apart at n = 4 and twenty at n = 64, and one scaling is enough.

An estimate available before the solve is still worth having. The point of a quantity computed from the data rather than from a run is that it costs nothing and arrives in time to change a decision, which is the standing argument the condition number of the model makes. Here it survives intact at the large end, where the large root is within 5.7 per cent of the largest modulus at C = 6M + 0.5K and within 1.9 per cent at C = 100M + K. What it will not do is bracket the small end, and a code that uses it to choose a shift, a tolerance or a deflation threshold near zero is using a constant where it needs a function of n.

Report the case, not only the roots. The two branches of the formula have discrepancies that grow at different powers, the branch is decided by three numbers already computed, and it costs one comparison to say which was taken. A library that returns two roots and not the branch has discarded the one bit that says how to read them.

And the ground truth is what makes any of this a measurement. Every “actual” number above is a closed form — the eigenvalues of a tridiagonal stencil and the roots of n scalar quadratics — so the ratios are the estimate against the answer rather than the estimate against another computation, which is the standing an answer that is known exists to provide. The same family is where a matrix that depends on its own eigenvalue draws its spectrum, and the same distinction between a map’s coefficients and its roots is what the roots are not the coefficients is about: three norms are a statement about the coefficients, and the small end of the spectrum is not a continuous function of them in any sense a norm measures.

The general sentence is short enough to carry out of the field. When a discrepancy grows with the size, measure the estimate before blaming it. An estimator that is constant in the size and an estimator that degrades produce indistinguishable ratios, and only one of them has a repair that looks like a better bound. Here the estimate moves four per cent, the answer moves by a factor of a hundred and sixty, and the correct account of the failure is a sentence about which quantities the estimator was given rather than about how tightly it uses them. That account also survives being asked the question the backward-stable answer to a problem nobody asked puts to every quantity in this field: what would have to be different for the number to come out right? Not the arithmetic, not the precision, and not the bound — the input.