On the mortality problem for matrices of low dimensions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2000

On the mortality problem for matrices of low dimensions

Résumé

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.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

inria-00099293 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00099293 , version 1

Citer

Olivier Bournez, Michael Branicky. On the mortality problem for matrices of low dimensions. [Intern report] A00-R-089 || bournez00b, 2000. ⟨inria-00099293⟩
44 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More