  A nonnegative matrix $A$ is called primitive if $A^k$ is positive for some
integer $k>0$. A generalization of this concept to finite sets of matrices is
as follows: a set of matrices $\mathcal M = \{A_1, A_2, \ldots, A_m \}$ is
primitive if $A_{i_1} A_{i_2} \ldots A_{i_k}$ is positive for some indices
$i_1, i_2, ..., i_k$. The concept of primitive sets of matrices comes up in a
number of problems within the study of discrete-time switched 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 primitivity of a matrix set in polynomial time.
Moreover, we show that the length of the shortest positive sequence can be
superpolynomial in the dimension of the matrices. On the other hand, defining
${\mathcal P}$ to be the set of matrices with no zero rows or columns, we give
a simple combinatorial proof of a previously-known characterization of
primitivity for matrices in ${\mathcal P}$ which can be tested in polynomial
time. This latter observation is related to the well-known 1964 conjecture of
Cerny on synchronizing automata; in fact, any bound on the minimal length of a
synchronizing word for synchronizing automata immediately translates into a
bound on the length of the shortest positive product of a primitive set of
matrices in ${\mathcal P}$. In particular, any primitive set of $n \times n$
matrices in ${\mathcal P}$ has a positive product of length $O(n^3)$.
