2026-07-25T02:44:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19737 2024-03-11T06:37:04Z ddc:004 open_access

Nonnegativity Problems for Matrix Semigroups D'Costa, Julian Ouaknine, Joël Worrell, James Decidability Linear Recurrence Sequences Schanuel’s Conjecture The matrix semigroup membership problem asks, given square matrices M,M₁,…,M_k of the same dimension, whether M lies in the semigroup generated by M₁,…,M_k. It is classical that this problem is undecidable in general, but decidable in case M₁,…,M_k commute. In this paper we consider the problem of whether, given M₁,…,M_k, the semigroup generated by M₁,…,M_k contains a non-negative matrix. We show that in case M₁,…,M_k commute, this problem is decidable subject to Schanuel’s Conjecture. We show also that the problem is undecidable if the commutativity assumption is dropped. A key lemma in our decidability proof is a procedure to determine, given a matrix M, whether the sequence of matrices (Mⁿ)_{n = 0}^∞ is ultimately nonnegative. This answers a problem posed by S. Akshay [S. Akshay et al., 2022]. The latter result is in stark contrast to the notorious fact that it is not known how to determine, for any specific matrix index (i,j), whether the sequence (Mⁿ)_{i,j} is ultimately nonnegative. Indeed the latter is equivalent to the Ultimate Positivity Problem for linear recurrence sequences, a longstanding open problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian D'Costa and Joël Ouaknine and James Worrell 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.27 urn:nbn:de:0030-drops-197371 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode