On the mortality problem for matrices of low dimensions - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1999

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.
Dans ce papier, nous discutons l'existence d'un algorithme pour décider si un ensemble donné de matrices 2 \times 2 est mortel: un ensemble F=\{A_1,\dots,A_m\} de matrices 2 \times 2 est dit \motnouv{mortel} s'il existe un entier k \ge 1 et des entiers i_1,i_2,\dots,i_k \in \{1, \ldots, m\} avec A_{i_1} A_{i_2} \cdots A_{i_k}=0. Nous présentons une synthèse des résultats connus sur ce problème et présentons quelques extensions: nous prouvons que le problème est BSS-indécidable pour les matrices réelles et Turing-décidable pour les matrices rationnelles. Nous relions le problème au problème de l'égalité des coefficients, au problème du zéro dans un coin et au problème de l'atteignabilité pour les fonctions affines par morceaux. Enfin, nous établissons des résultats de NP-complétude.
Fichier principal
Vignette du fichier
RR1999-20.pdf (305 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101904 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101904 , version 1

Citer

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⟩
42 Consultations
849 Téléchargements

Partager

More