## CSR expansions of matrix powers in max algebra

HTML articles powered by AMS MathViewer

- by Sergeĭ Sergeev and Hans Schneider PDF
- Trans. Amer. Math. Soc.
**364**(2012), 5969-5994 Request permission

## 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

- François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat,
*Synchronization and linearity*, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR**1204266** - Yves Balcer and Arthur F. Veinott Jr.,
*Computing a graph’s period quadratically by node condensation*, Discrete Math.**4**(1973), 295–303. MR**327566**, DOI 10.1016/0012-365X(73)90166-0 - Richard A. Brualdi and Herbert J. Ryser,
*Combinatorial matrix theory*, Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, Cambridge, 1991. MR**1130611**, DOI 10.1017/CBO9781107325708 - Peter Butkovič,
*Max-algebra: the linear algebra of combinatorics?*, Linear Algebra Appl.**367**(2003), 313–335. MR**1976928**, DOI 10.1016/S0024-3795(02)00655-9 - Peter Butkovič,
*Max-linear systems: theory and algorithms*, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2010. MR**2681232**, DOI 10.1007/978-1-84996-299-5 - P. Butkovič, R. A. Cuninghame-Green, and S. Gaubert,
*Reducible spectral theory with applications to the robustness of matrices in max-algebra*, SIAM J. Matrix Anal. Appl.**31**(2009), no. 3, 1412–1431. MR**2587784**, DOI 10.1137/080731232 - Jean Cochet-Terrasson, Stéphane Gaubert, and Jeremy Gunawardena,
*A constructive fixed point theorem for min-max functions*, Dynam. Stability Systems**14**(1999), no. 4, 407–433. MR**1746112**, DOI 10.1080/026811199281967 - Raymond Cuninghame-Green,
*Minimax algebra*, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin-New York, 1979. MR**580321**, DOI 10.1007/978-3-642-48708-8 - Bart 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), no. 1-3, 103–117. MR**1741919**, DOI 10.1016/S0024-3795(00)00013-6 - Ludwig Elsner and P. van den Driessche,
*On the power method in max algebra*, Linear Algebra Appl.**302/303**(1999), 17–32. Special issue dedicated to Hans Schneider (Madison, WI, 1998). MR**1733521**, DOI 10.1016/S0024-3795(98)10171-4 - Ludwig Elsner and P. van den Driessche,
*Modifying the power method in max algebra*, Proceedings of the Eighth Conference of the International Linear Algebra Society (Barcelona, 1999), 2001, pp. 3–13. MR**1839423**, DOI 10.1016/S0024-3795(00)00062-8 - Gernot M. Engel and Hans Schneider,
*Cyclic and diagonal products on a matrix*, Linear Algebra Appl.**7**(1973), 301–335. MR**323804**, DOI 10.1016/s0024-3795(73)80003-5 - Miroslav Fiedler and Vlastimil Pták,
*Diagonally dominant matrices*, Czechoslovak Math. J.**92**(1967), 420–433 (English, with Russian summary). MR**215869**, DOI 10.21136/CMJ.1967.100787 - G. Frobenius,
*Über Matrizen aus nicht negativen Elementen*, Sitzber. Preuss. Akad. Wiss. (1912), 456–477. - Martin Gavalec,
*Linear matrix period in max-plus algebra*, Linear Algebra Appl.**307**(2000), no. 1-3, 167–182. MR**1741924**, DOI 10.1016/S0024-3795(00)00020-3 - —,
*Periodicity in extremal algebra*, Gaudeamus, Hradec Králové, 2004. - B. Heidergott, G.-J. Olsder, and J. van der Woude,
*Max-plus at work*, Princeton Univ. Press, 2005. - Ki Hang Kim,
*Boolean matrix theory and applications*, Monographs and Textbooks in Pure and Applied Mathematics, vol. 70, Marcel Dekker, Inc., New York, 1982. With a foreword by Gian-Carlo Rota. MR**655414** - Monika Molnárová,
*Computational complexity of Nachtigall’s representation*, Optimization**52**(2003), no. 1, 93–104. MR**1962942**, DOI 10.1080/0233193031000090727 - Monika Molnárová,
*Generalized matrix period in max-plus algebra*, Linear Algebra Appl.**404**(2005), 345–366. MR**2149669**, DOI 10.1016/j.laa.2005.02.033 - Karl Nachtigall,
*Powers of matrices over an extremal algebra with applications to periodic graphs*, Math. Methods Oper. Res.**46**(1997), no. 1, 87–102. MR**1464921**, DOI 10.1007/BF01199464 - Blanka Semančíková,
*Orbits in max-min algebra*, Linear Algebra Appl.**414**(2006), no. 1, 38–63. MR**2209233**, DOI 10.1016/j.laa.2005.09.009 - Blanka Semančíková,
*Orbits and critical components of matrices in max-min algebra*, Linear Algebra Appl.**426**(2007), no. 2-3, 415–447. MR**2350666**, DOI 10.1016/j.laa.2007.05.017 - B. Semančíková,
*Private communication*, 2009. - Sergeĭ Sergeev,
*Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes*, Linear Algebra Appl.**431**(2009), no. 8, 1325–1339. MR**2547914**, DOI 10.1016/j.laa.2009.04.027 - Sergeĭ Sergeev, Hans Schneider, and Peter Butkovič,
*On visualization scaling, subeigenvectors and Kleene stars in max algebra*, Linear Algebra Appl.**431**(2009), no. 12, 2395–2406. MR**2563030**, DOI 10.1016/j.laa.2009.03.040 - Štefan Schwarz,
*On a sharp estimation in the theory of binary relations on a finite set*, Czechoslovak Math. J.**20(95)**(1970), 703–714. MR**282862**, DOI 10.21136/CMJ.1970.100992 - Helmut Wielandt,
*Unzerlegbare, nicht negative Matrizen*, Math. Z.**52**(1950), 642–648 (German). MR**35265**, DOI 10.1007/BF02230720

## 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
- 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.
- © Copyright 2012 American Mathematical Society
- 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
- MathSciNet review: 2946939