On eventual non-negativity and positivity for the weighted sum of powers of matrices

S. Akshay, Supratik Chakraborty, Debtanu Pal

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:

  1. 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.
  2. 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.
  3. 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

Abstract

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.
BibTeX
@inproceedings{akshay2022eventual,
  author = {S. Akshay and Supratik Chakraborty and Debtanu Pal},
  title = {{On eventual non-negativity and positivity for the weighted sum of powers of matrices}},
  booktitle = {IJCAR},
  year = {2022},
  url = {https://openreview.net/forum?id=OZ1jEseSfb},
}

Loading related content...

Figure