Deciding whether large powers of a matrix stay nonnegative is efficient
Eventual Nonnegativity of a Matrix Is in P
Logic in Computer Science
Summary
The paper studies the question of whether, after raising a matrix to very large powers, all the numbers inside become nonnegative. The authors show that there is a smart, step-by-step method that can answer this question quickly without checking every power. This contrasts with a related problem about single entries of powers, which remains unsolved. They achieve this by focusing on a special sequence of powers and using algebraic techniques to keep the computations manageable.
What this means in practice
- •For control system engineers: Decide efficiently if repeated application of a system matrix eventually yields nonnegative state variables for system stability analysis.
- •For software verification teams: Verify automatically if iterative linear transformations in software maintain nonnegative outputs after many iterations.
A theory result. No direct application yet.
Authors
Julian D'Costa
Abstract
Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $λ^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(λ)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.