A distance computed by a solve

Everything the graph field has measured so far had a combinatorial route to it. A component count can be got by breadth-first search, a conductance by counting edges, a partition by enumeration on a small enough graph. The spectral route was one of two, and having two was the point.

Effective resistance has no second route of that kind. It is defined by a linear system:

R(i, j)  =  (eᵢ − eⱼ)ᵀ L⁺ (eᵢ − eⱼ)

where L⁺ is the pseudoinverse of the Laplacian. There is no way to read it off the edge list, no counting argument that produces it, and no shortest path that approximates it. It is the potential difference when one ampere is injected at i and drawn out at j, and computing it means solving.

Three routes, and the third one is exact #

The absence of a combinatorial route makes the site’s habit harder and more valuable, so the field supplies three.

The grounded elimination. Delete one row and column of L, solve, read the potential difference. One factorisation serves every pair, since the inverse of the grounded matrix is what all of them are read from.

The spectral sum. R(i,j) = Σ over the non-zero modes of (uₖᵢ − uₖⱼ)²/λₖ. This uses the entire eigendecomposition, where the first route uses none of it, so the two share no arithmetic beyond the matrix they were both handed.

BigInt rationals. For an unweighted graph the Laplacian has integer entries, so the grounded system can be solved exactly in rationals and the answer is a ratio of two integers with no rounding anywhere.

The first row of the four-by-four grid, exactly:

0   157/224   263/224   181/112   157/224   97/112   8/7   327/224   ...

Against those, the elimination is right to 2.7·10⁻¹⁵ at worst and the spectral sum to a comparable level, with the solve’s own relative residual at 1.5·10⁻¹⁵.

That is the site’s strongest form of ground truth since the Hilbert inverse: the error is known rather than bounded, because one of the routes has none.

And there is an identity that fixes the total #

Foster’s theorem is the reason this field’s resistances can be checked without a second routine at all. For any connected graph,

Σ over edges of  w(e) · R(e)  =  n − 1

exactly, whatever the graph is. Not asymptotically, not up to a constant: the weighted resistances of the edges of an n-vertex graph sum to n − 1.

Measured across seven families:

graph               Foster's sum        n − 1     error
path 20             19.000000000000       19      0
cycle 17            16.000000000000       16      0
grid 5×6            29.000000000000       29      3.6·10⁻¹⁵
barbell 7           13.000000000000       13      1.1·10⁻¹⁴
two blocks 40       39.000000000000       39      3.6·10⁻¹⁴
preferential 40     39.000000000000       39      7.1·10⁻¹⁵
hypercube 4         15.000000000000       15      0

Three of the seven are exact — the path, the cycle and the hypercube, whose resistances happen to be representable — and the rest are at the rounding level.

Swept over the grid size, the identity’s error and the routes’ errors grow at different rates.

The two routes barely move and the identity’s residual grows. Across grids of 6, 9, 12 and 20 vertices the elimination’s worst error runs 4.54·10⁻¹⁶, 4.7·10⁻¹⁶, 6.3·10⁻¹⁶ and 7.79·10⁻¹⁶ and the spectral route’s 6.34·10⁻¹⁶, 6.27·10⁻¹⁶, 1.21·10⁻¹⁵ and 1.38·10⁻¹⁵ — factors of 1.7 and 2.2 across a factor of 3.3 in the size — while Foster’s residual goes 0, 1.8·10⁻¹⁵, 1.8·10⁻¹⁵ and 3.6·10⁻¹⁵.

That is the identity behaving as a sum rather than as a maximum, and it is why it is a check rather than a bound. Foster’s residual is an accumulation over every edge, so it grows with the edge count while the worst individual resistance error does not — at 4×5 the identity is off by 3.6·10⁻¹⁵ while no single resistance is wrong by more than 1.4·10⁻¹⁵. A reader who read the identity’s residual as the accuracy of the resistances would be over-estimating by about the square root of the edge count, and reading it the other way — as a bound on the worst — would be wrong in the safe direction and still wrong. It is a test that the answers are collectively right, and it says nothing about which of them is worst.

This is a check of a kind this site has very few of. A comparison against a second routine tests whether two implementations agree; an identity like Foster’s tests whether the answer is right, against a number nobody computed. It is available on every graph, at the cost of one pass over the edges once the resistances are known, and it would catch a systematic error that both floating-point routes made together.

Why the identity is the check worth having #

It is worth dwelling on Foster’s theorem, because it is a rarer kind of test than it looks and this site has been explicit about the difference.

Most verification in numerical work is comparative: run two implementations, or one implementation at two precisions, and check that they agree. That is a real test and it has a known blind spot — two routes that share a mistake agree perfectly. The site’s two routes to a number thread is built to avoid that by choosing routes with as little shared arithmetic as possible, and the two floating-point routes here are chosen that way.

Foster’s identity is a different kind of test. It compares the computed answer against a number derived from nothing but the graph’s vertex count, so no error in any implementation can satisfy it by accident. A routine that computed every resistance twice as large would agree with itself and fail Foster by a factor of two. One that dropped a term in the spectral sum would agree with nothing and fail Foster. One that grounded the wrong vertex would still pass, correctly, because the resistance does not depend on the grounding — and the identity is not supposed to catch that, because there is nothing there to catch.

The site has three checks of this class and it is worth listing them together: the Hilbert matrix’s closed-form inverse, Kirchhoff’s theorem returning an integer, and this. Each compares a computation against a mathematical fact rather than against another computation, and each is available only because the object has enough structure to have one.

How much of the answer the identity actually sees #

The paragraphs above are an argument for Foster’s identity and they are one-sided, because they say what class of error it catches and never how much of the computed answer it looks at. Two measurements, and both get worse as the graph gets bigger.

It constrains the edges, and the edges are a shrinking fraction of the pairs. All-pairs resistance on an n-vertex graph is n(n − 1)/2 numbers; Foster’s sum runs over m of them. On the complete graph those are the same set. Everywhere else they are not:

graph            edges    pairs    fraction Foster touches
complete 40       780      780              100%
barbell 40        381      780               49%
blocks 40         223      780               29%
grid 6×7           71      861              8.2%
skewed 40          77      780              9.9%
cycle 40           40      780              5.1%
path 40            39      780              5.0%

A resistance between two vertices that are not joined by an edge is not in the identity at all, and on the graphs this field actually cares about — sparse ones — that is nineteen answers in twenty. Foster is silent about them, correctly and completely.

And it is one number checking m of them, so an error that is not systematic is diluted. Perturb each edge resistance by an independent relative error of 10⁻³ and measure what reaches the sum:

graph           m       per-edge error   error in Foster's sum   dilution
cycle 16        16         1.0·10⁻³           1.95·10⁻⁴            5.1×
cycle 40        40         1.0·10⁻³           1.24·10⁻⁴            8.1×
grid 6×7        71         1.0·10⁻³           9.94·10⁻⁵           10.1×
blocks 40      223         1.0·10⁻³           5.73·10⁻⁵           17.4×
complete 30    435         1.0·10⁻³           3.94·10⁻⁵           25.4×

The dilution is √m/0.798 across all fifteen configurations measured, to within 12%. That constant is √(π/2) and it is the mean absolute value of a standard normal — which is to say the law is the central limit theorem and not a fact about graphs. Independent errors cancel in a sum, the sum has m terms, and what survives is the error divided by √m.

Put the two together and the shape of the check is clear: its breadth and its sharpness run in opposite directions in the density, and no graph gives both. The complete graph at n = 30 checks every one of the 435 pairs and hides a per-edge error twenty-five-fold. The path of forty hides a per-edge error only eightfold and checks one pair in twenty. There is no size and no family at which Foster’s identity is both a broad check and a sharp one.

None of that makes it a bad check — the errors it was introduced to catch are exactly the systematic ones, a factor of two everywhere or a dropped term, which do not cancel and which no dilution touches. It makes the earlier sentence — “it is available at every size” — half a claim. The availability is genuine; the power falls as √m while the number of quantities it is standing in for grows as m, so the identity holding on a large graph is a weaker statement than the identity holding on a small one, by a factor that is worth computing before relying on it.

The exact rational route is the reason this is a footnote rather than a problem. Below two dozen vertices there is an answer with no error in it at all, and that is what says the floating-point routes are right; Foster is what carries the confidence upward past the point where the exact route stops. Knowing the rate at which the carrying weakens is the difference between a check and a ritual.

What the quantity is #

Three properties make it useful, and the third is the one the next essay depends on.

It is a metric. R(i,k) ≤ R(i,j) + R(j,k), checked here on the four-by-four grid over several triples. So it is a genuine distance on the vertices, unlike the shortest-path distance in one important respect: it takes account of how many paths there are rather than only the shortest.

It is smaller than the hop distance, and by how much says something. On the grid the ratio of resistance to hop count runs from 0.31 to 0.70; on a cycle from 0.50 to 0.92; on the complete graph it is exactly 0.20 for every pair. Two vertices joined by many short paths have a resistance far below their hop distance; two joined by one path have resistance equal to it. On a path graph the resistance between two vertices is exactly the number of edges between them — the exact rational route returns the integer — because there is only one way to get there.

And it has closed forms on the families with symmetry. On the complete graph R(i,j) = 2/n for every pair, returned exactly as 2/5, 1/4 and 1/6 at n = 5, 8 and 12. On the cycle R(i,j) = d(n − d)/n where d is the hop distance, checked at three separations on a twelve-cycle. Those closed forms are what the assertions in this field are calibrated against, rather than against a plausible-looking number.

Why the pseudoinverse is not formed #

The definition names L⁺ and no implementation computes it.

Forming a pseudoinverse means an eigendecomposition or an SVD, which is cubic and dense, on a matrix that was sparse. Every entry of the result is nonzero even when L has three per row. And the quantity actually wanted is a handful of quadratic forms in it, not the matrix.

The grounded route gets them from one factorisation of an (n − 1) × (n − 1) matrix that inherits L’s sparsity, which is the same trade the inverse essays make in the elimination field: an inverse appears in the formula and a solve appears in the code, and the two are the same answer at different costs.

The grounding introduces the free parameter an earlier essay measured — which vertex to delete, worth up to nine hundred in the conditioning — and the resistance itself is independent of it, because the potential difference between two vertices does not depend on where the potential was pinned. That independence is worth checking rather than assuming, and it is: computing the same resistance with different vertices grounded agrees at the rounding level.

What the spectral route is for #

Given that the elimination is faster and no less accurate, the spectral sum looks like a check and nothing more. It is also the form in which the quantity is understood.

Written as a sum over modes, R(i,j) = Σ (uₖᵢ − uₖⱼ)²/λₖ, the small eigenvalues dominate. A pair of vertices separated by a bottleneck has a large component in the low modes — those are the modes that distinguish the two sides — and each such component is divided by a small λ. So a large effective resistance means a bottleneck, and the connection between resistance and the conductance essays is not an analogy: it is the same eigenvalues, weighted differently.

That is also why resistance is the right sampling probability for a spectral sparsifier. An edge with high effective resistance is an edge the graph’s low modes depend on, and losing it changes the quadratic form; an edge with low resistance is one of many parallel routes and can be replaced by its neighbours. Sampling in proportion to resistance is sampling in proportion to how much of the spectrum an edge carries, and Foster’s identity is what makes those probabilities sum to something known.

Where it is used, and why the definition looks odd until then #

A quantity defined by a solve invites the question of what it is for, and the answer is that it turns up in four places where nothing simpler works.

Sampling. The next essay’s sparsifier keeps each edge with probability proportional to its effective resistance, and the resulting graph preserves every quadratic form. No other sampling probability is known to do that.

Clustering and embedding. The resistance metric is a genuine distance that takes account of the number of paths rather than the shortest one, which is what makes it useful where a hop distance is not — two vertices joined by one long path and two joined by twenty short ones can have the same hop distance and resistances differing by a factor of twenty.

Network reliability. The resistance of an edge is exactly the probability that the edge appears in a uniformly random spanning tree, which connects it to the counting essay three along and gives Foster’s identity its combinatorial reading: the expected number of edges in a spanning tree is n − 1, because every spanning tree has n − 1 edges.

And solver design. A preconditioner built from a subgraph is scored by a sum of resistances, which is the quantity the tree essay calls stretch.

That last reading is the one that makes Foster’s theorem feel less like a coincidence. Σ w·R(e) = n − 1 says the resistances of the edges are a probability distribution scaled by n − 1, and the distribution is the one a random spanning tree induces. An identity with a probabilistic proof is a better thing to check a computation against than an identity with only an algebraic one, because it comes with an interpretation of what a violation would mean.

What it costs #

The exact route is the expensive one and it is worth being precise about how expensive.

BigInt rationals grow: the numerators and denominators of the entries of an exactly inverted integer matrix are integers of length proportional to the size, so the arithmetic is superquadratic in the dimension on top of the cubic elimination. In practice the route is affordable to about two dozen vertices, which is why this field’s figures cap it there and refuse beyond it.

That cap is the reason the exact route appears in one figure rather than in all of them. Everywhere else the check is Foster’s identity, which costs nothing and is available at every size — and the existence of the exact route on small graphs is what says Foster’s identity is being checked against the right thing.

The floating-point routes are ordinary: one elimination of an (n − 1) × (n − 1) sparse symmetric positive definite matrix, or one eigendecomposition. For all-pairs resistances the elimination is solved n − 1 times against unit vectors, which is a dense inverse in disguise; for a handful of pairs it is one factorisation and a few solves.

Where the accuracy actually goes #

One measurement is worth recording because it did not go the way the shape of the problem suggests.

The relative error of both floating-point routes against the exact answer stays at 10⁻¹⁵ across every family and size tried. It does not grow with n, and it does not grow with the graph’s conditioning in any visible way.

The reason is that a Laplacian’s grounded submatrix is well conditioned on these families — κ between about 100 and 1,400 — and pivoted elimination on a well-conditioned symmetric positive definite matrix is as good as arithmetic gets. The error identity predicts a forward error of about κ times the unit roundoff, which is 10⁻¹³ at worst, and the measurement comes in two orders below that.

So the difficulty in this quantity is not numerical. It is that the quantity is defined by a solve and therefore costs a solve, on an object whose other properties are all available by counting — and the essays that follow are about what that buys.

What a disconnected graph does to it #

The refusal this essay is checked by is worth explaining, because the failure is not a numerical one.

Between two vertices in different components the effective resistance is infinite. There is no path, no current flows, and the potential difference for a unit injection is unbounded. That is the correct answer and it is not a number, so a routine that returns one has computed something else.

What it has computed depends on how it failed. The grounded matrix of a disconnected graph is singular — the kernel has one dimension per component, and grounding one vertex removes only one of them — so the elimination hits a zero pivot. On the graphs in this field it hits a pivot of about 10⁻¹⁵ rather than exactly zero, for the reason the grounding essay measured: the elimination’s arithmetic is not exact even when the row sums are. So the solve proceeds, divides by a rounding error, and returns a resistance of order 10¹⁵ — a large number where the answer is infinity, from a computation that reported no error.

The routine here refuses instead, by counting components first. That check is a breadth-first search and costs less than one step of the elimination it precedes, and it converts a silently wrong number into a stated refusal. It is the same move the deliberate-zero essays argue for: a test the arithmetic cannot make reliably, made once, by a route that does not use the arithmetic.