|
The Perron-Frobenius theorem for homogeneous, monotone functions
Author(s):
Stéphane
Gaubert;
Jeremy
Gunawardena
Journal:
Trans. Amer. Math. Soc.
356
(2004),
4931-4950.
MSC (2000):
Primary 47J10;
Secondary 47H09, 47H07, 15A48
Posted:
March 23, 2004
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
If is a nonnegative matrix whose associated directed graph is strongly connected, the Perron-Frobenius theorem asserts that has an eigenvector in the positive cone, . We associate a directed graph to any homogeneous, monotone function, , and show that if the graph is strongly connected, then has a (nonlinear) eigenvector in . 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:
-
- 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.
Idempotency. 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
Email:
Stephane.Gaubert@inria.fr
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
Email:
jgunawardena@cgr.harvard.edu, jeremy@hms.harvard.edu
DOI:
10.1090/S0002-9947-04-03470-1
PII:
S 0002-9947(04)03470-1
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
Posted:
March 23, 2004
Copyright of article:
Copyright
2004,
American Mathematical Society
|