The Perron-Frobenius Theorem
A result about matrices with all-positive (or non-negative) entries guaranteeing a unique largest eigenvalue with an eigenvector that has all-positive entries — the mathematical basis for things like Google's PageRank and Markov chain steady states.
An eigenvalue tells you how much a matrix stretches space along a particular direction; a matrix generally has several, and in general there's no guarantee any of them is special. The Perron-Frobenius theorem says something surprisingly strong happens if every entry of the matrix is positive (or non-negative, under a mild extra condition): there's a single largest eigenvalue, larger in absolute value than every other eigenvalue, and its corresponding eigenvector can be chosen so every entry in it is positive too.
Think of a matrix describing how a population of animals split across several regions with positive numbers moves and reproduces from year to year — every entry (some individuals always move, some fraction always stays) is non-negative. The theorem guarantees that no matter the starting distribution across regions, the population's proportional split eventually settles into one specific, all-positive pattern — the eigenvector for that largest eigenvalue — and grows or shrinks overall at a single well-defined rate, the eigenvalue itself.
This is precisely the mathematics behind a Markov chain's steady-state distribution (transition probabilities are non-negative, and the steady state is that all-positive eigenvector for eigenvalue 1) and behind Google's original PageRank algorithm, where the "matrix" encodes which web pages link to which, and the theorem guarantees a single, well-defined ranking vector exists regardless of the messy, sparse link structure of the actual web.
The Perron-Frobenius theorem guarantees that a matrix with all non-negative entries has a unique largest eigenvalue whose eigenvector is all-positive — the reason Markov chains settle into a well-defined steady state and PageRank produces a single stable ranking.
Related concepts
Practice in interviews
Further reading
- Perron (1907); Frobenius (1912)