On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond



Bell, Paul C, Potapov, Igor and Semukhin, Pavel
(2019) On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond. [Internet Publication]

[img] Text
1902.10188v3.pdf - Submitted Version

Download (622kB) | Preview

Abstract

We consider the following variant of the Mortality Problem: given $k\times k$ matrices $A_1, A_2, \dots,A_{t}$, does there exist nonnegative integers $m_1, m_2, \dots,m_t$ such that the product $A_1^{m_1} A_2^{m_2} \cdots A_{t}^{m_{t}}$ is equal to the zero matrix? It is known that this problem is decidable when $t \leq 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 \leq 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 \times 2$ rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

Item Type: Internet Publication
Additional Information: Full version of the MFCS submission
Uncontrolled Keywords: cs.DM, cs.DM, cs.CC, F.2.1
Depositing User: Symplectic Admin
Date Deposited: 30 Sep 2019 14:13
Last Modified: 08 Jun 2022 16:10
Open Access URL: http://drops.dagstuhl.de/opus/volltexte/2019/11027...
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3056455