On primitivity of sets of matrices

详细信息    查看全文

• 作者：Vincent D. Blondel^a ; ^{vincent.blondel@uclouvain.be" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Raphaë ; l M. Jungers^a ; ^{raphael.jungers@uclouvain.be" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Alex Olshevsky^b ; ^{aolshev2@illinois.edu" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Nonnegative matrices ; Complexity theory ; State trajectories ; Switched networks ; Control algorithms
• 刊名：Automatica
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：61
• 期：Complete
• 页码：80-88
• 全文大小：559 K

文摘

A nonnegative matrix A$A$ is called primitive if A^k$A^k$ is positive for some integer k>0$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={A₁,A₂,…,A_m}$\mathcal{M}=\{A_1,A_2,\dots ,A_m\}$ is primitive if A_i1A_i2…A_ik$A_{i_1}{A}_{i_2}\dots A_{i_k}$ is positive for some indices i₁,i₂,...,i_k$i_1,i_2,...,i_k$. 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$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$\mathcal{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$\mathcal{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$\mathcal{P}$. In particular, any primitive set of n×n$n\times n$ matrices in P$\mathcal{P}$ has a positive product of length O(n³)$O\left(n^3\right)$.