matrices similares

Dadas dos matrices A y B , el problema de decidir si existe una matriz de permutación P tal que B = P - 1 A P es equivalente a (isomorfismo gráfico). Pero si relajamos P para que sea solo una matriz invertible, ¿cuál es la complejidad? ¿Existen otras restricciones en una matriz P invertible , además de ser una permutación, que relacionan este problema u otros problemas difíciles?$n \times n$$A$$B$$P$$B = P^{-1}AP$GI$P$$P$GI

Las matrices A y B cuyos elementos están en un campo F son similares (en F ) si y solo si tienen la misma forma normal de Frobenius . Según una búsqueda rápida, parece que la forma normal de Frobenius de una matriz n × n se puede calcular con operaciones de campo O ( n ³ ) [Sto98], y que esto se puede mejorar a algo comparable a la complejidad de la multiplicación de matrices [ Sto01].

[Sto98] Arne Storjohann. Un algoritmo O ( n ³ ) para la forma normal de Frobenius. En Actas del Simposio internacional de 1998 sobre computación simbólica y algebraica (ISSAC) , págs. 101-105, agosto de 1998. DOI: 10.1145 / 281508.281570 .

[Sto01] Arne Storjohann. Cálculo determinista de la forma de Frobenius. En el 42º Simposio IEEE sobre Fundamentos de Ciencias de la Computación (FOCS) , págs. 368–377, octubre de 2001. DOI: 10.1109 / SFCS.2001.959911 .

De hecho, existen otras restricciones sobre que relacionan este problema con IG. Por ejemplo, si se requiere que P sea ​​un producto Kronecker (tensor) P 1 ⊗ P 2 ⊗ P 3 , entonces el problema resultante es tan difícil como la equivalencia de los tensores de 3 vales, que es aproximadamente la misma complejidad que la Equivalencia de código lineal, que a su vez se sabe que es GI-hard (pero no se sabe que sea equivalente a GI).$P$$P$$P_1 \otimes P_2 \otimes P_3$

Otro punto de vista sobre su pregunta, que puede arrojar algo de luz sobre la situación general, es el siguiente. Para cualquier acción grupal de en un conjunto X n (uno para cada n ), se puede preguntar sobre la complejidad de decidir si dos puntos dados x , y ∈ X n están en el mismo órbita G n ; llame a esto el problema de la órbita de esa (familia de) acción (es). Entonces, su pregunta es esencialmente sobre la complejidad de los problemas de órbita que pueden expresarse de la siguiente manera: dada una acción lineal de un grupo G n en un espacio vectorial V $G_n$$X_n$$n$$x,y \in X_n$$G_n$$G_n$$V_n$, considere el problema de la órbita de la acción inducida de (por conjugación) en X n = V n ⊗ ( V n ) ∗ .$G_n$$X_n = V_n \otimes (V_n)^*$

Para el isomorfismo gráfico tenemos y V n = R n con la acción natural permutando coordenadas. Para la conjugación matricial tenemos G n = GL n ( F ) en su acción natural en V n = F n . Para el ejemplo anterior tenemos G n = GL a × GL b × GL c en su acción natural en 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$