On the mortality problem for matrices of low dimensions

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,\dots,A_m\} of 2 \times 2 matrices is said to be \motnouv{mortal} if there exist an integer k \ge 1 and some integers i_1,i_2,\dots,i_k \in \{1, \ldots, m\} with A_{i_1} A_{i_2} \cdots 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 left upper corner problem and to the reachability problem for piecewise affine functions. Finally, we state some NP-completeness results.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101904
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:24 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR1999-20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101904, version 1

Collections

Citation

Olivier Bournez, Michael Branicky. On the mortality problem for matrices of low dimensions. [Research Report] LIP RR-1999-20, Laboratoire de l'informatique du parallélisme. 1999, 2+13p. ⟨hal-02101904⟩

Share

Metrics

Record views

6

Files downloads

24