Orbits and critical components of matrices in max-min algebra (Q996299)

The paper deals with a speed-up of a known \(O(n^3)\) algorithm computing the period of a periodic orbit in max-min algebra. An orbit in the max-min algebra is a sequence of the state vectors \(x(r)\), \(r\in \mathbb{N}\) of a max-min system \(x(r+1)=A\otimes x(r)\), where the matrix multiplication is defined with respect to the operations \(\oplus=\max\) and \(\otimes=\min\). In 2006, the author gave an \(O(n^3)\) algorithm computing the period of a periodic orbit [ibid. 414, No.~1, 38--63 (2006; Zbl 1125.15020)]. In this paper, the computational complexity of this algorithm is decreased by using only those coordinate-orbits, which correspond to the minimal non-trivial threshold components, called the critical components, of the transition matrix. All parts of the new algorithm except the computing of the critical components have complexity \(O(n^2)\). The formula for the orbit period presented in this paper is optimal in the following sense: the number of coordinate-orbits in the formula cannot be reduced. The formula is also helpful in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. Furthermore, the paper shows 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.