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

Annotation

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.

Keywords

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

Full-text in one file

Download

DOI

10.20310/2686-9667-2019-24-127-252-271

UDC

512.643

Pages

252-271

References

[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.

Received

2019-06-21

Section of issue

Scientific articles

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