Problème des matrices mortelles
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[Problème des matrices mortelles]] dans les articles relatifs au sujet.
En informatique théorique, le problème des matrices mortelles (matrix mortality problem en anglais) est le problème de décision qui demande, étant donné un ensemble fini de matrices n×n à coefficients entiers, s'il existe une manière d'exprimer la matrice nulle comme produit fini de matrices de cet ensemble.
Ce problème est indécidable pour n≥3[1]. Il reste même indécidable restreint aux ensembles de 6 matrices (ou plus) pour n = 3, de 4 matrices pour n = 5, de 3 matrices pour n = 9, et de 2 matrices pour n = 15[2].
Dans le cas n = 2, la décidabilité du problème des matrices mortelles est une question ouverte. Toutefois, certains cas particuliers ont été résolus. On sait que le problème est décidable (pour n = 2) s'il est restreint aux ensembles de 2 matrices seulement[3], ou aux ensembles de matrices dont au plus une est inversible[4].
Notes[modifier | modifier le code]
- Mike Paterson, « Unsolvability in 3×3 matrices », Studies in Applied Mathematics, vol. 49, , p. 105–107
- (en) Julien Cassaigne, Vesa Halava, Tero Harju et Francois Nicolas, « Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More », .
- Olivier Bournez et Michael Branicky, « The Mortality Problem for Matrices of Low Dimensions », Theory of Computing Systems, vol. 35, , p. 433–448 (DOI 10.1007/s00224-002-1010-5, lire en ligne)
- (en) Christopher Carl Heckman, « The 2×2 Matrix Mortality Problem and Invertible Matrix », .
