Problème des matrices mortelles

Cet article est orphelin. Moins de trois articles lui sont liés (avril 2024).

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].