On primitivity of sets of matrices

A nonnegative matrix A is called primitive if A^k is positive for some integer k > 0. A generalization of this concept to sets of matrices is as follows: A set of matrices M= {A₁,A₂, . . . ,A _m} is primitive if A_i1A_i2 . . .A_ik is positive for some indices i₁, i₂, ..., i_k,. The concept of primitive sets of matrices is of importance in several applications, including the problem of computing the Lyapunov exponents of switching systems. In this paper, we analyze the computational complexity of deciding if a given set of matrices is primitive and we derive bounds on the length of the shortest positive product. We show that while primitivity is algorithmically decidable, unless P = NP it is not possible to decide positivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be exponential in the dimension of the matrices. On the other hand, we give a simple combinatorial proof of the fact that when the matrices have no zero rows nor zero columns, primitivity can be decided in polynomial time. This latter observation is related to the wellknown 1964 conjecture of Černý on synchronizing automata. Finally, we show that for such matrices the length of the shortest positive sequence is at most polynomial in the dimension.