An eigenvector that must not change sign

Perron’s theorem is one of the few statements in linear algebra with no qualifications in it. If A is a nonnegative matrix whose graph is strongly connected, then its spectral radius is an eigenvalue, it is simple, and its eigenvector can be chosen with every entry strictly positive.

Not non-negative. Strictly positive: no entry is zero, and the theorem says so for every such matrix, of every size, with no condition on conditioning or spacing.

A family where the entries have to be small #

The theorem is about real numbers and the computation is not performed in real numbers, so the question is whether a matrix exists on which the two part company. It does, and it is not contrived.

Take a clique of twelve vertices and attach a path of length t to one of them. The Perron root of the adjacency matrix is 11.007688 — just above the clique’s own 11, because the tail perturbs it slightly. The eigenvector is large on the clique and decays along the tail, and the decay is geometric with ratio about one over the Perron root: each step out along the tail divides the entry by roughly eleven.

Eleven a step is a decade a step. After sixteen steps the entries are 10⁻¹⁶ of the largest, which is where binary64’s relative resolution runs out.

tail length    smallest entry    entries below zero    of
18              6.5·10⁻²⁰              0                30
24             −1.5·10⁻²⁰              4                36
30             −1.0·10⁻²⁰              6                42
34             −1.0·10⁻²⁰             10                46

At a tail of eighteen every entry is still positive, and the smallest is 6.5·10⁻²⁰ — already subnormal, which is a separate story below. At twenty-four, four entries have crossed zero. At thirty-four, ten have.

What has gone wrong, precisely #

Nothing has gone wrong with the eigensolver. The eigenvalue is accurate to fourteen digits and the residual ‖Ax − ρx‖ relative to ‖A‖‖x‖ is at the rounding level. The vector returned is an excellent approximation to the true eigenvector in every norm anybody measures it in.

What has happened is that the true eigenvector’s smallest entries are 10⁻²⁰ times its largest, and an approximation accurate to a relative 10⁻¹⁶ of the vector’s norm has absolute error 10⁻¹⁶ in every entry — which is ten thousand times larger than the entries at the far end of the tail. Those entries are not approximated at all; they are noise, and noise has a sign.

This is the site’s oldest distinction wearing new clothes. A norm-wise error bound says nothing about the small entries of a vector, and an error measured entry by entry is the quantity that would have caught it. Every gate in this collection that checks an eigenvector checks a norm.

The theorem is not wrong and the computation is not wrong #

It is worth being careful about what is being claimed, because there is a tempting and incorrect reading.

The theorem is a statement about the exact eigenvector of the exact matrix, and it is true. The computed vector is an accurate approximation in the norm it was computed to, and it is fine. The two statements are compatible because the property in question — every entry strictly positive — is not a property that survives a norm-wise approximation.

That is a general point about which properties are robust. Positivity of a large entry survives any approximation with relative error below one. Positivity of an entry that is 10⁻²⁰ of the norm survives nothing. A theorem whose conclusion is about the sign of an arbitrarily small quantity cannot be checked numerically at all, and the honest statement of it in floating point is: every entry above the noise floor is positive, and below it there is nothing to say.

The numbers below the smallest one #

The entries here go subnormal, and it is worth noting because it is a second effect layered on the first.

Binary64’s smallest normal number is about 2.2·10⁻³⁰⁸, so 10⁻²⁰ is nowhere near underflow. What is relevant is the gradual loss of significance that happens to a quantity computed as a difference of larger ones: an entry of 10⁻²⁰ arrived as the sum of products of entries of order one, and its own accuracy is 10⁻¹⁶ absolute regardless of how small it is. It has no correct digits at all.

Extending the tail further does not make the situation worse in any measurable way — the smallest entry stops falling and sits at around 10⁻²⁰, which is where the noise floor is. That plateau in the table above is the noise floor being measured directly: entries below 10⁻²⁰ are not being computed, they are being generated.

The same effect on a graph nobody constructed #

The lollipop is built to make the point, so it is fair to ask whether the effect needs building.

It does not. What it needs is a graph whose Perron vector spans more than sixteen orders of magnitude, and that requires only a periphery a dozen or so steps from a dense core. Any of these produce it: a citation network with a dense recent core and long chains of older references; a road network with a city and a rural tail; a web crawl with a hub and a long chain of paginated archives; a mesh with a refined region and a coarse far field.

The general rule is quick to state. The Perron vector decays roughly as ρ⁻ᵈ with distance d from the core, where ρ is the Perron root. So the number of steps to the noise floor is about 16 ÷ log₁₀ ρ: sixteen steps for a core of degree eleven, thirty-two for a core of degree four, eight for a core of degree a hundred.

The denser the core, the shallower the periphery has to be for this to bite. A social graph with a core of degree a thousand puts every vertex more than five steps out below the floor — which is most of the graph.

The bound that is proved #

Beside the entries, the figure prints something this site almost never has: an enclosure of the answer that is a theorem rather than an estimate.

The Collatz–Wielandt characterisation says that for any strictly positive vector x, the Perron root lies between the smallest and largest of the ratios (Ax)ᵢ/xᵢ:

min (Ax)ᵢ/xᵢ   ≤   ρ(A)   ≤   max (Ax)ᵢ/xᵢ

That is a two-sided bound, it holds for every positive x rather than for a good one, and it costs one matrix–vector product. Neither half is asymptotic and neither carries an unknown constant.

Run on the same graph, starting from a random positive vector and taking power steps:

step    lower bound      upper bound      width
 1       0.559190        25.351571        2.5·10¹
40      11.0075678303    11.0076877614    1.2·10⁻⁴

After forty products the root is known to lie in an interval of width 1.2·10⁻⁴ around 11.0077, and that is not a statement about how well the iteration has converged — it is a statement about where the answer is.

Why that is rare #

Almost every error bar on this site is an estimate. A condition estimate is a lower bound with a probability attached and can be fooled by a constructed matrix. A residual is a computable quantity that bounds the backward error and says nothing about the forward one without a condition number nobody has. A randomised trace estimate has a variance rather than an interval.

The exceptions are interval arithmetic, which pays for its rigour in width, and this. Collatz–Wielandt is free, tight, and applies to a large class of matrices — every nonnegative one, which includes every adjacency matrix, every stochastic matrix and every Google matrix.

The catch is in the hypothesis: x must be strictly positive. That is why the assertion in this field refuses a vector with a zero in it rather than dividing by it, and it is also why the theorem cannot be used on the tail of the lollipop graph above once the entries have crossed zero. The bracket is exact where the vector is positive and undefined where it is not, and the region where it is undefined is exactly the region the essay is about.

What to do about it #

Three things, in the order they cost.

Read the vector relative to its own largest entry, and say where the floor is. An entry at 10⁻²⁰ of the maximum carries no information; reporting it as a centrality score, or comparing two of them, is reading noise. The floor is one unit roundoff times the norm, and it is one line to compute.

Use the bracket. Any positive vector gives a proved enclosure of the Perron root at the cost of one product. Anything doing power iteration already computes that product and is throwing the bound away.

And if the small entries genuinely matter, change the question. The relative accuracy of a small entry of an eigenvector is not something a norm-wise algorithm delivers, and asking for it is asking for a different computation — a relative-accuracy eigensolver, or a formulation in which the quantity of interest is not a small entry of a large vector. On a graph, that usually means asking about the tail on its own rather than about the whole object at once.

Two routes, and what they disagree about #

The site’s habit is to compute everything twice, and here the two routes disagree in an instructive place.

Through the symmetric eigensolver. For an undirected graph the adjacency matrix is symmetric, so the site’s own Jacobi sweep returns the whole spectrum, and the Perron pair is the largest eigenvalue and its column. That is what the figure draws.

Through the power iteration. Start positive, multiply, normalise, repeat. Every iterate is nonnegative by construction, because a nonnegative matrix times a nonnegative vector is nonnegative — there is no subtraction anywhere in the loop.

So the power iteration’s answer cannot have a negative entry, ever, whatever the arithmetic does. Measured on the same graph, the last eight entries of each:

power iteration   2.25e-18  2.06e-19  1.89e-20  1.73e-21  1.59e-22  1.45e-23  1.33e-24  1.21e-25
eigensolver       2.28e-18  1.36e-19  4.61e-20 -7.13e-22 -5.52e-21 -2.44e-20  1.33e-20 -5.19e-20

The two agree on the Perron root to nine digits — 11.007687761 both ways — and agree on the first of those entries to three. After that they part completely. The power iteration’s sequence continues to fall by a factor of about eleven a step, all the way to 1.2·10⁻²⁵, and every one of those entries is correct to several digits: each is the previous one divided by the root, computed by additions of positive numbers, with no cancellation anywhere. The eigensolver’s stops being a sequence at 10⁻¹⁹ and becomes noise.

So the route that is structurally incapable of returning a negative entry is also the accurate one, and it is accurate for the same reason. A Jacobi sweep performs rotations, which subtract; a power iteration on a nonnegative matrix does not subtract at all, so the relative accuracy of a small entry survives, and the theorem’s conclusion survives with it.

That is the useful form of the result. It is not that one method is better in general — the eigensolver returns the whole spectrum and the power iteration returns one pair — but that a property guaranteed by a theorem is preserved numerically only by an algorithm whose arithmetic cannot violate it. The same argument runs through relative-accuracy eigensolvers: what buys relative accuracy in the small eigenvalues is a factorisation with no subtractions in the wrong places, and it is a property of the algorithm rather than of the precision.

Where this bites in practice #

Two places, and neither of them is exotic.

Eigenvector centrality on a graph with a periphery. The construction above is a caricature of a real shape: a dense core with sparse structures hanging off it. Every vertex more than a dozen steps from the core has a centrality score that is noise, and a ranking that includes them is ranking rounding errors against each other. The ranking essay measures how many places of such a list are determined; this is the mechanism that makes the answer small.

Any test of the form “is this vector nonnegative”. A routine that checks whether a computed eigenvector satisfies its own theorem will find that it does not, on a graph like this, and the correct response is neither to loosen the check to zero tolerance nor to conclude the eigensolver is broken. It is to check nonnegativity at the noise floor, and to say what the floor was.

The general form is one this collection keeps arriving at: a property that holds exactly in the algebra needs a tolerance to be checked in the arithmetic, and choosing the tolerance is choosing what the check means. Deciding that a zero has arrived is the same decision for a different property, and rank is a decision is it for a third.

What the bracket does not give #

One limitation is worth stating, because the enclosure above is good enough that it invites being asked for more than it provides.

Collatz–Wielandt brackets the eigenvalue. It says nothing whatever about the eigenvector, and the eigenvector is what the essay is about. A run can know the Perron root to 10⁻⁴ from one product and still have a vector whose small entries are noise, and there is no analogous free two-sided bound on the entries.

Nor does the bracket narrow quickly. Its width fell from 25 to 1.2·10⁻⁴ over forty products — about a factor of two and a half a step, which is the gap between the Perron root and the next eigenvalue — so it converges at exactly the rate the power iteration does and is not a shortcut. What it buys is not speed but certainty: at any step, the interval printed contains the answer, whereas the iterate’s own change contains nothing but a claim about the last step.

That distinction is the one worth carrying out of this essay alongside the sign measurement. A quantity with an enclosure and a quantity with an estimate are different kinds of object, and this field has one of each sitting side by side in the same figure.

At other settings #