On Eventual Non-negativity and Positivity for the Weighted Sum of Powers of Matrices

S. Akshay, Supratik Chakraborty, Debtanu Pal

TL;DR

This paper explores the "eventual" behavior of linear dynamical systems by investigating whether the weighted sum of powers of multiple matrices—a problem dubbed ENNSoM—eventually becomes non-negative. The authors prove that while this problem is generally as hard as long-standing open questions in number theory, it becomes effectively decidable for the broad and practically significant class of diagonalizable matrices through a novel perturbation-based reduction technique.

What Problem Does This Paper Address?

In the study of linear dynamical systems (like a robot's movement or a chemical reaction's concentration over time), researchers often ask about "long-run" or "eventual" properties. A classic question is: given a matrix $A$, do the entries of $A^n$ eventually become non-negative for all sufficiently large $n$?

While the single-matrix case is well-understood, real-world systems are often more complex. They might be multi-modal (switching between different dynamics) or partially observable (where we only know a probability distribution over several possible dynamics). This leads to the more difficult problem addressed here: the Eventually Non-Negative Weighted Sum of Matrix Powers (ENNSoM).

Given a set of matrices and rational weights, does the sum $\sum w_i A_i^n$ eventually stay non-negative? This is critical for safety verification—ensuring a system eventually enters and stays within a "safe" (non-negative) state.

Methods

The authors employ a mix of computational complexity analysis and algebraic reductions:

  1. LRS Reductions: They establish a tight link between matrix powers and Linear Recurrence Sequences (LRS). They show that the ENNSoM problem is polynomially inter-reducible with the "Ultimate Positivity" problem for LRS.
  2. Hardness Proofs: By constructing specific matrix pairs that encode LRS behavior, they prove that for two or more matrices ($m \ge 2$), the problem is coNP-hard.
  3. Interleaving Technique: To provide upper bounds, they use a technique to "interleave" the entries of matrices into a single, much longer LRS, allowing them to leverage existing results from LRS theory.
  4. Perturbation-based Reduction: Their most significant contribution is a reduction for diagonalizable matrices. They show that a problem involving complex eigenvalues and multiplicities can be reduced to a simpler problem involving "simple" matrices (those with distinct eigenvalues) by applying carefully chosen rational perturbations.

Datasets

As a theoretical paper in computer science and linear algebra, no empirical datasets or training sets were used. The "evaluation" consists of mathematical proofs and the presentation of a formal algorithm (Algorithm 1) for the reduction procedure.

Key Insights and Ideas

  • The "Power of Two": There is a massive jump in complexity between $m=1$ and $m=2$. While the single-matrix case is in PTIME, adding just one more matrix makes the problem coNP-hard and links it to deep, unresolved problems in Diophantine approximation.
  • Diagonalizable vs. Simple: Most existing algorithms for these types of problems only work for "simple" matrices (distinct eigenvalues). However, many physical systems result in diagonalizable matrices with repeated eigenvalues. The authors bridge this gap, showing that the "repeated" case isn't fundamentally harder to decide than the "simple" one.
  • Multi-Matrix as a Tool: Surprisingly, the authors found that reasoning about sums of multiple matrices is actually a useful detour for solving certain problems involving a single matrix.
  • Scaling Invariance: The paper identifies "positive scaling invariant" properties—characteristics of matrix sequences that don't change if you multiply the whole sequence by a positive constant. This insight is the engine behind their main reduction theorem.

Key Results

  • Complexity Bounds: For "simple" matrices, the problem is in PSPACE, and it drops to PTIME if the rank of the matrices is fixed.
  • Decidability: The paper provides the first effective decision procedure for the ENNSoM problem over rational diagonalizable matrices.
  • Hardness: Proved that ENNSoM is at least as hard as the "Universal Theory of Reals," placing it in a category of problems that are notoriously difficult to solve efficiently.
  • Algorithm: They provide a concrete reduction algorithm that transforms a complex diagonalizable matrix problem into a set of simpler "real algebraic simple" matrix problems.

Limitations and Future Work

  • Non-Diagonalizable Matrices: The "Holy Grail" remains the general case for non-diagonalizable matrices (those with Jordan blocks). The authors note that their current perturbation techniques do not easily extend to these "defective" matrices.
  • The Skolem Problem: The work is still bounded by the "Skolem Problem" (deciding if an LRS ever hits zero), which has been open for nearly a century. While they solve the eventual version, the existence version (does it ever happen?) remains out of reach.
  • Real-Algebraic Weights: While the paper focuses on rational weights and entries, the authors suggest that many results could extend to real-algebraic numbers, though this would require a more complex 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 in this setting is as follows: given a set of pairs of rational weights and matrices \(\{(w_1, A_1), \ldots , (w_m, A_m)\}\), does there exist an integer N s.t for all \(n \ge N\), \(\sum _{i=1}^m w_i\cdot A_i^n \ge 0\) (resp. \(> 0\)). We study this problem, its applications and its connections to linear recurrence sequences. Our first result is that for \(m\ge 2\), the problem is as hard as the ultimate positivity of linear recurrences, a long standing open question (known to be \(\mathsf {coNP}\)-hard). Our second result is that for any \(m\ge 1\), the problem reduces to ultimate positivity of linear recurrences. This yields upper bounds for several subclasses of matrices by exploiting known results on linear recurrence sequences. Our third result is a general reduction technique for a large class of problems (including the above) from diagonalizable case to the case where the matrices are simple (have non-repeated eigenvalues). This immediately gives a decision procedure for our problem 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