Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes

In max algebra it is well known that the sequence of max algebraic powers A^k, with A an irreducible square matrix, becomes periodic after a finite transient time T(A), and the ultimate period γ is equal to the cyclicity of the critical graph of A.In this connection, we study computational complexity of the following problems: (1) for a given k, compute a periodic power A^r with and r?T(A), (2) for a given x, find the ultimate period of {A^l⊗x}. We show that both problems can be solved by matrix squaring in O(n³logn) operations. The main idea is to apply an appropriate diagonal similarity scaling A?X^-1AX, called visualization scaling, and to study the role of cyclic classes of the critical graph.