Linear matrix period in max-plus algebra Original Research Article

Linear periodicity of matrices in max-plus algebra is studied. It is proved that the linear period of a matrix can be computed in O(n3) time if the digraph of the matrix is strongly connected. The general problem of deciding whether a given matrix is almost linear periodic is shown to be NP-complete.