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
Published electronically: May 30, 2012
MathSciNet review: 2946939
Full-text PDF Free Access

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?)


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

Hans Schneider
Affiliation: Department of Mathematics, University of Wisconsin-Madison, Madison, Wisconsin 53706

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