Numerical Linear Algebra
where the algebra stops being the arithmetic
The matrix that is a 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.
34 min read 31 figures Where the algebra stops being the arithmeticIdentical algebra, different arithmeticMeasured, not asserted

Worth reading first: A matrix with no numbers in it · The units the matrix is measured in · A matrix that depends on its own eigenvalue.

A graph does not determine a matrix. It determines several, and the two that matter are built from the same degrees and the same edges by rules that differ in one diagonal scaling.

The combinatorial Laplacian is L = D − A. The normalised Laplacian is 𝓛 = D^{-1/2} L D^{-1/2}, which is the same matrix conjugated by the square roots of the degrees. Written entry by entry, 𝓛 has ones on the diagonal and −1/√(dᵢdⱼ) where there is an edge.

The scaling is small enough to look like bookkeeping and it is not. A conjugation by a diagonal matrix is a similarity only when the same matrix appears on both sides in inverse pairs, and it does not here: D^{-1/2}LD^{-1/2} is a congruence, not a similarity. Congruences preserve the number of positive, negative and zero eigenvalues — inertia — and preserve nothing else about the spectrum. So the two matrices have the same rank and the same number of components, and no relationship at all between their eigenvalues beyond that.

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. 1 Nine graphs, each with the bounds Cheeger’s inequality puts around its conductance and the conductance the sweep actually achieved. The inequality is stated for the normalised eigenvalue, and this is the reason.

The obvious guess, and what it costs

The guess everybody makes on meeting 𝓛 is that it is L divided by a degree — that on a graph whose degrees are all d, 𝓛 is exactly L/d, so on a graph whose degrees vary, 𝓛 must be L divided by something between the smallest and the largest.

The first half is true. On a d-regular graph D^{-1/2} is d^{-1/2} times the identity, the conjugation commutes with everything, and the spectra are proportional with constant d exactly. Every cycle, every hypercube and every complete graph in this field satisfies it.

The second half is false, and it is worth having the numbers.

graph            λ₂(L)     λ₂(𝓛)     ratio    degrees
grid 6×7         0.19806   0.06297    3.15     2 to 4
preferential 60  0.58610   0.19664    2.98     2 to 17
barbell 10       0.16905   0.01864    9.07     9 to 10
two blocks 60    2.55381   0.15383   16.60    10 to 22

The barbell is the clearest refutation. Its degrees are nine and ten — as close to regular as an irregular graph gets — and the ratio between the two second eigenvalues is 9.07, which is outside that range and not by a little. The two-block graph has degrees from ten to twenty-two and a ratio of 16.6, above every degree it has.

The reason is that λ₂ is not a function of any one vertex. It is a minimum of a Rayleigh quotient over a subspace, and the conjugation changes both the numerator and the constraint the minimisation runs under, in different ways at different vertices. There is no scalar to divide by because the two minimisations are not the same minimisation.

There are three names and two matrices

A third object is in circulation and it is worth placing, because it is the one a probabilist writes down and it is not a third matrix.

The random-walk Laplacian is D⁻¹L = I − D⁻¹A, whose second factor is the transition matrix of a walk that steps to a uniformly chosen neighbour. It is not symmetric, so it has no business in an essay about eigenvalues of real symmetric matrices — except that

D^{1/2} (D⁻¹L) D^{-1/2}  =  D^{-1/2} L D^{-1/2}  =  𝓛

which is a similarity, not a congruence. So D⁻¹L and 𝓛 have exactly the same eigenvalues, real, in [0, 2], and the two differ only in whether the eigenvectors carry a factor of D^{1/2}.

That is the whole relationship between the three, and it is asymmetric in a way worth stating plainly. The normalised Laplacian and the random-walk Laplacian are the same operator seen in two bases. The combinatorial Laplacian is a different operator. Naming all three “the Laplacian” is how a statement proved about one comes to be quoted about another, and the essays about the walk rely on the similarity above at every step: they compute a symmetric matrix’s spectrum with the site’s own symmetric eigensolver and read the answer as a property of a non-symmetric one.

There is a practical consequence too. A walk on a graph with a degree-one vertex has a transition matrix with an entry of 1 in it, and a walk on a graph with a degree-thirty vertex has entries of 1/30 — a range of thirty in a matrix whose symmetric cousin has every diagonal entry equal to one. The symmetric form is the better conditioned object to compute with and the non-symmetric one is the better object to think with, which is an ordinary situation and is why the change of basis is worth knowing rather than worth avoiding.

Which cut each of them is looking for

The useful way to tell them apart is to ask what each one’s second eigenvector is trying to do.

For the combinatorial Laplacian, minimising xᵀLx over vectors orthogonal to the constant and of unit length is a relaxation of the ratio cut: minimise the number of edges crossed, divided by the number of vertices on the smaller side. The denominator counts vertices.

For the normalised Laplacian the same minimisation, after the change of variable y = D^{1/2}x, is a relaxation of the conductance: minimise the weight crossed, divided by the total degree on the smaller side. The denominator counts edge endpoints.

Those are different objectives, and which is wanted depends entirely on what the vertices are. If they are machines to be given equal amounts of work, the count is right. If they are pages in a link graph and the question is how likely a random surfer is to cross, the volume is right. Neither is the correct one; they are answers to two questions that happen to have the same shape.

On a graph with equal degrees the two objectives coincide, which is why the distinction can be carried for a long time without ever being made. On the preferential-attachment graph here, the two sweeps return different partitions — one cuts after 29 vertices and the other after 30 — and the conductances they reach are 0.2321 and 0.2389. The combinatorial one wins on conductance, which is not what it was minimising, and there is no contradiction: a relaxation optimises its own objective and the sweep afterwards is a heuristic in both cases.

One real vector, 59 candidate cuts, and the best of them is number 29The Fiedler vector of the preferential 60, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 0.5861. 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 = 29 at a conductance of 0.2321 against a worst prefix of 1 — a factor of 4.31 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.01020304050601vertices on the smaller sideconductance of the prefix cut0.232, the best prefixthe rounding stepλ₂0.59cuts considered59best conductance0.23at k =29worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 2 The sweep of the combinatorial second eigenvector on a preferential-attachment graph. The normalised one produces a different curve and a cut one vertex along.

The inequality is about one of them, and only one

The result that makes spectral partitioning more than a heuristic is Cheeger’s inequality: for the normalised Laplacian’s second eigenvalue and the graph’s conductance φ,

λ₂/2  ≤  φ  ≤  √(2λ₂)

Both halves are theorems. The left one says a small eigenvalue is evidence that a good cut exists; the right one says a good cut cannot exist without a small eigenvalue. Together they say that the relaxation is not merely suggestive — it is within a square root of the truth.

Substitute the combinatorial eigenvalue and the left half is false, spectacularly:

graph            λ₂(L)/2    φ measured    out by
complete 20      10.00      0.5263        19.0×
two blocks 60     1.2769    0.08982       14.2×
grid 6×7          0.09903   0.09859        1.0×
star 30           0.5       1.0           holds

On the complete graph the bound claims the conductance is at least ten, and every cut of a complete graph has conductance about a half. The bound is out by nineteen and the failure is not marginal.

This is not a subtlety about which convention a textbook uses. It is a statement about which matrix the theorem is a theorem for, and the site has a name for this shape: a condition number scaling cannot move makes the same point about a diagonal rescaling that changes a computed quantity while changing nothing about the problem. The difference here is that both matrices are legitimate objects and both are used, so the mistake is not applying a bound to a badly scaled matrix — it is applying a bound to the wrong matrix.

The upper half is the more interesting one and the next essay in this anchor’s neighbour is about how loose it is, which is loosest exactly where it is quoted.

What the two share, and it is not much

They agree about the kernel. Both are positive semidefinite, both have rank n minus the number of components, and both have the component indicators — scaled, in the normalised case — spanning the kernel. That is the inertia, and it is what a congruence preserves.

They agree about nothing else. The combinatorial spectrum has no upper bound beyond twice the maximum degree; the normalised one is contained in [0, 2] for every graph, with 2 attained exactly when the graph is bipartite. That last fact is a genuine capability the combinatorial matrix does not have: a bipartite graph’s normalised spectrum is symmetric about 1 and its largest eigenvalue is exactly 2, so the normalised Laplacian detects bipartiteness and the combinatorial one does not. The cospectral pair at the end of this field is the sharpest instance: two graphs with identical combinatorial spectra, one of which contains a triangle and one of which is bipartite, separated at once by the other matrix.

The bounded spectrum is also why every account of random walks uses the normalised one. The walk matrix D⁻¹A is not symmetric, but D^{1/2}(D⁻¹A)D^{-1/2} = D^{-1/2}AD^{-1/2} = I − 𝓛 is, so the walk’s eigenvalues are one minus the normalised Laplacian’s, are real, and lie in [−1, 1] where a probabilist expects them. The rate is the second eigenvalue is that substitution used in earnest.

A third question neither of them answers

It is worth saying what the choice between these two does not settle, because the framing above can make it look as though picking the right Laplacian picks the right cut.

Both objects hand back a real vector, and both leave the rounding of that vector into a subset entirely open. The sweep — sort the entries, take every prefix, keep the best — is a heuristic applied afterwards, and it is the same heuristic in both cases. Cheeger’s inequality bounds what the best prefix of the normalised eigenvector’s sweep achieves, so it covers the heuristic as well as the relaxation; nothing analogous is available for the combinatorial one, and the ratio cut it relaxes is NP-hard to optimise exactly.

So the two matrices differ in which objective they relax and in how much is known about what happens next, and they do not differ at all in the step where a continuous answer becomes a discrete one. The vector that has to be rounded is about that step, and it applies to both.

The exactness is not shared either

The previous essay made a point of the combinatorial Laplacian’s null vector: L·1 is exactly the zero vector, because each row is a cancellation of integers, and the measurement returns 0 with no exponent.

The normalised Laplacian’s null vector is D^{1/2}·1, and it is not exact. Building it costs n square roots, each correctly rounded and none of them exact; the matrix entries carry two more square roots apiece. Measured on four graphs, ‖𝓛 D^{1/2}1‖∞ comes to between 2.2·10⁻¹⁶ and 3.8·10⁻¹⁵ — which is the rounding level and is not zero.

Nothing in these essays fails because of that, and the point of the measurement is not that something breaks. It is that a property the first Laplacian has structurally becomes, in the second, a property that holds to the rounding level — and those are different kinds of statement. An algorithm that deflates a known null vector out of every iterate is exact in one case and leaky in the other, at a rate that is tiny and nonzero, and whether the difference matters is a question about how long the iteration runs rather than a question about the graph.

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. 3 The graph the table above is measured on: degrees from two to seventeen, which is where the two matrices disagree most.

What the two cost to solve with

The scaling changes the conditioning as well as the spectrum, and not always in the direction the word “normalised” suggests.

Taking κ⁺ to be the largest eigenvalue over the smallest non-zero one — the condition number of the matrix restricted to the subspace anything is actually solved on:

graph          κ⁺(L)    κ⁺(𝓛)    λmax(L)   λmax(𝓛)
star 30        30.0      2.00      30.00     2.000
preferential   31.9      9.14      18.69     1.797
grid 6×7       38.0     31.8        7.53     2.000
barbell 10     70.0     64.0       11.83     1.192
path 30       364       341         3.99     2.000
hypercube 5     5.0      5.00      10.00     2.000

The normalised matrix is never worse conditioned here and is sometimes far better: on the star it is fifteen times better, because the whole of the combinatorial matrix’s condition number is the ratio between the hub’s degree and a leaf’s, and the scaling removes exactly that. On the regular graph the two are identical, as they must be. On the path — the worst-conditioned graph in the table by an order of magnitude — the improvement is seven per cent, because a path is nearly regular and its conditioning comes from its length rather than from its degrees.

So the scaling is doing what a diagonal equilibration does anywhere on this site: it removes the part of the conditioning that is about the units and leaves the part that is about the problem. On a graph whose degrees are all similar there is nothing to remove. The scaling essays make the general version of that argument, and the graph case is the cleanest instance the site has, because here the “units” are a degree and are therefore known exactly rather than guessed at.

The upper bound of 2 is the other half of it, and it is not an empirical observation: every normalised Laplacian on every graph has its spectrum inside [0, 2]. So κ⁺(𝓛) is always at most 2/λ₂(𝓛), and the entire conditioning of the normalised object is carried by one number — the same number Cheeger’s inequality is about. That does not happen for the combinatorial one, whose largest eigenvalue is somewhere between the maximum degree and twice it and therefore grows with the graph.

Which to use

The honest summary is short, and it is a modelling question rather than a numerical one.

If the vertices are the units and they should be balanced by count, the combinatorial Laplacian is the right object. Load balancing across processors, partitioning a mesh so each piece has the same number of elements, any application where a vertex is a thing that costs the same as any other vertex.

If the edges are the units and the question is about flow, the normalised one is right. Random walks, clustering where a high-degree vertex is genuinely more important, anything where Cheeger’s inequality is going to be quoted.

And if the graph is regular the question does not arise, which is why so much of the literature can be read without noticing that there was one.

What is not defensible is computing one and quoting a result about the other, and the reason that happens is that the two objects have the same name, the same picture, and second eigenvalues that look interchangeable until somebody measures both on the same graph.

At other settings

The lower bound is attained and the upper one is out by 21.5×Cheeger's inequality on nine graphs of about 24 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 21.5 — 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. 4 The same census on smaller graphs, where the bounds are wider apart.
The lower bound is attained and the upper one is out by 61.2×Cheeger's inequality on nine graphs of about 64 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 61.2 — 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⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph
Fig. 5 And on larger ones, where every bar has moved left and none has changed which end is tight.
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 The star, the one graph in the census whose two λ₂ are equal, at 1 exactly.
barbell 10: 20 vertices, 91 edges, and a matrix built from themThe barbell 10 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.169 and the largest computed zero is 6.94·10⁻¹⁶, a gap of 2.44·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 204.the matrix, measuredvertices20edges91‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.17laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 7 The barbell, whose degrees are nine and ten and whose two λ₂ are nine times apart.
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. 8 A regular graph, where the two matrices are one matrix and a constant.
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. 9 The sweep on a grid, where the two objectives choose the same cut.
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 0.01, 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 6.99·10⁻¹⁷ and the smallest eigenvalue above the threshold is 0.001891. 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 zero7·10⁻¹⁷smallest above it0.0019ratio2.7·10¹³the graph is connectedat every stop of the slider
Fig. 10 The spectrum of a graph with a weak join, where the second eigenvalue is the join.
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. 11 What the degrees do to a different quantity: the conditioning of a solve, on the same star.
What two lines of scaling are worth: the same quadratic in nine systems of unitsThe forward error against the closed form for an overdamped chain of 8 masses, before and after Fan–Lin–Van Dooren scaling. The unscaled curve runs 7.49·10⁻¹⁴ to 0.001258 — every digit gone by the far end — and the scaled one runs 1.26·10⁻¹³ to 8.23·10⁻¹⁴, flat to within a factor of 2.01. The scaling is γ = √(‖K‖/‖M‖) and δ = 2/(‖K‖ + γ‖C‖), computed from three norms and nothing else, and the map back is λ = γμ with no rounding in the statement. Flatness is the half that matters: after scaling every stop of the sweep IS the same problem, so there is nothing left for the change of units to do.0246810⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹log₁₀ γ, the change of unitsforward erroras writtenafter scalingone change of variableunscaled, worst0.0013scaled, worst1.7·10⁻¹³orders recovered10scaled coefficient spread4.5the answer was never the problemthe units were
Fig. 12 A diagonal scaling recovering accuracy in the field that first measured what one costs.
Two condition numbers of one 8×8 system, as its rows are put into different unitsFour curves against the spread of the row units, in decades. κ_∞ of the scaled matrix rises from 9.83 to 1.9·10¹⁰ while the componentwise condition number stays at 6.98 throughout — the same system, the same solution, and one of the two numbers is a fact about the units. Hilbert's two numbers are drawn flat beside them at 3.4·10¹⁰ and 1.2·10¹⁰: a matrix whose sensitivity no scaling repairs.0246810110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ_∞(DA)cond(DA)Hilbert κ_∞Hilbert condone system, two numbersκ_∞ at no spread9.8κ_∞ at 10 decades1.9·10¹⁰cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it
Fig. 13 Condition numbers that move when the units do, which is the same objection in another field.
What each way of eliminating a constraint inherits, over five decades of κ(A)The same system solved twice, at 8 unknowns and 3 constraints with κ(H) = 100. The range-space method forms S = AH⁻¹Aᵀ and inherits κ(S), which rises from 12.99 to 3.981·10¹⁰ — the square of κ(A), for the reason the normal equations square it. The null-space method solves with the reduced Hessian ZᵀHZ, whose condition number is 21.13 at the start of the sweep and 21.13 at the end: it does not contain κ(A) at all. The two forward errors, measured against a solution computed in BigInt rationals, follow their own condition numbers: 5.314·10⁻⁶ against 5.788·10⁻¹² at the far end. Both methods are correct and one of them is usable.01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares
Fig. 14 Two routes that are the same algebra and different arithmetic.
The 14 eigenvalues of a saddle-point matrix with 10 unknowns and 4 constraints, inside their closed-form bracketsK = [[H, Aᵀ], [A, 0]] with κ(H) = 100 and κ(A) = 100. The shaded bands are the Rusten–Winther brackets, computed from four numbers — the extreme eigenvalues of H and the extreme singular values of A — before the matrix was assembled: negative eigenvalues in [-0.995, -10·10⁻⁵] and positive ones in [0.01, 1.62]. The marks are the computed spectrum. There are exactly 10 above zero and 4 below, which is Sylvester's law of inertia and not a property of this matrix: K is congruent to blkdiag(H, −AH⁻¹Aᵀ), both blocks are definite, and congruence preserves signs. The two groups are separated by a gap containing zero, at a ratio of 39.3 between the innermost positive eigenvalue and the innermost negative one.-1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue4 negative10 positivecounted before it was formedpositive10negative4at zero0innermost ratio39the zero block is a theoremand so is the count either side of it
Fig. 15 Inertia, the quantity a congruence preserves and this essay leans on.
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. 16 How far an eigenvalue moves when the matrix does, which decides how close two λ₂ have to be.
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. 17 A spectrum with no gap, which the complete graph’s is an extreme case of.
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. 18 An eigenvector decided by a gap, which is the mechanism behind the partition essays here.
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. 19 The two errors, in the field that separated 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. 20 The amplifier that belongs to the problem, which a rescaling does not move.
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. 21 An answer that is known, against which a solve is measured rather than estimated.
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. 22 Orthogonality printed as a number, which is the site’s habit applied to an adjective.
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 mantissa on a slider, on a solve rather than on a graph.
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. 24 The loss of orthogonality, measured rather than described.
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. 25 A threshold deciding an integer, which is what a component count also is.
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. 26 The eigensolver both spectra in this essay were computed with.
How close Hager's estimate is to the true κ₁, over 200 seeded 8×8 matricesFive bars. The estimate is exactly the true condition number on 81% of the sample and inside ten per cent on 87%; the worst underestimate in the whole sample returns 38% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.each bar is a percentage — of the sample, or of the true condition numberexactly right80.5%inside 10%87.0%inside a factor of 287.0%worst in the sample, ×10037.7%the constructed matrix, ×1007.7%usually exactexact share0.81worst of the sample0.38the constructed matrix0.077a routine that is right most of the timeand never wrong in the safe direction
Fig. 27 An estimate with a spread, in the field about what an estimate is worth.
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. 28 The identity every measurement here reports against.
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. 29 A bound that is never attained, which the upper half of Cheeger’s is a graph-theoretic version of.
Two perturbation bounds and the error that was measured, on a 8×8 matrix spread over 8 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 4·10⁷ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement
Fig. 30 An error measured entry by entry rather than in a norm.
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. 31 An iteration whose rate is a spectral quantity of the matrix it was handed.

Where this goes next

the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero 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. 10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁸cond(A, x)4.8ratio of the bounds4·10⁷both curves above the data are boundsand only one of them is a measurement A condition number scaling cannot move Skeel's componentwise condition number is invariant under any row scaling — exactly, before any norm is taken, because two diagonal factors cancel entry by entry. It is never larger than the normwise one and can be arbitrarily smaller, and the ratio between them is a diagnostic for which kind of ill-conditioning a matrix has. 0246810110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ_∞(DA)cond(DA)Hilbert κ_∞Hilbert condone system, two numbersκ_∞ at no spread9.8κ_∞ at 10 decades1.9·10¹⁰cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it The units the matrix is measured in One linear system, written twice. The rows of the second are the rows of the first in different units, the solution is identical to the last bit, and the condition number has moved by eight orders of magnitude. One of those two numbers is a fact about the problem and the other is a fact about the notation.

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.

Algebraic connectivityConductanceDegree sequenceDiagonal scalingGraph laplacianNormalised laplacianQuadratic formSimilarity transformation