Source-linked AI summary
Perron-Frobenius theorem for nonnegative multilinear forms and extensions
S. Friedland, S. Gaubert, L. Han
TL;DR
The paper asks when nonnegative multilinear and polynomial maps possess unique positive eigenvectors, extending classical Perron-Frobenius theory beyond matrices. It uses homogeneous monotone-map and graph arguments, then analyzes a power algorithm. The main results give uniqueness under weak irreducibility with p_j ≥ d and establish convergence under weak primitivity, while identifying scope limitations.
Problem
The paper addresses uniqueness and convergence questions for eigenproblems of nonnegative multilinear forms and, more generally, polynomial maps.
Method
The paper reduces the multilinear problem to homogeneous monotone maps, uses graph connectivity for eigenvector results, extends the framework to polynomial maps, and analyzes a power algorithm.
Results
Under weak irreducibility and p_j ≥ d, the multilinear system has a unique positive solution; weak primitivity guarantees convergence of the power algorithm to a normalized eigenvector.
Takeaways & Limitations
The results extend Perron-Frobenius theory from nonnegative matrices to multilinear and polynomial maps, including an asymptotic convergence-rate characterization for the power algorithm.
Takeaways & Limitations
Weak primitivity does not ensure that every nonzero initialization reaches a vector with positive coordinates, and theorem conclusions can fail when exponent conditions are violated.
Abstract
from arXiv · showhide
We prove an analog of Perron-Frobenius theorem for multilinear forms with nonnegative coefficients, and more generally, for polynomial maps with nonnegative coefficients. We determine the geometric convergence rate of the power algorithm to the unique normalized eigenvector.
1 Introduction
The paper establishes Perron-Frobenius-type results for nonnegative multilinear forms, including uniqueness under weak irreducibility and exponent conditions, and extends them to polynomial eigenproblems and computation.
- Setting: The paper studies nonnegative multilinear forms represented by tensors and associated with d-partite graphs.The tensor is nonnegative when all multilinear coefficients are nonnegative.
- Main result: Theorem 1.1 gives sufficient conditions for uniqueness of positive solutions of system (1.2) for weakly irreducible and irreducible nonnegative tensors.Weak irreducibility is defined through connectivity of the associated graph, while irreducibility uses a stronger subset condition.
- Main result: Under weak irreducibility and p_j ≥ d for every j, system (1.2) has a unique positive solution.This is the theorem’s principal existence-and-uniqueness statement.
- Novelty and scope: For d ≥ 3 and p_1 = ⋯ = p_d = d, the result applies under weak irreducibility rather than the irreducibility required by earlier work.The paper also gives examples showing failure when the conditions p_j ≥ d are not satisfied.
- Extensions and computation: The paper extends the conclusions to more general polynomial eigenvalue problems and derives a weak-primitivity condition ensuring power-algorithm convergence with a spectral-gap-type asymptotic rate.The power sequence agrees with an earlier tensor algorithm up to normalization.
2 Eigenvectors of homogeneous monotone maps on Rn
This section develops the theory of homogeneous monotone maps on the positive cone, using Hilbert’s metric and graph conditions to obtain eigenvector existence, uniqueness, and convergence results.
- Hilbert metric: Hilbert’s metric measures the logarithmic spread between coordinatewise scaling bounds and becomes a metric on normalized rays.It identifies colinear positive vectors and is complete on the relevant normalized spaces.
- Homogeneous monotone maps: Homogeneous monotone maps preserve order and scale linearly on the interior of the nonnegative cone.An eigenvector satisfies F(x) = λx for a positive vector x and eigenvalue λ.
- Uniqueness: A contraction in Hilbert’s metric yields a unique projective fixed point by the Banach fixed point theorem.The corresponding map therefore has a unique positive eigenvector up to scaling.
- Boundary behavior: The Brouwer fixed-point construction guarantees an eigenvector in the nonnegative cone, but that eigenvector may lie on the boundary.Additional conditions are needed to ensure positivity.
- Existence: Strong connectivity of the associated digraph provides a sufficient condition for existence of an eigenvector in the positive cone.The graph condition is applied to homogeneous monotone maps.
- Jacobian criteria: A simple positive spectral-radius condition for the Jacobian, including primitivity as a special case, gives uniqueness of the positive eigenvector.The Jacobian is nonnegative because the map is monotone.
3 Proof of the main theorem
The proof converts the multilinear eigenproblem into a homogeneous monotone-map problem, uses graph connectivity and Jacobian arguments for uniqueness, and then establishes positivity and normalization for the original system.
- Graph construction: The tensor’s directed graph records effective variable dependence, with additional within-block edges determined by the exponent conditions.These edges connect coordinates when variables effectively appear in the corresponding map components.
- Graph conditions: Weak irreducibility implies strong connectivity of the directed graph used for the monotone-map theorem.This supplies the connectivity hypothesis needed in the existence argument.
- Existence and uniqueness: Under the stated exponent conditions and strong connectivity, the map has a unique positive eigenvector up to a positive multiple.The eigenvector and eigenvalue satisfy F(ξ_1, …, ξ_d) = μ(ξ_1, …, ξ_d).
- Existence and uniqueness: Any positive eigenvector has the same eigenvalue and is a positive scalar multiple of the distinguished eigenvector.This is the uniqueness statement used to identify all positive solutions.
- Positivity: For equal exponents p_j = p ≥ d and irreducible F, every admissible nonnegative eigenvector is necessarily positive and unique up to scaling.The proof rules out zero coordinates by contradicting irreducibility.
- Normalization: Normalizing the first factor in its p_1-norm forces the remaining factor norms to equal one and converts the eigenvector equation into system (1.2).The associated scalar is λ = μ^(p−1).
- Conclusion: The irreducible case therefore yields a unique positive solution of system (1.2).The argument also establishes positivity of λ and all factor coordinates.
4 Extension: Perron-Frobenius theorem for nonnegative polynomial maps
The paper extends Perron-Frobenius-type existence and uniqueness results from multilinear forms to polynomial maps with nonnegative coefficients, including a Collatz-Wielandt characterization for homogeneous maps.
- Definitions: A polynomial map is weakly irreducible when its associated directed graph, linking each output to effectively appearing variables, is strongly connected.Irreducibility additionally excludes nontrivial invariant parts of the nonnegative cone and implies weak irreducibility.
- Existence and uniqueness: Under weak irreducibility, for every a,p > 0, the normalized system (4.1) has a unique positive solution.The solution depends on the normalization parameters a and p.
- Existence and uniqueness: Under irreducibility, the normalized system has a unique solution, and every coordinate of that solution is positive.The proof uses invariance of the support part Q_I to rule out solutions with zero coordinates.
- Proof strategy: The construction embeds the polynomial map into a homogeneous monotone map of degree one whose directed graph contains the polynomial map’s graph.This permits Perron-Frobenius results for homogeneous monotone maps to establish existence and uniqueness for the polynomial eigenproblem.
- Homogeneous case: For homogeneous polynomial maps, the eigenvalue admits a Collatz-Wielandt-type minimax characterization analogous to the spectral-radius characterization of the Perron root.The paper identifies the polynomial eigenvalue as λ = µ^d, where µ is the associated homogeneous-map eigenvalue.
- Homogeneous case: The extension also bounds complex eigenvalues through the positive Perron eigenvalue of the homogeneous polynomial problem.For a complex eigenpair, applying the nonnegative map to coordinatewise moduli yields a comparison involving |ν|.
5 Algorithmic aspects
The paper analyzes a normalized power algorithm for homogeneous nonnegative polynomial maps. Weak primitivity guarantees convergence to the unique normalized positive eigenvector, while linearization supplies an explicit asymptotic rate.
- Convergence condition: Weak primitivity requires a strongly connected directed graph whose circuit lengths have greatest common divisor one.The condition is the polynomial-map analogue of primitivity used to obtain convergence.
- Scope boundary: Weak primitivity does not ensure that every nonzero initial vector becomes strictly positive after finitely many iterations.The convergence result therefore uses an initial vector from the interior rather than an arbitrary nonzero vector.
- Convergence condition: Under weak primitivity, the power algorithm converges to the unique normalized vector u in the interior of the nonnegative cone.The iteration starts from an arbitrary vector in the cone’s interior and uses normalization by ψ^⊤F(x(k)).
- Convergence rate: The convergence is geometric, but the general bound approaches rate 1 as the initial vector moves farther from u in Hilbert’s projective metric.The paper then linearizes the iteration around u to estimate its asymptotic speed explicitly.
- Convergence rate: The asymptotic rate is governed by the eigenvalues of the derivative matrix M = F′(u) after removing the Perron direction.If r is the maximal modulus of the remaining eigenvalues, Corollary 5.2 gives the corresponding rate for the normalized iterates.
6 Examples and remarks
The examples show that the threshold p_j ≥ d is necessary for uniqueness, while connectedness alone does not prevent multiple solutions below it. They also compare the multilinear results with classical matrix and tensor Perron–Frobenius settings.
- Examples for p < d: For p ≥ 3, the example tensor has the unique solution x1 = x2 = x3 = (0.51/p, 0.51/p)⊤.For p = 2 < d = 3, two additional positive solutions appear.
- Examples for p < d: For p = 2 < d = 3, the same example has two additional positive solutions beyond the symmetric positive solution.This demonstrates failure of uniqueness below the theorem’s p ≥ d condition.
- Examples for p < d: Weakly irreducible tensors can violate Theorem 1.1 even when p is very close to d.The paper introduces a positive tensor F2 as an example of this failure.
- Relation to earlier tensor results: For d = 3 and p = d, the induced tensor C is reducible even though the multilinear formulation is being compared with an irreducible-tensor theorem.The construction sets x1 = x2 = 0 and x3 = 1, making the left-hand side zero in every equation.
- Bilinear-form variation: For d = 2 and p1 = p2 = 1.5 < d, the system has three solutions; unequal exponents p1 = 1.2 and p2 = 2.5 also yield three positive solutions.These examples show that connectedness of the associated bipartite graph does not ensure the classical conclusion below the threshold.