On primitivity of sets of matrices

Vincent D. Blondel, Raphaël M. Jungers, Alex Olshevsky

Research output: Contribution to journalArticlepeer-review


A nonnegative matrix A is called primitive if Ak is positive for some integer k>0. A generalization by Protasov and Voynov (2012) of this concept to finite sets of matrices is as follows: a set of matrices M={A1,A2,...,Am} is primitive if Ai1Ai2...Aik is positive for some indices i1,i2,.,ik. 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 P 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 P 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 P. In particular, any primitive set of n×n matrices in P has a positive product of length O(n3).

Original languageEnglish (US)
Pages (from-to)80-88
Number of pages9
StatePublished - Nov 2015


  • Complexity theory
  • Control algorithms
  • Nonnegative matrices
  • State trajectories
  • Switched networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'On primitivity of sets of matrices'. Together they form a unique fingerprint.

Cite this