Numerical Linear Algebra
where the algebra stops being the arithmetic
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 on this site whose kernel is known before anything runs.
31 min read 28 figures Where the algebra stops being the arithmeticTwo routes to a numberExact ground truthMeasured, not asserted

Worth reading first: Rank is a decision · The condition number is an amplifier · A matrix that depends on its own eigenvalue.

Every matrix on this site so far has arrived as a matrix. It came from a discretisation, or from a measurement, or from a least-squares fit, and whatever produced it produced a rectangular array of numbers with a question attached: solve this, factorise this, tell me how sensitive it is.

A graph does not arrive that way. It arrives as a set of vertices and a set of pairs, with no arithmetic in it anywhere — a road network, a set of citations, the sparsity pattern of a matrix somebody else is trying to eliminate. There are no numbers to be sensitive about. The matrix is something built from the graph afterwards, by a rule, and there is more than one rule.

two blocks 40: 40 vertices, 223 edges, and a matrix built from themThe two blocks 40 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.458 and the largest computed zero is 4.26·10⁻¹⁶, a gap of 3.42·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 444.the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 1 Forty vertices in two loosely joined blocks, laid out at the second and third eigenvectors of the matrix built from them, with that matrix’s defining properties measured beside it.

That is the first thing this field changes. The second is what comes out at the end: not a number but a partition, a ranking or a count. A rounding error in the middle of a solve makes an answer slightly wrong. A rounding error in the middle of a count makes it a different count, and there is no continuum between five and six for the error to be small in.

The rule, and the property it has that nothing else here does

The Laplacian of a graph is L = D − A: the diagonal matrix of degrees, minus the adjacency matrix. Written out, its diagonal entry is how many edges meet at that vertex and its off-diagonal entry is minus one where there is an edge and zero where there is not.

Every row therefore sums to zero, and it does so exactly. Not to the rounding level — exactly. For an unweighted graph each row is a positive integer and a set of minus ones that count it, and the cancellation of integers in binary64 is exact because every one of those integers is representable and their sum is representable. The figure above measures it rather than asserting it, and the number printed is zero with no exponent after it.

This is worth stopping on, because nothing else in this collection has it. The Hilbert matrix’s inverse is known in closed form and its entries still have to be rounded to be stored. A null space computed from a factorisation is orthogonal to about 10⁻¹⁵. Here the kernel is the vector of ones, it is known before the matrix is built, and the matrix annihilates it in the arithmetic as well as in the algebra.

The quadratic form explains why. For any vector x,

xᵀLx = Σ over edges (i,j) of w(i,j) · (xᵢ − xⱼ)²

which is a sum over edges rather than over entries, is never negative, and is zero exactly when x is constant on every connected piece of the graph. That identity is the whole field in one line: L is positive semidefinite, its kernel is spanned by the indicator vectors of the connected components, and both facts are combinatorial statements wearing an algebraic coat.

The Laplacian is a Gram matrix, and its square root is free

There is a second way to write L that says something the first does not. Give every edge an arbitrary orientation and build the incidence matrix B, one row per edge, with √w in the column of the edge’s head and −√w in the column of its tail. Then

L = BᵀB

and the quadratic form identity above is nothing more than ‖Bx‖² written out.

So the Laplacian is a Gram matrix. On this site that is normally an alarm: forming AᵀA squares the condition number, and the whole least-squares field is about not doing it. A matrix handed over as a Gram matrix has already paid that price before anybody saw it, and no algorithm applied to it afterwards can get the digits back.

The situation here is the reverse, and the reversal is worth being precise about. B is not something that was formed and then squared; B is available for free, in closed form, from the edge list, at no arithmetic cost and with no rounding. Every entry of it is ±√w and its sparsity is two nonzeros a row. A least-squares problem with this design matrix can therefore be solved through a QR factorisation of B rather than through a factorisation of L, and the condition number that governs it is κ(B) rather than κ(B)² — which is exactly the trade the least-squares field spends four essays on, available here by construction because the object was combinatorial to begin with.

That is a general shape and it is worth naming: a matrix that comes from a structure often comes with its own square root, and the square root is the thing to compute with. The site meets it again in the Gramian of a linear system, where the factored form is what makes a reduction affordable, and in Cholesky-QR, where the same choice is made the wrong way round on purpose to see what it costs.

Two routes to one integer

If the kernel is spanned by component indicators then the number of zero eigenvalues is the number of connected components. That is a theorem, and it hands this site an unusually clean instance of a habit it runs on: the same integer, by two routes that share no arithmetic.

The first route is the spectrum. Diagonalise L, count the eigenvalues that are zero.

The second route is breadth-first search. Start at a vertex, walk to everything reachable, mark it, start again at the first unmarked vertex, and count how many times the outer loop ran. Nothing in that procedure adds, multiplies or compares two floating-point numbers. It reads the edge list. Its answer is not an approximation to the number of components; it is the number of components.

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. 2 Twenty eigenvalues of two ten-vertex paths joined by one edge, on a logarithmic scale so that the zero end is visible at all. One of them is below the threshold and the graph has one piece.

On the graphs this field builds, the two routes agree. A connected path of twenty gives one zero eigenvalue against one component, and the largest computed zero is 5.8·10⁻¹⁷ while the smallest eigenvalue above it is 0.0246 — a ratio of 4.2·10¹⁴. Two disjoint pieces give two and two, with a ratio of 3.1·10¹⁶. Three pieces give three and three at 5.9·10¹⁵.

Those ratios are what makes the agreement uninteresting. A quantity separated from its neighbour by fifteen orders of magnitude is not being decided by a threshold; it is being read off. Any cut anywhere in the empty fifteen decades returns the same integer.

Where it stops being a reading and becomes a decision

The interesting case is the one where the empty decades are not empty.

Take the same two ten-vertex paths and join them with a single edge whose conductance is not one but something small. The graph is connected at every positive weight — the edge is there, breadth-first search walks along it, and the combinatorial answer is one component whatever the number attached to that edge happens to be. The second eigenvalue, though, is about twice the conductance, and it slides down the axis as the conductance does.

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 10⁻⁸, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.02·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.26·10⁻¹⁷ and the smallest eigenvalue above the threshold is 2·10⁻⁹. 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.3·10⁻¹⁷smallest above it2·10⁻⁹ratio3.8·10⁷the graph is connectedat every stop of the slider
Fig. 3 The same graph with the joining edge at 10⁻⁸. The second eigenvalue is 2·10⁻⁹, still nine orders above the threshold, and the count is still one.

At a conductance of 10⁻⁸ the second eigenvalue is 2·10⁻⁹ and the threshold — 10⁻¹⁰ times the norm of L — is nine orders below it. The count is one, correctly. At a conductance of 10⁻¹⁰ the second eigenvalue is 2·10⁻¹¹, the threshold has not moved, and the count is two. The graph is connected. Breadth-first search says one. The spectrum says two, and the spectrum is not wrong about anything: it is reporting that this matrix is within 2·10⁻¹¹ of a matrix with two components, which is true and is a different statement.

This is rank is a decision arriving in a field where the number decided describes the object rather than the matrix. There, the threshold sorted singular values and the answer was how many columns a model had. Here the threshold sorts eigenvalues and the answer is how many pieces a road network has. The mechanism is identical and the consequence is not, because nobody argues about whether a road network has one piece or two.

And note where the crossover happens: at a conductance of about 10⁻⁹, which is seven orders above the unit roundoff. The decision is not being made at the rounding level. It is being made at a threshold somebody chose, and the choice is the whole of it.

What a closed form is worth here

Every family used in this field has a spectrum that is known, and the reason is a rule this site runs on rather than a convenience. A measurement taken on a random graph and checked against nothing is a measurement of the eigensolver.

The path on n vertices has eigenvalues 2 − 2cos(πk/n). The cycle has 2 − 2cos(2πk/n). The complete graph has one zero and n − 1 copies of n. The star has one zero, n − 2 copies of one, and a single n. Against the site’s own symmetric eigensolver these come back at worst 1.7·10⁻¹⁴, 2.6·10⁻¹⁴, 2.7·10⁻¹⁴ and 3.6·10⁻¹⁵ — which is what a Jacobi rotation sweep on a matrix of that norm should give, and is the check that the figures below are about graphs rather than about a routine.

The complete graph’s spectrum is worth a second look for what it says about the whole field. Every non-zero eigenvalue is n. There is no second-smallest eigenvalue distinct from the others, so there is no Fiedler vector and no preferred way to cut it — which is correct, because a complete graph has no preferred way to be cut. The algebra is not being coy; it is reporting a symmetry the object actually has, and a later essay in this anchor is about what a solver does when handed one.

The quadratic form is where the two halves meet

There is a temptation, on first meeting the Laplacian, to treat it as a matrix that happens to encode a graph, and to reach for the tools that work on matrices. That reading survives contact with the quadratic form for about one line.

xᵀLx = Σ w(xᵢ − xⱼ)² is a sum over edges. It has no entries in it and no indices that range over the whole vertex set at once. Computing it costs one pass over the edge list, which for a sparse graph is a fraction of the cost of forming a matrix–vector product the ordinary way — and, more to the point, it is what every argument in this field is made of. A cut is a vector of zeros and ones and its quadratic form is the number of edges crossing it. A spectral partition is the minimiser of that form over vectors that are not constant. A spectral sparsifier is a graph whose form matches another’s to within a factor.

So the object the field manipulates is the form, and the matrix is a way of writing it down. The figure above draws the graph laid out at its own second and third eigenvectors, which is not decoration: those are the two vectors that make the form as small as they can while staying orthogonal to the constant, so the picture is literally the answer the algebra gives when asked where the graph is loose.

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
Fig. 4 The second eigenvector of a barbell, sorted, with the conductance of every prefix cut beneath it. The eigenvector is real and the answer wanted is a subset, so something has to round.

What the diagonal is, when the edges have weights

Nothing above requires the edges to be unweighted, and most of the graphs in this field are not. A weight is a conductance rather than a count — larger means more strongly joined — and the degree on the diagonal is the sum of the conductances at that vertex rather than the number of edges. Every identity survives that generalisation unchanged, including the quadratic form and the kernel.

What does not survive is the exactness. A weighted Laplacian’s row sums are a cancellation of floating-point numbers rather than of integers, so they are zero to about one rounding of the largest weight rather than to zero. On the weighted graphs in this field that is 10⁻¹⁶ or so and nothing depends on the difference — but it is worth knowing which of the two situations a given figure is in, because the essays that use the exactness use it structurally. A solver that deflates the constant vector out of its iterates is relying on the constant vector being in the kernel; if it is only nearly in the kernel, the deflation leaks at the rate of the leak.

The other thing the weights change is what a threshold means. An unweighted graph’s Laplacian has integer entries and its norm is a small multiple of the largest degree, so a relative threshold is a threshold in units of “one edge”. A weighted graph can have conductances spanning ten orders, and then the relative threshold is measured against the largest of them and says nothing about the smallest — which is how the bridge above ends up on the wrong side of a cut nobody moved.

What is different about this field, stated once

Every field before this one asks how wrong a number is. The error field separates that wrongness into the algorithm’s contribution and the problem’s; the machine field asks how many answers there are; the rank essays ask what a threshold decides.

This field asks a different question, and it is not a refinement of any of those: what does a continuous computation decide when the answer it is asked for is discrete?

The answers it will produce are a partition of the vertices, an order on them, a count of pieces, a count of spanning trees. None of those has a small perturbation. A partition that is wrong is a different partition. A count that is wrong is a different integer. So the question of how big the error is has no meaning, and the question that replaces it is whether the answer is a function of the graph at all — which, on the evidence assembled over the next several essays, is quite often no.

The Laplacian’s exactly zero row sums are the one thing in the field that is not like that. They are an identity that survives the arithmetic intact, and every construction here leans on them: the grounded solve that computes an effective resistance, the deflation that makes an iterative solver converge, the projection that removes the constant vector before a partition is read. It is the one piece of exact ground truth the field is given for free, and it is worth knowing that the second Laplacian — the one the next essay is about — does not have it.

At other settings

grid 6×6: 36 vertices, 60 edges, and a matrix built from themThe grid 6×6 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.2679 and the largest computed zero is 2.36·10⁻¹⁶, a gap of 1.13·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 120.the matrix, measuredvertices36edges60‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.27laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 5 A grid, whose second and third eigenvectors are the two lowest sine modes, so the spectral layout recovers the grid.
barbell 12: 24 vertices, 133 edges, and a matrix built from themThe barbell 12 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.1443 and the largest computed zero is 8.24·10⁻¹⁶, a gap of 1.75·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 292.the matrix, measuredvertices24edges133‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.14laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 6 A barbell: two cliques joined by one edge, which the layout separates completely.
preferential 60: 60 vertices, 117 edges, and a matrix built from themThe preferential 60 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.5861 and the largest computed zero is 4.82·10⁻¹⁷, a gap of 1.22·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 248.the matrix, measuredvertices60edges117‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.59laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 7 A preferential-attachment graph, whose degrees span an order of magnitude.
2 components: 32 vertices, 31 edges, and a matrix built from themThe 2 components 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 2 zero eigenvalues count the connected components, which breadth-first search also puts at 2; the smallest non-zero eigenvalue is 0.03843 and the largest computed zero is 1.67·10⁻¹⁶, a gap of 2.3·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 124.the matrix, measuredvertices32edges31‖L·1‖∞0zero eigenvalues2components, by search2λ₂6.1·10⁻¹⁷laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 8 Two components on purpose, where the count of zero eigenvalues is two.
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. 9 The complete graph, whose only non-zero eigenvalue is n, repeated.
The count says 2 pieces and the graph has 1The Laplacian spectrum of two ten-vertex paths joined by a single edge of conductance 10⁻¹⁰, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.02·10⁻⁹, and the number of eigenvalues below it is the spectral count of connected components: 2. Breadth-first search, which performs no arithmetic on any weight, says 1. The largest computed zero is 2·10⁻¹¹ and the smallest eigenvalue above the threshold is 0.09789. 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 it2components, by search1largest computed zero2·10⁻¹¹smallest above it0.098ratio4.9·10⁹the graph is connectedat every stop of the slider
Fig. 10 The bridge at 10⁻¹⁰, where the spectral count says two and the graph has one piece.
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 10⁻⁴, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.02·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 9.42·10⁻¹⁷ and the smallest eigenvalue above the threshold is 1.999·10⁻⁵. 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 zero9.4·10⁻¹⁷smallest above it2·10⁻⁵ratio2.1·10¹¹the graph is connectedat every stop of the slider
Fig. 11 And at 10⁻⁴, where the second eigenvalue is well clear of the threshold.
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. 12 The inequality that connects the second eigenvalue to the best cut, on nine graphs at once.
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. 13 The same threshold argument in the field it was first made in, where the integer decided is a rank.
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. 14 An eigenvalue gap deciding an eigenvector, which is the continuous version of the decision here.
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. 15 The site’s other exactly known answer, against which a floating-point solve is measured.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−1.00flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.091rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 16 A spectrum with no gap anywhere, which is the situation a component count is never in.
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. 17 The two errors this site separates everywhere, in the field that named them.
How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 18 The amplifier that belongs to the problem rather than to the algorithm.
QᵀQ from classical Gram–Schmidt and from Householder on the 8×8 Hilbert matrixTwo eight-by-eight tables of QᵀQ. The upper one has ones on the diagonal and entries as large as one off it; the lower one is the identity to three decimal places everywhere.A = H8 · κ = 1.5·10¹⁰ · both factorisations reconstruct A to 6·10⁻¹⁷the diagonal is 1 in both — every column is a unit vector either way1.000000000001.000000000001.000000000001.000000000001.00000.002-0.002000001.0000.125-0.13300000.0020.1251.000-1.0000000-0.002-0.133-1.0001.000classical Gram–Schmidt1.000000000001.000000000001.000000000001.000000000001.000000000001.000000000001.000000000001.000Householderclassical ‖QᵀQ − I‖1.4Householder ‖QᵀQ − I‖1.4·10⁻¹⁵largest off-diagonal 1 against 3.1·10⁻¹⁶length is not angle
Fig. 19 Orthogonality as a measured number rather than an adjective.
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. 20 How far an eigenvalue moves when its matrix does, which is what a spectral count depends on.
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. 21 The symmetric eigensolver this field uses, converging on the off-diagonal norm.
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. 22 What happens to an eigenvector when its eigenvalue has no gap, which the complete graph has none of.
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. 23 The site’s precision knob, on a solve rather than on a graph.
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. 24 The identity every measurement here is eventually reported against.
A randomised rank-k solve, 4 seeds a rankRelative error against the rank kept, on a logarithmic vertical axis, with a vertical bar at each rank spanning the seeds. The band is 1.68 wide at rank 8, where the method is at its worst, and 1.004 wide at rank 20, where it is at its best. The same computation on the same data returns a different answer each time.0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.7spread at rank 201best median error0.15widest where the method is worstand the bound does not say so
Fig. 25 A rank that is a band rather than a number, which a component count also is.
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. 26 A bound never attained, in the field that measured it first.
Loss of orthogonality against condition number, in binary64A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.110²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖QᵀQ − I‖classicalmodifiedHouseholderκ²uκu8×8, eight seeds per κ, binary64all three reconstruct A
Fig. 27 Loss of orthogonality as a curve, which is the site’s oldest measured claim.
Conjugate gradients at κ = 104, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound119 steps40×40, spectrum spread evenly in logbound permits 1417
Fig. 28 An iteration whose rate is a spectral quantity, which is what the walk essays measure here.

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. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap. 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 An answer that is known Almost every demonstration of numerical error estimates the error by computing the same thing more carefully. The Hilbert matrix does not need that: its inverse is a closed form in integers, so the true answer is available exactly and the error is measured rather than approximated.

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.

Adjacency matrixAlgebraic connectivityConnected componentsExact ground truthGraph laplacianNull spaceQuadratic formRank is a decision