Numerical Linear Algebra
where the algebra stops being the arithmetic
The matrix that is a graph

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.
32 min read 27 figures Where the algebra stops being the arithmeticExact ground truthMeasured, not assertedTwo routes to a number

Worth reading first: A matrix with no numbers in it · Two Laplacians of one graph · A matrix that depends on its own eigenvalue.

Every method in this field reads a spectrum and answers a question about a graph. A component count, a conductance bound, a mixing time, a partition, a centrality — all of them are functions of eigenvalues and eigenvectors, and all of them are therefore functions of the graph only to the extent that the spectrum determines the graph.

It does not.

Two different graphs with the same spectrum, to the last digitA triangle joined to a square at one vertex, and the complete bipartite graph K₂,₃ with one pendant edge. Six vertices and seven edges each, 12 spanning trees each, and — for the combinatorial Laplacian — the same characteristic polynomial as an integer polynomial, checked in exact arithmetic rather than by comparing computed eigenvalues. Their computed spectra differ by 5.33·10⁻¹⁵, which is the eigensolver's own rounding and not a property of the graphs. Their degree sequences are 4, 2, 2, 2, 2, 2 and 3, 3, 3, 2, 2, 1, and the first contains a triangle while the second is bipartite — so they are not the same graph by two independent readings, and every method in this field that reads only the spectrum answers about the class.a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite
Fig. 1 A triangle joined to a square at one vertex, and the complete bipartite graph K₂,₃ with a pendant edge. Six vertices and seven edges each, and the same Laplacian spectrum.

The pair, and how it is checked

On the left, a triangle and a square sharing a vertex. On the right, K₂,₃ — three vertices each joined to both of two others — with one extra vertex hanging off. Six vertices and seven edges each.

Their Laplacian characteristic polynomials are

x⁶ − 14x⁵ + 73x⁴ − 176x³ + 192x² − 72x

for both, and that is checked as an integer polynomial rather than by comparing computed eigenvalues. The coefficients are computed by the Faddeev–LeVerrier recurrence in BigInt rationals, so the claim is that two sequences of seven integers are equal, which they are, exactly.

That distinction matters more here than almost anywhere on the site. Two computed spectra agreeing to 5.3·10⁻¹⁵ would be consistent with the graphs being cospectral and also with their being different by less than the eigensolver can see — and the whole point of the pair is to distinguish “the same” from “indistinguishable”. An exact check settles it and a numerical one cannot.

They are not the same graph, by two independent readings

Degree sequences. Sorted, the left graph’s is 4, 2, 2, 2, 2, 2 and the right’s is 3, 3, 3, 2, 2, 1. One has a vertex of degree four and no vertex of degree one; the other has neither.

Bipartiteness. The left graph contains a triangle, so it has an odd cycle and is not bipartite — and a bipartite graph is also the case where a random walk on it never mixes, so the property has consequences well beyond this pair. The right is K₂,₃ with a pendant edge, which is bipartite by construction.

Either fact alone proves the graphs are not isomorphic. Both are properties any reader can check by looking, and neither is visible in the spectrum.

They agree on more than the spectrum, too. Both have twelve spanning trees — which follows from cospectrality, since the count is the product of the non-zero eigenvalues divided by n, so the previous essay’s determinant cannot separate them either.

Where the pair came from

The pair was not taken from a table; it was found by enumeration, and the search is short enough to describe.

Every graph on six vertices is a subset of the fifteen possible edges, so there are 32,768 of them. Discarding the disconnected ones and those with fewer than five edges leaves a few thousand. Group them by their exact Laplacian characteristic polynomial — a vector of seven integers — and look for a group containing two graphs with different degree sequences, which guarantees non-isomorphism without having to test for it.

There are 110 distinct polynomials among the connected six-vertex graphs, and two of those groups contain graphs with different degree sequences. The pair above is the first, and the second is a larger pair on eight edges.

Two things about that are worth recording. Six vertices is the smallest size where this happens — below it, every connected graph is determined by its Laplacian spectrum, which the same enumeration confirms. And the grouping is exact: the polynomials are integer vectors compared for equality, so no threshold decides which graphs are cospectral, which would be the obvious way to get this wrong.

That is the same distinction a threshold on singular values forces, and here it is avoided entirely. A search that grouped by computed eigenvalues within a tolerance would have found the pair and would also have found spurious ones — graphs whose spectra differ in the twelfth digit — and no tolerance separates the two cases, because the differences between genuinely distinct spectra on six vertices go all the way down to zero.

What follows for every method in this field

The consequence is not that spectral methods are unsound. It is that they answer a question about an equivalence class, and it is worth going through what that means case by case.

A component count is safe. The number of zero eigenvalues is a genuine invariant and cospectral graphs have the same one, correctly — so the count and the threshold that reads it behave identically on both.

A conductance bound is safe, since both halves of it are functions of the spectrum alone. Cheeger’s inequality bounds a graph’s conductance in terms of its spectrum, so cospectral graphs have conductances in the same bracket — and they may have different conductances inside it, which the bound permits and does not detect.

A partition is not determined. The Fiedler vector depends on eigenvectors, not only eigenvalues, and cospectral graphs have different eigenvectors — so the sweep that rounds one can return different answers on two graphs a spectrum cannot separate. So two graphs a spectral method cannot tell apart can be partitioned differently, correctly, by the same method.

And a similarity search is unsound. Any pipeline that compares graphs by comparing spectra — a common technique, because a spectrum is a short vector and a graph is not — will report these two as identical. They are not, and the difference is large: one is bipartite and one has a triangle.

The other matrix separates them at once

The second Laplacian, which an earlier essay argued is a genuinely different object, tells them apart immediately:

                 normalised spectrum
triangle+square  0, 0.376510, 1, 1.222521, 1.500000, 1.900969
K₂,₃ + pendant   0, 0.528595, 1, 1.000000, 1.471405, 2.000000

The second eigenvalues differ by 0.152, which is not a rounding of anything, and the largest eigenvalue of the right-hand graph is exactly 2.

That last entry is the whole mechanism. The normalised Laplacian’s spectrum lies in [0, 2] for every graph, and 2 is attained if and only if the graph is bipartite. So the normalised spectrum detects bipartiteness, the combinatorial one does not, and the two matrices built from one object answer different questions — which was the earlier essay’s claim, and this is the sharpest available instance of it.

It is worth noticing what has happened. The information distinguishing these graphs was present in the object the whole time; the combinatorial matrix threw it away and the normalised one did not. “The spectrum of a graph” is not a well-formed phrase, and which matrix is meant decides what can be concluded.

The other matrix separates them at the first eigenvalueA triangle joined to a square at one vertex, and the complete bipartite graph K₂,₃ with one pendant edge. Six vertices and seven edges each, 12 spanning trees each, and — for the combinatorial Laplacian — the same characteristic polynomial as an integer polynomial, checked in exact arithmetic rather than by comparing computed eigenvalues. Drawn here for the NORMALISED Laplacian D^{-1/2}LD^{-1/2}, whose spectra differ by 0.2225: the second graph is bipartite, and a bipartite graph has an eigenvalue at exactly 2, which the first cannot have. A different matrix built from the same object asks a different question. Their degree sequences are 4, 2, 2, 2, 2, 2 and 3, 3, 3, 2, 2, 1, and the first contains a triangle while the second is bipartite — so they are not the same graph by two independent readings, and every method in this field that reads only the spectrum answers about the class.a triangle and a square, joinedK₂,₃ with a pendant edge123456012indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by0.22highest degree, left4highest degree, right3one has a trianglethe other is bipartite
Fig. 2 The same two graphs under the normalised Laplacian, whose spectra differ by 0.15 and whose right-hand graph carries an eigenvalue at exactly two.

How the polynomial is computed, and why not by the eigenvalues

The characteristic polynomial could be obtained by multiplying out (x − λᵢ) over the computed eigenvalues, and that is the route this essay could not use.

Multiplying six computed eigenvalues, each accurate to 10⁻¹⁴, gives coefficients accurate to about 10⁻¹³ relative — which for a coefficient of 176 means an absolute error of 10⁻¹¹, so the integers would have to be recovered by rounding, and the claim “these two polynomials are equal” would become “these two rounded polynomials are equal”, which is a claim about a tolerance.

Faddeev–LeVerrier avoids it entirely. The recurrence builds the coefficients from traces of powers of the matrix:

M₀ = 0,   Mₖ = A(Mₖ₋₁ + cₖ₋₁I),   cₖ = −tr(Mₖ)/k

and every operation in it is a multiplication or addition of rationals. On an integer matrix the intermediate entries stay rational with small denominators, the trace divisions come out whole, and the coefficients arrive as exact integers with no rounding at any step.

The recurrence is famously unstable in floating point — the divisions by k against traces that grow like ‖A‖ᵏ lose digits fast, and nobody would use it numerically. In exact arithmetic that instability does not exist, which is a clean instance of a distinction this site makes often: numerical stability is a property of an algorithm in an arithmetic, not of the algorithm. A method that is unusable in binary64 can be the right one in rationals, and the reason to reach for it here is that the claim being made is exact.

And the normalised one is not enough either

The obvious next move is to conclude that the normalised Laplacian is the right invariant. It is not.

Normalised-cospectral pairs exist as well, and so do pairs that are cospectral for both matrices at once. There is no single matrix built from a graph whose spectrum determines it — the whole subject of graph isomorphism would be a two-line eigenvalue computation if there were.

What is true is a hierarchy of partial results. Almost all graphs are determined by their spectrum, in the sense that the fraction of cospectral pairs falls as the number of vertices grows; the smallest Laplacian-cospectral pair has six vertices; adding invariants (the number of triangles, the degree sequence, the spectrum of a complement) rules out more pairs. None of that produces a complete invariant, and none of it is a numerical statement.

How common is this

The pair above is the smallest, which invites the question of whether it is a curiosity or a hazard, and the answer depends on which end of the size range the graphs come from.

On six vertices, the enumeration finds two cospectral groups out of 110 polynomials — so a couple of per cent of the connected six-vertex graphs share a spectrum with a non-isomorphic one. That is small.

It rises before it falls. The fraction of graphs on n vertices that are not determined by their adjacency spectrum peaks somewhere in the teens — a substantial fraction at n = 10 to 12 by published enumerations — and then falls as n grows, with the conjecture, unproven, that it tends to zero.

So the risk profile is unusual: the graphs most likely to collide are the small ones, and small graphs are exactly the ones a spectral fingerprint would be used on, because a large graph’s spectrum is expensive and a small graph’s is not.

There is a second reason the count understates the hazard. The enumeration above is over all graphs, weighted uniformly, and a random graph on many vertices is highly irregular and almost never cospectral with anything. Real graphs are not random: they have symmetry, repeated motifs, and substructures that appear more than once — and every one of those raises the chance of a collision, because cospectral pairs are usually built from exactly such structure. The construction that generates most known pairs, Godsil–McKay switching, needs a set of vertices with a particular regularity in how they attach to the rest, which is common in engineered graphs and rare in random ones.

What this field’s habit says to do about it

The site’s rule is that a claim should be given a test it could fail. Applied here it produces something concrete and cheap.

Report the invariants the spectrum does not carry. The degree sequence costs one pass, and it is the same quantity that decides where to ground a solve. Whether the graph is bipartite costs a breadth-first search. The number of triangles costs a sparse matrix product. Any of them would have separated the pair above, and all three together are less work than the eigendecomposition that did not.

Do not compare graphs by spectra alone. A pipeline that fingerprints a graph by its eigenvalues has a collision rate that is small and is not zero, and the collisions are not near-misses — they are graphs with different topology reported as identical.

And say which matrix. A result quoted about “the graph Laplacian” is ambiguous between two matrices that disagree about bipartiteness, about conditioning, and about the theorem Cheeger’s inequality is stated for.

The adjacency spectrum is a third object, and it disagrees too

The site’s refusal for this essay is about a different cospectrality, and it is worth unpacking because it shows that the phenomenon is not one phenomenon.

The classical smallest cospectral pair is for the adjacency matrix, on five vertices: a four-cycle with an isolated vertex, and the five-vertex star. Both have adjacency spectrum {2, 0, 0, 0, −2}. It is the example in every textbook.

Their Laplacian spectra are completely different — one graph is disconnected and has two zero eigenvalues, the other is connected and has one. So adjacency-cospectral does not imply Laplacian-cospectral, and the assertion in this library is fed exactly that pair and required to reject the claim that it does.

The converse fails too. The pair in this essay is Laplacian-cospectral and not adjacency-cospectral, because their degree sequences differ and the adjacency spectrum’s second moment is the sum of degrees.

So there are at least three spectra a graph has — adjacency, combinatorial Laplacian, normalised Laplacian — and they are cospectral in three different equivalence relations, none of which implies another. A statement of the form “these graphs are cospectral” is incomplete without saying in which, and the three answers on the pairs above are: no, yes, no.

Why this is the field’s last word

The graph field has been about a continuous computation producing a discrete answer, and the failures have all had the same shape: a rounding decides a partition, a threshold decides a count, a format decides an integer. Every one of them was a property of the arithmetic meeting a property of the question.

This one is different and it is the reason it comes last. Nothing here is about the arithmetic at all. The exact characteristic polynomials are equal, in exact arithmetic, on a machine with infinite precision. No improvement to a solver, no change of matrix, no increase in precision separates these two graphs by their combinatorial spectrum, because the information is not there.

That is the boundary of the whole field. Everything before it says the arithmetic decides more than it should; this says that even a perfect arithmetic decides less than a reader assumes. A spectral method answers what the spectrum determines, and that is a smaller thing than the graph — measurable, on six vertices, exactly.

One consolation

It would be wrong to end without the useful half, because the pair above can be read as evidence against spectral methods and it is not.

Everything these two graphs share, they share correctly. They have the same number of components, the same number of spanning trees, the same sum of degrees, the same number of edges, and conductances inside the same Cheeger bracket. A spectral method asked any of those questions returns the right answer for both, and would be wrong only if it were asked to distinguish them — which is a question about isomorphism rather than about any quantity in this field.

The scope of the caution is therefore narrow and precise. Do not use a spectrum as an identity. Use it for the quantities it determines, which is most of what this field computes, and add a cheap combinatorial invariant whenever the question is whether two graphs are the same one.

At other settings

complete 20: 20 vertices, 190 edges, and a matrix built from themThe complete 20 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 20 and the largest computed zero is 7.22·10⁻¹⁶, a gap of 2.77·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 400.the matrix, measuredvertices20edges190‖L·1‖∞0zero eigenvalues1components, by search1λ₂20laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 3 A graph whose spectrum determines it, since no other graph has one eigenvalue repeated n − 1 times.
cycle 24: 24 vertices, 24 edges, and a matrix built from themThe cycle 24 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.06815 and the largest computed zero is 4.87·10⁻¹⁶, a gap of 1.4·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 96.the matrix, measuredvertices24edges24‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.068laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 4 A cycle, whose spectrum determines it and whose eigenvectors do not determine a partition.
hypercube 5: 32 vertices, 80 edges, and a matrix built from themThe hypercube 5 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 2 and the largest computed zero is 2.7·10⁻¹⁷, a gap of 7.42·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 64.the matrix, measuredvertices32edges80‖L·1‖∞0zero eigenvalues1components, by search1λ₂2laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 5 A hypercube, whose spectrum is the binomial distribution scaled and is shared with no other graph of its size.
star 30: 30 vertices, 29 edges, and a matrix built from themThe star 30 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 1 and the largest computed zero is 1.21·10⁻¹⁶, a gap of 8.26·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 60.the matrix, measuredvertices30edges29‖L·1‖∞0zero eigenvalues1components, by search1λ₂1laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 6 A star, whose spectrum is 0, one repeated, and n.
Twenty eigenvalues, one of them zero, and the graph has one pieceThe Laplacian spectrum of two ten-vertex paths joined by a single edge of conductance 1, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.06·10⁻⁹, and the number of eigenvalues below it is the spectral count of connected components: 1. Breadth-first search, which performs no arithmetic on any weight, says 1. The largest computed zero is 5.81·10⁻¹⁷ and the smallest eigenvalue above the threshold is 0.02462. A count of components is therefore a rank decision at a threshold, and the bridge's conductance decides which side of it λ₂ falls on — at nine orders above the rounding level, not at it.13579111315171910⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹indexeigenvalue of L10⁻¹⁰‖L‖, the thresholda count that is a thresholdeigenvalues below it1components, by search1largest computed zero5.8·10⁻¹⁷smallest above it0.025ratio4.2·10¹⁴the graph is connectedat every stop of the slider
Fig. 7 A spectrum read for a component count, which is an invariant cospectral graphs share correctly.
The lower bound is attained and the upper one is out by 37.3×Cheeger's inequality on nine graphs of about 40 vertices each: for the normalised Laplacian's λ₂, λ₂/2 ≤ φ ≤ √(2λ₂), where φ is the conductance the sweep cut actually achieves. Each row shows the two bounds as a bar and the measured conductance as a dot inside it. The lower bound is tight on the complete at a ratio of 1. The upper bound is loosest on the barbell — by a factor of 37.3 — which is the graph in the census with a real bottleneck, and therefore the shape the inequality is always quoted about. The square root is what makes it loose: it is the price of turning a spectral quantity into a combinatorial guarantee, and it is paid where the guarantee is wanted.10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph
Fig. 8 A bound that cospectral graphs share, around conductances they may not.
One graph, nudged by 10⁻¹², and 3 different partitionsThree seven-vertex cliques joined in a triangle by three single edges, one of whose conductances is raised by 0. When all three are equal the graph has a three-fold symmetry, λ₂ and λ₃ coincide — measured here at a gap of 1.72·10⁻¹⁵ — and there is no Fiedler vector: there is a plane, and every unit vector in it is an exact eigenvector. Eight runs on this graph with its edge weights nudged by a relative 10⁻¹² — four orders above the rounding, and far below anything anybody would call a difference in the data — return 3 distinct partitions, at conductances 0.0455. All of them are correct answers to the relaxation, and on a symmetric graph they are equally good ones. Which one a library returns is decided by its starting vector, and the site has an essay about a plane surviving what its vectors do not.14710131619110¹indexeigenvalue of Lan eigenvalue with no vectorλ₂0.35λ₃0.35gap1.7·10⁻¹⁵partitions found3best conductance0.045worst0.045two eigenvalues, one valueand the answer is not a function of the graph
Fig. 9 Eigenvectors that do not determine an answer, which is the other way this field’s methods underdetermine.
One real vector, 35 candidate cuts, and the best of them is number 18The Fiedler vector of the grid 6×6, 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.26795. 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.1 against a worst prefix of 1 — a factor of 10 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.06121824303610⁻¹1vertices on the smaller sideconductance of the prefix cut0.1, the best prefixthe rounding stepλ₂0.27cuts considered35best conductance0.1at k =18worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 10 A partition read from eigenvectors, which cospectral graphs do not share.
Every count recovered exactly, up to n = 15The number of spanning trees of the complete graph on n vertices, by Kirchhoff's theorem: the determinant of the Laplacian with one row and column deleted, which is nⁿ⁻² by Cayley's formula and is therefore a whole number known in advance. It is computed twice — in BigInt rationals, where the answer is exact, and by the site's own pivoted elimination in binary64. The filled curve is the relative error of the elimination, which never leaves the rounding level: worst 3.41·10⁻¹⁵ across the whole range, so the algorithm is backward stable at every size. The dashed curve is the spacing between consecutive doubles at the answer's own magnitude, relative to the answer. The error is committed by the format and not by the elimination, which is a distinction no residual can make.57911131510⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted11worst relative error3.4·10⁻¹⁵largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out
Fig. 11 The count these two graphs also share, being a product of their eigenvalues.
Resistance to 15 vertices, against an answer that is a ratio of integersEffective resistance from vertex 0 to every other vertex of the grid 4×4, computed twice in floating point — once by grounding a vertex and eliminating, once by summing (uₖᵢ − uₖⱼ)²/λₖ over the whole spectrum — and once in BigInt rationals, where for an unweighted graph the answer is exactly a ratio of two integers and there is no rounding anywhere. The curves are the relative errors of the two floating-point routes against that exact answer: at worst 4.75·10⁻¹⁶ for the elimination and 9.98·10⁻¹⁶ for the spectral sum, which use no arithmetic in common beyond the matrix they are both handed. Foster's theorem says Σ w·R over the edges is exactly n − 1 whatever the graph is; it comes to 15 against 15.1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination4.8·10⁻¹⁶worst, by spectrum10·10⁻¹⁶solve residual1.5·10⁻¹⁵Foster's sum15n − 115difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known
Fig. 12 A quantity computed from the whole spectrum, which cospectral graphs need not share.
One system, 30 ways to remove its kernel, and 898× between themA Laplacian is singular, so a solve has to remove its kernel, and the usual way is to delete one row and column — grounding a vertex, in the electrical reading. Which vertex is a free parameter that no account of the method mentions, and it is set by whichever index the code happens to drop. Every point here is one choice on the star 30: the condition number of the resulting positive definite matrix against the degree of the vertex removed. Grounding vertex 1, of degree 1, gives κ = 898; grounding vertex 0, of degree 29, gives 1 — a factor of 898 between two ways of solving the identical problem. The trend is that a high-degree vertex is the better ground, which has a reading: grounding a vertex fixes its potential, and fixing the potential of something the rest of the graph is strongly attached to constrains more of the graph.1611162126110¹10²10³degree of the grounded vertexcondition number of what is left1, the best choicea parameter nobody setsvertices tried30best κ1at degree29worst κ898at degree1spread898one row and column deletedand it matters which
Fig. 13 A property of a graph that the spectrum does not carry.
Same matrix, same arithmetic, 4.13× the fillGaussian elimination on the Laplacian of the grid 6×6, under five orderings, counting the edges that did not exist before. Eliminating a vertex removes it and joins its neighbours into a clique — the star–mesh transform, which is what the Schur complement of a Laplacian does — so fill is a set of edges rather than a set of nonzeros, and the matrix that remains is still a graph: symmetric, zero row sums, nonpositive off the diagonal, checked at every step and worst at 3·10⁻¹⁵. Minimum degree fills 71 edges against 293 for the worst ordering here, on a graph with 60 to start with. Nothing about the arithmetic differs between these five runs.05101520253035059118177236295vertices eliminatededges of fill so farminDegree: 71natural: 125reverse: 125random: 160maxDegree: 293fill, by orderingminDegree71natural125reverse125random160maxDegree293edges to start60eliminating a vertex makes a cliqueand the order decides how big
Fig. 14 Fill, which is a property of the graph and of an ordering, and is invisible in a spectrum.
How far a perturbation of size ε moves an eigenvalue, 8×8A log–log plot of eigenvalue movement against perturbation size. The symmetric case lies on a line of slope one; the non-symmetric case lies on a line of slope one eighth, and at a perturbation of ten to the minus sixteen it has already moved by a hundredth.10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹size of the perturbation ‖δA‖how far the eigenvalues moveJordan block, ε^(1/8)symmetric, ≤ ‖δA‖rounding error alone moves it to 10⁻²six seeds per symmetric point; Jordan is closed formsymmetry beats precision
Fig. 15 How far an eigenvalue moves when its matrix does, which is not the mechanism here.
The spectrum of C⁻¹T against T's own, n = 64, ρ = 0.8Two sorted spectra on a linear vertical axis. The unpreconditioned Toeplitz matrix spreads its eigenvalues across its whole range; the preconditioned operator puts 97% of them within a tenth of 1, with 0 below zero.08162432404856640123456789index, sortedeigenvalueT aloneC⁻¹Teigenvalues, not singular valuesfraction within 0.1 of 10.97eigenvalues below zero0λ_min of the preconditioner0.11the dashed line is 1, where the cluster formsthe solid line is zero
Fig. 16 A cluster of eigenvalues, which is what cospectrality is an exact version of.
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. 17 An eigenvector with no gap to define it.
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 An answer that is known, which the characteristic polynomials here are.
What a perturbation of 10⁻⁶ moves, against the gap it is applied acrossThree curves against the gap between two eigenvalues, both axes logarithmic. Two are flat; the third rises steeply as the gap closes and then levels off.10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻⁸10⁻⁵10⁻²gap between the two eigenvalueshow far it movedthe eigenvectorsthe eigenvaluestheir plane‖E‖ / gapone perturbation, three answerseigenvalue shift, spread over the sweep1plane angle, spread over the sweep1eigenvector angle, spread1.6·10⁵the dashed line is Davis–Kahan's ‖E‖/gaptwo of the three never noticed
Fig. 19 A gap deciding an eigenvector, which two cospectral graphs have identical versions of.
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. 20 A threshold deciding an integer, which is not what fails in this essay.
Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 21 The precision knob, which changes nothing about this result at any setting.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 22 The two errors, neither of which is present here.
Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ
Fig. 23 The identity that has nothing to say about an invariant that is missing.
Growth factor under partial pivoting to n = 40: the bound, the worst case, and realityGrowth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8
Fig. 24 A bound never attained, in the field that measured it first.
Jacobi sweeps on the 6×6 Hilbert matrixA plot of the off-diagonal norm against sweep number, falling from about one to ten to the minus seventeen in five sweeps, with the matrix shown at three stages beneath it.01234567810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹sweep‖off-diagonal‖eigenvalues, largest first1.6190.24240.016326.157·10⁻⁴1.257·10⁻⁵1.083·10⁻⁷κ = 1.5·10⁷‖VᵀV − I‖ = 1.9·10⁻¹⁵1.000.500.330.250.200.170.500.330.250.200.170.140.330.250.200.170.140.130.250.200.170.140.130.110.200.170.140.130.110.100.170.140.130.110.100.09as given1.620.050.00-0.040.00-0.000.050.240.000.010.00-0.000.000.000.000.00-0.00-0.00-0.040.010.000.020.000.000.000.00-0.000.000.00·-0.00-0.00-0.000.00·0.00after one sweep1.62······0.24······0.00······0.02······0.00······0.00after 8 sweepseach sweep is n(n−1)/2 rotationsthe trace is conserved
Fig. 25 The eigensolver whose agreement to 5·10⁻¹⁵ is not what this essay rests on.
122 steps to forget where it started, and λ₂ said 131A random walk on a sixty-vertex graph with two blocks joined at a density of 0.03, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 122 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.900071 from the walk matrix, and the number of steps that predicts is 131. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 9.22 steps.0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk
Fig. 26 A quantity determined by a spectrum, which cospectral graphs therefore share.
14 of 14 places survive the arithmetic and 3 survive one missing linkThe top 15 of a PageRank ranking on an eighty-page link graph, and how many of its 14 adjacent comparisons keep their order under three kinds of doubt. Perturbing the teleport vector at the rounding level moves every entry by at most 4.05·10⁻¹¹ and settles 14 of them. Moving α across the range everybody uses moves entries by 0.00123 and settles 11. Removing a single arc — one link that might or might not have been crawled — moves entries by 0.00443 and settles 3. The gaps between consecutive entries run from 6.28·10⁻⁵ to 0.00241, so the ordering is decided by the data at a scale ten orders above anything the arithmetic does. This is the one field on the site where the computation is not the weakest part of the answer.places settled, of 14the arithmetic14 of 14one missing link3 of 14α from 0.80 to 0.9011 of 14entries move by 4.05·10⁻¹¹entries move by 0.00443entries move by 0.00123three kinds of doubtcomparisons14smallest gap6.3·10⁻⁵largest gap0.0024arithmetic band4.1·10⁻¹¹one-link band0.0044α band0.0012the arithmetic settles nearly all of themthe data settles three
Fig. 27 A ranking, which depends on eigenvectors and is not shared.

Where this goes next

10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph Two Laplacians of one graph D − A and D^{-1/2}(D − A)D^{-1/2} 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. 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out A count that comes out of a determinant The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen. 14710131619110¹indexeigenvalue of Lan eigenvalue with no vectorλ₂0.35λ₃0.35gap1.7·10⁻¹⁵partitions found3best conductance0.045worst0.045two eigenvalues, one valueand the answer is not a function of the graph A partition decided in the last digit On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.

What links here

Computed from the collection, not written here: the essays that point at this one.

Reads more easily once this is understood

Essays that name this one as worth reading first.

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.

BipartiteCharacteristic polynomialCospectral graphsExact ground truthGraph invariantGraph laplacianNormalised laplacianSpanning tree