×

Semigroup of matrices acting on the max-plus projective space. (English) Zbl 1189.15020

The max-plus semifield \(\mathbb{R}_{\max}\) is the set \(\mathbb{R}\cup\{-\infty\}\) equipped with the operations \(\boxplus=\max\) and \(\boxtimes= +\). The author investigates the action of semigroups of \(d\times d\) matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.
In terms of orbits, the main result of the paper states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most \(d\)! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton. The proof of the main result is preceded by some elements of spectral and asymptotic theory of max-plus matrices and by the proof of a theorem on nice semigroups of matrices \(S\subset\mathbb{R}^{d\times d}_{\max}\), which implies the main result for semigroups of projective maps defined by a nice semigroup of matrices.
In the final part of the paper, the author deduces as a corollary of the main result the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.

MSC:

15A30 Algebraic systems of matrices
20M30 Representation of semigroups; actions of semigroups on sets
15B52 Random matrices (algebraic aspects)
60F05 Central limit and other weak theorems
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI

References:

[1] F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, An algebra for discrete event systems, Synchronization and Linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons Ltd., Chichester, 1992.; F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, An algebra for discrete event systems, Synchronization and Linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons Ltd., Chichester, 1992. · Zbl 0824.93003
[2] Baccelli, F.; Hong, D., Tcp is max-plus linear and what it tells us on its throughput, (SIGCOMM 00: Proceedings of the Conference on Applications, Technologies, Architectures and Protocols for Computer Communication (2000), ACM Press), 219-230
[3] Butkovič, Peter, Strong regularity of matrices—a survey of results, Discrete Appl. Math., 48, 1, 45-68 (1994) · Zbl 0804.06017
[4] Butkovic, P., Simple image set of (max; +) linear mappings, Discrete Appl. Math., 105, 73-86 (2000) · Zbl 0976.15013
[5] G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, Analyse du comportement périodique des systèmes de production par la théorie des dioı¨ des, Rapport de recherche 191, INRIA, Le Chesnay, France, 1983.; G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, Analyse du comportement périodique des systèmes de production par la théorie des dioı¨ des, Rapport de recherche 191, INRIA, Le Chesnay, France, 1983.
[6] Cohen, G.; Dubois, D.; Quadrat, J. P.; Viot, M., A linear system theoretic view of discrete event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control, AC-30, 210-220 (1985) · Zbl 0557.93005
[7] Raymond Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin, 1979.; Raymond Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin, 1979. · Zbl 0399.90052
[8] Cohen, J. E., Subadditivity, generalized products of random matrices and operations research, SIAM Rev., 30, 1, 69-86 (1988) · Zbl 0639.60091
[9] Crandall, M. G.; Tartar, L., Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc., 78, 3, 385-390 (1980) · Zbl 0449.47059
[10] M. Develin, F. Santos, B. Sturmfels, On the rank of a tropical matrix, in: E. Goodman, J. Pach, E. Welzl (Eds.), Discrete and Computational Geometry, vol. 52, MSRI Publications, Cambridge Univ. Press, 2005, pp. 213-242.; M. Develin, F. Santos, B. Sturmfels, On the rank of a tropical matrix, in: E. Goodman, J. Pach, E. Welzl (Eds.), Discrete and Computational Geometry, vol. 52, MSRI Publications, Cambridge Univ. Press, 2005, pp. 213-242. · Zbl 1095.15001
[11] Gaubert, S., On the burnside problem for semigroups of matrices in the (max, +) algebra, Semigroup Forum, 52, 271-292 (1996) · Zbl 0858.20050
[12] S. Gaubert, D. Hong, Series Expansions of Lyapunov Exponents and Forgetful Monoids, Technical report, INRIA, 2000.; S. Gaubert, D. Hong, Series Expansions of Lyapunov Exponents and Forgetful Monoids, Technical report, INRIA, 2000.
[13] Heidergott, B.; de Vries, R., Towards a (Max,+) control theory for public transportation networks, Discrete Event Dyn. Syst., 11, 4, 371-398 (2001) · Zbl 0999.93046
[14] Hennion, H., Limit theorems for products of positive random matrices, Ann. Probab., 25, 4, 1545-1587 (1997) · Zbl 0903.60027
[15] D. Hong, Lyapunov Exponents: When the Top Joins the Bottom, Technical Report RR-4198, INRIA, 2001, <http://www.inria.fr/rrrt/rr-4198.html>; D. Hong, Lyapunov Exponents: When the Top Joins the Bottom, Technical Report RR-4198, INRIA, 2001, <http://www.inria.fr/rrrt/rr-4198.html>
[16] B. Heidergott, G.J. Oldser, J. van der Woude, Modeling and analysis of synchronized systems: a course on max-plus algebra and its applications, Max Plus at Work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2006.; B. Heidergott, G.J. Oldser, J. van der Woude, Modeling and analysis of synchronized systems: a course on max-plus algebra and its applications, Max Plus at Work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2006. · Zbl 1130.93003
[17] Kakutani, S., Two fixed-point theorems concerning bicompact convex sets, Proc. Imp. Acad., 14, 7, 242-245 (1938) · JFM 64.1101.03
[18] Mairesse, J., Products of irreducible random matrices in the \((\max, +)\) algebra, Adv. in Appl. Probab., 29, 2, 444-477 (1997) · Zbl 0890.60063
[19] G. Merlet, Memory Loss Property for Products of Random Matrices in the \(( \max , + )\)<http://hal.archives-ouvertes.fr/ccsd-00001607>; G. Merlet, Memory Loss Property for Products of Random Matrices in the \(( \max , + )\)<http://hal.archives-ouvertes.fr/ccsd-00001607> · Zbl 1217.93102
[20] G. Merlet, Limit Theorems for Iterated Random Topical Operators, Technical report, IRMAR, submitted for publication, <http://hal.archives-ouvertes.fr/ccsd-00004594>; G. Merlet, Limit Theorems for Iterated Random Topical Operators, Technical report, IRMAR, submitted for publication, <http://hal.archives-ouvertes.fr/ccsd-00004594>
[21] Merlet, G., A central limit theorem for stochastic recursive sequences of topical operators, Ann. Appl. Probab., 17, 4, 1347-1361 (2007) · Zbl 1220.60016
[22] Merlet, G., Cycle time of stochastic max-plus linear systems, Electron. J. Probab., 13, 322-340 (2008) · Zbl 1190.60021
[23] S. Sergeev, Multiorder, kleene stars and cyclic projectors in the geometry of max cones, 2008, <http://arxiv.org/abs/0807.0921; S. Sergeev, Multiorder, kleene stars and cyclic projectors in the geometry of max cones, 2008, <http://arxiv.org/abs/0807.0921 · Zbl 1179.15033
[24] Vincent, J.-M., Some ergodic results on stochastic iterative discrete events systems, Discrete Event Dyn. Syst., 7, 2, 209-232 (1997) · Zbl 0880.93057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.