 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.83
URN: urn:nbn:de:0030-drops-110279
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11027/
 Go to the corresponding LIPIcs Volume Portal

### On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

 pdf-format:

### 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 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.

### 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:1--83:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-117-7},
ISSN =	{1868-8969},
year =	{2019},
volume =	{138},
editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 