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 gamma 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 r equivalent to k(mod gamma) and r >= T(A), (2) for a given x, find the ultimate period of {A' circle times x}. We show that both problems can be solved by matrix squaring in O(n(3) log n) operations. The main idea is to apply an appropriate diagonal similarity scaling A bar right arrow X-1 AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. (C) 2009 Elsevier Inc. All rights reserved.