Weakly and strongly stable max-plus matrices

A max-plus matrix A is called weakly stable if the orbit of A does not reach an eigenvector of A for any starting vector x unless x is an eigenvector itself. This is in contrast to strongly stable (robust) matrices for which the orbit reaches an eigenvector with any nontrivial starting vector. Maxplus matrices are used to describe multiprocessor interactive systems for which reachability of a steady regime is equivalent to reachability of an eigenvector by a matrix orbit. We prove that an irreducible matrix is weakly stable if and only if its critical graph is a Hamiltonian cycle in the associated graph. We extend this condition to reducible matrices. These criteria can be checked in polynomial time. They complement the known criteria for strong stability which will also be presented.