Primitive sets of nonnegative matrices and synchronizing automata

A set of nonnegative matrices M = {M1, M2, . . . , Mk} is called primitive if there exist indices i1, i2, . . . , im such that Mi1Mi2 . . . Mim is positive (i.e. has all its entries > 0). The length of the shortest such product is called the exponent of M. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains, automata theory etc. Recently, connections between synchronizing automata and primitive sets of matrices were established. In the present paper, we significantly strengthen these links by providing equivalence results, both in terms of combinatorial characterization, and computational aspects. We study the maximal exponent among all primitive sets of n×n matrices, which we denote by exp(n). We prove that limn→∞ log exp(n) n = log 3 3 , and moreover, we establish that this bound leads to a resolution of the Černý problem for carefully synchronizing automata. We also study the set of matrices with no zero rows and columns, denoted by NZ, due to its intriguing connections to the Černý conjecture and the recent generalization of Perron-Frobenius theory for this class. We characterize computational complexity of different problems related to the exponent of NZ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. Namely, we show that the exponent of a set of matrices having total support is bounded by 2n 2 − 5n + 5.