Polynomial algorithm for linear matrix period in max-plus algebra (Q5949928)

The author proves that if the matrix \(A\) is almost linear periodic, the linear factor matrix and the linear period of \(A\) can be computed in \(O(n^3)\) time. On the other hand, it is shown that the computation of the coordinate linear period \(I\text{ per}(a^*_{ij})\) for given indices, \(i,j\in n\) is an NP-hard problem. Further, a polynomial algorithm is described, which decides whether a given matrix \(A\) is almost linear periodic, if \(A\) fulfills the condition of incomparable trivial strongly connected components. The results of this paper may be useful in computing the linear period of periodic graphs, or in investigating the periodic behaviour and stability of discrete event system.