论文标题
最终的非负和阳性矩阵幂的加权总和
On eventual non-negativity and positivity for the weighted sum of powers of matrices
论文作者
论文摘要
线性动力系统的长期行为通常是通过查看构成系统基础的矩阵和复发的最终属性来研究的。在这种情况下，许多问题的核心的一个基本问题是：给定一组理性的权重和矩阵{（W_1，A_1），。 。 。 ，（w_m，a_m）}，我们询问这些矩阵的加权加权总和最终是非负p（分别为n个阳性），即，是否存在大于n的整数n s.t（w_1 a_1 a_1 a_1 a_1 a_1 a_1 a_1 a_1^n + ... + w_m a_m^n）是最大的0（resp。均超过0（resp。均超过0）。当M = W_1 = 1时，受限制的设置导致所谓的最终非阴性（或最终是阳性）矩阵，这些矩阵具有良好的光谱特性，并且在控制理论中得到了很好的研究。从程序验证到部分可观察到的多模式系统，更多的应用程序出现在不同的上下文中。 我们的目标是研究此问题及其与线性复发序列的联系。我们的第一个结果是，对于M至少2个，问题与线性复发的最终阳性一样困难，这是一个长期存在的开放问题（已知是束缚）。我们的第二个结果是降低了另一个方向，表明对于任何M至少1个，该问题降低到线性复发的最终阳性。这显示了通过在线性复发序列上利用已知结果的几个矩阵子类的上限。我们的第三个主要结果是针对与简单的实地矩阵相应问题的合理对角矩阵的大量问题（包括上述问题）的新型还原技术（包括上述问题）。这产生了可对角矩阵的有效决策程序。
The long run behaviour of linear dynamical systems is often studied by looking at eventual properties of matrices and recurrences that underlie the system. A basic problem that lies at the core of many questions in this setting is the following: given a set of pairs of rational weights and matrices {(w_1 , A_1 ), . . . , (w_m , A_m )}, we ask if the weighted sum of powers of these matrices is eventually non-negative P (resp. n positive), i.e., does there exist an integer N s.t for all n greater than N , (w_1 A_1^n + ... + w_m A_m^n) is atmost 0 (resp. greater than 0). The restricted setting when m = w_1 = 1, results in so-called eventually non-negative (or eventually positive) matrices, which enjoy nice spectral properties and have been well-studied in control theory. More applications arise in varied contexts, ranging from program verification to partially observable and multi-modal systems. Our goal is to investigate this problem and its link to linear recurrence sequences. Our first result is that for m at least 2, the problem is as hard as the ultimate positivity of linear recurrences, a long standing open question (known to be coNP-hard). Our second result is a reduction in the other direction showing that for any m at least 1, the problem reduces to ultimate positivity of linear recurrences. This shows precise upper bounds for several subclasses of matrices by exploiting known results on linear recurrence sequences. Our third main result is a novel reduction technique for a large class of problems (including those mentioned above) over rational diagonalizable matrices to the corresponding problem over simple real-algebraic matrices. This yields effective decision procedures for diagonalizable matrices.
