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

Journal article

We consider the following variant of the mortality problem: given k×k matrices A1, A2, . . . , At, do there exist t nonnegative integers m1, m2, . . . , mt such that the product A1m1 A2m2· · · Atmt is equal to the zero matrix? It is known that this problem is decidable when t ≤ 2 for matrices over algebraic numbers but becomes undecidable for sufficiently large t and k, even for integral matrices. In this paper, we prove the first decidability results for t > 2. We show as one of our central results that for t = 3 this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the primary decomposition theorem for matrices. Up to now, this result has not been used to prove decidability results about matrix semigroups. As a corollary we obtain that the above problem is decidable for t = 3 and k ≤ 3 for matrices over algebraic numbers and for t = 3 and k = 4 for matrices over real algebraic numbers. Another consequence is that the set of triples (m1, m2, m3) for which the equation A1m1 A2m2 A3m3 equals the zero matrix is equal to a finite union of direct products of semilinear sets. For t = 4 we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular 2 × 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations.

Authors: Bell, PC; Potapov, I; Semukhin, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 281
• Article number: 104736
• Publication date: 2021-02-18
• Acceptance date: 2021-02-14
• DOI: 10.1016/j.ic.2021.104736
• EISSN: 1090-2651
• ISSN: 0890-5401
• Language: English
• Keywords: Baker's theorem; mortality problem; FFR; Skolem's problem; matrix equations; primary decomposition theorem; linear recurrence sequences