Abstract
This paper investigates the "eventual" behavior of linear dynamical systems by analyzing whether the weighted sum of powers of multiple matrices—a problem termed ENNSoM—eventually becomes non-negative. While the problem is shown to be as difficult as long-standing open questions in number theory for general cases, the authors demonstrate that it is effectively decidable for the class of diagonalizable matrices. This is achieved through a novel perturbation-based reduction technique that simplifies complex eigenvalue multiplicities into a manageable framework.
Introduction
In the analysis of linear dynamical systems—ranging from robotics and control theory to chemical reaction modeling—researchers frequently seek to understand long-term or "eventual" properties. A fundamental question in this domain is whether the state of a system, often represented by matrix powers $A^n$, eventually remains within a safe, non-negative region for all sufficiently large $n$.
While the single-matrix case is well-documented, modern systems are increasingly multi-modal (switching between dynamics) or partially observable (modeled as a distribution over several dynamics). This complexity necessitates the study of the Eventually Non-Negative Weighted Sum of Matrix Powers (ENNSoM) problem: given a set of matrices $A_i$ and rational weights $w_i$, does the sum $\sum w_i A_i^n$ eventually stay non-negative? This property is a cornerstone for the safety verification of complex automated systems.
Complexity and Hardness
The transition from a single matrix ($m=1$) to multiple matrices ($m \ge 2$) represents a significant jump in computational complexity. While the single-matrix case is solvable in polynomial time (PTIME), the authors prove that for two or more matrices, the ENNSoM problem becomes coNP-hard.
This hardness is established by linking matrix powers to Linear Recurrence Sequences (LRS). The authors demonstrate that ENNSoM is polynomially inter-reducible with the "Ultimate Positivity" problem for LRS. Furthermore, the problem is shown to be at least as difficult as the "Universal Theory of Reals," placing it among a class of problems that are notoriously resistant to efficient solutions and deeply connected to unresolved questions in Diophantine approximation.
Methodological Framework
The paper employs several sophisticated algebraic and computational techniques to bound the problem:
- LRS Reductions and Interleaving: By constructing specific matrix pairs that encode LRS behavior, the authors establish tight complexity links. They utilize an "interleaving" technique to merge entries of multiple matrices into a single, extended LRS, allowing the application of existing LRS theoretical results to the multi-matrix context.
- Perturbation-based Reduction: The most significant methodological contribution is a reduction procedure for diagonalizable matrices. Many physical systems result in matrices with repeated eigenvalues, which typically complicates analysis. The authors show that problems involving complex eigenvalues and multiplicities can be reduced to a simpler set of problems involving "simple" matrices (those with distinct eigenvalues) by applying carefully chosen rational perturbations.
- Scaling Invariance: The engine behind their reduction theorem is the identification of "positive scaling invariant" properties. These are characteristics of matrix sequences that remain unchanged when the entire sequence is multiplied by a positive constant, allowing for the simplification of the underlying algebraic structures.
Key Results
The research provides the first effective decision procedure for the ENNSoM problem over rational diagonalizable matrices. Key findings include:
- Decidability: The authors provide a concrete algorithm that transforms a complex diagonalizable matrix problem into a set of simpler "real algebraic simple" matrix problems.
- Complexity Bounds: For "simple" matrices (those with distinct eigenvalues), the problem is shown to be in PSPACE. If the rank of the matrices is fixed, the complexity drops to PTIME.
- Diagonalizable vs. Simple: The paper bridges a critical gap in the literature, proving that the "repeated eigenvalue" case is not fundamentally harder to decide than the "simple" case for diagonalizable matrices.
Discussion and Future Directions
Despite the progress made for diagonalizable matrices, the "Holy Grail" of this research remains the general case for non-diagonalizable (defective) matrices involving Jordan blocks. The current perturbation techniques do not easily extend to these structures, as the interaction between Jordan blocks and powers of $n$ introduces additional layers of complexity.
Furthermore, the work remains bounded by the Skolem Problem—the century-old challenge of deciding if an LRS ever hits zero. While this paper successfully solves the eventual version of the problem (will it stay non-negative?), the existence version (will it ever be negative?) remains an open challenge. Future work may also explore extending these results from rational weights to real-algebraic numbers, which would require a more robust computational framework.
Summary updated