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. 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.
Proceedings of STACS 24, LIPIcs 289, 2024. 16 pages.
PDF
© 2024 Julian D'Costa, Joël Ouaknine, and James Worrell.