Generator

The 14 eigenvalues of a saddle-point matrix with 10 unknowns and 4 constraints, inside their closed-form brackets

One function in the kkt library, called 32 times across 5 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 76 claims it put to the test while drawing them, and where it stands against the rule this site is named for.

At its defaults it draws the 14 eigenvalues of a saddle-point matrix with 10 unknowns and 4 constraints, inside their closed-form brackets. K = [[H, Aᵀ], [A, 0]] with κ(H) = 100 and κ(A) = 100. The shaded bands are the Rusten–Winther brackets, computed from four numbers — the extreme eigenvalues of H and the extreme singular values of A — before the matrix was assembled: negative eigenvalues in [-0.995, -10·10⁻⁵] and positive ones in [0.01, 1.62]. The marks are the computed spectrum. There are exactly 10 above zero and 4 below, which is Sylvester's law of inertia and not a property of this matrix: K is congruent to blkdiag(H, −AH⁻¹Aᵀ), both blocks are definite, and congruence preserves signs. The two groups are separated by a gap containing zero, at a ratio of 39.3 between the innermost positive eigenvalue and the innermost negative one.

saddle-inertia is one function in lib/figures/kkt.js — the matrix a constraint makes — an inertia known before assembly, and a failure with an address. Everything below came out of it during this build, at arguments taken from the essays rather than invented for this page. A figure here is the figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.

The 14 eigenvalues of a saddle-point matrix with 10 unknowns and 4 constraints, inside their closed-form bracketsK = [[H, Aᵀ], [A, 0]] with κ(H) = 100 and κ(A) = 100. The shaded bands are the Rusten–Winther brackets, computed from four numbers — the extreme eigenvalues of H and the extreme singular values of A — before the matrix was assembled: negative eigenvalues in [-0.995, -10·10⁻⁵] and positive ones in [0.01, 1.62]. The marks are the computed spectrum. There are exactly 10 above zero and 4 below, which is Sylvester's law of inertia and not a property of this matrix: K is congruent to blkdiag(H, −AH⁻¹Aᵀ), both blocks are definite, and congruence preserves signs. The two groups are separated by a gap containing zero, at a ratio of 39.3 between the innermost positive eigenvalue and the innermost negative one.-1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue4 negative10 positivecounted before it was formedpositive10negative4at zero0innermost ratio39the zero block is a theoremand so is the count either side of it

K = [[H, Aᵀ], [A, 0]] with κ(H) = 100 and κ(A) = 100. The shaded bands are the Rusten–Winther brackets, computed from four numbers — the extreme eigenvalues of H and the extreme singular values of A — before the matrix was assembled: negative eigenvalues in [-0.995, -10·10⁻⁵] and positive ones in [0.01, 1.62]. The marks are the computed spectrum. There are exactly 10 above zero and 4 below, which is Sylvester's law of inertia and not a property of this matrix: K is congruent to blkdiag(H, −AH⁻¹Aᵀ), both blocks are definite, and congruence preserves signs. The two groups are separated by a gap containing zero, at a ratio of 39.3 between the innermost positive eigenvalue and the innermost negative one.

show: "dependent-flip"

The arguments are the ones A constraint the count stops seeing passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Where an inertia count stops seeing a nearly dependent constraint, against the curvature along itFor a 10 × 4 saddle-point problem at a constrained minimum whose fourth constraint has singular value σ, the largest σ on a quarter-decade grid at which each route's count is first not (10, 4, 0), median of eight draws, against the curvature h of H along that constraint's weak direction, on logarithmic axes. The Bunch–Kaufman LDLᵀ count first fails at 1.8·10⁻¹¹ for h = -1·10⁻⁴, 1.8·10⁻¹⁰ for h = -0.01, 1.4·10⁻⁹ for h = -1, 1.8·10⁻⁸ for h = -100 — a fitted slope of 0.49 against |h|, with the dashed line of slope one half through the value at h = −1. The unpivoted elimination fails slightly higher. The count through an orthonormal null-space basis is right down to rounding, and a rank test at tolerance 10·u·‖A‖ drops the constraint only at 1.1·10⁻¹⁵.10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶|h|, the curvature of H along the weak directionσ at which the count is first wrong10⁻⁴10⁻³10⁻²10⁻¹110¹10²no interchangesLDLᵀ of Krank tolerancethrough Z: right to 10⁻¹⁶10 × 4, eight draws per curvatureh = -1·10⁻⁴: LDLᵀ first wrong at σ1.8·10⁻¹¹h = -0.01: LDLᵀ first wrong at σ1.8·10⁻¹⁰h = -1: LDLᵀ first wrong at σ1.4·10⁻⁹h = -100: LDLᵀ first wrong at σ1.8·10⁻⁸the pair's small eigenvalue is σ²/|h|the count loses it long before the rank does

For a 10 × 4 saddle-point problem at a constrained minimum whose fourth constraint has singular value σ, the largest σ on a quarter-decade grid at which each route's count is first not (10, 4, 0), median of eight draws, against the curvature h of H along that constraint's weak direction, on logarithmic axes. The Bunch–Kaufman LDLᵀ count first fails at 1.8·10⁻¹¹ for h = -1·10⁻⁴, 1.8·10⁻¹⁰ for h = -0.01, 1.4·10⁻⁹ for h = -1, 1.8·10⁻⁸ for h = -100 — a fitted slope of 0.49 against |h|, with the dashed line of slope one half through the value at h = −1. The unpivoted elimination fails slightly higher. The count through an orthonormal null-space basis is right down to rounding, and a rank test at tolerance 10·u·‖A‖ drops the constraint only at 1.1·10⁻¹⁵.

show: "dependent-verdicts"

The arguments are the ones A constraint the count stops seeing passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

What the inertia count says as a constraint becomes dependent, h = -1For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature -1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K, the lower one the count through an orthonormal null-space basis. The LDLᵀ count is the full verdict on every draw down to 10⁻⁸, and below that it is split between the full verdict and the dropped one at every σ, without settling.LDLᵀ of Kthe reduced Hessian through Z8 draws8 draws110⁻²10⁻⁴10⁻⁶10⁻⁸10⁻¹⁰10⁻¹²10⁻¹⁴10⁻¹⁶σ, the constraint's smallest singular valuefull problem: a minimumweak constraint droppedneitherevery draw is a genuine minimumrounding decides where the constraint ends

For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature -1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K, the lower one the count through an orthonormal null-space basis. The LDLᵀ count is the full verdict on every draw down to 10⁻⁸, and below that it is split between the full verdict and the dropped one at every σ, without settling.

show: "dependent-verdicts", h: 1

The arguments are the ones A constraint the count stops seeing passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

What the inertia count says as a constraint becomes dependent, h = 1For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature 1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K, the lower one the count through an orthonormal null-space basis. The LDLᵀ count is the full verdict on every draw down to 10⁻⁸, and below that it is split between the full verdict and counts that are neither at every σ, without settling.LDLᵀ of Kthe reduced Hessian through Z8 draws8 draws110⁻²10⁻⁴10⁻⁶10⁻⁸10⁻¹⁰10⁻¹²10⁻¹⁴10⁻¹⁶σ, the constraint's smallest singular valuefull problem: a minimumweak constraint droppedneitherevery draw is a genuine minimumrounding decides where the constraint ends

For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature 1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K, the lower one the count through an orthonormal null-space basis. The LDLᵀ count is the full verdict on every draw down to 10⁻⁸, and below that it is split between the full verdict and counts that are neither at every σ, without settling.

show: "dependent-loop"

The arguments are the ones A constraint the count stops seeing passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The inertia-correction shift on a minimum with a nearly dependent constraint, h = -1The shift the inertia-correction loop settles on — 0, 10⁻⁴, then a hundred times that, then eight times each failure — for eight draws of a 10 × 4 problem that is at a constrained minimum and needs no shift, against the singular value σ of its nearly dependent fourth constraint, with curvature -1 along the constraint's weak direction. Dots are the largest shift over the eight draws and bars at the floor mark draws left unshifted. Down to σ = 10⁻⁷ no draw is shifted. Below 10⁻⁸ 22 of the 88 draws are, by as much as 2620 at σ = 10⁻¹⁰.10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁴σ, the constraint's smallest singular valueshift the loop put on H10⁻⁴10⁻⁵10⁻⁶10⁻⁷10⁻⁸10⁻⁹10⁻¹⁰10⁻¹¹10⁻¹²10⁻¹³10⁻¹⁴h = -1, eight draws per σ, every one a minimumdraws shifted, of 8822largest shift, at σ = 10⁻¹⁰2621shift the problem needed0the bars are the draws the loop left aloneno shift of H can bring back a constraint the count has lost

The shift the inertia-correction loop settles on — 0, 10⁻⁴, then a hundred times that, then eight times each failure — for eight draws of a 10 × 4 problem that is at a constrained minimum and needs no shift, against the singular value σ of its nearly dependent fourth constraint, with curvature -1 along the constraint's weak direction. Dots are the largest shift over the eight draws and bars at the floor mark draws left unshifted. Down to σ = 10⁻⁷ no draw is shifted. Below 10⁻⁸ 22 of the 88 draws are, by as much as 2620 at σ = 10⁻¹⁰.

show: "dependent-verdicts", dc: 1e-8

The arguments are the ones A constraint the count stops seeing passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

What the inertia count says as a constraint becomes dependent, h = -1, constraint block perturbed by 10⁻⁸For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature -1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K with 10⁻⁸ subtracted along the constraint block's diagonal, the lower one the count through an orthonormal null-space basis. Every draw reads the full verdict above σ = 10⁻⁴, the square root of |h| times δc, and the dropped one below it.LDLᵀ of K − 10⁻⁸ on the constraint blockthe reduced Hessian through Z8 draws8 draws110⁻²10⁻⁴10⁻⁶10⁻⁸10⁻¹⁰10⁻¹²10⁻¹⁴10⁻¹⁶σ, the constraint's smallest singular valuefull problem: a minimumweak constraint droppedneitherevery draw is a genuine minimumthe perturbation decides where the constraint ends

For σ from 1 down to 10⁻¹⁶ in half decades, eight draws of a 10 × 4 problem at a constrained minimum whose fourth constraint has singular value σ and whose Hessian has curvature -1 along that constraint's weak direction. Each bar stacks the draws whose count is the full problem's verdict, the verdict of the problem with the weak constraint dropped, and neither. The upper panel is a Bunch–Kaufman LDLᵀ of K with 10⁻⁸ subtracted along the constraint block's diagonal, the lower one the count through an orthonormal null-space basis. Every draw reads the full verdict above σ = 10⁻⁴, the square root of |h| times δc, and the dropped one below it.

What it checked while drawing

Every figure above checked its own claims on the way to being drawn, and a claim that failed would have stopped the picture rather than shipped a wrong one. Those checks used to leave no trace at all: a passing one returned true and the only evidence the figure had checked anything was that nothing crashed. The list below is what they actually said, collected by running this generator with an observer installed — not a description of what it is believed to check.

76 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.

below it every draw is the dropped verdict, σ = 10^-4.5 — checked 24 times

above the square root of |h| times δc every draw is the full verdict, σ = 10^0 — checked 10 times

the count forgets the constraint far above the rank tolerance at h = -0.0001 — checked 4 times

a conditioning of the constraint the sweep is drawn at

a conditioning the comparison is drawn at: 10, 10⁴ or 10⁸

a constrained problem with a null space to have curvature in

a constraint no larger than the problem

a constraint that is nearly dependent rather than dependent

a coupling between the weak direction and the null space no larger than the curvatures

a curvature along the weak direction that has a sign

a curvature the verdict grid is drawn at

a Hessian with negative eigenvalues

a negative curvature for the negative directions

a negative curvature the loop sweep is drawn at

a pivot rule this routine implements

a reduced Hessian with the negative curvatures asked for

a size the spectrum can be drawn at

a well-conditioned constraint stops on no saddle at κ(A) = 10

and every positive one

and the unpivoted, spectral and null-space counts agree with it

at |δ| = 1 the ldl route is right on both sides

at |δ| = 1 the pivots route is right on both sides

at |δ| = 1 the reduced route is right on both sides

at κ(A) = 10 only saddles at rounding are passed

at κ(A) = 10⁸ saddles past a hundredth are

consult the null space on a wrong count, or always

every negative eigenvalue is inside the closed-form bracket

fewer constraints than unknowns

fewer constraints than unknowns, so something is left to minimise

fewer negative reduced curvatures than null-space directions

four bisections bring the worst ratio under five

Jacobi needs a symmetric matrix

matmul shapes agree

no perturbation, or one between 10⁻¹⁴ and 10⁻⁴

several constraints, one of which is nearly a combination of the others

the inertia is (n, m, 0), as the congruence says

the K routes grow like κ(A)² and the Z route like κ(A)

the LDLᵀ count is In(ZᵀHZ) + (m, m, 0)

the loop finds a shift below its cap

which a Cholesky refuses

while the count sees the constraint no draw is shifted

Against the rule

It draws a decomposition and prints its residual. It calls inertia, rustenWinther, and every figure above carries the badge — which residualcheck verifies by looking for it in the emitted SVG rather than by finding the call that builds one. A badge that is constructed and then left out of the body is the failure that check exists for.

Across the library: the rule bites on 217 of 397 generators — 199 print a residual and 18 are exempt with a published reason; 180 factorise nothing. Read from lib/residual-rule.js, which is the same body the gate enforces from, and the gate's last check fails the build if this page and it disagree about any generator.

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

The matrix a constraint makes

A constraint the count stops seeing

Let one constraint drift towards being a combination of the others and the inertia of the saddle-point matrix keeps its promise only while σ²/|h| can be resolved — σ the constraint's smallest singular value, h the curvature along the direction it barely constrains. At h = −1 the count stops seeing the constraint at σ = 1.4·10⁻⁹, six decades before any rank test would drop it, and below that it reports a genuine minimum as a saddle on three to six draws in eight. No shift of H brings the constraint back: the correction loop shifts a problem that needed nothing by as much as 2,620. A perturbation of the constraint block does not bring it back either — it decides, at σ = √(|h|δ).

The matrix a constraint makes

A loop that asks the null space why

An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see. One QR of the constraint matrix on a wrong count tells them apart — it shifts none of the 22 weak-constraint minima the ordinary loop shifted by up to 2,621 — and its reduced eigenvalue gives the shift a saddle needs in one step, twice the need exactly, where the schedule overshoots by up to 17,783 times. But at κ(A) = 10⁸ the loop still certifies 57 saddles of 152, because a false certificate is a count that read right, and a check made only on wrong counts never sees it. Asking every time leaves five, all shallower than 2·10⁻⁸.

The matrix a constraint makes

A minimum the Hessian cannot see

A Hessian with four negative eigenvalues can sit at a constrained minimum, and a Cholesky of it stops at the third row. One symmetric indefinite factorisation of the saddle-point matrix settles the question anyway — ten positive pivots and four negative — without a basis for the null space ever being formed. The count is exact in the algebra and blind in floating point, in a band that grows like κ(A)²; the route through the null space is blind in one that grows like κ(A).

The matrix a constraint makes

The shift that stops at the first right count

A nonconvex solver that finds the wrong inertia adds δI to H and tries again, and the δ it settles on is used as though it measured the curvature it corrects. It does not. On a well-conditioned constraint it is the schedule's number — 1.8·10⁴ times the need at a curvature of 5.6·10⁻⁹, between one and 7.3 times above 10⁻² — and on an ill-conditioned one the loop stops wherever the count first reads right: 63 of 152 saddles at κ(A) = 10⁸, the deepest with curvature 56. Refining the shift by bisection removes the first error and adds to the second.

The matrix a constraint makes

The zero that is not a missing entry

A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.

The whole library · All essays · What must fail