Polynomial algorithm for linear matrix period in max-plus algebra

Linear periodicity of matrices in max-plus algebra is studied. It is proved that the linear factor matrix and the linear period of a matrix A can be computed in O(n³) time, if A is almost linear periodic. Computation of the coordinate linear period lper(aij^*) for given indices i,j ∈ n is shown to be NP-hard. Further, a polynomial algorithm is described, which decides whether a given matrix is almost linear periodic, if the matrix fulfils a condition of incomparability for trivial strongly connected components. In general, this problem is NP-complete.