Primitive sets of nonnegative matrices and synchronizing automata

A set of nonnegative matrices M={M_1, M_2, …, M_k} is called PRIMITIVE if there exist indices i_1, i_2, …, i_m such that the product M_{i_1} M_{i_2} … M_{i_m} 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 etc. In my talk I will speak about the recently discovered connections between synchronizing automata and primitive sets of matrices. An automaton is called SYNCHRONIZING if there exist a word w and a state f such that the action of w brings all states to f. On one hand, the properties of synchronizing automata are relatively well studied due to their applications to industrial automation, coding theory, group theory, etc. On the other hand, there is still a persisting interest of the research community to the topic due to one of the most famous open problems in automata theory. Namely, the CERNY CONJECTURE states that the length of the shortest synchronizing word of an n-state automaton is at most (n-1)^2. In my talk I will explain how the aforementioned connections lead to a relatively large number of results about primitive sets of matrices. Namely, we will see that the maximal exponent among all primitive sets of n by n matrices is roughly equal to 3^(n/3). Furthermore, the problem of deciding whether a given set of matrices is primitive is PSPACE-complete. In my talk the set of matrices with no zero rows and columns, denoted by NZ, will receive a special attention due to its intriguing connections to the Cerny conjecture and the recent generalization of Perron-Frobenius theory for this class. I will characterize the 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 will see that the exponent of a set of matrices having total support is bounded by 2n^2 -5n +5. These results are not published. The preprint is available on http: //arxiv. org/abs/1602. 07556.

Authors

• Balázs Gerencsér
• Vladimir V. Gusev
• Raphaël M. Jungers ICTEAM Institute, UCLouvain, Louvain-la-Neuve, Belgium

Keywords

No keywords are indexed for this paper.