Orbits and critical components of matrices in max–min algebra

AbstractA speed-up of a known O(n3) algorithm computing the period of a periodic orbit in max–min algebra is presented. If the critical components (or the transitive closure A+) of the transition matrix A are known, the computational complexity of the algorithm is O(n2). This is achieved by using only those coordinates of the orbit that are related to the critical components. On the other hand, no critical component can be omitted. As the critical components are pairwise disjoint, the new formula is helpful also in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. All parts of the paper are connected with the fact that the periodic regime of an orbit is encoded in its critical coordinates. We show that the non-critical coordinates of the state vector after n−1 steps can be ignored, how to generate a known periodic regime by using a small number of coordinates of the state vector and that the difference between the defect of an orbit and the quasidefect of its critical coordinates is small. The final part deals with the situation when the matrix is reduced after the orbit has reached its periodic regime