Menu: Home :: go to Journal :: switch to Russian :: switch to English
You are here: all Journals and Issues→ Journal→ Issue→ Article

Core of a matrix in max algebra and in nonnegative algebra: A survey


This paper presents a light introduction to Perron–Frobenius theory in max algebra and in nonnegative linear algebra, and a survey of results on two cores of a nonnegative matrix. The (usual) core of a nonnegative matrix is defined as ∩_(k≥1) span_+ (A^k) , that is, intersection of the nonnegative column spans of matrix powers. This object is of importance in the (usual) Perron-Frobenius theory, and it has some applications in ergodic theory. We develop the direct max-algebraic analogue and follow the similarities and differences of both theories.


max algebra; nonnegative matrix theory; Perron–Frobenius theory; matrix power; eigenspace; core

Full-text in one file









[1] N. N. Vorob’ev, “The extremal matrix algebra”, Soviet Mathematics Doklady, 4 (1963), 1220–1223. [2] N. N. Vorob’ev, “Extremal Algebra of Positive Matrices”, Elektronische Informationsverarbeitung und Kybernetik, 3:1 (1967), 39–71 (In Russian). [3] N. N. Vorob’ev, “Extremal Algebra of Non-Negative Matrices”, Elektronische Informationsverarbeitung und Kybernetik, 6:4–5 (1970), 303–312 (In Russian). [4] P. I. Dudnikov, S. N. Samborski˘ı, “Endomorphisms of finitely generated free semimodules”, Math. USSR-Izv., 38:1 (1992), 91–105. [5] N. K. Krivulin, Methods of Idempotent Algebra in Problems of Modeling and Analysis of Complex Systems, Publ. St. Petersburg State. University, St. Petersburg, 2009 (In Russian). [6] G. L. Litvinov, V.P. Maslov, A. N. Sobolevskii, “Idempotent interval analysis and optimization problems”, Reliable Computing, 7:5 (2001), 353–377, arXiv: org/abs/math.SC/0101080. [7] V.P. Maslov, “On new principle of superposition for optimization problems”, Russian Math. Surveys, 42:3 (1987), 43–54. [8] V. N. Kolokoltsov, V.P. Maslov, Idempotent Analysis and Its Applications, Kluwer Academic Pub., 1997. [9] G. B. Shpiz, “An eigenvector existence theorem in idempotent analysis”, Math. Notes, 82:3 (2007), 410–417. [10] M. Akian, R. Bapat, S. Gaubert, “Max-plus algebras”, Handbook of Linear Algebra. V. 39: Discrete Mathematics and its Applications, eds. L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias, Chapman and Hall, London; New York, 2007. [11] F. L. Baccelli, G. Cohen, G. J. Olsder, J. P. Quadrat, “Synchronization and Linearity: an Algebra for Discrete Event Systems”, Journal of the Operational Research Society, 45:1 (1994). [12] A. Berman, R .J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Society for Industrial and Applied Mathematics, Philadelphia, 1994. [13] S. Bezuglyi, J. Kwiatkowski, K. Medynets, B. Solomyak, “Invariant measures on stationary Bratteli diagrams”, Ergodic Theory Dynam. Systems, 30:4 (2010), 973–1007. [14] R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge, 1991. [15] P. Butkovic, “Max-algebra: the linear algebra of combinatorics?”, Linear Alg. Appl., 367 (2003), [16] P. Butkovic, Max-linear Systems: Theory and Algorithms, Springer, London, 2010. [17] P. Butkovic, R. A. Cuninghame-Green, S. Gaubert, “Reducible spectral theory with applications to the robustness of matrices in max-algebra”, SIAM J. on Matrix Analysis and Applications, 31:3 (2009), 1412–1431. [18] P. Butkovic, H. Schneider, S. Sergeev, “Generators, extremals and bases of max cones”, Linear Alg. Appl., 421 (2007), 394–406, arXiv: org/abs/math.RA/0604454. [19] P. Butkovic, H. Schneider, S. Sergeev, “Two cores of a nonnegative matrix, submitted”, 2012, arXiv: org/abs/math.RA/1208.1939. [20] P. Butkovic, H. Schneider, S. Sergeev, “On the max-algebraic core of a nonnegative matrix”, 2013, arXiv: org/abs/1305.7339. [21] P. Butkovic, H. Schneider, S. Sergeev, “Z-matrix equations in max algebra, nonnegative linear algebra and other semirings”, Linear and Multilin. Alg., 60:10 (2012), 1191-1210, arXiv:org/abs/1110.4564. [22] M.-H. Chi, “The long-run behaviour of Markov chains”, Linear Alg. Appl., 244 (1996), 111–121. [23] G. Cohen, D. Dubois, J. P. Quadrat, M. Viot, “Analyse du comportement p´eriodique de syst`emes de production par la th´eorie des dio¨ıdes”, Rapport de Recherche, 1983, №191. [24] R. A. Cuninghame-Green, “Minimax Algebra”, Lecture Notes in Economics and Mathematical Systems. V. 166, Springer, Berlin, 1979. [25] R. A. Cuninghame-Green, “Describing industrial processes with interference and approximating their steady-state behaviour”, Operations Research, 13:1 (1962), 95–100. [26] G. F. Frobenius, “ ¨Uber Matrizen aus nicht negativen Elementen”, Sitzungsberichte der K¨oniglich Preussischen Akademie der Wissenschaften, 23, Sitzungsberichte, Berlin, 1912, 456–477. [27] S. Gaubert, Th´eorie des syst`emes lin´eaires dans les dio¨ıdes, PhD thesis, Th`ese de l’Ecole Nationale Sup´erieure des Mines de Paris, Juillet, 1992, 304 pp. [28] S. Gaubert, R. D. Katz, “The Minkowski theorem for max-plus convex sets”, Linear Alg. Appl., 421:2-3 (2007), 356–369, arXiv: org/abs/math.GM/0605078. [29] M. Gavalec, Periodicity in Extremal Algebras, Gaudeamus, Hradec Kr´alov´e, 2004. [30] M. Gondran, M. Minoux, “Valeurs propres et vecteurs propres dans les dio¨ıdes”, EDF Bulletin de la Direction des Etudes et Recherches. Serie C. Mathematiques Informatique, 2 (1977), 25–41. [31] D. J. Hartfiel, Nonhomogeneous Matrix Products, World Scientific, Singapore, 2002. [32] B. Heidergott, G.-J. Olsder, J. van der Woude, Max-plus at Work, Princeton Univ. Press, Princeton, 2005. [33] R. D. Katz, H. Schneider, S. Sergeev, “On commuting matrices in max algebra and in classical nonnegative algebra”, Linear Alg. Appl., 436 (2012), 276–292, arXiv: org/abs/1005.1424. [34] C.-K. Li, H. Schneider, “Applications of Perron-Frobenius theory to population dynamics”, J. of Mathematical Biology, 44:5 (2002), 450–462, arXiv: org/abs/math.RA/0109008. [35] G. L. Litvinov, V.P. Maslov, “The correspondence principle for idempotent calculus and some computer applications”, Idempotency, ed. J. Gunawardena, Cambridge Univ. Press, Cambridge, 1998, 420–443, arXiv: org/abs/math/0101021. [36] G. L. Litvinov, V.P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005. [37] G. L. Litvinov, V.P. Maslov, S. N. Sergeev, Idempotent and tropical mathematics and problems of mathematical physics. V. 1,2, Independent University of Moscow, Moscow, 2007, arXiv:org/abs/0709.4119. [38] G. L. Litvinov, S. N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009. [39] Advances in Soviet Mathematics. V. 13: Idempotent analysis, ed. V.P. Maslov, S. N. Samborski˘ı, AMS, Providence, 1992. [40] W. M. McEneaney, Max-plus Models for Nonlinear Control and Estimation, Systems & Control:Foundations & Applications, Birkh¨auser, Boston, 2006. [41] G. Merlet, “Semigroup of matrices acting on the max-plus projective space”, Linear Alg. Appl., 432:8 (2010), 1923–1935. [42] M. Moln´arov´a, “Generalized matrix period in max-plus algebra”, Linear Alg. Appl., 404 (2005), 345–366. [43] M. Moln´arov´a, J. Pribiˇs, “Matrix period in max-algebra”, Discrete Appl. Math., 103 (2000), 167–175. [44] N. J. Pullman, “A geometric approach to the theory of nonnegative matrices”, Linear Alg. Appl., 4 (1971), 297–312. [45] H. Schneider, “The influence of the marked reduced graph of a nonnegative matrix on the Jordan form and on related properties: A survey”, Linear Alg. Appl., 84 (1986), 161–189. [46] B. De Schutter, “On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra”, Linear Alg. Appl., 307 (2000), 103–117. [47] E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 1981. [48] S. Sergeev, “Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes”, Linear Alg. Appl., 431:6 (2009), 1325–1339, arXiv: org/abs/0903.3960. [49] S. Sergeev, H. Schneider, “CSR expansions of matrix powers in max algebra”, Transactions of AMS, 364 (2012), 5969–5994, arXiv: org/abs/0912.2534. [50] S. Sergeev, H. Schneider, P. Butkoviˇc, “On visualization scaling, subeigenvectors and Kleene stars in max algebra”, Linear Alg. Appl., 431:12 (2009), 2395–2406, arXiv: org/abs/0808.1992. [51] G. Sierksma, “Limiting polytopes and periodic Markov chains”, Linear and Multilinear Algebra, 46 (1999), 281–298. [52] B.-S. Tam, H. Schneider, “On the core of a cone-preserving map”, Transactions of the AMS, 343:2 (1994), 479–524. [53] E. Wagneur, “Modulo¨ıds and pseudomodules. 1. Dimension theory”, Discrete Math., 98 (1991), 57–73.



Section of issue

Scientific articles

Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.