Problème de permutation (difficile)

[invited26e6276]

Bonjour,

Dans le cadre d'un problème de permutation je tombe sur l'équation suivante : soit et des matrices de permutations connues. J'aimerai trouver une matrice de permutation par bloc (on connaît le nombre et la taille de chaque bloc) qui satisfait :




Ayant déjà feuilleté pas mal d'ouvrages en quête d'idées pour résoudre ce problème, mais n'ayant rien trouvé je m'adresse à vous.

La difficulté réside dans le fait que X est une matrice de permutation par bloc. Ce qui fait qu'il est difficile de trouver une couverture compléte en cycle de 4 du produit considéré (uniquement des cycles de 4, pas de point fixe ou transposition).

Voila, n'hésitez pas à demander des précisions.
J'espère que quelqu'un pourra m'aiguiller.
-----

[Armen92]

Je ne sais si cela aide :
L'équation M^4=I montre que, si M est diagonalisable et de dimension ≥4, ses valeurs propres sont e^(i k pi/2), k=0,1,2,3 par exemple.
Si donc M est de dimension supérieure à 4, son spectre est dégénéré (par Cayley-Hamilton).

[invited26e6276]

Merci, Armen92, pour ta réponse. Désolé de ne pas avoir répondu plus tôt.
C'était une possibilité que j'ai déjà exploré, c'est à dire résoudre :



Ca mène à une assez jolie relation entre X et U du type :



Ce procédé me paraît assez intéressant car il permet de résoudre n'importe quel problème de ce type (même avec des puissances élevé) avec des équations quadratiques.
Malheureusement ce n'est pas linéaire, et je n'ai pas trouvé de façon pratique pour résoudre une telle équation (algorithmiquement parlant).
En revanche, entre temps, j'ai pu déterminer une grandeur linéaire qui reste conservé. Par comodité je transforme en :





Maintenant vu que X est par bloque, il existe un vecteur, ayant une valeur différente pour chaque bloc, tel que :



Etant donné que X est par bloque on peut conclure que et doivent satisfaire une parité. C'est à dire pour chaque bloc on doit avoir le même nombre d'entrée d'un autre bloc de chaque côté de l'égalité. Ce qui permet d'écrire (Nombre de blocs)² équations linéaires sur X. Cette parité est assez pratique pour un algorithme d'optimisation.