Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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