The Perron-Frobenius theorem for homogeneous, monotone functions. (English) Zbl 1067.47064

Gaubert, Stéphane; Gunawardena, Jeremy

Trans. Am. Math. Soc. 356, No. 12, 4931-4950 (2004).

The classical Perron-Frobenius theorem is extended to nonlinear maps. We state the main result of the paper. Let \(\mathbb{R}^+\) be the set of positive reals. A map \(f:(\mathbb{R}^+)^n \to(\mathbb{R}^+)^n\) of the positive cone in the \(n\)-dimensional real vector space is called homogeneous if \(f(\lambda x)=\lambda f(x)\) for every \(\lambda\in \mathbb{R}^+\) and for every \(x\in(\mathbb{R}^+)^n\), and monotone if \(x\leq y\), \(x,y\in(\mathbb{R}^+)^n\) implies \(f(x)\leq f(y)\) (the partial order \(\leq\) in \((\mathbb{R}^+)^n\) is the product ordering). If \(f\) is any homogeneous monotone function, the associate graph \(G(f)\) is defined as a directed graph on the vertices \(\{1,2,\dots,n\}\), and with edge from \(i\) to \(j\) if and only if \[ \lim_{u\to\infty} f_i(u_{\{j\}}) =\infty, \] where \(f_i\) is the \(i\)th component of \(f\) and \(u_{\{j\}}\in (\mathbb{R}^+)^n\) has the \(j\)th component \(u\) and all other components 1.
Theorem. If \(f\) is a homogeneous monotone map, and if \(G(f)\) is strongly connected, i.e., there exists a directed path between any two distinct vertices, then \(f\) has an eigenvector, i.e., there exist \(x\in(\mathbb{R}^+)^n\) and \(\lambda\in\mathbb{R}^+\) such that \(f(x)=\lambda x\). In contrast to the case when \(f\) is linear, the vector \(x\) need not be unique (up to a scalar multiple).
The proof is based on the techniques of the Hilbert projective metric. In particular, the property that a homogeneous monotone function \(f\) has an eigenvector if and only if some orbit (and hence all orbits) of \(f\) are bounded in the Hilbert projective metric, plays a key role.

Reviewer: Leiba Rodman (Williamsburg)

MSC:

47H07	Monotone and positive operators on ordered Banach spaces or other ordered topological vector spaces
47J10	Nonlinear spectral theory, nonlinear eigenvalue problems
15B48	Positive matrices and their generalizations; cones of matrices

Keywords:

monotone maps; nonlinear eigenvectors; positive cone; Perron-Frobenius theorem

References:

[1]	Marianne Akian and Stéphane Gaubert, Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Anal. 52 (2003), no. 2, 637 – 679. · Zbl 1030.47048 · doi:10.1016/S0362-546X(02)00170-0
[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]	François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. · Zbl 0824.93003
[4]	John Bather, Optimal decision procedures for finite Markov chains. II. Communicating systems, Advances in Appl. Probability 5 (1973), 521 – 540. · Zbl 0275.90049 · doi:10.2307/1425832
[5]	Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. · Zbl 0815.15016
[6]	G. Birkhoff. Extensions of Jentzsch’s theorem. Transactions of the AMS, 85:219-227, 1957. · Zbl 0079.13502
[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. · Zbl 1249.93123
[9]	Michael G. Crandall and Luc Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), no. 3, 385 – 390. · Zbl 0449.47059
[10]	C. Dellacherie, Modèles simples de la théorie du potentiel non linéaire, Séminaire de Probabilités, XXIV, 1988/89, Lecture Notes in Math., vol. 1426, Springer, Berlin, 1990, pp. 63 – 104 (French). · doi:10.1007/BFb0083758
[11]	Erik Dietzenbacher, The nonlinear Perron-Frobenius theorem: perturbations and aggregation, J. Math. Econom. 23 (1994), no. 1, 21 – 31. · Zbl 0789.90020 · doi:10.1016/0304-4068(94)90033-7
[12]	S. Gaubert and J. Gunawardena. A non-linear hierarchy for discrete event dynamical systems. Proceedings of WODES’98, IEE, Cagliari, Italy, August 1998. · Zbl 0933.49017
[13]	S. Gaubert and J. Gunawardena. Existence of eigenvectors for monotone homogeneous functions. Technical Report HPL-BRIMS-99-008, Hewlett-Packard Labs, 1999.
[14]	Kazimierz Goebel and W. A. Kirk, Topics in metric fixed point theory, Cambridge Studies in Advanced Mathematics, vol. 28, Cambridge University Press, Cambridge, 1990. · Zbl 0708.47031
[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]	Jeremy Gunawardena, An introduction to idempotency, Idempotency (Bristol, 1994) Publ. Newton Inst., vol. 11, Cambridge Univ. Press, Cambridge, 1998, pp. 1 – 49. · Zbl 0898.16032 · doi:10.1017/CBO9780511662508.003
[17]	J. Gunawardena. From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems. Theoretical Computer Science, 293:141-167, 2003. · Zbl 1036.93045
[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]	Elon Kohlberg, Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res. 5 (1980), no. 3, 366 – 372. · Zbl 0442.90102 · doi:10.1287/moor.5.3.366
[20]	Elon Kohlberg and John W. Pratt, The contraction mapping approach to the Perron-Frobenius theory: why Hilbert’s metric?, Math. Oper. Res. 7 (1982), no. 2, 198 – 210. · Zbl 0498.15005 · doi:10.1287/moor.7.2.198
[21]	Vassili N. Kolokoltsov, Nonexpansive maps and option pricing theory, Kybernetika (Prague) 34 (1998), no. 6, 713 – 724. 5th IEEE Mediterranean Conference on Control and Systems (Paphos, 1997). · Zbl 1274.91420
[22]	V. N. Kolokoltsov and V. P. Maslov. Idempotent Analysis and Applications. Kluwer Academic, 1997. · Zbl 0941.93001
[23]	M. A. Krasnosel\(^{\prime}\)skiĭ, Positive solutions of operator equations, Translated from the Russian by Richard E. Flaherty; edited by Leo F. Boron, P. Noordhoff Ltd. Groningen, 1964.
[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. · Zbl 0030.12902
[25]	V. P. Maslov and S. N. Samborskiĭ , Idempotent analysis, Advances in Soviet Mathematics, vol. 13, American Mathematical Society, Providence, RI, 1992.
[26]	Henryk Minc, Nonnegative matrices, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1988. A Wiley-Interscience Publication. · Zbl 0638.15008
[27]	Michio Morishima, Equilibrium, stability, and growth: A multi-sectoral analysis, Clarendon Press, Oxford, 1964. · Zbl 0117.15406
[28]	Roger D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl. 73 (1986), 59 – 122. · Zbl 0588.15016 · doi:10.1016/0024-3795(86)90233-8
[29]	Roger D. Nussbaum, Hilbert’s projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc. 75 (1988), no. 391, iv+137. · Zbl 0666.47028 · doi:10.1090/memo/0391
[30]	Roger D. Nussbaum, Iterated nonlinear maps and Hilbert’s projective metric. II, Mem. Amer. Math. Soc. 79 (1989), no. 401, iv+118. · Zbl 0669.47031 · doi:10.1090/memo/0401
[31]	Yorimasa Oshime, An extension of Morishima’s nonlinear Perron-Frobenius theorem, J. Math. Kyoto Univ. 23 (1983), no. 4, 803 – 830. · Zbl 0548.34034
[32]	Dinah Rosenberg and Sylvain Sorin, An operator approach to zero-sum repeated games, Israel J. Math. 121 (2001), 221 – 246. · Zbl 1054.91014 · doi:10.1007/BF02802505
[33]	R. Solow and P. A. Samuelson. Balanced growth under constant returns to scale. Econometrica, 21:412-424, 1953. · Zbl 0050.36805
[34]	W. H. M. Zijm, Generalized eigenvectors and sets of nonnegative matrices, Linear Algebra Appl. 59 (1984), 91 – 113. · Zbl 0548.15015 · doi:10.1016/0024-3795(84)90161-7