Fact-checked by Grok 2 weeks ago

Perron–Frobenius theorem

The Perron–Frobenius theorem is a cornerstone result in linear algebra that describes the spectral properties of positive and nonnegative square matrices, guaranteeing the existence of a dominant positive real eigenvalue (the Perron root) with an associated strictly positive eigenvector, and ensuring that this eigenvalue has the largest modulus among all eigenvalues.^[1]^[2] Proved initially by Oskar Perron in 1907 for matrices with strictly positive entries, the theorem was extended by Georg Frobenius in 1912 to encompass nonnegative matrices, addressing cases where some entries may be zero while maintaining irreducibility or primitivity conditions to ensure the key spectral guarantees.^[1]^[3] For a positive matrix A \in \mathbb{R}^{n \times n} (all entries a_{ij} > 0), the theorem states that there exists a unique positive eigenvalue r = \rho(A) (the spectral radius) such that r > |\lambda| for all other eigenvalues \lambda, with a corresponding positive eigenvector x > 0 satisfying Ax = rx, and bounds on r given by the minimum and maximum row sums of A.^[1] In the nonnegative case, for an irreducible nonnegative matrix (whose associated directed graph is strongly connected), the theorem asserts that \rho(A) is a simple positive eigenvalue with a positive eigenvector, has algebraic multiplicity one, and satisfies \rho(A) \geq |\lambda| for other eigenvalues, with strict inequality if the matrix is primitive (some power is positive).^[2]^[1] The theorem's significance lies in its broad applicability across disciplines, providing tools for analyzing stability and long-term behavior in systems modeled by such matrices. In economics, it underpins the Leontief input-output model, where the Perron root determines the maximum growth rate of production without shortages.^[1] In biology and ecology, it models population dynamics, such as in Leslie matrices for age-structured populations, ensuring a dominant growth rate with a stable positive distribution.^[4] For Markov chains and stochastic processes, the theorem implies the existence of a unique stationary distribution corresponding to the eigenvalue 1 for transition matrices, facilitating convergence analysis in probabilistic systems like genetics or queueing models.^[1] Additionally, in computer science and web technology, it forms the basis of Google's PageRank algorithm, where the Perron eigenvector ranks webpage importance based on nonnegative link matrices.^[1] These applications highlight the theorem's role in guaranteeing positivity and dominance in iterative processes and network analyses.

Theorem Statement

Positive Matrices

A positive matrix is a square matrix in which every entry is strictly greater than zero.^[5] The Perron–Frobenius theorem for positive matrices states that if A is an n \times n positive matrix, then A has a unique positive real eigenvalue r, known as the Perron root, which is simple (of algebraic multiplicity one) and strictly greater in modulus than all other eigenvalues \lambda of A, satisfying |\lambda| < r for every \lambda \neq r. This eigenvalue r equals the spectral radius \rho(A), defined as the maximum modulus of the eigenvalues of A. Associated with r is a positive eigenvector \mathbf{v} > 0 (positive in every component), unique up to positive scalar multiples, satisfying the equation

A \mathbf{v} = r \mathbf{v}.

This eigenvector is the Perron vector.^[5]^[6] The spectral radius \rho(A) = r follows directly from the eigenvalue characterization, and the strict inequality |\lambda| < r for other eigenvalues ensures that r dominates the spectrum, implying that the powers of A grow asymptotically like r^k times a rank-one projection onto the Perron eigenvector. The positivity of the eigenvector arises from the strict positivity of the matrix entries, which guarantees that no non-positive vector can be an eigenvector for the dominant eigenvalue.^[6]^[3] A high-level proof sketch begins by establishing the existence of r as the spectral radius using variational principles, such as the Collatz–Wielandt formula, which characterizes r = \max_{\mathbf{x} > 0} \min_i (A\mathbf{x})_i / x_i. Positivity and uniqueness of the eigenvector are then shown by contradiction, leveraging the fact that for positive matrices, the eigenspace for r cannot contain non-positive vectors. Simplicity follows from perturbation arguments or the absence of Jordan blocks due to the strict dominance. Full details of these techniques appear in later sections on proof methods.^[3]^[6]

Classification of Non-Negative Matrices

A non-negative matrix is a square matrix whose entries are all real numbers greater than or equal to zero.^[7] Such matrices form the foundational class for the Perron–Frobenius theorem beyond the strictly positive case, where the presence of zero entries introduces structural complexities that affect spectral properties.^[8] Non-negative matrices are classified as reducible or irreducible based on their connectivity structure. A non-negative matrix A is reducible if there exists a permutation matrix P such that P^T A P is block upper triangular with at least two nonzero diagonal blocks, implying the matrix can be decomposed into decoupled subsystems.^[7] In contrast, A is irreducible if, for every pair of indices i, j, there exists a positive integer k such that (A^k)_{i,j} > 0; equivalently, the directed graph associated with A—where vertices represent rows/columns and edges indicate positive entries—is strongly connected, ensuring paths between all pairs of vertices.^[7]^[8] Within the irreducible class, further distinctions arise between primitive and imprimitive matrices. An irreducible non-negative matrix A is primitive if there exists a positive integer k such that A^k > 0 (all entries strictly positive), with the index of primitivity defined as the smallest such k.^[7]^[8] If A is irreducible but not primitive, it is imprimitive, characterized by a cyclicity index h > 1, which is the greatest common divisor of the lengths of directed cycles in its associated graph.^[7] For imprimitive matrices, the peripheral spectrum—eigenvalues of modulus equal to the spectral radius r—consists of exactly h simple eigenvalues r, \omega r, \dots, \omega^{h-1} r, where \omega is a primitive h-th root of unity, equally spaced on the circle of radius r in the complex plane.^[7] Every irreducible non-negative matrix possesses a Perron root, the spectral radius r > 0, which is a simple eigenvalue with a strictly positive eigenvector, though additional properties like strict dominance over other eigenvalues hold only in the primitive subclass.^[7]^[8] This classification framework is essential for extending Perron–Frobenius results from positive matrices, where the Perron root is always simple and dominant, to the broader non-negative setting.^[7]

Irreducible Non-Negative Matrices

For an irreducible non-negative matrix A \in \mathbb{R}^{n \times n}, the Perron–Frobenius theorem asserts that the spectral radius r = \rho(A) is a simple eigenvalue, and there exists a positive right eigenvector v > 0 such that A v = r v. Moreover, there exists a positive left eigenvector u > 0 such that u^T A = r u^T, and these can be normalized so that u^T v = 1. All other eigenvalues \lambda of A satisfy |\lambda| \leq r, with equality holding only if \lambda = \omega r for some h-th root of unity \omega, where h is the index of imprimitivity of A.^[9] The index of imprimitivity h, also known as the period or cyclicity, is the greatest common divisor of the lengths of all directed cycles in the associated directed graph of A, where irreducibility ensures the graph is strongly connected. If A is primitive (i.e., h = 1), then r is strictly dominant: |\lambda| < r for all other eigenvalues \lambda \neq r. In the imprimitive case with cyclicity h > 1, there are exactly h eigenvalues on the circle |\lambda| = r, namely r, \omega r, \omega^2 r, \dots, \omega^{h-1} r, where \omega = e^{2\pi i / h} is a primitive h-th root of unity, and each has algebraic multiplicity one. The positive right eigenvector v is unique up to positive scaling, and similarly for the left eigenvector u.^[9] This formulation extends the original result of Perron for positive matrices to the broader class of irreducible non-negative matrices, where some zero entries are permitted as long as the matrix cannot be permuted into block upper-triangular form with more than one block. The peripheral spectrum—those eigenvalues with modulus equal to r—thus consists solely of the Perron root in the primitive case, reflecting the absence of periodic structure in the graph, while the imprimitive case introduces rotational symmetry in the eigenvalues due to the cyclic index h.^[5]^[9]

Additional Properties

The Perron–Frobenius eigenvalue exhibits monotonicity properties with respect to entrywise ordering of nonnegative matrices. Specifically, for nonnegative matrices A and B, if $0 \leq B \leq A entrywise, then \rho(B) \leq \rho(A). For an irreducible nonnegative matrix A, the inequality is strict: if $0 \leq B \leq A and B \neq A, then \rho(B) < \rho(A). A variational characterization of the Perron root, known as the Collatz–Wielandt formula, provides an optimization-based expression for \rho(A) of a nonnegative matrix A. For any positive vector x > 0,

\rho(A) = \max_{x > 0} \min_i \frac{(Ax)_i}{x_i} = \min_{x > 0} \max_i \frac{(Ax)_i}{x_i}.

This formula equates the Perron root to both the maximum of the minimum Rayleigh-like quotients and the minimum of the maximum quotients over positive vectors, highlighting its min-max nature. For a positive matrix A, the asymptotic behavior of its powers reveals the dominance of the Perron eigenspace. As k \to \infty,

\frac{A^k}{\rho(A)^k} \to v u^T,

where u and v are the left and right Perron eigenvectors normalized such that u^T v = 1. This convergence to a rank-one matrix underscores the spectral gap separating \rho(A) from other eigenvalues. Perturbations that preserve positivity maintain the dominance of the Perron root. If A is positive and E is a sufficiently small perturbation such that A + E > 0, then \rho(A + E) remains a simple, real, positive eigenvalue strictly greater in modulus than all other eigenvalues of A + E. This stability follows from the continuity of the spectral radius and the isolation of the Perron eigenvalue in the positive case. In the context of stochastic matrices, which are nonnegative with row sums equal to 1, the Perron root is precisely 1. The all-ones vector serves as a right eigenvector for eigenvalue 1, and by the Perron–Frobenius theorem, this is the spectral radius.

Applications

Non-Negative and Stochastic Matrices

The Perron–Frobenius theorem provides several useful bounds for the spectral radius \rho(A) of a non-negative matrix A. Specifically, \rho(A) lies between the minimum and maximum row sums of A: \min_i \sum_j a_{ij} \leq \rho(A) \leq \max_i \sum_j a_{ij}.^[10] Additional bounds can be derived using the trace and determinant; for instance, a positive trace of an irreducible non-negative matrix implies primitivity, which strengthens eigenvalue dominance properties.^[10] A key characterization of the spectral radius for positive matrices is the Collatz–Wielandt formula: \rho(A) = \inf \{ t > 0 \mid \exists x > 0, \, Ax \leq t x \}, where the infimum is achieved at the Perron eigenvector.^[11] For row-stochastic matrices P (non-negative with rows summing to 1), the Perron–Frobenius theorem identifies 1 as a simple eigenvalue, with a corresponding positive left eigenvector \pi > 0 normalized such that \pi P = \pi and \sum \pi_i = 1, serving as the unique stationary distribution.^[10] If P is primitive (irreducible and with positive trace), then P^k converges to the rank-1 matrix whose rows are all \pi^T as k \to \infty.^[10] In population growth models, non-negative rate matrices (such as Leslie matrices P = T + F, with T for survival transitions and F for fertilities) have \rho(P) as the dominant growth rate, with a positive stable age distribution given by the corresponding Perron eigenvector.^[12] Scaling the fertility component by the net reproductive rate R_0 = \rho(F(I - T)^{-1}) yields a model with growth rate exactly 1.^[12] The Birkhoff–Hopf theorem extends these ideas to doubly stochastic matrices (non-negative with both rows and columns summing to 1), stating that any positive matrix can be scaled by positive diagonal matrices to become doubly stochastic, linking to majorization via the preservation of majorized vectors under doubly stochastic transformations.^[13]

Graph Theory and Markov Chains

In algebraic graph theory, the Perron–Frobenius theorem applies to the adjacency matrix A of a directed graph G, where A_{ij} = 1 if there is an edge from vertex i to j, and 0 otherwise. The matrix A is irreducible if and only if G is strongly connected, meaning there exists a directed path from every vertex to every other vertex.^[14]^[2] In this case, the Perron root r of A equals the spectral radius of G, and the corresponding positive Perron eigenvector has components that indicate the eigenvector centrality of the vertices, measuring their relative importance based on connectivity.^[15] For a d-regular directed graph, where every vertex has out-degree d, the Perron root r equals d, with the all-ones vector as the Perron eigenvector.^[15] Moreover, A is primitive if and only if G is aperiodic, meaning the greatest common divisor of the lengths of its directed cycles is 1.^[16] The theorem extends naturally to finite Markov chains, where the transition matrix P is row-stochastic and non-negative. The chain is irreducible if and only if P is irreducible, ensuring communication between all states.^[17] By the Perron–Frobenius theorem, P has a unique positive eigenvalue 1 (the Perron root r = 1) with a positive left eigenvector \pi that, when normalized to sum to 1, gives the unique stationary distribution of the chain.^[1] If P is primitive (equivalently, the chain is irreducible and aperiodic), the chain is ergodic, and the distribution of the chain converges to \pi regardless of the initial state.^[17]^[18] For imprimitive irreducible matrices, the index of imprimitivity h > 1 equals the period of the Markov chain, defined as the greatest common divisor of the lengths of return paths to a state, leading to cyclic behavior in the limits.^[19] The rate of convergence to the stationary distribution, when it occurs, is governed by the ratio of the subdominant eigenvalue magnitude |\lambda_2| to the Perron root, with |\lambda_2|/r < 1 ensuring geometric decay; for stochastic P, this simplifies to |\lambda_2| < 1.^[17] A prominent application appears in Google's PageRank algorithm, which models web surfing as a Markov chain on the directed graph of hyperlinks. The core matrix is damped as G = d H + (1 - d) E, where H is the hyperlink transition matrix, E is the matrix of all 1/n entries, and $0 < d < 1 is the damping factor (typically 0.85), rendering G primitive and irreducible with Perron root r = 1. The positive eigenvector of G provides the PageRank scores, reflecting steady-state page importance.^[20]^[21]

Operator Theory

In the context of operator theory, the Perron–Frobenius theorem generalizes to infinite-dimensional settings through the study of positive operators on ordered Banach spaces. Consider a Banach space X equipped with a closed convex cone X_+ that induces a partial order via x \geq 0 if x \in X_+. A bounded linear operator T: X \to X is positive if it preserves the cone, meaning T(X_+) \subset X_+, or equivalently, Tx \geq 0 whenever x \geq 0. This can be characterized using the dual order: for all x \geq 0 and positive continuous linear functionals y^* \in (X^*)_+ (those with y^*(z) \geq 0 for z \geq 0), \langle Tx, y^* \rangle \geq 0.^[22] The key extension is provided by the Krein–Rutman theorem, which serves as an infinite-dimensional analog of the Perron–Frobenius theorem for compact positive operators. Specifically, let X_+ be a solid cone (with nonempty interior). If T is a compact, positive, and irreducible operator (meaning no nontrivial invariant ideals in the order sense), then the spectral radius r(T) > 0 is a simple eigenvalue of T, isolated in the spectrum \sigma(T), with a strictly positive eigenvector u in the interior of X_+, satisfying

Tu = r(T) u, \quad u \gg 0.

Moreover, r(T) has strictly larger modulus than any other point in \sigma(T), ensuring dominance, and the eigenspace is one-dimensional. Irreducibility here implies that for any x > 0 (in the interior), Tx \gg 0. This theorem captures the essential spectral properties of positive operators, mirroring the finite-dimensional case but adapted to abstract spaces.^[23] A concrete application arises with integral operators featuring positive kernels, such as Volterra operators on spaces like C([a,b]) of continuous functions, defined by

(Tf)(t) = \int_a^t k(t,s) f(s) \, ds,

where k(t,s) > 0 for s < t. The Krein–Rutman theorem guarantees that r(T) is a simple positive eigenvalue with a positive eigenfunction, and this radius r(T) quantifies the long-term growth rate of iterates T^n f or the semigroup generated by T, determining asymptotic stability or expansion in the positive cone. For instance, in periodic settings, r(T) aligns with parameters like delay lengths that ensure positive solutions exist only if the kernel supports nontrivial growth.^[24] In differential equations, particularly linear elliptic partial differential equations on bounded domains, positive compact operators derived from Green's functions or resolvents apply the Krein–Rutman theorem to identify principal eigenvalues that set stability thresholds. For an operator like A = -\Delta + c with c > 0 and Dirichlet boundary conditions, the principal eigenvalue \lambda_1 of A is simple and positive, with a positive eigenfunction, and \operatorname{Re}(\mu) \geq \lambda_1 for all other eigenvalues \mu \in \sigma(A). The resolvent T = A^{-1} has spectral radius r(T) = 1/\lambda_1. Solutions to the associated PDE decay exponentially if the forcing term is below this threshold (i.e., if the effective growth parameter is less than \lambda_1) and exhibit instability otherwise, providing critical bifurcation points in reaction-diffusion systems.^[23] Unlike the finite-dimensional matrix case, where the spectrum consists of finitely many isolated eigenvalues, the spectrum of a compact positive operator on an infinite-dimensional Banach space is at most countable, potentially accumulating only at 0, while r(T) remains an isolated point of maximal modulus with the described multiplicity and eigenvector properties. This accumulation at 0 reflects the compactness, allowing essential spectrum only at the origin, but preserves the dominant role of the Perron–Frobenius root in spectral theory.^[22]

Proof Techniques

Eigenvalue Dominance for Positive Matrices

For a positive matrix A, the Perron–Frobenius theorem asserts that the spectral radius \rho(A) is a simple positive real eigenvalue r, accompanied by a positive eigenvector, and that r strictly exceeds the modulus of every other eigenvalue of A.^[3] To establish the dominance of this eigenvalue, first note that the spectral radius \rho(A) satisfies \rho(A) = \lim_{k \to \infty} \|A^k\|^{1/k} for any consistent matrix norm \|\cdot\|, as given by Gelfand's formula. Suppose there exists an eigenvalue \lambda of A with |\lambda| \geq r = \rho(A). Since the spectral radius is the maximum modulus of any eigenvalue, it follows that |\lambda| \leq \rho(A), so |\lambda| = r. Thus, any eigenvalue achieving the spectral radius must lie on the circle |z| = r in the complex plane.^[3] A key lemma states that for a positive matrix A, any eigenvalue \lambda with |\lambda| = \rho(A) must be positive real. To see this, consider an eigenvector z corresponding to such a \lambda, so Az = \lambda z. Taking moduli yields A|z| \geq |Az| = |\lambda| |z| = \rho(A) |z|, with equality holding if and only if the phases of the components of z align in a specific way due to the positivity of A. Applying the Brouwer fixed-point theorem to the normalized map f(x) = Ax / \|Ax\| on the positive orthant shows that the fixed point corresponds to a positive real eigenvalue, and any other \lambda on the circle would contradict the uniqueness of the attracting fixed point in the power iteration dynamics.^[3] The strict dominance r > |\lambda| for all other eigenvalues \lambda follows from constructing auxiliary sequences that bound the growth rates. Define the Collatz–Wielandt quotient for a positive vector x > 0 as q(x) = \min_i \frac{(Ax)_i}{x_i}. Then r = \sup_{x > 0} q(x), achieved at the positive Perron eigenvector. For any other eigenvalue \lambda with eigenvector z \neq 0, consider the positive part x = |z|; the inequality A x \geq |\lambda| x implies q(x) \geq |\lambda|, but since q(x) < r unless x is the Perron eigenvector (up to scaling), it follows that |\lambda| < r. Moreover, power bounds from A^k show that the growth \|A^k\|^{1/k} \to r, and contributions from other eigenspaces decay relative to the dominant one due to their smaller moduli.^[3] A useful bound on the Perron root is given by the row sums of A: if s_{\min} = \min_i \sum_j a_{ij} and s_{\max} = \max_i \sum_j a_{ij}, then s_{\min} \leq r \leq s_{\max}. This arises by applying the all-ones vector e to A, yielding A e = s where s_{\min} e \leq s \leq s_{\max} e, and normalizing shows the Rayleigh quotient bounds r. Equality holds if and only if all row sums are equal.^[25] Consequently, all eigenvalues of A except the Perron root r lie strictly inside the disk |z| < r in the complex plane, ensuring the spectral isolation of the dominant eigenvalue.^[3]

Power Iteration and Eigenpairs

The power iteration, also known as the power method, is an iterative algorithm designed to compute the Perron eigenpair—the dominant eigenvalue r > 0 (the Perron root) and its associated positive eigenvector v > 0—of a positive matrix A > 0. The algorithm initializes with a positive vector x_0 > 0 and generates subsequent iterates via

x_{k+1} = \frac{A x_k}{\| A x_k \|},

where \| \cdot \| denotes a suitable vector norm, such as the Euclidean norm. As k \to \infty, x_k converges to a normalized version of the Perron eigenvector v (satisfying \| v \| = 1), while the associated Rayleigh quotient

r_k = \frac{x_k^T A x_k}{x_k^T x_k}

converges to the Perron root r. This convergence leverages the spectral properties guaranteed by the Perron–Frobenius theorem for positive matrices, where r is simple and strictly dominant over all other eigenvalues \lambda with |\lambda| < r.^[26] For positive matrices, the iterates preserve positivity: if x_0 > 0, then A x_0 > 0, and inductively A^k x_0 > 0 for all k \geq 1. The proof of convergence proceeds via spectral decomposition of A. Assuming A is diagonalizable for simplicity (a common case), write x_0 = c_1 v + \sum_{j=2}^n c_j v_j, where v is the Perron eigenvector and v_j are generalized eigenvectors for the remaining eigenvalues \lambda_j with |\lambda_j| < r. Then,

A^k x_0 = r^k c_1 v + \sum_{j=2}^n \lambda_j^k c_j v_j,

and normalizing by r^k yields

\frac{A^k x_0}{r^k} = c_1 v + \sum_{j=2}^n \left( \frac{\lambda_j}{r} \right)^k c_j v_j.

Since |\lambda_j / r| < 1 for j \geq 2, the sum vanishes as k \to \infty, provided c_1 \neq 0 (which holds for generic positive x_0). The Rayleigh quotient r_k then approaches r because the iterates align with the dominant eigenspace. Moreover, for positive initial vectors, the sequence \{ r_k \} increases monotonically to r, as each iterate improves the alignment with the positive Perron eigenvector while respecting the positivity of A.^[27]^[26] The rate of convergence is geometric, governed by the spectral gap: the error \| x_k - v \| (in an appropriate norm) satisfies

\| x_k - v \| = O \left( \left| \frac{\lambda_2}{r} \right|^k \right),

where \lambda_2 is the eigenvalue of largest modulus among the non-Perron eigenvalues, ensuring |\lambda_2| / r < 1. This ratio quantifies the dominance of r, with smaller values yielding faster convergence; for non-diagonalizable cases, the rate includes polynomial factors from Jordan blocks, but remains subexponential in k. The Rayleigh quotient converges at the same rate, providing a reliable estimate of r at each step.^[26]^[27] A key asymptotic property is the limiting behavior of the normalized matrix powers:

\lim_{k \to \infty} \frac{A^k}{r^k} = v u^T,

where u > 0 is the left Perron eigenvector normalized such that u^T v = 1. This rank-one matrix v u^T is the Perron projector onto the dominant eigenspace, and the limit holds uniformly for positive matrices, reflecting their primitivity (every positive matrix raised to any power remains positive). This projector facilitates applications like Markov chain stationary distributions.^[26] The power method extends to any initial non-negative vector x_0 \geq 0, x_0 \neq 0, without loss of convergence: the first application of A induces strict positivity (A x_0 > 0), after which the iterates follow the positive case. This robustness stems from the irreducibility and positivity inherent in positive matrices, ensuring the component along v is eventually amplified regardless of the starting point in the non-negative cone.^[27]^[26]

Multiplicity and Eigenvector Uniqueness

For an irreducible non-negative matrix A, the Perron eigenvalue r > 0 has algebraic multiplicity one. To see this, consider the positive right eigenvector v > 0 with A v = r v and the positive left eigenvector u > 0 (eigenvector of the transpose A^T) with u^T A = r u^T, normalized so that u^T v = 1. The space \mathbb{R}^n decomposes as the direct sum of the one-dimensional span of v and the hyperplane H = \{ x \mid u^T x = 0 \}, which is invariant under A. The spectral radius of the restriction of A to H is strictly less than r, as otherwise there would exist a non-zero x \in H with | \lambda | = r for some eigenvalue \lambda of this restriction, contradicting the dominance of r by the Perron-Frobenius theorem properties for submatrices derived from irreducibility. Thus, the characteristic polynomial of A factors as (t - r) times a polynomial whose roots all have modulus less than r, implying algebraic multiplicity one for r.^[28]^[8] The geometric multiplicity of r is also one, with the eigenspace \ker(A - r I) one-dimensional and spanned by the positive eigenvector v > 0. Suppose there exists another linearly independent eigenvector x such that A x = r x. By the Perron-Frobenius theorem, any eigenvector corresponding to an eigenvalue of modulus r is non-negative, so x \geq 0 without loss of generality (up to scaling). Then u^T x = c for some scalar c, but biorthogonality gives u^T (A x) = r u^T x, so r c = r c, which is consistent; however, since u > 0 and x \geq 0, u^T x > 0 unless x = 0. Linear independence from v would require a combination \alpha v + \beta x = 0 with \alpha, \beta \neq 0, but positivity arguments show no such non-trivial non-negative solution exists beyond multiples of v. Specifically, suppose w = \alpha v + \beta x \geq 0 with \beta \neq 0; normalizing, the minimum ratio of components leads to a strict inequality in A w = r w at the minimizing index due to irreducibility, forcing w to be a positive multiple of v, a contradiction. Thus, the kernel is spanned solely by v.^[28]^[25] The positive eigenvector v > 0 for r is unique up to positive scaling. Any other non-negative eigenvector for r must be a positive multiple of v, as non-negativity and irreducibility imply strict positivity, and the uniqueness follows from the one-dimensional eigenspace. More generally, for eigenvalues \lambda with |\lambda| = r, there are no other non-negative eigenvectors except in the imprimitive case, where peripheral eigenvalues on the circle |\lambda| = r may admit non-negative (but not strictly positive) eigenvectors corresponding to cyclic permutations. For primitive matrices, where some power of A is positive, r is the unique eigenvalue with |\lambda| = r, and thus the only real positive eigenvalue, ensuring no other positive eigenvectors exist.^[28]^[29]

Variational Characterizations

The Collatz–Wielandt formula provides a variational characterization of the Perron root r for a positive matrix A > 0, expressing it as both a supremum of minima and an infimum of maxima over positive vectors. Specifically,

r = \sup_{x > 0} \min_{1 \leq i \leq n} \frac{(Ax)_i}{x_i} = \inf_{x > 0} \max_{1 \leq i \leq n} \frac{(Ax)_i}{x_i},

where equality holds when x is a positive eigenvector corresponding to r.^[30]^[31] This formula arises from considering the function f(x) = \min_i (Ax)_i / x_i on the set of positive vectors normalized to lie on the unit simplex \Delta = \{ x \in \mathbb{R}^n_+ : \sum_i x_i = 1 \}. The proof relies on the continuity of f on the interior of \Delta and the compactness of its closure, ensuring that the supremum is attained at a point where f(x) = r, which coincides with the positive Perron eigenvector. The infimum over maxima follows dually, with equality again at the eigenvector.^[32]^[11] For irreducible nonnegative matrices A \geq 0, the formula extends by restricting to positive vectors, yielding

r = \sup_{\substack{x \geq 0 \\ x \neq 0}} \min_{\substack{1 \leq i \leq n \\ x_i > 0}} \frac{(Ax)_i}{x_i} = \inf_{\substack{x \geq 0 \\ x \neq 0}} \max_{\substack{1 \leq i \leq n \\ x_i > 0}} \frac{(Ax)_i}{x_i},

with equality at the positive Perron eigenvector; this is established by approximating A with positive matrices A + \epsilon \mathbf{1}\mathbf{1}^T for small \epsilon > 0 and taking limits.^[11]^[33] The Collatz–Wielandt formula generalizes the Rayleigh quotient characterization of the dominant eigenvalue for symmetric positive matrices, replacing the quadratic form with componentwise ratios to handle nonsymmetric cases while preserving the min-max structure.^[30] In optimization terms, the Perron root r represents the optimal growth rate within the positive cone, as it maximizes the minimal expansion factor \min_i (Ax)_i / x_i over positive directions x, reflecting the theorem's interpretation as a spectral optimization problem over the nonnegative orthant.^[34]

Projection Limits and Inequalities

The Perron projection for a positive matrix A with spectral radius r is defined as the limit P = \lim_{k \to \infty} A^k / r^k, which exists and equals v u^T, where v and u are the positive right and left Perron eigenvectors normalized such that u^T v = 1. This matrix P is rank-one with strictly positive entries, serves as a projection operator satisfying P^2 = P, and commutes with A via A P = P A = r P.^[35] To establish this limit, consider the Jordan canonical form of A, A = S J S^{-1}, where J consists of Jordan blocks corresponding to the eigenvalues. The spectral radius r is a simple eigenvalue by the Perron–Frobenius theorem for positive matrices, so its Jordan block is $1 \times 1. As k \to \infty, the contributions from Jordan blocks with eigenvalues \lambda where |\lambda| < r decay geometrically since (\lambda / r)^k \to 0, while nilpotent parts in those blocks raise to higher powers and vanish faster. The dominant term arises solely from the Perron eigenvalue block, yielding the rank-one outer product v u^T after normalization.^[3] Key inequalities bound the spectral radius r = \rho(A). The Gerschgorin circle theorem states that every eigenvalue lies in at least one of the disks centered at the diagonal entries a_{ii} with radii \sum_{j \neq i} a_{ij}, implying \rho(A) \leq \max_i \left( a_{ii} + \sum_{j \neq i} a_{ij} \right) = \|A\|_\infty for non-negative A.^[3] More generally, for any matrix norm \| \cdot \| induced by a vector norm, \rho(A) \leq \|A\|, with equality holding for positive matrices when the norm aligns with the Perron eigenvectors, such as the \ell_1 or \ell_\infty norms. For imprimitive irreducible non-negative matrices with index of imprimitivity h > 1, the limit \lim_{k \to \infty} A^k / r^k does not exist due to oscillatory behavior from the h peripheral eigenvalues r \omega^j where \omega = e^{2\pi i / h}, j = 0, \dots, h-1. Instead, the h-th root limit \lim_{k \to \infty} (A^h)^k / r^{hk} exists and yields a rank-one projection analogous to the primitive case, while the full power sequence cycles through h distinct positive rank-one projections summing to the peripheral projection.^[36] The peripheral projection Q generalizes the Perron projection to the invariant subspace spanned by generalized eigenspaces for all eigenvalues with modulus r; it satisfies A Q = Q A = r Q and is the direct sum of the individual spectral projections onto those eigenspaces, ensuring Q has non-negative entries and rank equal to the dimension of the peripheral eigenspace.

Examples and Limitations

Illustrative Examples

To illustrate the Perron–Frobenius theorem for positive matrices, consider the 2×2 matrix A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}, which has all positive entries.^[25] The characteristic polynomial is \det(A - \lambda I) = \lambda^2 - 5\lambda - 2 = 0, with roots \lambda = \frac{5 \pm \sqrt{33}}{2}. The dominant eigenvalue is r \approx 5.372, and the other eigenvalue is approximately -0.372, confirming that r > |\lambda| for all other eigenvalues \lambda. The corresponding right eigenvector v satisfies (A - r I)v = 0; solving yields v \approx \begin{pmatrix} 0.31 \\ 0.69 \end{pmatrix} (normalized such that the components sum to 1), with both entries positive, as guaranteed by the theorem.^[25] For a primitive stochastic matrix, consider a 3-state Markov chain with transition matrix P = \begin{pmatrix} 0.90 & 0.01 & 0.09 \\ 0.01 & 0.90 & 0.01 \\ 0.09 & 0.09 & 0.90 \end{pmatrix}, where each row sums to 1 and all entries are positive, ensuring primitivity.^[37] The dominant eigenvalue is r = 1, with corresponding left eigenvector (stationary distribution) \pi = \begin{pmatrix} 1/3 \\ 1/3 \\ 1/3 \end{pmatrix}, all entries positive. Powers P^n converge to the matrix with rows equal to \pi, demonstrating convergence to the stationary distribution regardless of the initial state, as the subdominant eigenvalues have absolute value less than 1.^[37] An example of an irreducible but imprimitive nonnegative matrix with period h = 2 is B = \begin{pmatrix} 0 & 4 \\ 1 & 0 \end{pmatrix}, whose directed graph consists of a cycle of even length.^[38] The eigenvalues are r = 2 and -r = -2, both on the circle of radius r in the complex plane, with geometric multiplicity 1 for each, illustrating that the peripheral spectrum consists of h eigenvalues equally spaced on the circle while the dominant eigenvalue remains real, positive, and simple with a positive eigenvector.^[38] In population dynamics, the Perron–Frobenius theorem applies to Leslie matrices, which model age-structured populations with nonnegative fertilities on the top row and nonnegative survival probabilities on the subdiagonal. The dominant eigenvalue r represents the intrinsic growth rate of the population, with the corresponding positive eigenvector giving the stable age distribution.^[25]

Counterexamples

The Perron–Frobenius theorem fails to provide its full guarantees, such as a simple dominant eigenvalue with a unique positive eigenvector, when applied to reducible non-negative matrices. For a reducible non-negative matrix, the spectral radius \rho(A) equals the maximum of the spectral radii of its irreducible diagonal blocks after permutation to block upper triangular form, but \rho(A) need not be simple, and associated eigenvectors may lack strict positivity. Consider a block diagonal matrix A = \operatorname{diag}(A_1, A_2), where A_1 and A_2 are non-negative square matrices. Here, \rho(A) = \max\{\rho(A_1), \rho(A_2)\}. If \rho(A_1) = \rho(A_2), then A has multiple eigenvalues of modulus \rho(A), so the spectral radius is not a simple eigenvalue. A specific counterexample is the non-negative reducible matrix

A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.

The eigenvalues are both 1, with algebraic multiplicity 2, so the spectral radius \rho(A) = 1 is not simple. The corresponding eigenspace is one-dimensional, spanned by the nonnegative vector \begin{pmatrix} 1 \\ 0 \end{pmatrix}, which is not strictly positive, and no strictly positive eigenvector exists for \lambda = 1. In such reducible cases, the power method fails to converge to a unique dominant eigenpair. For the above A, the powers are

A^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix},

and normalizing by \rho(A)^k = 1 yields matrices whose entries grow unboundedly with k, preventing convergence. The theorem holds without these failures for irreducible non-negative matrices, where the spectral radius is always simple with a unique positive eigenvector (up to scaling); reducible examples thus illustrate how irreducibility is essential for the positivity properties.

Terminology

Core Definitions

The Perron–Frobenius theorem pertains to square matrices with non-negative entries, where standard notation denotes a matrix A as non-negative if every entry a_{ij} \geq 0, written A \geq 0. A matrix is positive if every entry a_{ij} > 0, denoted A > 0. This notation extends componentwise to vectors in \mathbb{R}^n, where the non-negative cone consists of vectors x \geq 0 with all components non-negative, and the positive cone comprises vectors x > 0 with all components strictly positive.^[34] The spectral radius of a matrix A, denoted \rho(A), is defined as the maximum modulus of its eigenvalues: \rho(A) = \max \{ |\lambda| : \lambda \text{ is an eigenvalue of } A \}. The peripheral spectrum refers to the set of eigenvalues lying on the circle of radius \rho(A) in the complex plane, specifically \{ \lambda : |\lambda| = \rho(A) \}.^[34]^[39] In the context of the theorem, the Perron root (or Perron–Frobenius number) is the positive real eigenvalue \rho(A) of a non-negative matrix A that admits a corresponding positive eigenvector x > 0. This eigenvalue coincides with the spectral radius for positive matrices and is simple and dominant.^[34]^[39]

Historical Context

The Perron–Frobenius theorem originated with Oskar Perron's work in 1907, where he established the existence of a dominant positive eigenvalue and corresponding positive eigenvector for matrices with strictly positive entries, motivated by his work on continued fractions in papers such as "Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus" and "Zur Theorie der Matrizen."^[40]^[41] Perron's result, published in "Zur Theorie der Matrizen," highlighted the spectral properties of such matrices, laying the groundwork for later generalizations.^[40] Ferdinand Georg Frobenius extended these ideas in a series of papers from 1908 to 1912, broadening the theorem to irreducible nonnegative matrices and introducing the concept of cyclicity to characterize the periodicity in the associated directed graph.^[42] In his 1908 and 1909 works on matrices with positive elements, Frobenius refined Perron's findings, while his 1912 paper "Über Matrizen aus nicht negativen Elementen" fully developed the version for nonnegative irreducible cases, proving the Perron root's simplicity and the eigenvector's positivity under irreducibility.^[9] These contributions solidified the theorem's role in matrix theory. The theorem saw independent rediscoveries and extensions in operator theory, notably by M. A. Krasnoselskii in his 1964 book "Positive Solutions of Operator Equations," which adapted the results to positive operators on Banach spaces. Its evolution accelerated in the mid-20th century with applications to Markov chains, where the Perron root determines the stationary distribution's decay rate, as explored in probabilistic models from the 1950s onward. A key generalization came earlier with the Krein–Rutman theorem in 1948, extending the spectral dominance to compact positive operators on cones in Banach spaces. In modern contexts, the theorem influences numerical methods for computing the spectral radius, such as inverse iteration techniques that leverage the Perron root's dominance for stability in large-scale eigenvalue problems. Recent extensions appear in quantum information theory, where Perron–Frobenius-type results analyze the spectral properties of quantum operations and decoherence in quantum walks.^[43]

References

[1]
[PDF] The Perron Frobenius Theorem and a Few of Its Many Applications
In 1912, Frobenius extended Perron´s original theorem to several types of nonnegative matrices. The first extension is that the matrix can have a few zeros, as ...
[2]
[PDF] Lecture: Basic Matrix Results (2 of 3)
Jan 29, 2015 · Here is a basic statement of the Perron-Frobenius theorem. Theorem 2 (Perron-Frobenius) Let A ∈ Rn×n be an irreducible non-negative matrix. ...
[3]
The Many Proofs and Applications of Perron's Theorem | SIAM Review
This paper chronicles the wide dispersal of Perron's 1907 result on positive matrices into many fields of science. The many proofs given during the last 93 ...
[4]
[PDF] Applications of The Perron-Frobenius Theorem - University of Toledo
Oskar Perron in 1907 proved the following theorem [Per07] : Theorem (Perron's Theorem). Let A be a strictly positive valued n × n matrix. Then A has a.
[5]
Zur Theorie der Matrices - EuDML
Perron, Oskar. "Zur Theorie der Matrices." Mathematische Annalen 64 (1907): 248-263. <http://eudml.org/doc/158317>.<|control11|><|separator|>
[6]
Matrix Analysis - Cambridge University Press & Assessment
Roger A. Horn, The Johns Hopkins University, Charles R. Johnson, College of William and Mary, Virginia. Publisher: Cambridge University Press.Missing: URL | Show results with:URL
[7]
[PDF] Notes on the Perron-Frobenius theory of nonnegative matrices
Definition 2.1. A primitive matrix is a square nonnegative matrix some power of which is positive. The primitive case is the heart of the Perron-Frobenius ...
[8]
[PDF] The Perron-Frobenius theorem.
A non-negative matrix square T is called primitive if there is a k such that all the entries of Tk are positive. It is called irreducible if for any i, j there ...
[9]
[PDF] Über Matrizen aus nicht negativen Elementen.
FROBENIUS: Über Matrizen aus nicht negativen Elementen. 457. In § 11 dehne ich die Untersuchung auf zerlegbare Matrizen aus, und in § 12 zeige ich, daß eine ...
[10]
https://archive.org/download/mathematics_202103/Berman%20And%20Plemmons%20-%20Nonnegative%20Matrices%20In%20The%20Mathematical%20Sciences%20%28Classics%20In%20Applied%20Mathematics%29%20%28Siam%201994%29.pdf
[11]
[PDF] 8.2 POSITIVE MATRICES Positive Eigenpair
In 1942 the German mathematician Lothar Collatz (1910–1990) discovered the following formula for the Perron root, and in 1950 Helmut Wielandt (p. 534) used it ...Missing: characterization | Show results with:characterization<|control11|><|separator|>
[12]
[PDF] Applications of Perron-Frobenius Theory to Population Dynamics
By the use of Perron-Frobenius theory, simple proofs are given of the Fundamental. Theorem of Demography and of a theorem of Cushing and Yicang on the net repro ...
[13]
[PDF] An elementary proof of the Birkhoff-Hopf theorem
If A is any nxn matrix, all of whose entries are positive, then there exist positive diagonal matrices D1 andD2 such that D1AD2 is doubly stochastic, and such ...
[14]
[PDF] perron-frobenius theory
Perron's theorem for positive matrices is stated below, and the proof is in [127]. Page 2. 168. Perron's Theorem for Positive Matrices. If Anxn > 0 with r = p ...
[15]
[PDF] BACKGROUND ON GRAPHS
May 4, 2022 · Theorem: Perron-Frobenius An irreducible, nonnegative n × n matrix A has a real, positive eigenvalue λ1 such that: (i) λ1 is a simple ...Missing: connectivity | Show results with:connectivity<|control11|><|separator|>
[16]
[PDF] Perron-Frobenius, Spectral Theorem, Jordan Normal Form, Cauchy-Bi
So: Q adjacency matrix of graph G: Q irreducible iff G is SC. Definition: A non-negative matrix Q is primitive if there is a k such that for every i, j, we ...Missing: strong connectivity
[17]
[PDF] Markov chains and the Frobenius-Perron theorem - UC Davis Math
The chain is called aperiodic if the transition matrix is irreducible with period 1. (equivalently, A is primitive).
[18]
[PDF] ECE276B: Planning & Learning in Robotics Lecture 2: Markov Chains
Perron-Frobenius Theorem (Finite Ergodic Markov Chain). Theorem. Consider an irreducible, aperiodic, finite Markov chain with transition matrix P. Then, the ...<|control11|><|separator|>
[19]
[PDF] Lecture 6: Discrete-time Markov Chains III - DTU Informatics
A stationary distribution is a constant (in time) solution to this recursion ... According to the Perron-Frobenius theorem: If the chain is aperiodic.Missing: primary source
[20]
[PDF] The PageRank Citation Ranking: Bringing Order to the Web
Jan 29, 1998 · This paper describes PageRank, a method for rating Web pages objectively and mechanically, effectively measuring the human interest and.
[21]
[PDF] Lecture 34: Perron Frobenius theorem
Apr 27, 2011 · Perron Frobenius theorem: If all entries of a n × n matrix A are positive, then it has a unique maximal eigenvalue. Its eigenvector has ...Missing: original | Show results with:original
[22]
[PDF] Lecture 2: Positivity and the Perron–Frobenius Theorem
Jun 24, 2023 · Let (X,k·kX) be a Banach space. Let A ∈ L(X) be a bounded linear operator on the Banach space X. Then A is said to be a compact operator if ...
[23]
[PDF] Krein-Rutman Theorem and the Principal Eigenvalue
The Krein-Rutman theorem plays a very important role in nonlinear par- tial differential equations, as it provides the abstract basis for the proof of.Missing: threshold | Show results with:threshold<|control11|><|separator|>
[24]
[PDF] Intricate Structure of the Analyticity Set for Solutions of a Class of ...
Mar 13, 2019 · By the Krein-Rutman Theorem, if the spectral radius r(L) of L is strictly positive, that is if r(L) > 0, then equation (1.1) has a solution ...
[25]
[PDF] Theorem 1.1 (Frobenius-Perron). L - UChicago Math
Introduction. We begin by stating the Frobenius-Perron Theorem: Theorem 1.1 (Frobenius-Perron). Let B be an n × n matrix with nonnegative real entries.
[26]
[PDF] The power method, Perron-Frobenius theory, Page-Rank computation
proof: See the Appendix. D. Let λ1 be such that |λ1| = ρ(A) and assume that all λi such that |λi| = ρ(A) are equal to λ1 (in such case we say that λ1 ...
[27]
[PDF] Perron-Frobenius Theorem - Washington University in St. Louis
... Matrices ... Stationary distributions q = p∞ (for the column stochastic case) solve the eigenvalue equation q = Mq with column stochastic M having eigenvalue 1.
[28]
[PDF] Detailed Proof of The Perron Frobenius Theorem
Oct 30, 2016 · Algebraic multiplicity of an eigenvalue is its multiplicity as a root of the characteristic polynomial of the matrix, and its geometric ...
[29]
[PDF] Lecture 17 Perron-Frobenius Theory
Perron-Frobenius Theory. 17–6. Page 7. Perron-Frobenius theorem for regular matrices suppose A ∈ R n×n is nonnegative and regular, i.e., Ak > 0 for some k.
[30]
None
### Summary of Power Method for Perron Root from http://carlmeyer.com/pdfFiles/Computing%20the%20Perron%20Root.pdf
[31]
[PDF] Perron–Frobenius Theory of Nonnegative Matrices
ρ (A) xT = xT A =⇒ ρ (A) xT y = xT Ay = λxT y =⇒ ρ (A) = λ. In 1942 the German mathematician Lothar Collatz (1910–1990) discovered the following formula for the ...
[32]
[PDF] APPENDIX TO PART III
4 This is known as the Collatz-Wielandt Formula, as discussed for example in ... Note from the compactness of Θ [condition (i)] together with the weak inequality ...
[33]
[PDF] The Perron-Frobenius Theorem and its Application to Population ...
The Perron-Frobenius Theorem for Positive Matrices ensures that x must be a positive multiple of the Perron vector B which implies that x > 0. We want to show ...
[34]
[PDF] A new proof of the Perron–Frobenius theorem: a variational approach
Jul 19, 2024 · to the Perron root of irreducible nonnegative matrices under arbitrary perturbations. ... Nonnegative matrices in the mathematical sciences.
[35]
[PDF] notes on the perron-frobenius theory of nonnegative matrices
Definition 2.1. A primitive matrix is a square nonnegative matrix some power of which is positive. The primitive case is the heart of the Perron-Frobenius ...
[36]
Explicit formulae for limit periodic flows on networks - ScienceDirect
Jul 1, 2016 · 3.2. If is imprimitive then, by the Perron–Frobenius theory, there are additional eigenvalues on the unit circle, given by λ l = e 2 π i d l , ...
[37]
[PDF] Stochastic Matrices The following 3 × 3 matrix defines a discrete ...
A stochastic matrix has elements where Pij ≥ 0 for all i,j, and the sum of all Pij for a given j is 1.
[38]
[PDF] notes on the perron-frobenius theory of nonnegative matrices
Proof of the Perron Theorem. There are three steps. STEP 1: get the positive eigenvector. The unit simplex S is the set of nonnegative vectors v such that ||v| ...<|control11|><|separator|>
[39]
[PDF] arXiv:1711.06670v3 [math.RA] 30 Jul 2019
Jul 30, 2019 · The spectral radius (also called the Frobenius-Perron dimension) of a matrix is an elementary and extremely useful invariant in linear ...<|control11|><|separator|>
[40]
https://doi.org/10.1007/BF01449896
[41]
[PDF] G. Frobenius Über Matrizen aus positiven Elementen
Frosenıus: Über Matrizen aus positiven Elementen. 471. Über Matrizen aus positiven Elementen. Von G. FRroBENIUS. Sad die Elemente einer Matrix alle reell und ...