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

AbstractIn max algebra it is well known that the sequence of max algebraic powers Ak, 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 Ar with r≡k(modγ) and r⩾T(A), (2) for a given x, find the ultimate period of {Al⊗x}. We show that both problems can be solved by matrix squaring in O(n3logn) 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