The largest gap is inside the null space

A pencil (A, B) has an infinite eigenvalue for every direction in which B is singular, and a descriptor system has one for every algebraic constraint in the model. Counting them is therefore counting the zero singular values of B, and a floating-point routine has to decide which of the computed singular values those are.

The decision needs a rule, and two are in circulation. Cut at a fixed threshold — something near n·σ₁·ε, with ε the machine epsilon, which is what the rank-revealing routines in the standard libraries use when nobody supplies a tolerance. Or cut at the largest gap: form the ratios between consecutive singular values, find the largest, and put the boundary there. The second is the one usually recommended, and the reason given is a good one. A threshold is a constant somebody typed, and a gap is a property of the matrix.

On twenty-five pencils whose entries are integers, whose rank deficiency is exact, and to which nothing has been added, the threshold rule returns the right count twenty-five times. The largest-gap rule returns it sixteen.

The count is available exactly, which is what makes this measurable at all #

The eigenvalues of a pencil are the roots of det(A − λB), and that polynomial has degree n only when B is nonsingular. Each direction of B’s null space costs it a degree, so n minus the degree is the number of eigenvalues at infinity. For an integer pencil the polynomial can be had with nothing rounded: evaluate the determinant in BigInt rationals at n + 1 integer points and interpolate, the same route a spanning-tree count takes to an integer that was known in advance. What comes back is a degree, and a degree is an integer.

The pencils here are built in the semi-explicit form — a block of differential states and a block of algebraic constraints — and then multiplied on both sides by unimodular integer matrices. That changes nothing about the pencil and destroys every visible trace of the construction: the matrices that reach the determinant have no zero rows and nothing about them announces the answer. Twenty-five of them, at every size from four to eight and every constraint count from one to n − 1, and the exact degree is n − k on all twenty-five.

So there is a reference answer, and the two float rules can be scored against it rather than against each other. That is the whole of the experiment, and it is worth saying what it does not contain. There is no noise. No entry has been perturbed, no matrix has been through an assembly, and the deficiency is not approximate — B has an exact null space of dimension k, and the singular values that correspond to it are mathematically zero.

The threshold rule is scored by counting the singular values at or below n·σ₁·ε. The gap rule is scored by finding the largest ratio σᵢ/σᵢ₊₁ and reporting rank i.

One constraint is the case that cannot go wrong #

At one constraint the two rules cannot disagree, and the reason is structural rather than lucky.

B has a one-dimensional null space, so exactly one singular value is mathematically zero. Whatever size the decomposition returns for it — 5.40·10⁻¹⁵⁸ in the figure above, 5.06·10⁻¹⁸ at n = 7, 2.36·10⁻¹⁵⁵ at n = 8 — it is the last entry in the list, and the only ratio it participates in is the one at the boundary. There is no interior to the null block, so there is nowhere else for a gap to be. Across five sizes and twenty seeds the largest-gap rule is right at k = 1 every time, one hundred runs out of one hundred.

That is the picture the recommendation is made from, and it is a fair one as far as it goes. The boundary ratio at k = 1, n = 6 is 5.55·10¹⁵⁶. Nothing anywhere near it exists among the nonzero singular values, which are spread over a single order of magnitude. A rule that hunts for the largest ratio finds a jump of a hundred and fifty-six orders and cuts there, and it is right for the reason it looks right.

The trouble begins at two, and it begins without any change in kind. The entries are still integers, the deficiency is still exact, and the only thing that is different is that the null block now has an inside.

Two constraints, and the largest ratio is between two zeros #

The singular values are 4.27, 2.60, 0.918, 0.416, 1.13·10⁻¹⁶ and 4.10·10⁻¹⁵⁷. The polynomial’s degree is 4, so two of the six eigenvalues are at infinity and the rank of B is four. The last two entries are the null space, and they are the null space exactly: B has no fifth or sixth singular value, and those two numbers are what a floating-point decomposition produces where the mathematics has nothing.

The gap at the true boundary is 0.416 over 1.13·10⁻¹⁶, a factor of 3.69·10¹⁵. The gap one position later is 1.13·10⁻¹⁶ over 4.10·10⁻¹⁵⁷, a factor of 2.75·10¹⁴⁰. The second is a hundred and twenty-five orders larger than the first, and a rule that takes the largest ratio takes it, reports rank five, and returns one infinite eigenvalue where there are two.

This particular pencil has been drawn before. The essay that recommends the gap rule reads its singular values off the page — 4.3, 2.6, 0.92, 0.42, 1.1·10⁻¹⁶, with the sixth below 10⁻¹⁵⁰ — and calls the decision comfortable to the point of being no decision at all. Everything in that sentence is true of the threshold rule and of a reader looking at the list. It is not true of the rule that essay goes on to recommend. The fifteen-order gap it names is real, it is at the right place, and it is not the largest one.

The consequence is an integer error rather than a small one. A count of infinite eigenvalues that is short by one leaves the solver with a spurious finite eigenvalue at the ratio of two quantities that are both rounding, and there is nothing in that eigenvalue’s residual to say so — the same shape as a number that decides nothing being read as though it decided something. A rank rule that is off by one is off by a whole eigenvalue.

Three constraints, and it is right again #

Adding a third constraint to the same construction makes the rule right again, and the mechanism is worth stating precisely because it is the whole subject.

The three singular values of the null space come back as exact zeros. A ratio between two of them is 0/0, which is not a large gap and not a small one — it is the absence of a gap, and it is excluded. What remains is 1 over 0, an infinite ratio, and it sits at position three, which is where the degree says the boundary is. The rule cuts there and reports rank three, correctly.

Nothing about the pencil got easier. It has more constraints than the failing case, a larger null space and a lower rank, and the reason it is decided correctly is that the decomposition happened to return zeros rather than denormal-sized survivors. The verdict turned on the arithmetic’s bookkeeping about numbers that are all equal to each other.

Four constraints, and the failure is a division rather than a size #

At four constraints the same family fails again, and not by a margin. The boundary ratio is 2.34·10¹⁶, which by any ordinary standard is a decisive jump — sixteen orders, on a matrix whose nonzero singular values span half an order. It loses to an infinite one formed inside the null space, between a survivor at 4.28·10⁻¹⁷ and an exact zero below it.

That is a different failure from the one at two constraints. There the rule lost a comparison of magnitudes and could in principle have won it. Here it loses to infinity, and no amount of separation at the real boundary would have helped: any finite ratio loses. The rule’s decision has stopped being a comparison of evidence and become a question of which of the null space’s zeros the decomposition rounded to zero and which it did not.

Both failures share a cause, which is that the decomposition does not return a cluster where the mathematics has zeros. Across the twenty-five pencils there are eighty mathematically zero singular values. Fifty-seven of them come back as exact zeros. The other twenty-three come back spread from 2.79·10⁻¹⁶ down to 3.40·10⁻¹⁶⁶ — a hundred and fifty orders of magnitude, among numbers that are all the same number.

The verdict belongs to the rounding rather than to the pencil #

The sharpest reading of all this is not that the gap rule is wrong at two constraints. It is that its verdict is not a property of the problem at any level a caller can see.

At two constraints it is wrong at n = 4 and n = 6 and right at n = 5, n = 7 and n = 8. At n = 6 it is right at one constraint, wrong at two, right at three, wrong at four and right at five. The pencils are built by one construction with one parameter moved; nothing about the constraint count or the size predicts the answer. What decides it is where the singular values of an exactly rank-deficient matrix happened to land, and those landings are an artefact of the decomposition rather than information about the pencil.

The figure above is the case that makes this concrete. Two constraints, exactly as in the failing six-by-six, and the two null-space singular values come back 1.08·10⁻¹⁵⁵ and 2.96·10⁻¹⁶¹. Their ratio is 3.64·10⁵. The boundary’s is 6.11·10¹⁵⁴. The rule is right, and it is right because the interior spread of a block of zeros happened to be five orders rather than a hundred and forty.

Over the full sweep the threshold rule agrees with the exact degree on twenty-five of twenty-five and the gap rule on sixteen, failing at (n, k) = (4,2), (5,3), (5,4), (6,2), (6,4), (7,3), (7,4), (8,3) and (8,4). Repeating the whole sweep at twenty different constructions of the same shape gives five hundred pencils: the threshold rule is right on 500 of 500 and the gap rule on 306, which is 61.2%. Its per-cell rate is what would be expected from the mechanism rather than from the mathematics — never wrong at k = 1, never wrong at k = n − 1 except twice in a hundred, and wrong between twelve and seventeen times in twenty everywhere in the middle, which is exactly where the null block has an inside.

What the recommendation is actually a picture of #

The intuition behind the gap rule is not wrong. It is a picture of a different situation, and the difference is the one thing worth carrying away from all of this.

When a matrix of true rank r has been perturbed at relative size δ, the n − r small singular values are not zero — they are O(δ), scattered over a factor of maybe a hundred, and they form a group. The largest ratio inside that group is small, the ratio at the boundary is about 1/δ, and the rule finds the boundary because the noise floor is a floor. This collection’s rank essay is about that case at length, and the figure above is it: six singular values sitting on each other at 10⁻¹⁴ and a jump of 8.2·10¹² above them.

An exact zero has no floor to sit on. There is no δ setting the scale, because there is no perturbation, and what a decomposition returns instead is whatever falls out of the last few operations on quantities that cancelled completely. Those results carry no common magnitude at all, which is why they arrive spread over a hundred and fifty orders. The gap rule needs the small singular values to be wrong by a consistent amount, and here they are right.

That inverts the usual reading of exactness. An exact rank deficiency is normally the easy case, the one an exact route is brought in to certify. For this rule it is the hard case, and the harder the deficiency is — more constraints, deeper cancellation — the worse it gets.

What being right costs the other rule #

The threshold rule is right five hundred times out of five hundred here and it would be a mistake to read that as a recommendation without reading its margins.

Its cut sits at n·σ₁·ε, between 2.51·10⁻¹⁵ and 1.78·10⁻¹⁴ across the sweep. Above it, the smallest genuinely nonzero singular value clears the cut by a factor of at least 1.1·10¹³ on every one of the five hundred pencils. Below it, the largest mathematically zero singular value is under the cut by a factor of at least 17. Seventeen, not 10¹³. The rule is right at every pencil here and its margin on the side that matters is four orders of magnitude smaller than a reader looking at the figures would guess.

And its failure point is still a number somebody typed. Give these pencils entries that have been through a floating-point assembly and the null-space singular values lift to wherever the assembly’s rounding puts them; the threshold fails as soon as that exceeds n·σ₁·ε, and where that happens is a fact about the constant, not about the matrix. That is the whole objection to thresholds, it is correct, and it survives everything measured here. The finding is narrower and it is not that thresholds are good: the gap rule’s advantage is real under perturbation and it is not an advantage at ε = 0, where the rule is worse than the constant it was supposed to replace.

There is a rule that is right on all five hundred and it is barely a change. Take the largest gap, but only among positions whose upper singular value is above n·σ₁·ε — never form a ratio whose numerator is already judged to be zero. That is 500 of 500, and it fixes the failures for the reason they happen: it forbids the rule from looking for a boundary inside the null space. The threshold has not gone away, it has been demoted from deciding the rank to bounding where the search may look, and the gap still reports the evidence.

What follows for anything that counts a rank #

Print where the gap fell, not only how large it was. The size of the largest ratio is what gets reported and it is the less informative half; a gap of 10¹⁴⁰ at the wrong position is a confident wrong answer, and the position is what a caller can check against a constraint count known from the modelling side. This site’s habit of printing the quantity that decided something beside the thing it decided is the whole of the fix.

Do not trust an exact deficiency to be the easy case. Integer entries make the reference answer available and they do not make the float route safe. That is the opposite of the usual trade, where an exact answer to a measured problem is exact about a matrix nobody asked about; here the exact route is right and the float route reads a matrix that is genuinely rank-deficient and gets it wrong.

A rank over the integers and a rank over the reals are two different questions. They are, and the rank depends on the ring makes that case for a single matrix. What is added here is that a third number exists — the rank a floating-point rule reports — and it can disagree with both while every input is exact.

A cheap surrogate for a singular value inherits this. The cheap rank reads a rank off the diagonal of a pivoted factorisation rather than off a decomposition, and the same reasoning applies to any gap taken in those numbers: whether the small ones cluster is a question about the arithmetic, not about the matrix.

And the decision is the same decision wherever it appears. Whether a computed quantity has arrived at zero is its own question, and the answer here is that a quantity that is exactly zero can be harder to recognise than one that is nearly zero, which is not what the distinction between a structural zero and a small number leads a reader to expect.

Where the axis ends, and the refusal #

The comparison stops at n = 8 for a reason that belongs to the reference rather than to the claim. The exact degree comes from a determinant in BigInt rationals, whose numerators and denominators roughly double in length at every elimination step, so an eight-by-eight pencil is comfortable and a sixty-by-sixty one is not. Every number here is therefore measured at a size where an exact answer exists, and the rule being scored is the same rule at any size — a rank decision on an eight-by-eight is made the same way as one on an eight-thousand-by-eight-thousand, which is what makes a small exact example worth anything.

The other end of the axis is refused outright. A pencil with no constraints has no infinite eigenvalues, no rank deficiency and no null block, and both rules are then trivially right about a matrix that never posed the question. Drawing that case would make the comparison look like a comparison of two adequate rules, so the figure is fed a pencil with zero constraints and required to decline it. The essay’s own axis begins at one constraint, where the gap rule cannot fail, and the argument is what happens at two — which is a claim about the middle of a range and has to be stated without the ends propping it up.

That leaves the pencil field with three readings of one object and a consistent moral. The pencil itself is not the one-matrix problem with a change of variables. Its infinite eigenvalues are the model’s constraints rather than a breakdown. And a pencil whose determinant vanishes identically has no answer at all while a solver returns n numbers with small residuals. In each case a floating-point routine returns something plausible about a question whose exact answer is an integer, and in each case the only way to know is to have computed the integer.