Cyclic classes and attraction cones in max algebra

الأصل · EN

In max algebra it is well-known that the sequence Aᵏ, with A an irreducible square matrix, becomes periodic at sufficiently large k. This raises a number of questions on the periodic regime of Aᵏ and Aᵏ x, for a given vector x. Also, this leads to the concept of attraction cones in max algebra, by which we mean sets of vectors whose ultimate orbit period does not exceed a given number. This paper shows that some of these questions can be solved by matrix squaring (A,A²,A⁴,...), analogously to recent findings concerning the orbit period in max-min algebra. Hence the computational complexity of such problems is of the order O(n³ log n). The main idea is to apply an appropriate diagonal similarity scaling A -> X⁻¹AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. For powers of a visualized matrix in the periodic regime, we observe remarkable symmetry described by circulants and their rectangular generalizations. We exploit this symmetry to derive a concise system of equations for attraction cpne, and we present an algorithm which computes the coefficients of the system.