Geodesic
Core of a matrix in max algebra and in nonnegative algebra: a survey
Vestnik rossijskih universitetov. Matematika, Tome 24 (2019) no. 127, pp. 252-271 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $\cap_{k\geqslant 1} {\rm 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
Mots-clés : eigenspace, core. 
@article{VTAMU_2019_24_127_a1,
     author = {P. Butkovic and H. Schneider and S. Sergeev},
     title = {Core of a matrix in max algebra and in nonnegative algebra: a survey},
     journal = {Vestnik rossijskih universitetov. Matematika},
     pages = {252--271},
     year = {2019},
     volume = {24},
     number = {127},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTAMU_2019_24_127_a1/}
}
TY  - JOUR
AU  - P. Butkovic
AU  - H. Schneider
AU  - S. Sergeev
TI  - Core of a matrix in max algebra and in nonnegative algebra: a survey
JO  - Vestnik rossijskih universitetov. Matematika
PY  - 2019
SP  - 252
EP  - 271
VL  - 24
IS  - 127
UR  - http://geodesic.mathdoc.fr/item/VTAMU_2019_24_127_a1/
LA  - ru
ID  - VTAMU_2019_24_127_a1
ER  - 
%0 Journal Article
%A P. Butkovic
%A H. Schneider
%A S. Sergeev
%T Core of a matrix in max algebra and in nonnegative algebra: a survey
%J Vestnik rossijskih universitetov. Matematika
%D 2019
%P 252-271
%V 24
%N 127
%U http://geodesic.mathdoc.fr/item/VTAMU_2019_24_127_a1/
%G ru
%F VTAMU_2019_24_127_a1
P. Butkovic; H. Schneider; S. Sergeev. Core of a matrix in max algebra and in nonnegative algebra: a survey. Vestnik rossijskih universitetov. Matematika, Tome 24 (2019) no. 127, pp. 252-271. http://geodesic.mathdoc.fr/item/VTAMU_2019_24_127_a1/

[1] N. N. Vorob'ev, “The extremal matrix algebra”, Soviet Mathematics Doklady, 4 (1963), 1220–1223 | Zbl

[2] N. N. Vorob'ev, “Extremal Algebra of Positive Matrices”, Elektronische Informationsverarbeitung und Kybernetik, 3:1 (1967), 39–71 (In Russian) | MR

[3] N. N. Vorob'ev, “Extremal Algebra of Non-Negative Matrices”, Elektronische Informationsverarbeitung und Kybernetik, 6:4–5 (1970), 303–312 (In Russian) | MR

[4] P. I. Dudnikov, S. N. Samborskiĭ, “Endomorphisms of finitely generated free semimodules”, Math. USSR-Izv., 38:1 (1992), 91–105 | DOI | MR | MR

[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. Sobolevski{ĭ}, “Idempotent interval analysis and optimization problems”, Reliable Computing, 7:5 (2001), 353–377, arXiv: org/abs/math.NA/9911126 | DOI | MR | MR | Zbl | Zbl

[7] V. P. Maslov, “On new principle of superposition for optimization problems”, Russian Math. Surveys, 42:3 (1987), 43–54 | DOI | MR | Zbl

[8] V. N. Kolokoltsov, V. P. Maslov, Idempotent Analysis and Its Applications, Kluwer Academic Pub., 1997 | MR | MR | Zbl

[9] G. B. Shpiz, “An eigenvector existence theorem in idempotent analysis”, Math. Notes, 82:3 (2007), 410–417 | DOI | MR | Zbl

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

[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) | MR

[12] A. Berman, R .J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Society for Industrial and Applied Mathematics, Philadelphia, 1994 | MR

[13] S. Bezuglyi, J. Kwiatkowski, K. Medynets, B. Solomyak, “Invariant measures on stationary Bratteli diagrams”, Ergodic Theory Dynam. Systems, 30:4 (2010), 973–1007 | DOI | MR | Zbl

[14] R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge, 1991 | MR | Zbl

[15] P. Butkovič, “Max-algebra: the linear algebra of combinatorics?”, Linear Alg. Appl., 367 (2003), 313–335 | DOI | MR | Zbl

[16] P. Butkovič, Max-linear Systems: Theory and Algorithms, Springer, London, 2010 | MR | Zbl

[17] P. Butkovič, 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 | DOI | MR

[18] P. Butkovič, H. Schneider, S. Sergeev, “Generators, extremals and bases of max cones”, Linear Alg. Appl., 421 (2007), 394–406, arXiv: org/abs/math.RA/0604454 | DOI | MR | Zbl

[19] P. Butkovič, H. Schneider, S. Sergeev, “Two cores of a nonnegative matrix, submitted”, 2012, arXiv: org/abs/math.RA/1208.1939

[20] P. Butkovič, H. Schneider, S. Sergeev, “On the max-algebraic core of a nonnegative matrix”, 2013, arXiv: org/abs/1305.7339 | MR

[21] P. Butkovič, 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 | DOI | MR | Zbl

[22] M.-H. Chi, “The long-run behaviour of Markov chains”, Linear Alg. Appl., 244 (1996), 111–121 | DOI | MR | Zbl

[23] G. Cohen, D. Dubois, J. P. Quadrat, M. Viot, “Analyse du comportement périodique de systèmes de production par la théorie des dio{ï}des”, Rapport de Recherche, 1983, no. 191

[24] R. A. Cuninghame-Green, “Minimax Algebra”, Lecture Notes in Economics and Mathematical Systems, v. 166, Springer, Berlin, 1979 | DOI | MR | Zbl

[25] R. A. Cuninghame-Green, “Describing industrial processes with interference and approximating their steady-state behaviour”, Operations Research, 13:1 (1962), 95–100 | DOI

[26] G. F. Frobenius, “Über Matrizen aus nicht negativen Elementen”, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, 23, Sitzungsberichte, Berlin, 1912, 456–477

[27] S. Gaubert, Théorie des systèmes linéaires dans les dio{ï}des, PhD thesis, Thèse de l'Ecole Nationale Supérieure 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 | DOI | MR | Zbl

[29] M. Gavalec, Periodicity in Extremal Algebras, Gaudeamus, Hradec Králové, 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 | MR

[31] D. J. Hartfiel, Nonhomogeneous Matrix Products, World Scientific, Singapore, 2002 | MR | Zbl

[32] B. Heidergott, G.-J. Olsder, J. van der Woude, Max-plus at Work, Princeton Univ. Press, Princeton, 2005 | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[36] G. L. Litvinov, V. P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005 | MR

[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/0710.0377 | MR

[38] G. L. Litvinov, S. N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009 | MR | Zbl

[39] Advances in Soviet Mathematics, v. 13, Idempotent analysis, ed. V. P. Maslov, S. N. Samborski{ĭ}, AMS, Providence, 1992 | MR

[40] W. M. McEneaney, Max-plus Models for Nonlinear Control and Estimation, Systems Control: Foundations Applications, Birkh{ä}user, Boston, 2006 | MR

[41] G. Merlet, “Semigroup of matrices acting on the max-plus projective space”, Linear Alg. Appl., 432:8 (2010), 1923–1935 | DOI | MR | Zbl

[42] M. Molnárová, “Generalized matrix period in max-plus algebra”, Linear Alg. Appl., 404 (2005), 345–366 | DOI | MR | Zbl

[43] M. Molnárová, J. Pribiš, “Matrix period in max-algebra”, Discrete Appl. Math., 103 (2000), 167–175 | DOI | MR | Zbl

[44] N. J. Pullman, “A geometric approach to the theory of nonnegative matrices”, Linear Alg. Appl., 4 (1971), 297–312 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[47] E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 1981 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[50] S. Sergeev, H. Schneider, P. Butkovič, “On visualization scaling, subeigenvectors and Kleene stars in max algebra”, Linear Alg. Appl., 431:12 (2009), 2395–2406, arXiv: org/abs/0808.1992 | DOI | MR | Zbl

[51] G. Sierksma, “Limiting polytopes and periodic Markov chains”, Linear and Multilinear Algebra, 46 (1999), 281–298 | DOI | MR | Zbl

[52] B.-S. Tam, H. Schneider, “On the core of a cone-preserving map”, Transactions of the AMS, 343:2 (1994), 479–524 | DOI | MR | Zbl

[53] E. Wagneur, “Moduloïds and pseudomodules. 1. Dimension theory”, Discrete Math., 98 (1991), 57–73 | DOI | MR | Zbl