Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes (Q837011)

The present paper is concerned with the study of computational complexity for the problems: 1. for a given \(k\), compute periodic power \(A^r\) with \(\gamma= k\pmod\gamma\), \(r\geq T(A)\); 2. for a given \(x\), find the ultimate period of \(\{A^\ell\circledast x\}\). It is proved that both problems can be solved by matrix squaring in \(O(n^3\log n)\) operations.