Numerical Linear Algebra
where the algebra stops being the arithmetic
Eigenvalues, singular values, rank

An eigenvalue with no value

If the second matrix of a pencil is singular then some of the eigenvalues are infinite, and that is not a degeneracy — it is the algebraic constraints of the model, one per constraint. What survives is a pair of numbers rather than one, and on the line those pairs live on, infinity is an ordinary point with an ordinary residual.
29 min read 23 figures Where the algebra stops being the arithmeticExact ground truthTwo routes to a numberMeasured, not asserted

Worth reading first: Two matrices and one problem · Rank is a decision · The number that decides nothing.

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.

The eigenvalues of a 6×6 pencil with 2 algebraic constraints, on the projective lineλ = α/β is a ratio, so an eigenvalue of a pencil is a direction rather than a number and it lives on a line whose two ends are the same point. Drawn as an angle φ = arctan λ, the 4 finite eigenvalues — -0.3769, 0.565, 4.383, 6.428 — sit inside the arc, and the 2 infinite ones sit at its ends, which is one point and not two. Nothing about them is degenerate: each carries a residual ‖βAx − αBx‖ in the same scaling as every other, the largest being 5.53·10⁻¹⁴, and an infinite eigenvalue's residual is ‖Bx‖/‖B‖ — the statement that its eigenvector is a null vector of B. The count is not a rank decision here: it is n minus the degree of det(A − λB), computed in exact rational arithmetic.λ = 0λ = ∞λ = ∞-0.37690.5654.3836.4282 eigenvalues here, and it is one placecounted exactly, in rationalsfinite eigenvalues4at infinity2degree of det(A − λB)4worst residual, either kind5.5·10⁻¹⁴an eigenvalue is a ratioand a ratio has a direction, not a size
Fig. 1 Six eigenvalues of a 6×6 pencil, drawn where they live. Four are inside the arc and two are at its ends, which are one point and not two.

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 eigenvalues of a 6×6 pencil with 0 algebraic constraints, on the projective lineλ = α/β is a ratio, so an eigenvalue of a pencil is a direction rather than a number and it lives on a line whose two ends are the same point. Drawn as an angle φ = arctan λ, the 6 finite eigenvalues — -0.7663, -0.01384, 0.9593, 4.611, 5.61, 7.6 — sit inside the arc, and the 0 infinite ones sit at its ends, which is one point and not two. Nothing about them is degenerate: each carries a residual ‖βAx − αBx‖ in the same scaling as every other, the largest being 8.9·10⁻¹⁵, and an infinite eigenvalue's residual is ‖Bx‖/‖B‖ — the statement that its eigenvector is a null vector of B. The count is not a rank decision here: it is n minus the degree of det(A − λB), computed in exact rational arithmetic.λ = 0λ = ∞λ = ∞-0.7663-0.013840.95934.6115.617.6no constraints: B is nonsingular and nothing is at the polescounted exactly, in rationalsfinite eigenvalues6at infinity0degree of det(A − λB)6worst residual, either kind8.9·10⁻¹⁵an eigenvalue is a ratioand a ratio has a direction, not a size
Fig. 2 With no constraints, B is nonsingular and nothing is at the poles: an ordinary spectrum.
The eigenvalues of a 6×6 pencil with 4 algebraic constraints, on the projective lineλ = α/β is a ratio, so an eigenvalue of a pencil is a direction rather than a number and it lives on a line whose two ends are the same point. Drawn as an angle φ = arctan λ, the 2 finite eigenvalues — 0.4384, 4.562 — sit inside the arc, and the 4 infinite ones sit at its ends, which is one point and not two. Nothing about them is degenerate: each carries a residual ‖βAx − αBx‖ in the same scaling as every other, the largest being 1.55·10⁻¹⁵, and an infinite eigenvalue's residual is ‖Bx‖/‖B‖ — the statement that its eigenvector is a null vector of B. The count is not a rank decision here: it is n minus the degree of det(A − λB), computed in exact rational arithmetic.λ = 0λ = ∞λ = ∞0.43844.5624 eigenvalues here, and it is one placecounted exactly, in rationalsfinite eigenvalues2at infinity4degree of det(A − λB)2worst residual, either kind1.5·10⁻¹⁵an eigenvalue is a ratioand a ratio has a direction, not a size
Fig. 3 And with four, most of the eigenvalues are at infinity — a model that is mostly constraints, which is what a high-index differential-algebraic system looks like.

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.

Where each norm works, for a vector of 8Four horizontal rows, one per format. Each carries a pale bar for the format's whole range, a bar above it for the scaled norm and a shorter bar below it for the naive one.-47-37-27-17-7313233301234log₁₀ of the vector's normfp1611 bitsbfloat168 bitstf3211 bitsbinary3224 bitspale: the format's range · blue: √(Σ(xᵢ/m)²)·m · red: √(Σxᵢ²)fp16 and tf32 have the same eleven significand bitsand their bars do not overlap
Fig. 4 What the division costs when it is done anyway, in the arithmetic field’s terms: a quantity that overflows before it is a quantity.
A 16-bit budget, split between range and precisionTwo curves against the width of the exponent field. One rises steeply and one falls in a straight line. Vertical lines mark the splits real hardware formats use.3456789101100.250.50.751bits in the exponent fieldeach curve as a fraction of its own maximumbfloat16fp16rangeprecisionto 617 decadesto 3.9 digitswhat the split buysbfloat16: largest number3.4·10³⁸fp16: largest number6.6·10⁴a bit of exponent doubles the rangea bit of significand adds a third of a digit
Fig. 5 And the format that has to hold it. There is no representable number that means “the answer is a direction with no length”.

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.

QᵀQ from classical Gram–Schmidt and from Householder on the 8×8 Hilbert matrixTwo eight-by-eight tables of QᵀQ. The upper one has ones on the diagonal and entries as large as one off it; the lower one is the identity to three decimal places everywhere.A = H8 · κ = 1.5·10¹⁰ · both factorisations reconstruct A to 6·10⁻¹⁷the diagonal is 1 in both — every column is a unit vector either way1.000000000001.000000000001.000000000001.000000000001.00000.002-0.002000001.0000.125-0.13300000.0020.1251.000-1.0000000-0.002-0.133-1.0001.000classical Gram–Schmidt1.000000000001.000000000001.000000000001.000000000001.000000000001.000000000001.000000000001.000Householderclassical ‖QᵀQ − I‖1.4Householder ‖QᵀQ − I‖1.4·10⁻¹⁵largest off-diagonal 1 against 3.1·10⁻¹⁶length is not angle
Fig. 6 The habit the badge comes from: a claim about a factorisation turned into a number that could be wrong.

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; 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.

The singular values of B, and the number of infinite eigenvalues the exact polynomial says there areThe pencil has 2 algebraic constraints, so 2 of its 6 eigenvalues are infinite. Two routes say so and they are not the same kind of statement. The exact route computes det(A − λB) in BigInt rationals and finds it has degree 4, so n − 4 = 2 eigenvalues are at infinity — an integer, arrived at without rounding. The float route counts the singular values of B below a cut, and the values run 4.27, 2.6, 0.918, 0.416, 1.13·10⁻¹⁶, 4.1·10⁻¹⁵⁷: the gap is a factor of 2.75·10¹⁴⁰ and it falls in the right place, so the decision is comfortable here. It is still a decision, and it is the same decision this site's rank essay is about.σ14.27σ22.6σ30.918σ40.416σ51.13·10⁻¹⁶σ610⁻¹⁸n = 6, and det(A − λB) has degree 4an integer, and a judgementdegree of det(A − λB), exactly4infinite eigenvalues, from the degree2singular values below the cut2largest gap in the spectrum2.7·10¹⁴⁰a degree cannot be nearly threeand a singular value can be nearly zero
Fig. 7 The two routes side by side. The bar chart is the float route — the singular values of B, with a cut — and the caption carries the integer the exact route returns.

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 singular values of B, and the number of infinite eigenvalues the exact polynomial says there areThe pencil has 1 algebraic constraint, so 1 of its 6 eigenvalues are infinite. Two routes say so and they are not the same kind of statement. The exact route computes det(A − λB) in BigInt rationals and finds it has degree 5, so n − 5 = 1 eigenvalues are at infinity — an integer, arrived at without rounding. The float route counts the singular values of B below a cut, and the values run 3.25, 2.36, 1.04, 0.835, 0.3, 5.4·10⁻¹⁵⁸: the gap is a factor of 5.55·10¹⁵⁶ and it falls in the right place, so the decision is comfortable here. It is still a decision, and it is the same decision this site's rank essay is about.σ13.25σ22.36σ31.04σ40.835σ50.3σ610⁻¹⁸n = 6, and det(A − λB) has degree 5an integer, and a judgementdegree of det(A − λB), exactly5infinite eigenvalues, from the degree1singular values below the cut1largest gap in the spectrum5.6·10¹⁵⁶a degree cannot be nearly threeand a singular value can be nearly zero
Fig. 8 One constraint, one degree short, one singular value at the floor.
The singular values of B, and the number of infinite eigenvalues the exact polynomial says there areThe pencil has 4 algebraic constraints, so 4 of its 6 eigenvalues are infinite. Two routes say so and they are not the same kind of statement. The exact route computes det(A − λB) in BigInt rationals and finds it has degree 2, so n − 2 = 4 eigenvalues are at infinity — an integer, arrived at without rounding. The float route counts the singular values of B below a cut, and the values run 3.16, 1, 4.28·10⁻¹⁷, 0, 0, 0: the gap is a factor of −∞ and it falls in the right place, so the decision is comfortable here. It is still a decision, and it is the same decision this site's rank essay is about.σ13.16σ21σ34.28·10⁻¹⁷σ410⁻¹⁸σ510⁻¹⁸σ610⁻¹⁸n = 6, and det(A − λB) has degree 2an integer, and a judgementdegree of det(A − λB), exactly2infinite eigenvalues, from the degree4singular values below the cut4largest gap in the spectrum−∞a degree cannot be nearly threeand a singular value can be nearly zero
Fig. 9 And four. The gap in the spectrum of B moves with the count, and so does the degree.

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.

Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 10 The decision in its original setting: a spectrum, a noise level, and a gap that shrinks in proportion so a fact can be watched turning into an opinion.
A randomised rank-k solve, 4 seeds a rankRelative error against the rank kept, on a logarithmic vertical axis, with a vertical bar at each rank spanning the seeds. The band is 1.68 wide at rank 8, where the method is at its worst, and 1.004 wide at rank 20, where it is at its best. The same computation on the same data returns a different answer each time.0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.7spread at rank 201best median error0.15widest where the method is worstand the bound does not say so
Fig. 11 And the band around it, which is what the decision looks like when the evidence is weighed rather than thresholded.

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 nothing says where.

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.

How far |r_nn| sits above σ_min on Kahan's matrix, against the size and the parameter3 curves of |r_nn| ÷ σ_min against n, one per Kahan parameter. Every curve rises without turning over, reaching 7·10⁴ at n = 30, c = 0.5. Column pivoting makes no interchange at any point on any of them, so the failure is not a poor choice — there is nothing to choose.813182328110¹10²10³10⁴10⁵10⁶size of the matrix|r_nn| ÷ σ_minthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 307·10⁴interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row
Fig. 12 The matrix that makes the cheap verdict wrong, from the essay on rank-revealing factorisations: a gap that is not where a cheaper method says it is.

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 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.

Where 24 perturbations of size 10⁻¹⁰ put the eigenvalues of two 6×6 matrices with the same spectrumTwo clouds of eigenvalues in the complex plane. Both matrices have every eigenvalue at 0.8 exactly; both were perturbed by the same 24 random matrices of norm 10⁻¹⁰. The normal matrix's eigenvalues stay within 7.43·10⁻¹¹ of where they were — the size of the perturbation — and the bidiagonal's spread out to 0.0325, a factor of 4.4·10⁸ further on the same data.100.1750.35real partimaginary part0.8bidiagonalnormalone spectrum, two matricesthe perturbation10⁻¹⁰normal, furthest moved7.4·10⁻¹¹bidiagonal, furthest0.033ratio4.4·10⁸the two matrices have identical eigenvaluesand one of them says so under perturbation
Fig. 13 The one-matrix version of eigenvalue sensitivity, from the essay that measured it: how far a spectrum moves under a perturbation, and which part of it moves most.

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. 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 a repeated eigenvalue without one are different objects, and the difference is invisible in the list of eigenvalues.

Three perturbations of 10⁻¹⁴, three eigenvectors, one planeA circle with three radii at widely different angles, one for each perturbation, and a table of their residuals showing all three satisfy the eigenvalue equation.every radius is an eigenvectorseed 11: 2.0°seed 23: 60.5°seed 41: 18.2°none of them is wrongspread of the returned angles1spread of the returned planes1.3·10⁻¹⁵worst ‖Ax − λx‖5·10⁻¹⁵an exactly repeated eigenvalueno correct answer to fail to return
Fig. 14 The one-matrix version: a double eigenvalue with only one eigenvector, and what that does to everything downstream of it.
The six largest Ritz values, against a doubled eigenvalue at 10Distance from 10 for each of the six largest Ritz values, on a logarithmic vertical axis. The single-vector run of 16 steps has one value at 10 to 2.6·10⁻¹² and its second is 1.696 away — it has found the eigenvalue once. The block of two has two values at 10, to 1.1·10⁻⁹ and 4.7·10⁻⁹.12345610⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹Ritz value, largest firstdistance from 10one vectora block of twoa space, not a ratecopies found, one vector1copies found, block of two2Krylov dimension, one vector16the second copy is not in the spaceat any number of steps
Fig. 15 And why a block method is the only thing that sees a repeated eigenvalue at all.

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.

The arrowhead matrix, eliminated from each endThree sparsity plots. The first shows an arrowhead matrix with a dense first row and column. The second shows its Cholesky factor, completely dense. The third shows the factor obtained after moving the dense row to the end, which has no fill at all.the matrix43 entriestip eliminated first253 entriestip eliminated last43 entries‖A − LLᵀ‖/‖A‖, tip first1.4·10⁻¹⁶‖A − LLᵀ‖/‖A‖, tip last0dense factor is n(n+1)/2 = 253 · sparse factor is 2n − 1 = 43one row swapped to the endnothing numerical chose between them
Fig. 16 One of the structured objects that comes out of the third of those, from the sparsity field: a constraint block coupling everything it touches.
Two penalties on the same problem, against the offset in the signalBest relative error for each penalty at four offsets. With no offset the two are within 1% of each other. At an offset of 10 the derivative penalty is 1.95 times better, because a constant lies in its null space and costs it nothing, while the norm penalty pays for the whole offset at every λ.best relative error at each offset‖x‖, offset 00.1906‖L₁x‖, offset 00.1880‖x‖, offset 20.0552‖L₁x‖, offset 20.0516‖x‖, offset 50.0310‖L₁x‖, offset 50.0241‖x‖, offset 100.0248‖L₁x‖, offset 100.0127what the null space buysadvantage at offset 01advantage at offset 21.1advantage at offset 51.3advantage at offset 101.9the norm penalty pays for a constantthe derivative penalty does not
Fig. 17 And the standard alternative to solving with the constraint at all — pushing it into the objective with a penalty, and the null space that leaves behind.

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.

The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 18 The same argument in the form this site opened with: a class of problems whose answer is known, so that the error of every other route is measured rather than estimated.
log₁₀|det H_n| by three routes, to n = 20The exact rational determinant of the Hilbert matrix falls to 10^-225 at n = 20. The accumulated logarithm of the pivots follows it to n = 13 and then departs, reaching 10^-195 — wrong by 31 orders of magnitude and still an ordinary-looking number. The product of the pivots is a separate curve that ends at n = 20, where it underflows to exactly zero.25811141720-250-200-150-100-500nlog₁₀|det H_n|exact rationalΣ log|u_ii|Π u_iithree routes, one theoremexact at the largest n-225accumulated logarithm-195decades of disagreement31smallest pivot at that n5.6·10⁻¹⁷every pivot is a normal numberat every size on this axis
Fig. 19 And the warning that goes with it, from the determinant essays: an exact route is not automatically a usable one, and the quantity here is not the determinant but its degree.

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 coefficient matrix of AX + XB = C against the answer, to n = 20At n = 20 the unknown X has 400 entries and the coefficient matrix of the linear map has 1.6·10⁵ — 0.00 gigabytes of doubles. Eliminating it costs 4.27·10⁷ operations against the 4.8·10⁵ Bartels and Stewart's algorithm needs, a ratio of 89. The Kronecker form is what the equation means and it is not a method.10¹10¹10³10⁵10⁷10⁹10¹¹nentries, and operationsKronecker flopsits entriesBartels–Stewartentries in Xat n = 20unknowns400coefficient entries1.6·10⁵gigabytes of doubles0.0013flop ratio89the equation is linear in Xand nobody writes down its matrix
Fig. 20 The other place on this site where the object being reasoned about is far larger than the answer, and where nobody forms it.

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.

The same three schemes on a problem with no layer in itWorst nodal error against the grid size, both axes logarithmic, for a manufactured smooth solution on the identical operator at ε = 0.001. Adding no diffusion gives 0.0016, 4·10⁻⁴, 10⁻⁴, falling by four at each refinement. The tuned diffusion gives 0.092, 0.043, 0.018 — 57 times worse at the coarsest grid, and falling more slowly.10²10⁻⁴10⁻³10⁻²10⁻¹grid points nworst nodal errorupwindtunedcentralthe same tuning, another problemtuned ÷ central at n = 3157tuned ÷ central at n = 127182central's error at the finest grid10⁻⁴exact on the problem it was derived fromand harmful on the one beside it
Fig. 21 The general form: a computation that is entirely correct about a problem that was not posed.
The eigenvalues of a 6×6 pencil with 1 algebraic constraints, on the projective lineλ = α/β is a ratio, so an eigenvalue of a pencil is a direction rather than a number and it lives on a line whose two ends are the same point. Drawn as an angle φ = arctan λ, the 5 finite eigenvalues — -0.3786, 0.08367, 3.102, 4.705, 6.487 — sit inside the arc, and the 1 infinite ones sit at its ends, which is one point and not two. Nothing about them is degenerate: each carries a residual ‖βAx − αBx‖ in the same scaling as every other, the largest being 1.42·10⁻¹³, and an infinite eigenvalue's residual is ‖Bx‖/‖B‖ — the statement that its eigenvector is a null vector of B. The count is not a rank decision here: it is n minus the degree of det(A − λB), computed in exact rational arithmetic.λ = 0λ = ∞λ = ∞-0.37860.083673.1024.7056.4871 eigenvalue here, and it is one placecounted exactly, in rationalsfinite eigenvalues5at infinity1degree of det(A − λB)5worst residual, either kind1.4·10⁻¹³an eigenvalue is a ratioand a ratio has a direction, not a size
Fig. 22 One constraint, one eigenvalue at the pole, and five inside the arc.
The eigenvalues of a 6×6 pencil with 3 algebraic constraints, on the projective lineλ = α/β is a ratio, so an eigenvalue of a pencil is a direction rather than a number and it lives on a line whose two ends are the same point. Drawn as an angle φ = arctan λ, the 3 finite eigenvalues — -0.04892, 4.357, 4.692 — sit inside the arc, and the 3 infinite ones sit at its ends, which is one point and not two. Nothing about them is degenerate: each carries a residual ‖βAx − αBx‖ in the same scaling as every other, the largest being 1.28·10⁻¹⁴, and an infinite eigenvalue's residual is ‖Bx‖/‖B‖ — the statement that its eigenvector is a null vector of B. The count is not a rank decision here: it is n minus the degree of det(A − λB), computed in exact rational arithmetic.λ = 0λ = ∞λ = ∞-0.048924.3574.6923 eigenvalues here, and it is one placecounted exactly, in rationalsfinite eigenvalues3at infinity3degree of det(A − λB)3worst residual, either kind1.3·10⁻¹⁴an eigenvalue is a ratioand a ratio has a direction, not a size
Fig. 23 And three, where half the model is constraint.

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.

Where this goes next

10¹10⁴10⁷10¹⁰10¹³10¹⁶10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ(B)relative error, and asymmetryvia B⁻¹Avia Choleskyasymmetry of B⁻¹Au · κ(B)against a spectrum known exactlyslope, via B⁻¹A0.92slope, via Cholesky0.98worst ratio between them2.3asymmetry of B⁻¹A1.1the symmetry claim is trueand it is not about the accuracy Two matrices and one problem Ax = λBx is what a finite element model, a structural vibration and a constrained optimisation actually produce, and it is not the one-matrix problem with a change of variables. Everybody is told not to form B⁻¹A because it is not symmetric. That is true, the departure from symmetry is about one, and it is not what decides the accuracy. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap. does this matrix look nearly singular?green: the test agrees with the truth · red: it does not · the bar under each number is its magnitude, over sixty-two decades|det A||det A|^(1/n)σ_min1/κ = σ_min/σ_max0.1·I at n = 40perfectly conditioned10⁻⁴⁰0.10.11κ = 10¹⁰, |det| = 1nearly singular1110·10⁻⁶10·10⁻¹¹Hilbert at n = 8nearly singular2.7·10⁻³³8.5·10⁻⁵1.1·10⁻¹⁰6.6·10⁻¹¹the two counterexamplesκ of the scaled identity1its determinant10⁻⁴⁰κ of the normalised matrix10¹⁰its determinant1det(cA) = cⁿ det(A)so a determinant carries the units n times over The number that decides nothing The determinant is the first scalar anybody attaches to a matrix and the last one worth consulting. A tenth of the identity has a determinant of 10⁻⁶⁰ and a condition number of exactly one. The Hilbert matrix's determinant stops being right at n = 13 and stops being a number at n = 29, and nothing in between reports either.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Descriptor systemDeterminantExact arithmeticGeneralised eigenvalue problemInfinite eigenvalueMatrix pencilNumerical rankProjective lineSingular values