Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Power iteration — where it appears

Repeated multiplication by a matrix, normalising each time, which converges to its dominant eigenvector. Its rate is the ratio of the two largest eigenvalues in modulus, and it fails to converge at all when they are equal in modulus.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

01428425670849810⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)0.9predicted rate0.77measured0.77iterations108against the solve10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A ranking that is an eigenvector

PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise. The iteration and the elimination agree to 4·10⁻¹⁷. What α is set to changes which pages come third, fourth and fifth.

graph · random walk 0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk

The rate is the second eigenvalue

A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces.

graph · random walk 1611162126313610⁻²²10⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹vertex, clique first then tail|entry| relative to the largestone rounding of the largest entrya bound that is provedPerron root11bracket, low11bracket, high11bracket width1.2·10⁻⁴smallest entry-1.5·10⁻²⁰entries below zero4every entry is positiveand the picture disagrees

An eigenvector that must not change sign

Perron's theorem says the leading eigenvector of a connected nonnegative matrix is strictly positive. On a clique with a long tail, four of its thirty-six entries come back negative — and beside them is the one two-sided bound on this site that is proved rather than estimated.

graph · perron frobenius

Named alongside it

The objects these essays reach for when they reach for this one.

PagerankPerron frobeniusRandom walkBipartiteCentralityCertificateCollatz wielandtConductanceDangling nodeEigenvectorMixing timeNormalised laplacian

All concepts