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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11027/
Bell, Paul C. ;
Potapov, Igor ;
Semukhin, Pavel
On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11027},
URN = {urn:nbn:de:0030-drops-110279},
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 |
