podobne matryce

Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że są permutacją, które wiążą ten problem z innymi trudnymi problemami?A B P $n \times n$$A$$B$$P$$B = P^{-1}AP$GI$P$$P$GI

Macierze A i B, których elementy są w polu F, są podobne (w F ) wtedy i tylko wtedy, gdy mają tę samą postać normalną Frobeniusa . Według szybkiego wyszukiwania wydaje się, że normalną postać Frobeniusa macierzy n × n można obliczyć za pomocą operacji w polu O ( n ³ ) [Sto98] i że można to poprawić do czegoś porównywalnego ze złożonością mnożenia macierzy [ Sto01].

[Sto98] Arne Storjohann. Algorytm O ( n ³ ) dla postaci normalnej Frobeniusa. W Proceedings of the International International Symposium on Symbolic and Algebraic Computation (ISSAC) , s. 101–105, sierpień 1998. DOI: 10.1145 / 281508.281570 .

[Sto01] Arne Storjohann. Deterministyczne obliczenia postaci Frobeniusa. W 42. sympozjum IEEE na temat podstaw informatyki (FOCS) , s. 368–377, październik 2001 r. DOI: 10.1109 / SFCS.2001.959911 .

Rzeczywiście istnieją inne ograniczenia dotyczące które wiążą ten problem z OG. Na przykład, jeśli wymaga się, aby P był produktem Kroneckera (tensora) P 1 ⊗ P 2 ⊗ P 3 , wynikający z tego problem jest tak trudny jak równoważność 3-walentnych tensorów, co jest mniej więcej taką samą złożonością jak równoważność kodu liniowego, który z kolei jest znany z GI-hard (ale nie jest znany jako równoważny GI).$P$$P$$P_1 \otimes P_2 \otimes P_3$

Kolejny punkt widzenia na twoje pytanie, który może rzucić nieco światła na ogólną sytuację, jest następujący. Dla każdej akcji Grupa na zadany X n (po jednym dla każdego z n ), można zadać o złożoności decydowania czy dwie dane punkty x , y ∈ X n w tym samym G n -orbit; nazwij to problemem orbit dla tego działania (rodziny). Twoje pytanie dotyczy zatem zasadniczo złożoności problemów orbity, które można sformułować następująco: biorąc pod uwagę liniowe działanie grupy G n na przestrzeni wektorowej V $G_n$$X_n$$n$$x,y \in X_n$$G_n$$G_n$$V_n$Rozważmy problem orbity wywołanego działaniem (sprzęgana) na X, n = V n ⊗ ( V n ) * .$G_n$$X_n = V_n \otimes (V_n)^*$

Na wykresie izomorfizmie mamy i V n = R n z naturalnego działania przestawiania współrzędnych. Do koniugacji macierzy mamy G n = GL n ( F ) w jego naturalnym działaniu na V n = F n . W powyższym przykładzie mamy G n = GL a × GL b × GL c w jego naturalnym działaniu na V n = F a ⊗ $G_n = S_n$$V_n = \mathbb{R}^n$$G_n = \text{GL}_n(\mathbb{F})$$V_n = \mathbb{F}^n$$G_n = \text{GL}_a \times \text{GL}_b \times \text{GL}_c$ .$V_n = \mathbb{F}^{a} \otimes \mathbb{F}^b \otimes \mathbb{F}^c$