Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

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 $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:

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


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google