Problème des matrices mortelles
De Wikipedia, l'encyclopédie encyclopedia
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.
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
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.
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].