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

https://hal.inria.fr/inria-00100725
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:50:02 PM
Last modification on : Friday, February 26, 2021 - 3:28:05 PM

Identifiers

  • HAL Id : inria-00100725, version 1

Collections

Citation

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. ⟨inria-00100725⟩

Share

Metrics

Record views

132