CSR expansions of matrix powers in max algebra

Abstract

We study the behavior of max-algebraic powers of a reducible nonnegative n by n matrix A. We show that for t>3n^2, the powers A^t can be expanded in max-algebraic powers of the form CS^tR, where C and R are extracted from columns and rows of certain Kleene stars and S is diadonally similar to a Boolean matrix. We study the properties of individual terms and show that all terms, for a given t>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>0} is ultimately linear periodic for each starting vector y, showing that this question can be also answered in O(n^4 log n) time. We give examples illustrating our main results.

25 pages, minor corrections, added 3 illustrations

Cited by in corpus (10)

• Weak CSR expansions and transience bounds in max-plus algebra
• Generalizations of Bounds on the Index of Convergence to Weighted Digraphs
• Tropical linear algebra with the Lukasiewicz T-norm
• Two cores of a nonnegative matrix
• Fiedler-Ptak scaling in max algebra
• On the max-algebraic core of a nonnegative matrix
• On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
• New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
• The ultimate rank of tropical matrices
• Algorithm for the CSR expansion of max-plus matrices using the characteristic polynomial