TY - GEN

T1 - On primitivity of sets of matrices

AU - Blondel, Vincent D.

AU - Jungers, Raphael M.

AU - Olshevsky, Alex

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84902332916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902332916&partnerID=8YFLogxK

U2 - 10.1109/CDC.2013.6760072

DO - 10.1109/CDC.2013.6760072

M3 - Conference contribution

AN - SCOPUS:84902332916

SN - 9781467357173

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 1360

EP - 1365

BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 52nd IEEE Conference on Decision and Control, CDC 2013

Y2 - 10 December 2013 through 13 December 2013

ER -