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