matrices similaires

16

Étant donné deux matrices A et B , le problème de décider s'il existe une matrice de permutation P telle que B = P - 1 A P est équivalent à (Isomorphisme graphique). Mais si nous relaxons P pour n'être qu'une matrice inversible, alors quelle est la complexité? Existe-t-il d'autres restrictions sur une matrice P inversible , en plus d'être une permutation, qui relient ce problème à d' autres problèmes difficiles?n×nABPB=P1APGIPPGI

DurgaDatta
la source
J'aurais peut-être dû poser cette question avant de poster une réponse, mais qu'avez-vous essayé avant de poster cette question ici?
Tsuyoshi Ito
@TsuyoshiIto J'ai essayé dans wikipdia et mathworld, j'ai également essayé une requête de recherche dans google, cette question est-elle trop élémentaire pour être posée ici? J'étais plus intéressé à savoir si une variante de ce problème donnerait un aperçu de l'IG.
DurgaDatta
Merci. Je pense que le niveau de la question est correct, mais je me demandais simplement pourquoi vous n'êtes pas arrivé à la même conclusion que moi. Ce que j'ai fait pour écrire la réponse consiste simplement à rechercher la «similitude de matrice» dans Wikipedia pour trouver une forme normale qui peut être calculée facilement (contrairement à la forme normale de Jordan, qui nécessite un champ algébriquement fermé). Je pense que vous auriez pu trouver les mêmes informations si vous aviez regardé Wikipédia plus attentivement.
Tsuyoshi Ito
Je ferai attention la prochaine fois. Je vous remercie.
DurgaDatta

Réponses:

11

Les matrices A et B dont les éléments sont dans un champ F sont similaires (dans F ) si et seulement si elles ont la même forme normale de Frobenius . Selon une recherche rapide, il semble que la forme normale de Frobenius d'une matrice n × n peut être calculée avec des opérations sur le terrain O ( n 3 ) [Sto98], et que cela peut être amélioré en quelque chose de comparable à la complexité de la multiplication matricielle [ Sto01].

[Sto98] Arne Storjohann. Un algorithme O ( n 3 ) pour la forme normale de Frobenius. Dans Actes du Symposium international de 1998 sur le calcul symbolique et algébrique (ISSAC) , pp. 101-105, août 1998. DOI: 10.1145 / 281508.281570 .

[Sto01] Arne Storjohann. Calcul déterministe de la forme Frobenius. In 42nd IEEE Symposium on Foundations of Computer Science (FOCS) , pp. 368–377, octobre 2001. DOI: 10.1109 / SFCS.2001.959911 .

Tsuyoshi Ito
la source
5

Il existe en effet d'autres restrictions sur qui relient ce problème à l'IG. Par exemple, si l'on exige que P soit un produit Kronecker (tenseur) P 1P 2P 3 , alors le problème résultant est aussi difficile que l'équivalence des tenseurs 3-valents, ce qui est à peu près la même complexité que l'équivalence du code linéaire, qui à son tour est connu pour être GI-dur (mais pas connu pour être équivalent à GI).PPP1P2P3

Un autre point de vue sur votre question, qui peut éclairer la situation générale, est le suivant. Pour toute action de groupe de sur un ensemble X n (un pour chaque n ), on peut s'interroger sur la complexité de décider si deux points donnés x , y X n sont dans la même orbite G n ; appelons cela le problème de l'orbite pour cette (famille de) action (s). Votre question porte alors essentiellement sur la complexité des problèmes d'orbite qui peuvent être formulés comme suit: étant donné une action linéaire d'un groupe G n sur un espace vectoriel V nGnXnnx,yXnGnGnVn, considérons le problème de l'orbite de l' action induite de (par conjugaison) sur X n = V n( V n ) .GnXn=Vn(Vn)

Pour l'isomorphisme du graphe, nous avons et V n = R n avec l'action naturelle en permutant les coordonnées. Pour la conjugaison matricielle, nous avons G n = GL n ( F ) dans son action naturelle sur V n = F n . Pour l'exemple ci-dessus, nous avons G n = GL a × GL b × GL c dans son action naturelle sur V n = F aFGn=SnVn=RnGn=GLn(F)Vn=FnGn=GLa×GLb×GLcVn=FaFbFc

Joshua Grochow
la source