Recognizing Weakly Stable Matrices
Recognizing Weakly Stable Matrices
复制标题
DOI：
10.1137/110837942
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
P. Butkovic;H. Schneider;Sergeĭ Sergeev
中科院分区：
文献类型：
--
作者：
P. Butkovic;H. Schneider;Sergeĭ Sergeev
如果序列（轨道）$x,A\otimes x,A^{2}\otimes x,\ldots$对于任何$x$都没有达到$A$的特征向量，除非$x$是特征向量，则最大加矩阵$A$被称为弱稳定。这与先前研究的强稳定（鲁棒）矩阵形成对比，其中轨道达到具有任何非平凡起始向量的特征向量。最大加矩阵用于描述多处理器交互系统，其中稳定状态的可达性相当于矩阵轨道的特征向量的可达性。我们证明，当且仅当其临界图是关联图中的哈密顿循环时，不可约矩阵是弱稳定的。我们将此条件扩展到可约矩阵。这些标准可以在多项式时间内检查。
A max-plus matrix $A$ is called weakly stable if the sequence (orbit) $x,A\otimes x,A^{2}\otimes x,\ldots$ does not reach an eigenvector of $A$ for any $x$ unless $x$ is an eigenvector. This is in contrast to previously studied strongly stable (robust) matrices for which the orbit reaches an eigenvector with any nontrivial starting vector. Max-plus matrices are used to describe multiprocessor interactive systems for which reachability of a steady regime is equivalent to reachability of an eigenvector by a matrix orbit. We prove that an irreducible matrix is weakly stable if and only if its critical graph is a Hamiltonian cycle in the associated graph. We extend this condition to reducible matrices. These criteria can be checked in polynomial time.