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

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 |