  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.
