Сердцевина матрицы в макс-алгебре и в неотрицательной алгебре: Обзор

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

макс-алгебра, теория неорицательных матриц, теория Перрона-Фробениуса, степень матрицы, собственнное подпространство, сердцевина

1. Н. Н. Воробьев, “Экстремальная алгебра матриц”, Докл. АН СССР, 152:1 (1963), 24-27.

2. Н. Н. Воробьев, “Экстремальная алгебра положительных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 3:1 (1967), 39-71.

3. Н. Н. Воробьев, “Экстремальная алгебра неотрицательных матриц”, Elektronische Informationsverarbeitung und Kybernetik, 6:4-5 (1970), 303-312.

4. П. И. Дудников, С. Н. Самборский, “Эндоморфизмы полумодулей над полукольцами с идемпотентной операцией”, Изв. АН СССР. Сер. матем., 55:1 (1991), 93-109.

5. Н. К. Кривулин, Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем, Изд. Санкт-Петербургского Гос. Ун-та, Санкт-Петербург, 2009.

6. Г. Л. Литвинов, В. П. Маслов, А. Н. Соболевский, “Идемпотентная математика и интервальный анализ”, Вычислительные технологии, 6:6 (2001), 47-70.

7. В. П. Маслов, “О новом принципе суперпозиции для задач оптимизации”, УМН, 42:3(255) (1987), 39-48.

8. В. П. Маслов, В. Н. Колокольцов, Идемпотентный анализ и его применение в оптимальном управлении, Физматлит, М., 1994.

9. Г. Б. Шпиз, “Теорема о существовании собственного вектора в идемпотентном анализе”, Матем. заметки, 82:3 (2007), 459-468.

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), 313-335.

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 periodique de systemes de production par la theorie des diodes”, 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 behavior”, Operations Research, 13:1 (1962), 95-100.

26. G. F. Frobenius, “Uber Matrizen aus nicht negativen Elementen”, Sitzungsberichte der Koniglich Preussischen Akademie der Wissenschaften, 23, Sitzungsberichte, Berlin, 1912, 456-477.

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

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 Kralove, 2004.

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

31. D. J. Hartel, Nonhomogeneous Matrix Products, World Scientic, 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, Birkhauser, 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. Molnarova, “Generalized matrix period in max-plus algebra”, Linear Alg. Appl., 404(2005), 345-366.

43. M. Molnarova, J. Pribis, “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 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.

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. Butkovic, “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, “Modulods and pseudomodules. 1. Dimension theory”, Discrete Math., 98 (1991), 57-73.