Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

CSR expansions of matrix powers in max algebra


Authors: Sergeĭ Sergeev and Hans Schneider
Journal: Trans. Amer. Math. Soc. 364 (2012), 5969-5994
MSC (2010): Primary 15A80, 15A23, 15A21
DOI: https://doi.org/10.1090/S0002-9947-2012-05605-4
Published electronically: May 30, 2012
MathSciNet review: 2946939
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the behavior of max-algebraic powers of a reducible nonnegative matrix $ A\in \mathbb{R}_+^{n\times n}$. We show that for $ t\geq 3n^2$, the powers $ A^t$ can be expanded in max-algebraic sums of terms of the form $ CS^tR$, where $ C$ and $ R$ are extracted from columns and rows of certain Kleene stars, and $ S$ is diagonally similar to a Boolean matrix. We study the properties of individual terms and show that all terms, for a given $ t\geq 3n^2$, can be found in $ O(n^4\log n)$ operations. We show that the powers have a well-defined ultimate behavior, where certain terms are totally or partially suppressed, thus leading to ultimate $ CS^tR$ terms and the corresponding ultimate expansion. We apply this expansion to the question whether $ \{A^ty,\; t\geq 0\}$ is ultimately linear periodic for each starting vector $ y$, showing that this question can also be answered in $ O(n^4\log n)$ time. We give examples illustrating our main results.


References [Enhancements On Off] (What's this?)

  • 1. F.L. Baccelli, G. Cohen, G.-J. Olsder, and J.-P. Quadrat, Synchronization and linearity: an algebra for discrete event systems, Wiley, 1992. MR 1204266 (94b:93001)
  • 2. Y. Balcer and A.F. Veinott, Computing a graph's period quadratically by node condensation, Discrete Mathematics 4 (1973), 295-303. MR 0327566 (48:5908)
  • 3. R.A. Brualdi and H.J. Ryser, Combinatorial matrix theory, Cambridge Univ. Press, 1991. MR 1130611 (93a:05087)
  • 4. P. Butkovič, Max-algebra: the linear algebra of combinatorics?, Linear Algebra Appl. 367 (2003), 313-335. MR 1976928 (2004d:15006)
  • 5. -, Max-linear systems: theory and algorithms, Springer-Verlag, London, 2010. MR 2681232 (2011e:15049)
  • 6. P. Butkovič, R. A. Cuninghame-Green, and S. Gaubert, Reducible spectral theory with applications to the robustness of matrices in max-algebra, SIAM J. on Matrix Anal. and Appl. 31 (2009), no. 3, 1412-1431. MR 2587784 (2011b:15061)
  • 7. J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena, A constructive fixed-point theorem for min-max functions, Dynamics and Stability of Systems 14 (1999), no. 4, 407-433. MR 1746112 (2000m:47077)
  • 8. R. A. Cuninghame-Green, Minimax algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer, Berlin, 1979. MR 580321 (82a:90043)
  • 9. B. de Schutter, On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra, Linear Algebra Appl. 307 (2000), 103-117. MR 1741919 (2000j:15045)
  • 10. L. Elsner and P. van den Driessche, On the power method in max algebra, Linear Algebra Appl. 302-303 (1999), 17-32. MR 1733521 (2000k:15021)
  • 11. -, Modifying the power method in max algebra, Linear Algebra Appl. 332-334 (2001), 3-13. MR 1839423 (2002c:15037)
  • 12. G.M. Engel and H. Schneider, Cyclic and diagonal products on a matrix, Linear Algebra Appl. 7 (1973), 301-335. MR 0323804 (48:2160)
  • 13. M. Fiedler and V. Pták, Diagonally dominant matrices, Czechoslovak Math. J. 17 (1967), no. 92, 420-433. MR 0215869 (35:6704)
  • 14. G. Frobenius, Über Matrizen aus nicht negativen Elementen, Sitzber. Preuss. Akad. Wiss. (1912), 456-477.
  • 15. M. Gavalec, Linear matrix period in max-plus algebra, Linear Algebra Appl. 307 (2000), 167-182. MR 1741924 (2000m:15020)
  • 16. -, Periodicity in extremal algebra, Gaudeamus, Hradec Králové, 2004.
  • 17. B. Heidergott, G.-J. Olsder, and J. van der Woude, Max-plus at work, Princeton Univ. Press, 2005.
  • 18. K.H. Kim, Boolean matrix theory and applications, Marcel Dekker, New York, 1982. MR 655414 (84a:15001)
  • 19. M. Molnárová, Computational complexity of Nachtigall's representation, Optimization 52 (2003), 93-104. MR 1962942 (2004a:05097)
  • 20. -, Generalized matrix period in max-plus algebra, Linear Algebra Appl. 404 (2005), 345-366. MR 2149669 (2006f:15018)
  • 21. K. Nachtigall, Powers of matrices over an extremal algebra with applications to periodic graphs, Mathematical Methods of Operations Research 46 (1997), 87-102. MR 1464921 (99e:05076)
  • 22. B. Semančíková, Orbits in max-min algebra, Linear Algebra Appl. 414 (2006), 38-63. MR 2209233 (2006j:15057)
  • 23. -, Orbits and critical components of matrices in max-min algebra, Linear Algebra Appl. 426 (2007), 415-447. MR 2350666 (2009a:15063)
  • 24. B. Semančíková, Private communication, 2009.
  • 25. S. Sergeev, Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes, Linear Algebra Appl. 431 (2009), 1325-1339. MR 2547914 (2010k:15056)
  • 26. S. Sergeev, H. Schneider, and P. Butkovič, On visualization scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra Appl., 431 (2009), no. 12, 2395-2406. MR 2563030 (2010j:15028)
  • 27. Š. Schwartz, On a sharp estimation in the theory of binary relations on a finite set, Czechoslovak Math. J. 20 (1970), 703-714. MR 0282862 (44:96)
  • 28. H. Wielandt, Unzerlegbare nicht negative Matrizen, Math. Z. 52 (1950), 642-645. MR 0035265 (11:710g)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 15A80, 15A23, 15A21

Retrieve articles in all journals with MSC (2010): 15A80, 15A23, 15A21


Additional Information

Sergeĭ Sergeev
Affiliation: School of Mathematics, University of Birmingham, Watson Building, Edgbaston B15 2TT, United Kingdom
Email: sergiej@gmail.com

Hans Schneider
Affiliation: Department of Mathematics, University of Wisconsin-Madison, Madison, Wisconsin 53706
Email: hans@math.wisc.edu

DOI: https://doi.org/10.1090/S0002-9947-2012-05605-4
Received by editor(s): December 29, 2009
Received by editor(s) in revised form: March 1, 2011
Published electronically: May 30, 2012
Additional Notes: This work was supported by EPSRC grant RRAH12809 and RFBR grant 08-01-00601.
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society