** Paul Bell** p.c.bell@keele.ac.uk

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

## Bell

## Authors

### Abstract

We consider a variant of the mortality problem: given k × k matrices A1, . . . , At , do there exist nonnegative integers m1, . . . , mt such that Am1 1 · · · Amt t 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 Am1 1 Am2 2 Am3 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 2 × 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations

Acceptance Date | Feb 14, 2021 |
---|---|

Publication Date | Dec 1, 2021 |

Journal | Information and Computation |

Print ISSN | 0890-5401 |

Publisher | Elsevier |

DOI | https://doi.org/10.1016/j.ic.2021.104736 |

Publisher URL | https://www.sciencedirect.com/science/article/pii/S0890540121000511?via%3Dihub |

#### Files

**1902.10188.pdf**
(622 Kb)

PDF

**Publisher Licence URL**

https://creativecommons.org/licenses/by-nc-nd/4.0/

#### You might also like

**Polynomially ambiguous probabilistic automata on restricted languages**
(2022)

Journal Article

**Towards Uniform Online Spherical Tessellations**
(2022)

Journal Article

**On Injectivity of Quantum Finite Automata**
(2021)

Journal Article

**Freeness properties of weighted and probabilistic automata over bounded languages**
(2019)

Journal Article

**Towards Uniform Online Spherical Tessellations**
(2019)

Book Chapter