Files

13060729.pdf
  • Open Access
  • Adobe PDF
  • 266.16 KB
Download

Details

Authors
Abstract
A nonnegative matrix is called primitive if is positive for some integer . A generalization by Protasov and Voynov (2012) of this concept to finite sets of matrices is as follows: a set of matrices is primitive if is positive for some indices . 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 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 to be the set of matrices with no zero rows or columns, we give a combinatorial proof of the Protasov–Voynov characterization (2012) of primitivity for matrices in which can be tested in polynomial time. This latter observation is related to the well-known 1964 conjecture of Černý 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 . In particular, any primitive set of matrices in has a positive product of length .
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Blondel, V., Jungers, R., & olshevsky, A. (2015). On primitivity of sets of matrices. Automatica, 61, 80-88. https://doi.org/10.1016/j.automatica.2015.07.026 (Original work published 2015)