Nonnegativity problems for matrix semigroups

Conference item

The matrix semigroup membership problem asks, given square matrices M, M1, ..., Mk of the same dimension, whether M lies in the semigroup generated by M1, ..., Mk. It is classical that this problem is undecidable in general, but decidable in case M1, ..., Mk commute. In this paper we consider the problem of whether, given M1, ..., Mk, the semigroup generated by M1, ..., Mk contains a non-negative matrix. We show that in case M1, ..., Mk 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 (Mn)∞n=0 is ultimately nonnegative. This answers a problem posed by S. Akshay [1]. 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 (Mn)i,j is ultimately nonnegative. Indeed the latter is equivalent to the Ultimate Positivity Problem for linear recurrence sequences, a longstanding open problem.

Authors: D'Costa, J; Ouaknine, J; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl – Leibniz Center for Informatics
• Host title: 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
• Article number: 27
• Series: Leibniz International Proceedings in Informatics
• Series number: 289
• Publication date: 2024-03-11
• Event title: 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
• Event location: Clermont-Ferrand, France
• Event website: https://stacs2024.limos.fr/
• Event start date: 2024-03-12
• Event end date: 2024-03-14
• DOI: 10.4230/LIPIcs.STACS.2024.27
• ISSN: 1868-8969
• ISBN: 9783959773119
• Language: English
• Keywords: decidability; Schanuel’s conjecture; linear recurrence sequences