mathematicsВестник российских университетов. МатематикаRussian Universities Reports. Mathematics2686-96672782-3342Тамбовский государственный университет имени Г.Р. Державина10.20310/2686-9667-2019-24-127-252-271mathematics-255Research ArticleСТАТЬИARTICLESСердцевина матрицы в макс-алгебре и в неотрицательной алгебре: ОбзорCore of a matrix in max algebra and in nonnegative algebra: A surveyБутковичПетерButkovicPeterP.Butkovic@bham.ac.ukШнайдерГансSchneiderHanshans@math.wisc.eduСергеевСергейSergeevSergeisergeevs@maths.bham.ac.ukУниверситет Бирмингема, Школа МатематикиРоссияUniversity of Birmingham, School of MathematicsRussian FederationУниверситет Мадисона, штат ВисконсинРоссияUniversity of Wisconsin-MadisonRussian Federation20192310201924127252271Copyright © Буткович П., Шнайдер Г., Сергеев С., 20192019Буткович П., Шнайдер Г., Сергеев С.Butkovic P., Schneider H., Sergeev S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://mathematics.elpub.ru/jour/article/view/255

Эта статья предлагает краткое введение в теорию Перрона-Фробениуса в макс-алгебре и в неотрицательной линейной алгебре, а также обсуждение результатов, касающихся сердцевин неотрицательных матриц, понимаемых в двух смыслах. Обычная сердцевина неотрицательной матрицы определяется как ∩ k ≥1 span+ (A k ) , то есть как пересечение подпространств, натянутых на неотрицательные столбцы степеней этой матрицы. Этот объект важен для обычной теории Перрона-Фробениуса. Он имеет приложения в эргодической теории. Мы прослеживаем прямую макс-алгебраическую аналогию и проявляем совпадения и различия обеих теорий.

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 algebranonnegative matrix theoryPerron-Frobenius theorymatrix powereigenspacecoreReferencesН. Н. Воробьев, “Экстремальная алгебра матриц”, Докл. АН СССР, 152:1 (1963), 24-27.Н. Н. Воробьев, “Экстремальная алгебра матриц”, Докл. АН СССР, 152:1 (1963), 24-27.Н. Н. Воробьев, “Экстремальная алгебра положительных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 3:1 (1967), 39-71.Н. Н. Воробьев, “Экстремальная алгебра положительных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 3:1 (1967), 39-71.Н. Н. Воробьев, “Экстремальная алгебра неотрицательных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 6:4-5 (1970), 303-312.Н. Н. Воробьев, “Экстремальная алгебра неотрицательных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 6:4-5 (1970), 303-312.П. И. Дудников, С. Н. Самборский, “Эндоморфизмы полумодулей над полукольцами с идемпотентной операцией”, Изв. АН СССР. Сер. матем., 55:1 (1991), 93-109.П. И. Дудников, С. Н. Самборский, “Эндоморфизмы полумодулей над полукольцами с идемпотентной операцией”, Изв. АН СССР. Сер. матем., 55:1 (1991), 93-109.Н. К. Кривулин, Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем, Изд. Санкт-Петербургского Гос. Ун-та, Санкт-Петербург, 2009.Н. К. Кривулин, Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем, Изд. Санкт-Петербургского Гос. Ун-та, Санкт-Петербург, 2009.Г. Л. Литвинов, В. П. Маслов, А. Н. Соболевский, “Идемпотентная математика и интервальный анализ”, Вычислительные технологии, 6:6 (2001), 47-70.Г. Л. Литвинов, В. П. Маслов, А. Н. Соболевский, “Идемпотентная математика и интервальный анализ”, Вычислительные технологии, 6:6 (2001), 47-70.В. П. Маслов, “О новом принципе суперпозиции для задач оптимизации”, УМН, 42:3(255) (1987), 39-48.В. П. Маслов, “О новом принципе суперпозиции для задач оптимизации”, УМН, 42:3(255) (1987), 39-48.В. П. Маслов, В. Н. Колокольцов, Идемпотентный анализ и его применение в оптимальном управлении, Физматлит, М., 1994.В. П. Маслов, В. Н. Колокольцов, Идемпотентный анализ и его применение в оптимальном управлении, Физматлит, М., 1994.Г. Б. Шпиз, “Теорема о существовании собственного вектора в идемпотентном анализе”, Матем. заметки, 82:3 (2007), 459-468.Г. Б. Шпиз, “Теорема о существовании собственного вектора в идемпотентном анализе”, Матем. заметки, 82:3 (2007), 459-468.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.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.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).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).A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Society for Industrial and Applied Mathematics, Philadelphia, 1994.A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Society for Industrial and Applied Mathematics, Philadelphia, 1994.S. Bezuglyi, J. Kwiatkowski, K. Medynets, B. Solomyak, “Invariant measures on stationary Bratteli diagrams”, Ergodic Theory Dynam. Systems, 30:4 (2010), 973-1007.S. Bezuglyi, J. Kwiatkowski, K. Medynets, B. Solomyak, “Invariant measures on stationary Bratteli diagrams”, Ergodic Theory Dynam. Systems, 30:4 (2010), 973-1007.R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge, 1991.R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, Cambridge, 1991.P. Butkovic, “Max-algebra: the linear algebra of combinatorics?”, Linear Alg. Appl., 367 (2003), 313-335.P. Butkovic, “Max-algebra: the linear algebra of combinatorics?”, Linear Alg. Appl., 367 (2003), 313-335.P. Butkovic, Max-linear Systems: Theory and Algorithms, Springer, London, 2010.P. Butkovic, Max-linear Systems: Theory and Algorithms, Springer, London, 2010.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.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.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.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.P. Butkovic, H. Schneider, S. Sergeev, “Two cores of a nonnegative matrix, submitted”, 2012, arXiv: org/abs/math.RA/1208.1939.P. Butkovic, H. Schneider, S. Sergeev, “Two cores of a nonnegative matrix, submitted”, 2012, arXiv: org/abs/math.RA/1208.1939.P. Butkovic, H. Schneider, S. Sergeev, “On the max-algebraic core of a nonnegative matrix”, 2013, arXiv: org/abs/1305.7339.P. Butkovic, H. Schneider, S. Sergeev, “On the max-algebraic core of a nonnegative matrix”, 2013, arXiv: org/abs/1305.7339.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.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.M.-H. Chi, “The long-run behaviour of Markov chains”, Linear Alg. Appl., 244 (1996), 111-121.M.-H. Chi, “The long-run behaviour of Markov chains”, Linear Alg. Appl., 244 (1996), 111-121.G. Cohen, D. Dubois, J. P. Quadrat, M. Viot, “Analyse du comportement periodique de systemes de production par la theorie des diodes”, Rapport de Recherche, 1983, №191.G. Cohen, D. Dubois, J. P. Quadrat, M. Viot, “Analyse du comportement periodique de systemes de production par la theorie des diodes”, Rapport de Recherche, 1983, №191.R. A. Cuninghame-Green, “Minimax Algebra”, Lecture Notes in Economics and Mathematical Systems. V. 166, Springer, Berlin, 1979.R. A. Cuninghame-Green, “Minimax Algebra”, Lecture Notes in Economics and Mathematical Systems. V. 166, Springer, Berlin, 1979.R. A. Cuninghame-Green, “Describing industrial processes with interference and approximating their steady-state behavior”, Operations Research, 13:1 (1962), 95-100.R. A. Cuninghame-Green, “Describing industrial processes with interference and approximating their steady-state behavior”, Operations Research, 13:1 (1962), 95-100.G. F. Frobenius, “Uber Matrizen aus nicht negativen Elementen”, Sitzungsberichte der Koniglich Preussischen Akademie der Wissenschaften, 23, Sitzungsberichte, Berlin, 1912, 456-477.G. F. Frobenius, “Uber Matrizen aus nicht negativen Elementen”, Sitzungsberichte der Koniglich Preussischen Akademie der Wissenschaften, 23, Sitzungsberichte, Berlin, 1912, 456-477.S. Gaubert, Theorie des systemes lineaires dans les diodes, PhD thesis, These de l'Ecole Nationale Superieure des Mines de Paris, Juillet, 1992, 304 pp.S. Gaubert, Theorie des systemes lineaires dans les diodes, PhD thesis, These de l'Ecole Nationale Superieure des Mines de Paris, Juillet, 1992, 304 pp.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.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.M. Gavalec, Periodicity in Extremal Algebras, Gaudeamus, Hradec Kralove, 2004.M. Gavalec, Periodicity in Extremal Algebras, Gaudeamus, Hradec Kralove, 2004.M. Gondran, M. Minoux, “Valeurs propres et vecteurs propres dans les diodes”, EDF Bulletin de la Direction des Etudes et Recherches. Serie C. Mathematiques Informatique, 2 (1977), 25-41.M. Gondran, M. Minoux, “Valeurs propres et vecteurs propres dans les diodes”, EDF Bulletin de la Direction des Etudes et Recherches. Serie C. Mathematiques Informatique, 2 (1977), 25-41.D. J. Hartel, Nonhomogeneous Matrix Products, World Scientic, Singapore, 2002.D. J. Hartel, Nonhomogeneous Matrix Products, World Scientic, Singapore, 2002.B. Heidergott, G.-J. Olsder, J. van der Woude, Max-plus at Work, Princeton Univ. Press, Princeton, 2005.B. Heidergott, G.-J. Olsder, J. van der Woude, Max-plus at Work, Princeton Univ. Press, Princeton, 2005.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.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.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.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.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.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.G. L. Litvinov, V.P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005.G. L. Litvinov, V.P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005.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.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.G. L. Litvinov, S. N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009.G. L. Litvinov, S. N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009.Advances in Soviet Mathematics. V. 13: Idempotent analysis, ed. V.P. Maslov, S. N. Samborski, AMS, Providence, 1992.Advances in Soviet Mathematics. V. 13: Idempotent analysis, ed. V.P. Maslov, S. N. Samborski, AMS, Providence, 1992.W. M. McEneaney, Max-plus Models for Nonlinear Control and Estimation, Systems & Control:Foundations & Applications, Birkhauser, Boston, 2006.W. M. McEneaney, Max-plus Models for Nonlinear Control and Estimation, Systems & Control:Foundations & Applications, Birkhauser, Boston, 2006.G. Merlet, “Semigroup of matrices acting on the max-plus projective space”, Linear Alg. Appl., 432:8 (2010), 1923-1935.G. Merlet, “Semigroup of matrices acting on the max-plus projective space”, Linear Alg. Appl., 432:8 (2010), 1923-1935.M. Molnarova, “Generalized matrix period in max-plus algebra”, Linear Alg. Appl., 404(2005), 345-366.M. Molnarova, “Generalized matrix period in max-plus algebra”, Linear Alg. Appl., 404(2005), 345-366.M. Molnarova, J. Pribis, “Matrix period in max-algebra”, Discrete Appl. Math., 103 (2000), 167-175.M. Molnarova, J. Pribis, “Matrix period in max-algebra”, Discrete Appl. Math., 103 (2000), 167-175.N. J. Pullman, “A geometric approach to the theory of nonnegative matrices”, Linear Alg. Appl., 4 (1971), 297-312.N. J. Pullman, “A geometric approach to the theory of nonnegative matrices”, Linear Alg. Appl., 4 (1971), 297-312.H. Schneider, “The inuence 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.H. Schneider, “The inuence 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.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.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.E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 1981.E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, Springer, New York, 1981.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.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.S. Sergeev, H. Schneider, “CSR expansions of matrix powers in max algebra”, Transactions of AMS, 364 (2012), 5969-5994, arXiv: org/abs/0912.2534.S. Sergeev, H. Schneider, “CSR expansions of matrix powers in max algebra”, Transactions of AMS, 364 (2012), 5969-5994, arXiv: org/abs/0912.2534.S. Sergeev, H. Schneider, P. Butkovic, “On visualization scaling, subeigenvectors and Kleene stars in max algebra”, Linear Alg. Appl., 431:12 (2009), 2395-2406, arXiv: org/abs/0808.1992.S. Sergeev, H. Schneider, P. Butkovic, “On visualization scaling, subeigenvectors and Kleene stars in max algebra”, Linear Alg. Appl., 431:12 (2009), 2395-2406, arXiv: org/abs/0808.1992.G. Sierksma, “Limiting polytopes and periodic Markov chains”, Linear and Multilinear Algebra, 46 (1999), 281-298.G. Sierksma, “Limiting polytopes and periodic Markov chains”, Linear and Multilinear Algebra, 46 (1999), 281-298.B.-S. Tam, H. Schneider, “On the core of a cone-preserving map”, Transactions of the AMS, 343:2 (1994), 479-524.B.-S. Tam, H. Schneider, “On the core of a cone-preserving map”, Transactions of the AMS, 343:2 (1994), 479-524.E.Wagneur, “Modulods and pseudomodules. 1. Dimension theory”, Discrete Math., 98 (1991), 57-73.E.Wagneur, “Modulods and pseudomodules. 1. Dimension theory”, Discrete Math., 98 (1991), 57-73.

The authors declare that there are no conflicts of interest present.