← All papers
First page of Eventual Nonnegativity of a Matrix Is in P

Eventual Nonnegativity of a Matrix Is in P

Julian D'Costa

cs.LO Sep 20, 2026 · v2
The structural criterion for eventual nonnegativity and key algebraic inequalities behind the complexity analysis are formalised sorry-free in Lean 4 with Mathlib.
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.

Given a rational matrix A, decide whether every sufficiently large power A^n is entrywise nonnegative. The previous decision procedure split powers into residue classes modulo a torsion exponent D that can be exponential in the input size.

Nonnegative exponents are closed under addition, so a single coprime progression A^{Dk+1} suffices to decide the problem. Eigenvalues are grouped into torsion classes by common Dth power. Grouped coefficients are computed in individual root fields Q(λ), and Galois equivariance bounds their degree and height, which enables certified zero and sign tests. The structural criterion and key inequalities are machine-checked in Lean 4; the end-to-end complexity bound is not, because Mathlib lacks infrastructure for algorithmic complexity.

Eventual nonnegativity of rational matrices is decidable in deterministic polynomial time. Variants of the algorithm decide eventual positivity and whether any nonnegative power exists. A sorry-free Lean formalisation of the criterion is publicly available.