Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

Bell, PC, Potapov, I and Semukhin, P (2021) On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. Information and Computation. ISSN 0890-5401

[img] Text
BPSInC21.pdf - Accepted Version
Restricted to Repository staff only until 18 February 2022.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (435kB)

Abstract

We consider a variant of the mortality problem: given matrices $A_1, ..., A_t$, do there exist nonnegative integers $m_1, \ldots, m_t$ such that $A_1^{m_1} \cdots A_t^{m_t}$ equals the zero matrix? This problem is known to be decidable when $t \leq 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 $(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 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 2x2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

Item Type: Article
Uncontrolled Keywords: 08 Information and Computing Sciences
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Divisions: Computer Science & Mathematics
Publisher: Elsevier
Date Deposited: 01 Jul 2021 08:55
Last Modified: 01 Jul 2021 09:00
DOI or Identification number: 10.1016/j.ic.2021.104736
URI: https://researchonline.ljmu.ac.uk/id/eprint/15200

Actions (login required)

View Item View Item