CSR expansions of matrix powers in max algebra

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.