2026-08-17T22:50:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11027 2024-03-06T10:47:05Z ddc:004 open_access

On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond Bell, Paul C. Potapov, Igor Semukhin, Pavel Linear recurrence sequences Skolem’s problem mortality problem matrix equations primary decomposition theorem Baker’s theorem We consider the following variant of the Mortality Problem: given k x k matrices A_1, A_2, ...,A_{t}, does there exist nonnegative integers m_1, m_2, ...,m_t such that the product A_1^{m_1} A_2^{m_2} * ... * A_{t}^{m_{t}} is equal to the zero matrix? It is known that this problem is decidable when t <= 2 for matrices over algebraic numbers but becomes undecidable for sufficiently large t and k even for integral matrices. In this paper, we prove the first decidability results for t>2. We show as one of our central results that for t=3 this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for t=3 and k <= 3 for matrices over algebraic numbers and for t=3 and k=4 for matrices over real algebraic numbers. Another consequence is that the set of triples (m_1,m_2,m_3) for which the equation A_1^{m_1} A_2^{m_2} A_3^{m_3} equals the zero matrix is equal to a finite union of direct products of semilinear sets. For t=4 we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular 2 x 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul C. Bell and Igor Potapov and Pavel Semukhin 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.83 urn:nbn:de:0030-drops-110279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.83 eng https://creativecommons.org/licenses/by/3.0/legalcode