Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

One real vector, 23 candidate cuts, and the best of them is number 12

One function in the graphlap library, called 9 times across 4 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 10 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 one real vector, 23 candidate cuts, and the best of them is number 12. The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

fiedler-sweep is one function in lib/figures/graphlap.js — the matrix a graph makes — row sums that are exactly zero, a count that is a threshold, and a partition with no vector. 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.

One real vector, 23 candidate cuts, and the best of them is number 12The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

family: "barbell", n: 24

The arguments are the ones A bound with a square root in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

One real vector, 23 candidate cuts, and the best of them is number 12The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the barbell 12, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.14435. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

family: "barbell", n: 10

The arguments are the ones The vector that has to be rounded passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

One real vector, 9 candidate cuts, and the best of them is number 5The Fiedler vector of the barbell 5, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.29844. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 5 at a conductance of 0.04762 against a worst prefix of 1 — a factor of 21 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.024681010⁻¹1vertices on the smaller sideconductance of the prefix cut0.0476, the best prefixthe rounding stepλ₂0.3cuts considered9best conductance0.048at k =5worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the barbell 5, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.29844. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 5 at a conductance of 0.04762 against a worst prefix of 1 — a factor of 21 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

family: "barbell", n: 16

The arguments are the ones The vector that has to be rounded passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

One real vector, 15 candidate cuts, and the best of them is number 8The Fiedler vector of the barbell 8, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.20417. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 8 at a conductance of 0.01754 against a worst prefix of 1 — a factor of 57 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.0369121510⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.0175, the best prefixthe rounding stepλ₂0.2cuts considered15best conductance0.018at k =8worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the barbell 8, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.20417. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 8 at a conductance of 0.01754 against a worst prefix of 1 — a factor of 57 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

family: "barbell", n: 36

The arguments are the ones The vector that has to be rounded passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

One real vector, 35 candidate cuts, and the best of them is number 18The Fiedler vector of the barbell 18, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.10051. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 18 at a conductance of 0.003257 against a worst prefix of 1 — a factor of 307 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.06121824303610⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00326, the best prefixthe rounding stepλ₂0.1cuts considered35best conductance0.0033at k =18worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the barbell 18, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.10051. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 18 at a conductance of 0.003257 against a worst prefix of 1 — a factor of 307 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

family: "blocks", n: 60

The arguments are the ones The vector that has to be rounded passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

One real vector, 59 candidate cuts, and the best of them is number 30The Fiedler vector of the two blocks 60, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 2.5538. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 30 at a conductance of 0.08982 against a worst prefix of 1 — a factor of 11.1 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.010203040506010⁻¹1vertices on the smaller sideconductance of the prefix cut0.0898, the best prefixthe rounding stepλ₂2.6cuts considered59best conductance0.09at k =30worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The Fiedler vector of the two blocks 60, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 2.5538. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 30 at a conductance of 0.08982 against a worst prefix of 1 — a factor of 11.1 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.

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.

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

a cut with two non-empty sides

a family the library builds

a graph the sweep can afford

a graph with at least two vertices

a planted partition with no isolated vertex

a positive weight

every endpoint inside the vertex set

Jacobi needs a symmetric matrix

no edge given twice

no self-loop

Against the rule

It draws a decomposition and prints its residual. It calls fiedler, 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 that is a graph

A bound with a square root in it

Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂). The lower bound is attained exactly. The upper one is loose by a factor of fourteen — on the one graph in the census with a real bottleneck, which is the shape it is always quoted about.

 The matrix that is a graph

A matrix with no numbers in it

A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object in these essays whose kernel is known before anything runs.

 The matrix that is a graph

The vector that has to be rounded

A spectral partition is an eigenvector, and an eigenvector is a real vector. The answer wanted is a subset. Something has to turn one into the other, and the something is a heuristic applied after the linear algebra has finished.

 The matrix that is a graph

Two Laplacians of one graph

The combinatorial Laplacian D − A and the normalised one, which conjugates it by the inverse square roots of the degrees, are built from the same object, are not similar to each other, and answer different questions. On a graph whose degrees are equal they coincide. On one whose degrees span an order of magnitude their second eigenvalues are sixteen times apart.

The whole library · All essays · What must fail