Bell, PC, Potapov, I and Semukhin, P (2021) On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. Information and Computation. ISSN 08905401

Text
BPSInC21.pdf  Accepted Version Available under License Creative Commons Attribution Noncommercial No Derivatives. Download (435kB)  Preview 
Abstract
We consider a variant of the mortality problem: given matrices $A_1, ..., A_t$, do there exist nonnegative integers $m_1, \ldots, m_t$ such that $A_1^{m_1} \cdots A_t^{m_t}$ equals the zero matrix? This problem is known to be decidable when $t \leq 2$ but undecidable for integer matrices with sufficiently large $t$ and $k$. We prove that for t=3 this problem is Turingequivalent to Skolem's problem and thus decidable for k <= 3 (resp. k=4) over (resp. real) algebraic numbers. Consequently, 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 a finite union of direct products of semilinear sets. For t=4 we show that the solution set can be nonsemilinear, and thus there is unlikely to be a connection to Skolem's problem. We prove decidability for uppertriangular 2x2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and Sunit equations.
Item Type:  Article 

Uncontrolled Keywords:  08 Information and Computing Sciences 
Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software 
Divisions:  Computer Science & Mathematics 
Publisher:  Elsevier 
Date Deposited:  01 Jul 2021 08:55 
Last Modified:  18 Feb 2022 00:50 
DOI or Identification number:  10.1016/j.ic.2021.104736 
URI:  https://researchonline.ljmu.ac.uk/id/eprint/15200 
Actions (login required)
View Item 