Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0002-9947-2012-05605-4
PII: S 0002-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