Document Open Access Logo

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

Authors Paul C. Bell , Igor Potapov , Pavel Semukhin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.83.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Paul C. Bell
  • Department of Computer Science, Byrom Street, Liverpool John Moores University, Liverpool, L3-3AF, UK
Igor Potapov
  • Department of Computer Science, Ashton Building, Ashton Street, University of Liverpool, Liverpool, L69-3BX, UK
Pavel Semukhin
  • Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK

Funding

  • Potapov, Igor: Partially supported by EPSRC grants EP/R018472/1 and EP/M00077X/1.
  • Semukhin, Pavel: Supported by ERC grant AVS-ISS (648701).

Acknowledgements

We thank Prof. James Worrell for useful discussions, particularly related to S-unit equations.

Cite As Get BibTex

Paul C. Bell, Igor Potapov, and Pavel Semukhin. On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.83

Abstract

We consider the following variant of the Mortality Problem: given k x k matrices A_1, A_2, ...,A_{t}, does there exist nonnegative integers m_1, m_2, ...,m_t such that the product A_1^{m_1} A_2^{m_2} * ... * A_{t}^{m_{t}} 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 (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 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 x 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computability
  • Mathematics of computing → Computations on matrices
Keywords
  • Linear recurrence sequences
  • Skolem’s problem
  • mortality problem
  • matrix equations
  • primary decomposition theorem
  • Baker’s theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. L. Babai, R. Beals, J-Y. Cai, G. Ivanyos, and E. M. Luks. Multiplicative equations over commuting matrices. In Proc. of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 96, 1996. Google Scholar
  2. C. Baier, S. Kiefer, J. Klein, S. Klüppelholz, D. Müller, and J. Worrell. Markov Chains and Unambiguous Büchi Automata. In Computer Aided Verification - 28th International Conference, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part I, pages 23-42, 2016. Google Scholar
  3. P. C. Bell, V. Halava, T. Harju, J. Karhumäki, and I. Potapov. Matrix equations and Hilbert’s tenth problem. International Journal of Algebra and Computation, 18:1231-1241, 2008. Google Scholar
  4. P. C. Bell, M. Hirvensalo, and I. Potapov. Mortality for 2× 2 matrices is NP-hard. In Mathematical Foundations of Computer Science (MFCS 2012), volume LNCS 7464, pages 148-159, 2012. Google Scholar
  5. P. C. Bell, M. Hirvensalo, and I. Potapov. The identity problem for matrix semigroups in SL₂(ℤ) is NP-complete. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 187-206, 2017. Google Scholar
  6. Paul C. Bell, Igor Potapov, and Pavel Semukhin. On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond. CoRR, abs/1902.10188, 2019. URL: http://arxiv.org/abs/1902.10188.
  7. V. Blondel, E. Jeandel, P. Koiran, and N. Portier. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34:6:1464-1473, 2005. Google Scholar
  8. V. D. Blondel, O. Bournez, P. Koiran, C. Papadimitriou, and J. N. Tsitsiklis. Deciding stability and mortality of piecewise affine dynamical systems. Theoretical Computer Science, 255(1-2):687-696, 2001. Google Scholar
  9. V. D. Blondel and N. Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, pages 91-98, 2002. Google Scholar
  10. V. D. Blondel and J. N. Tsitsiklis. Complexity of stability and controllability of elementary hybrid systems. Automatica, 35:479-489, 1999. Google Scholar
  11. Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, and Zicheng Liu. Efficient Average-Case Algorithms for the Modular Group. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 143-152, 1994. Google Scholar
  12. Jin-yi Cai, Richard J. Lipton, and Yechezkel Zalcstein. The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 135-142, 1994. Google Scholar
  13. J. Cassaigne, V. Halava, T. Harju, and F. Nicolas. Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More. CoRR, abs/1404.0644, 2014. Google Scholar
  14. V. Chonev, J. Ouaknine, and J. Worrell. On the Complexity of the Orbit Problem. Journal of the ACM, 63(3):1-18, 2016. Google Scholar
  15. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the Skolem Problem for Continuous Linear Dynamical Systems. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 100:1-100:13, 2016. Google Scholar
  16. J.-H. Evertse, K. Győry, C. L. Stewart, and R. Tijdeman. S-unit equations and their applications. In New advances in transcendence theory (Durham, 1986), pages 110-174. Cambridge Univ. Press, Cambridge, 1988. Google Scholar
  17. E. Galby, J. Ouaknine, and J. Worrell. On matrix powering in low dimensions. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 329-340, 2015. Google Scholar
  18. K. Győry. On the abc conjecture in algebraic number fields. Acta Arith., 133(3):281-295, 2008. Google Scholar
  19. V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. Skolem’s problem - on the border between decidability and undecidability. In TUCS Technical Report Number 683, 2005. Google Scholar
  20. G. Hansel. Une démonstration simple du théorème de Skolem-Mahler-Lech. Theoret. Comput. Sci., 43(1):91-98, 1986. Google Scholar
  21. Michael A. Harrison. Lectures on Linear Sequential Machines. Academic Press, Inc., Orlando, FL, USA, 1969. Google Scholar
  22. K. Hoffman and R. Kunze. Linear algebra. Second edition. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. Google Scholar
  23. Juha Honkala. Products of matrices and recursively enumerable sets. Journal of Computer and System Sciences, 81(2):468-472, 2015. Google Scholar
  24. R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1990. Google Scholar
  25. Ravindran Kannan and Richard J. Lipton. The Orbit Problem is Decidable. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80, pages 252-261, New York, NY, USA, 1980. ACM. Google Scholar
  26. J.-Y. Kao, N. Rampersad, and J. Shallit. On NFAs where all states are final, initial, or both. Theor. Comput. Sci., 410(47-49):5010-5021, 2009. Google Scholar
  27. S.-K. Ko, R. Niskanen, and I. Potapov. On the Identity Problem for the Special Linear Group and the Heisenberg Group. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 132:1-132:15, 2018. Google Scholar
  28. Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. CoRR, abs/1507.05145, 2015. URL: http://arxiv.org/abs/1507.05145.
  29. C. Lech. A note on recurring series. Ark. Mat. 2, 1953. Google Scholar
  30. Alexei Lisitsa and Igor Potapov. Membership and Reachability Problems for Row-Monomial Transformations. In Jiří Fiala, Václav Koubek, and Jan Kratochvíl, editors, Mathematical Foundations of Computer Science 2004, pages 623-634, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  31. Markus Lohrey. Rational subsets of unitriangular groups. IJAC, 25(1-2):113-122, 2015. Google Scholar
  32. K. Mahler. Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen. In Akad. Wet. Amsterdam 38, pages 50-60, 1935. Google Scholar
  33. M. Mignotte, T. N. Shorey, and R. Tijdeman. The distance between terms of an algebraic recurrence sequence. J. Reine Angew. Math., 349:63-76, 1984. Google Scholar
  34. C. Nuccio and E. Rodaro. Mortality Problem for 2× 2 Integer Matrices. In SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, pages 400-405, 2008. URL: https://doi.org/10.1007/978-3-540-77566-9_34.
  35. J. Ouaknine, J. Sousa Pinto, and J. Worrell. On termination of integer linear loops. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 957-969, 2015. Google Scholar
  36. J. Ouaknine, A. Pouly, J. Sousa-Pinto, and J. Worrell. Solvability of Matrix-Exponential Equations. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), pages 798-806, 2016. Google Scholar
  37. Joël Ouaknine and James Worrell. Decision Problems for Linear Recurrence Sequences. In Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012. Proceedings, pages 21-28, 2012. Google Scholar
  38. Joël Ouaknine and James Worrell. On the Positivity Problem for Simple Linear Recurrence Sequences,. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 318-329, 2014. Google Scholar
  39. Joël Ouaknine and James Worrell. Positivity Problems for Low-Order Linear Recurrence Sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366-379, 2014. Google Scholar
  40. M. S. Paterson. Unsolvability in 3× 3 matrices. Studies in Applied Mathematics, 49(1):105-107, 1970. Google Scholar
  41. Igor Potapov and Pavel Semukhin. Decidability of the Membership Problem for 2× 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 170-186, 2017. Google Scholar
  42. Igor Potapov and Pavel Semukhin. Membership Problem in GL(2, Z) Extended by Singular Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 44:1-44:13, 2017. Google Scholar
  43. T. Skolem. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und diophantischer Gleichungen. Skand. Mat. Kongr., 8:163-188, 1934. Google Scholar
  44. N. K. Vereshchagin. The problem of the appearance of a zero in a linear recursive sequence. Mat. Zametki 38, 347(2):609-615, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact