An eigenvalue with no value

The eigenvalues of a pencil are the roots of det(A − λB). That polynomial has degree at most n, and the reason it is at most rather than exactly is the subject of this essay.

The coefficient of λⁿ is det(−B). If B is nonsingular, the polynomial has degree n and there are n finite eigenvalues. If B is singular, that coefficient is zero, the degree drops, and the missing roots have gone somewhere — they have gone to infinity, and going to infinity is not a way of disappearing.

Where they come from, which is a model rather than an accident #

The clearest case is a system of differential equations with constraints in it.

E ẋ = A x

with E singular. Some rows of E are zero, and the corresponding equations have no derivative in them at all: they are algebraic constraints, not differential ones. That is a descriptor system, or a differential-algebraic equation, and the number of infinite eigenvalues of the pencil (A, E) is the number of constraints.

Nothing about it is degenerate. A robot arm with a closed kinematic loop, a circuit with an ideal voltage source, an incompressible flow, an optimisation with equality constraints — all of them produce exactly this, and the infinite eigenvalues are the constraints saying that the system does not have a dynamic mode there. Filtering them out as noise is filtering out the part of the model that says the answer lies on a surface — the same mistake as reading a number that decides nothing as though it decided something, run the other way round.

Why the answer is a pair #

The trouble with saying that λ is infinite is that a program has to hold it in a variable.

The repair is to stop dividing. An eigenvalue of a pencil is a pair (α, β), not a number, and the equation it satisfies is

β A x = α B x .

When β ≠ 0 this is Ax = (α/β)Bx and λ = α/β is the ordinary eigenvalue. When β = 0 it is Bx = 0, which says x is a null vector of B — a perfectly ordinary statement about a perfectly ordinary vector.

The pair is only defined up to scale, so it is normalised: α² + β² = 1. What that makes each eigenvalue is a direction rather than a magnitude, and the space of directions in a plane is a circle with opposite points identified — the projective line. The figure at the top of this essay draws it: λ = arctan of the angle, zero at the top, positive to the right, negative to the left, and infinity at both ends of the arc, which are the same place.

This is the whole reason libraries return α and β separately. LAPACK’s generalised eigenvalue routines have returned alphar, alphai and beta since they were written, and every caller who has divided them without checking has produced a division by zero for a reason the model put there deliberately. Whether that zero has in fact arrived is its own decision, and it is the same decision the rank route below has to make.

And the residual is the same residual #

The rule this site is named for says no decomposition is drawn without its residual printed, and the pair makes that possible for infinite eigenvalues as easily as for finite ones. The natural quantity is

‖βAx − αBx‖ ⁄ (|β|‖A‖ + |α|‖B‖)‖x‖

which for β = 0 is ‖Bx‖/‖B‖‖x‖ — exactly the statement that x is a null vector of B, and exactly the number a rank computation would report about it.

Measured on the hero’s pencil, the worst residual over all six eigenvalues, finite and infinite together, is 5.5·10⁻¹⁴. There is no separate handling and no special case. An infinite eigenvalue is a well-conditioned, accurately computed, ordinary answer.

Counting them exactly #

Here is where the pencil gives this collection something it has not had on the eigenvalue problem: an exact route.

det(A − λB) is a polynomial whose coefficients are polynomial functions of the entries. For an integer or rational pencil that means it can be computed with nothing rounded anywhere: evaluate the determinant in BigInt rationals at n + 1 integer points, and interpolate. Evaluating is this site’s existing exact determinant — the same route a spanning-tree count takes to an integer known in advance to be one — and interpolating is Lagrange in the same rationals. The degree that comes back is an integer, arrived at without a single rounding.

And the number of infinite eigenvalues is n minus that degree.

On descriptor pencils with k = 0, 1, 2 and 3 constraints, the degree comes back at exactly n − k every time. That is not a tautology: the pencils are built in semi-explicit form and then multiplied on both sides by unimodular integer matrices, which changes nothing about the pencil and destroys every visible trace of the structure. The matrices that go into the exact determinant have no zero rows and nothing about them says what the answer will be.

The count is the arithmetic, not an inference from it. Walking k from none to nearly all, the finite count runs 6, 5, 4, 3 and 1 while the degree runs 6, 5, 4, 3 and 1 — the same integer both times, at every stop, with the infinite count making up the difference to six exactly.

The pattern is arithmetic and holds at every stop: six eigenvalues throughout, one moving from finite to infinite with each constraint added, and the degree of the determinant equal to the number still finite. Nothing is lost as constraints accumulate — the count is conserved, and only its distribution between the finite plane and infinity changes.

The residuals say the same thing from the floating-point side and are worth reading beside it. The worst residual across those five pencils is 8.9·10⁻¹⁵, 1.42·10⁻¹³, 5.53·10⁻¹⁴, 1.28·10⁻¹⁴ and 1.93·10⁻¹⁷ — no trend, no degradation as the infinite eigenvalues take over, and the largest of them at k = 1 rather than at k = 5. So the finite eigenvalues are not being harmed by the infinite ones; the pencil with five eigenvalues at infinity computes its one finite eigenvalue better than the pencil with none computes its six. That is the opposite of what “the problem is nearly singular” would suggest, and it is the reason the pair (α, β) is the right object: nothing in the computation ever forms the ratio that would be infinite.

And counting them the way a library has to #

The exact route needs exact entries. A stiffness matrix assembled from measured material properties does not have them, and neither does anything that has been through a floating-point assembly.

So the float route counts the singular values of B that are judged to be zero. That is a rank decision, and this collection already has an essay saying at length that rank is a decision rather than a property — that a floating-point matrix does not have a rank, it has a spectrum of singular values and a place somebody chose to cut.

On the constructed pencils above the decision is comfortable to the point of being no decision at all. The singular values of B fall 4.3, 2.6, 0.92, 0.42, 1.1·10⁻¹⁶ — and the sixth is below 10⁻¹⁵⁰, because the entries are integers and the rank deficiency is exact. The gap is fifteen orders and it falls exactly where the polynomial’s degree says it should.

That is the easy case, and it is easy for a reason worth naming: the matrix came from integers. Give the same pencil entries that have been through a floating-point assembly and the two zero singular values lift off the floor to wherever the assembly’s rounding puts them — 10⁻⁹, say, on a badly scaled model — and the gap closes from fifteen orders to eight. It is still a comfortable decision at eight. It stops being one somewhere, and where depends entirely on which rule is being used.

Where it stops, for each of the two rules #

Perturb B by ε‖B‖ and ask each rule for the count, twelve draws at each of seventeen sizes of ε:

                    fixed threshold τ = 10⁻¹⁰      largest gap
k = 1  first wrong at     10⁻⁹                      4.0·10⁻²
k = 2  first wrong at     10⁻¹⁰                     1.0·10⁻²
k = 3  first wrong at     10⁻¹⁰                     1.0·10⁻²

The fixed threshold fails exactly where it was told to. That is not a measurement of the pencil; τ was placed at 10⁻¹⁰ and the rule stops working when the perturbation reaches 10⁻¹⁰, on every pencil here and on every pencil anywhere. A rule whose failure point is a number somebody typed is not reporting anything about the matrix.

The largest-gap rule fails at a perturbation of one to four per cent of ‖B‖ — eight orders further — and its failure point is a property of the pencil, because it is where the lifted singular values stop being distinguishable from the genuine ones.

The failure runs in both directions, and the mechanism is the interesting part. A perturbation of size ε lifts the k zero singular values to values near ε that are themselves spread over orders: three random near-zero singular values routinely differ by a factor of a hundred. So the largest gap can land inside the lifted cluster, splitting it. At k = 2 and ε = 10⁻², ten of forty draws report one infinite eigenvalue where there are two, and every failure is in that direction. Push ε further and the lifted cluster reaches the genuine singular values, the gap lands inside those, and the rule overcounts: at k = 1 and ε = 10⁻¹, eighteen of forty report two, three or four.

So the practical advice has a shape. Use the gap rather than a threshold, because it buys eight orders and because it is answering a question about the matrix. Then read what it did rather than only its answer: the size of the largest gap says how far the decision is from the next-best one, and a largest gap of 10 is a decision that the next per cent of perturbation will reverse.

What is worth carrying is what happens when they stop agreeing, and it is a specific and unpleasant failure. The count of infinite eigenvalues is an integer, and a rank decision that is off by one changes it by a whole eigenvalue. Not by a digit — by an eigenvalue. A pencil judged to have two infinite eigenvalues when it has three has one spurious finite eigenvalue in its output, at a value that is the ratio of two quantities that are both rounding error, and there is nothing about its residual that says so.

The count is not stable and the pencil is #

One more thing follows from the count being an integer, and it is the reassuring half.

An infinite eigenvalue is not sensitive. Perturb B by ε and its exactly-zero singular values become O(ε), so the eigenvalues that were at infinity move to about 1/ε — enormous, finite, and utterly different from infinity as numbers. As directions they have moved by about ε, which is nothing.

That is the second reason for the pair. On the projective line the perturbation of an infinite eigenvalue is a small perturbation; on the real line it is a jump from infinity to 10⁸ — the same distinction between a quantity and the coordinate it is written in that a condition number scaling cannot move turns on. The representation that makes the answer stable is the same representation that makes it storable, and neither of those is a coincidence — both are the observation that λ was never a number.

The measured version: the eigenvalues drawn in the hero at k = 2 sit at the poles, and a perturbation of the pencil by 10⁻⁹ moves them along the arc by about 10⁻⁹. Their values have gone from infinite to around 10⁹, which is a change of infinite size in the only variable a caller usually looks at.

Which is why the index matters #

There is a second number that comes with all of this and it is worth a paragraph even though it is not something this essay measures.

The infinite eigenvalues of a pencil come with a structure — a Jordan structure at infinity — and its size is the index of the descriptor system. Index one means the constraints are algebraic and nothing worse; index two or three means the numerical solution of the differential-algebraic system needs to differentiate the constraints, and the sensitivity of the answer to perturbations grows with each differentiation.

A count of infinite eigenvalues does not give the index; the count is the total multiplicity and the index is the largest block — the same gap between a number and the structure behind it that deciding that a zero has arrived opens for a single matrix. Two pencils with three infinite eigenvalues each can be an index-one system with three constraints or an index-three system with one, and they behave completely differently.

That is the same distinction this collection drew on the one-matrix problem: a repeated eigenvalue with a full set of eigenvectors and one without are different objects, and the difference is invisible in the list of eigenvalues.

What the constraints are, in the three models #

It is worth naming what the infinite eigenvalues are in three settings, because “algebraic constraint” is abstract and the three concrete forms are recognisable.

In a mechanism, they are the joints. A closed kinematic chain has more coordinates than degrees of freedom, and the extra coordinates are tied together by equations with no derivative in them. The count of infinite eigenvalues is the count of independent constraint equations, which is the number the modeller subtracted to get the degrees of freedom in the first place.

In a circuit, they are the ideal elements. A voltage source fixes a node voltage algebraically; a capacitor loop or an inductor cutset produces a constraint among currents. The modified nodal analysis matrix pencil has one infinite eigenvalue per such relation, and circuit simulators have detected and deflated them since the 1970s under the name “index reduction”.

In an incompressible flow, they are the pressure. The continuity equation has no time derivative in it, so the pressure is not a state — it is whatever makes the velocity divergence-free at each instant. Every pressure degree of freedom is an infinite eigenvalue of the pencil, which is why saddle-point solvers are their own subject.

In all three the count is known before any matrix is assembled, which makes it one of the rare numerical quantities with an independent check available from the modelling side. A computed count that disagrees with the constraint count is evidence of an assembly error, and it is evidence that costs a rank decision to obtain.

Two routes, and one of them cannot be run #

The comparison in this essay is unusual for this collection in that the two routes are not equally available.

The exact route is more than a check on the float one — it is a different kind of statement. It returns an integer that no perturbation can move, computed from data that has not been rounded, and it can only be run when the entries are exact. The float route runs on anything and returns a judgement.

Where both are available they agree, which is what makes the second trustworthy on the problems where only it can be used. That is the whole argument for keeping an exact route on a site about floating point: not because anybody would compute this way at scale, but because a judgement that has never been checked against a fact is a judgement about which nothing is known.

And the exact route has a ceiling #

The exact determinant is exact and it is not free. Its cost grows with n, and its numbers grow faster than its operation count: the rationals that come out of an elimination on integer entries have numerators and denominators that roughly double in length at every step, so a 6×6 pencil is comfortable and a 60×60 one is not.

That is not a defect. It is the same trade this collection priced on the determinant itself, where an exact route to a scalar remained available long after the float routes had stopped being right — and where the exact route stopped being affordable long before the subject stopped being interesting.

What makes the ceiling tolerable here is that the quantity being checked is an integer that does not depend on the size of the problem. A rank decision on a 6×6 pencil and a rank decision on a 6000×6000 one are the same decision made in the same way, so a check that is only available at the small end is a check on the method rather than on any particular matrix. That is the strongest form of what a small exact example is for.

The refusal #

The assertion is fed an exact characteristic polynomial asked for on entries that are not integers.

The failure it prevents is the worst kind available to an exact method: rounding the entries, running the exact arithmetic on the rounded matrix, and returning an integer. The answer that comes back is exactly correct — about a pencil nobody asked about. Nothing downstream can tell, because the output of the routine is a degree, and a degree carries no evidence about the matrix it came from.

That is the general shape of what goes wrong with exactness used carelessly, and it is why the conversion refuses rather than rounds.

What is next #

Both essays so far have had a pencil with a well-defined answer, even when part of the answer was at infinity. The next one is about a pencil where det(A − λB) is identically zero — where every λ is an eigenvalue, the question has no content, and a solver handed a slightly perturbed version of it returns n numbers with small residuals, all of which change completely when the perturbation does.