Dadas duas matrizes e , o problema de decidir se existe uma matriz de permutação tal que seja equivalente a (gráfico isomorfismo). Mas se relaxarmos para ser apenas uma matriz invertível, então qual é a complexidade? Existem outras restrições em uma matriz invertível , além de ser uma permutação, que relacionam esse problema ou outros problemas difíceis?GI
GI
16
Respostas:
As matrizes A e B cujos elementos estão em um campo F são semelhantes (em F ) se e somente se tiverem a mesma forma normal de Frobenius . De acordo com uma pesquisa rápida, parece que a forma normal Frobenius de uma n × n matriz pode ser calculado com O ( n 3 ) operações de campo [Sto98], e que isso pode ser melhorado para algo comparável à complexidade da multiplicação de matrizes [ Sto01].
Arne Storjohann. Um algoritmo O ( n 3 ) para a forma normal de Frobenius. Em Anais do Simpósio Internacional de 1998 sobre Computação Simbólica e Algébrica (ISSAC) , pp. 101-105, agosto de 1998. DOI: 10.1145 / 281508.281570 .
[Sto01] Arne Storjohann. Cálculo determinístico da forma de Frobenius. No 42º Simpósio do IEEE sobre Fundamentos da Ciência da Computação (FOCS) , pp. 368–377, outubro de 2001. DOI: 10.1109 / SFCS.2001.959911 .
fonte
De fato, existem outras restrições em que relacionam esse problema à IG. Por exemplo, se alguém exige que P seja um produto Kronecker (tensor) P 1 ⊗ P 2 ⊗ P 3 , o problema resultante é tão difícil quanto a equivalência de tensores de 3 valentes, que é aproximadamente a mesma complexidade que a Equivalência de código linear, que por sua vez é conhecido por ser resistente ao GI (mas não conhecido por ser equivalente ao GI).P P P1⊗P2⊗P3
Outro ponto de vista da sua pergunta, que pode lançar alguma luz sobre a situação geral, é o seguinte. Para qualquer ação grupal de em um conjunto X n (um para cada n ), pode-se perguntar sobre a complexidade de decidir se dois pontos x , y ∈ X n estão no mesmo óxido de G n ; chame isso de problema de órbita para essa (família de) ação (s). Sua pergunta é essencialmente sobre a complexidade dos problemas de órbita que podem ser expressos da seguinte forma: dada uma ação linear de um grupo G n em um espaço vetorial V nGn Xn n x , y∈ Xn Gn Gn Vn , considere o problema de órbita da ação induzida de (por conjugação) em X n = V n ⊗ ( V n ) ∗ .Gn Xn= Vn⊗ ( Vn)∗
Para isomorfismo gráfico, temos e V n = R n com a ação natural, permutando coordenadas. Para a conjugação da matriz, temos G n = GL n ( F ) em sua ação natural sobre V n = F n . Para o exemplo acima, temos G n = GL a × GL b × GL c em sua ação natural em V n = F a ⊗ FGn= Sn Vn= Rn Gn= GLn( F ) Vn= Fn Gn= GLuma× GLb× GLc .Vn= Fuma⊗ Fb⊗ Fc
fonte