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 \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.
Type de document :
Rapport
[Intern report] A00-R-089 || bournez00b, 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00099293
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:33
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00099293, version 1

Collections

Citation

Olivier Bournez, Michael Branicky. On the mortality problem for matrices of low dimensions. [Intern report] A00-R-089 || bournez00b, 2000. 〈inria-00099293〉

Partager

Métriques

Consultations de la notice

76