Abstract
In this paper we discuss the existence of an algorithm to decide if a given set of 2 \times 2 matrices is mortal. A set F={A 1 ,\ldots,A m } of square matrices is said to be mortal if there exist an integer k \geq 1 and some integers i 1 ,i 2 ,\ldots,i k ∈ {1, \ldots, m} with A i1 A i2 ⋅s A ik =0 . We survey this problem and propose some new extensions. We prove the problem to be BSS-undecidable for real matrices and Turing-decidable for two rational matrices. We relate the problem for rational matrices to the entry-equivalence problem, to the zero-in-the-corner problem, and to the reachability problem for piecewise-affine functions. Finally, we state some NP-completeness results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bournez, O., Branicky, M. The Mortality Problem for Matrices of Low Dimensions. Theory Comput. Systems 35, 433–448 (2002). https://doi.org/10.1007/s00224-002-1010-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-002-1010-5