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]
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: | 19 Jan 2023 00:25 |
DOI: | 10.4230/LIPIcs.MFCS.2019.83 |
Open Access URL: | http://drops.dagstuhl.de/opus/volltexte/2019/11027... |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3056455 |