On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond



Bell, Paul C, Potapov, Igor and Semukhin, Pavel
(2021) On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond. Information and Computation, 281. p. 104736.

[img] Text
BPSInC21.pdf - Author Accepted Manuscript

Download (435kB) | Preview

Abstract

We consider a variant of the mortality problem: given k×k matrices A1,…,At, do there exist nonnegative integers m1,…,mt such that A1m1⋯Atmt equals the zero matrix? This problem is known to be decidable when t≤2 but undecidable for integer matrices with sufficiently large t and k. We prove that for t=3 this problem is Turing-equivalent to Skolem's problem and thus decidable for k≤3 (resp. k=4) over (resp. real) algebraic numbers. Consequently, the set of triples (m1,m2,m3) for which the equation A1m1A2m2A3m3 equals the zero matrix is a finite union of direct products of semilinear sets. For t=4 we show that the solution set can be non-semilinear, and thus there is unlikely to be a connection to Skolem's problem. We prove decidability for upper-triangular 2×2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

Item Type: Article
Uncontrolled Keywords: Linear recurrence sequences, Skolem's problem, Mortality problem, Matrix equations, Primary decomposition theorem, Baker's theorem
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 09 Nov 2021 10:46
Last Modified: 18 Jan 2023 21:25
DOI: 10.1016/j.ic.2021.104736
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3142958