Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The Perron-Frobenius theorem for homogeneous, monotone functions

Authors: Stéphane Gaubert and Jeremy Gunawardena
Journal: Trans. Amer. Math. Soc. 356 (2004), 4931-4950
MSC (2000): Primary 47J10; Secondary 47H09, 47H07, 15A48
Published electronically: March 23, 2004
MathSciNet review: 2084406
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: If $A$ is a nonnegative matrix whose associated directed graph is strongly connected, the Perron-Frobenius theorem asserts that $A$ has an eigenvector in the positive cone, $(\mathbb R^{+})^n$. We associate a directed graph to any homogeneous, monotone function, $f: (\mathbb R^{+})^n \rightarrow (\mathbb R^{+})^n$, and show that if the graph is strongly connected, then $f$ has a (nonlinear) eigenvector in $(\mathbb R^{+})^n$. Several results in the literature emerge as corollaries. Our methods show that the Perron-Frobenius theorem is ``really'' about the boundedness of invariant subsets in the Hilbert projective metric. They lead to further existence results and open problems.

References [Enhancements On Off] (What's this?)

  • 1. M. Akian and S. Gaubert.
    Spectral theorem for convex monotone homogeneous maps and ergodic control.
    Nonlinear Analysis, 52:637-679, 2003. MR 2003i:93085
  • 2. S. Amghibech and C. Dellacherie.
    Une version non-linéaire, d'après G. J. Olsder, du théorème d'existence et d'unicité d'une mesure invariante pour une transition sur un espace fini.
    Séminaire de Probabilités de Rouen, 1994.
  • 3. F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat.
    Synchronization and Linearity.
    Wiley Series in Probability and Mathematical Statistics. John Wiley, 1992. MR 94b:93001
  • 4. J. Bather.
    Optimal decision procedures for finite Markov chains. Part II: communicating systems.
    Advances in Applied Probability, 5:521-540, 1973. MR 54:14791
  • 5. A. Berman and R. J. Plemmons.
    Nonnegative Matrices in the Mathematical Sciences.
    Classics in Applied Mathematics. SIAM, 1994. MR 95e:15013
  • 6. G. Birkhoff.
    Extensions of Jentzsch's theorem.
    Transactions of the AMS, 85:219-227, 1957. MR 19:296a
  • 7. T. Bousch and J. Mairesse.
    Fonctions topicales à portée finie et fonctions uniformément topicales.
    Préprint LIAFA 2003-002.
  • 8. A. D. Burbanks, R. D. Nussbaum, and C. T. Sparrow.
    Continuous extension of order-preserving homogeneous maps.
    Kybernetica, 39(2):205-215, 2003.
  • 9. M. G. Crandall and L. Tartar.
    Some relations between nonexpansive and order preserving maps.
    Proceedings of the AMS, 78(3):385-390, 1980. MR 81a:47054
  • 10. C. Dellacherie.
    Modèles simples de la théorie du potentiel non-linéaire, pages 52-104.
    Number 1426 in Lecture Notes in Mathematics. Springer, 1990. MR 91k:31015
  • 11. E. Dietzenbacher.
    The non-linear Perron-Frobenius theorem.
    Journal of Mathematical Economics, 23:21-31, 1994. MR 95d:90021
  • 12. S. Gaubert and J. Gunawardena.
    A non-linear hierarchy for discrete event dynamical systems.
    Proceedings of WODES'98, IEE, Cagliari, Italy, August 1998.
  • 13. S. Gaubert and J. Gunawardena.
    Existence of eigenvectors for monotone homogeneous functions.
    Technical Report HPL-BRIMS-99-008, Hewlett-Packard Labs, 1999.
  • 14. K. Goebel and W. A. Kirk.
    Topics in Metric Fixed Point Theory, volume 28 of Cambridge Studies in Advanced Mathematics.
    Cambridge University Press, 1990. MR 92c:47070
  • 15. Max-Plus Working Group.
    Max-plus algebra and applications to system theory and optimal control.
    In Proceedings of the International Congress of Mathematicians, Zürich, 1994. Birkhäuser, 1995.
  • 16. J. Gunawardena, editor.
    Publications of the Isaac Newton Institute. Cambridge University Press, 1998. MR 99b:16072
  • 17. J. Gunawardena.
    From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems.
    Theoretical Computer Science, 293:141-167, 2003.
  • 18. J. Gunawardena and M. Keane.
    On the existence of cycle times for some nonexpansive maps.
    Technical Report HPL-BRIMS-95-003, Hewlett-Packard Labs, 1995.
  • 19. E. Kohlberg.
    Invariant half-lines of nonexpansive piecewise-linear transformations.
    Mathematics of Operations Research, 5(3):366-372, 1980. MR 82a:55005
  • 20. E. Kohlberg and J. W. Prat.
    The contraction mapping approach to the Perron-Frobenius theory: why Hilbert's metric?
    Mathematics of Operations Research, 7:198-210, 1982. MR 83m:15013
  • 21. V. N. Kolokoltsov.
    Nonexpansive maps and option pricing theory.
    Kybernetika, 34:713-724, 1998. MR 2000e:91077
  • 22. V. N. Kolokoltsov and V. P. Maslov.
    Idempotent Analysis and Applications.
    Kluwer Academic, 1997.
  • 23. M. A. Krasnoselskii.
    Positive Solutions of Operator Equations.
    Noordhoff, 1964. MR 31:6107
  • 24. M. G. Krein and M. A. Rutman.
    Linear operators leaving invariant a cone in a Banach space.
    Uspehi Matematiceskih Nauk, 3:3-95, 1948.
    Available as AMS Translations Number 26. MR 10:256c
  • 25. V. P. Maslov and S. N. Samborskii, editors.
    Idempotent Analysis, volume 13 of Advances in Soviet Mathematics.
    American Mathematical Society, 1992. MR 93h:00018
  • 26. H. Minc.
    Nonnegative Matrices.
    Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley, 1988. MR 89i:15001
  • 27. M. Morishima.
    Equilibrium, Stability and Growth.
    London, 1964. MR 32:1006
  • 28. R. D. Nussbaum.
    Convexity and log convexity for the spectral radius.
    Linear Algebra and its Applications, 73:59-122, 1986. MR 87g:15026
  • 29. R. D. Nussbaum.
    Hilbert's projective metric and iterated nonlinear maps.
    Memoirs of the AMS, 75(391), 1988. MR 89m:47046
  • 30. R. D. Nussbaum.
    Iterated nonlinear maps and Hilbert's projective metric, II.
    Memoirs of the AMS, 79(401), 1989. MR 90c:47109
  • 31. Y. Oshime.
    An extension of Morishima's nonlinear Perron-Frobenius theorem.
    Journal of Mathematics of Kyoto University, 23:803-830, 1983. MR 85k:65045
  • 32. D. Rosenberg and S. Sorin.
    An operator approach to zero-sum repeated games.
    Israel Journal of Mathematics, 121:221-246, 2001. MR 2002k:91031
  • 33. R. Solow and P. A. Samuelson.
    Balanced growth under constant returns to scale.
    Econometrica, 21:412-424, 1953. MR 15:49b
  • 34. W. H. M. Zijm.
    Generalized eigenvectors and sets of nonnegative matrics.
    Linear Algebra and its Applications, 59:91-113, 1984. MR 85f:15018

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 47J10, 47H09, 47H07, 15A48

Retrieve articles in all journals with MSC (2000): 47J10, 47H09, 47H07, 15A48

Additional Information

Stéphane Gaubert
Affiliation: INRIA, Domaine de Voluceau, B.P. 105, 78153 Le Chesnay Cédex, France

Jeremy Gunawardena
Affiliation: Bauer Center for Genomics Research, Harvard University, 7 Divinity Avenue, Cambridge, Massachusetts 02139
Address at time of publication: Department of Systems Biology, Harvard Medical School, 200 Longwood Avenue, Boston, Massachusetts 02115

Keywords: Collatz-Wielandt property, Hilbert projective metric, nonexpansive function, nonlinear eigenvalue, Perron-Frobenius theorem, strongly connected graph, super-eigenspace, topical function
Received by editor(s): May 10, 2001
Received by editor(s) in revised form: July 2, 2003
Published electronically: March 23, 2004
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society