On primitivity of sets of matrices

Vincent D. Blondel, Raphael M. Jungers, Alex Olshevsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A nonnegative matrix A is called primitive if Ak is positive for some integer k > 0. A generalization of this concept to sets of matrices is as follows: A set of matrices M= {A1,A2, . . . ,A m} is primitive if Ai1Ai2 . . .Aik is positive for some indices i1, i2, ..., ik,. The concept of primitive sets of matrices is of importance in several applications, including the problem of computing the Lyapunov exponents of switching 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 positivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be exponential in the dimension of the matrices. On the other hand, we give a simple combinatorial proof of the fact that when the matrices have no zero rows nor zero columns, primitivity can be decided in polynomial time. This latter observation is related to the wellknown 1964 conjecture of Černý on synchronizing automata. Finally, we show that for such matrices the length of the shortest positive sequence is at most polynomial in the dimension.

Original languageEnglish (US)
Title of host publication2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1360-1365
Number of pages6
ISBN (Print)9781467357173
DOIs
StatePublished - 2013
Externally publishedYes
Event52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy
Duration: Dec 10 2013Dec 13 2013

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other52nd IEEE Conference on Decision and Control, CDC 2013
Country/TerritoryItaly
CityFlorence
Period12/10/1312/13/13

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint

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

Cite this