On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
We consider the following variant of the Mortality Problem: given k × k matrices A1, A2, . . ., At, does there exist nonnegative integers m1, m2, . . ., mt such that the product Am11 Am22 · · · Amtt is equal to the zero matrix? It is known that this problem is decidable when t ≤ 2 for matrices over...
| Main Authors: | , , |
|---|---|
| 格式: | Conference item |
| 出版: |
Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
2019
|
| _version_ | 1826299912840544256 |
|---|---|
| author | Bell, P Potapov, I Semukhin, P |
| author_facet | Bell, P Potapov, I Semukhin, P |
| author_sort | Bell, P |
| collection | OXFORD |
| description | We consider the following variant of the Mortality Problem: given k × k matrices A1, A2, . . ., At, does there exist nonnegative integers m1, m2, . . ., mt such that the product Am11 Am22 · · · Amtt 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 that was not used to show decidability results in matrix semigroups before. 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 Am11 Am22 Am33 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. |
| first_indexed | 2024-03-07T05:09:09Z |
| format | Conference item |
| id | oxford-uuid:daf7f5c6-cf81-4b64-8c38-876bfa472db8 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:09:09Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum fur Informatik |
| record_format | dspace |
| spelling | oxford-uuid:daf7f5c6-cf81-4b64-8c38-876bfa472db82022-03-27T09:07:00ZOn the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyondConference itemhttp://purl.org/coar/resource_type/c_5794uuid:daf7f5c6-cf81-4b64-8c38-876bfa472db8Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum fur Informatik2019Bell, PPotapov, ISemukhin, PWe consider the following variant of the Mortality Problem: given k × k matrices A1, A2, . . ., At, does there exist nonnegative integers m1, m2, . . ., mt such that the product Am11 Am22 · · · Amtt 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 that was not used to show decidability results in matrix semigroups before. 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 Am11 Am22 Am33 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. |
| spellingShingle | Bell, P Potapov, I Semukhin, P On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title | On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title_full | On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title_fullStr | On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title_full_unstemmed | On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title_short | On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond |
| title_sort | on the mortality problem from multiplicative matrix equations to linear recurrence sequences and beyond |
| work_keys_str_mv | AT bellp onthemortalityproblemfrommultiplicativematrixequationstolinearrecurrencesequencesandbeyond AT potapovi onthemortalityproblemfrommultiplicativematrixequationstolinearrecurrencesequencesandbeyond AT semukhinp onthemortalityproblemfrommultiplicativematrixequationstolinearrecurrencesequencesandbeyond |