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. 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.
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, ou aux ensembles de matrices dont au plus une est inversible.
Notes
Catégorie:Problème algorithmique Catégorie:Algèbre linéaire Catégorie:Informatique théorique