Bonjour,

Mon problème est le suivant (je note M' la transposée d'une matrice M):

Etant donné une matrice A booléenne, je souhaite trouver (sous réserve d'existence) deux matrices de permutation R et Q telles que RAQ est une matrice symétrique.

Si je ne me trompe pas, ce problème équivaut à trouver une matrice de permutation P telle que PA est symétrique
(en effet, s'il existe deux matrices de permutation R et Q telles que RAQ est symétrique, alors Q(RAQ)Q' est symétrique, donc P = QR convient)

Ce problème s'écrit : PA = (PA)'
soit : PAP = A'

Je voudrais savoir si on sait des choses sur ce problème ? Connait-on un algorithme polynomial permettant de le résoudre ? Est-il NP-Complet ?

Ce problème m'a fait penser au problème de l'isomorphisme de graphes. Etant donné deux graphes ayant pour matrices d'adjacence A et B respectivement, on cherche une permutation P telle que PAP' = B. Ce problème est célèbre, mais à ma connaissance, on ne connaît pas d'algorithme polynomial, et on ignore s'il NP-complet.

Merci d'avance pour vos réponses.