Abstract
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 wellknown 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 nonsemilinear, 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 uppertriangular 2 x 2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and Sunit equations.
BibTeX  Entry
@InProceedings{bell_et_al:LIPIcs:2019:11027,
author = {Paul C. Bell and Igor Potapov and Pavel Semukhin},
title = {{On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {83:183:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11027},
URN = {urn:nbn:de:0030drops110279},
doi = {10.4230/LIPIcs.MFCS.2019.83},
annote = {Keywords: Linear recurrence sequences, Skolem's problem, mortality problem, matrix equations, primary decomposition theorem, Baker's theorem}
}
Keywords: 

Linear recurrence sequences, Skolem's problem, mortality problem, matrix equations, primary decomposition theorem, Baker's theorem 
Collection: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 
Issue Date: 

2019 
Date of publication: 

20.08.2019 