Skip to Main content Skip to Navigation
Journal articles

On the mortality problem for matrices of low dimensions

Olivier Bournez 1 Michael Branicky
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we discuss the existence of an algorithm to decide if a given set of $2 × 2$ matrices is mortal. A set $F=s ¼,A_ms>$ of square matrices is said to be \motnouv{mortal} if there exist an integer $k >³ 1$ and some integers $i_1,i_2,>¼,i_k >Î s <1, >¼, ms>$ with $A_{i_1} A_{i_2} s~ A_{i_k}=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.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:50:02 PM
Last modification on : Friday, May 13, 2022 - 10:18:05 PM

Links full text




Olivier Bournez, Michael Branicky. On the mortality problem for matrices of low dimensions. Theory of Computing Systems, Springer Verlag, 2002, 35 (4), pp.433-448. ⟨10.1007/s00224-002-1010-5⟩. ⟨inria-00100725⟩



Record views