matrizes semelhantes

16

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?n×nABPB=P1APGIPPGI

DurgaDatta
fonte
Talvez eu devesse ter perguntado isso antes de postar uma resposta, mas o que você tentou antes de postar esta pergunta aqui?
Tsuyoshi Ito
@TsuyoshiIto eu tentei no wikipdia e mathworld, também tentei alguma consulta de pesquisa no google, essa pergunta é muito elementar para ser feita aqui? Eu estava mais interessado se alguma variante desse problema desse algumas idéias para a IG.
DurgaDatta
Obrigado. Eu acho que o nível da pergunta está bom, mas eu me perguntava por que você não chegou à mesma conclusão que eu. O que fiz para escrever a resposta é apenas procurar "semelhança de matriz" na Wikipedia para encontrar uma forma normal que possa ser computada facilmente (diferente da forma normal de Jordan, que requer um campo fechado algebricamente). Eu acho que você poderia ter encontrado a mesma informação se tivesse examinado a Wikipedia com mais cuidado.
Tsuyoshi Ito
Serei cuidadoso da próxima vez. Obrigado.
DurgaDatta

Respostas:

11

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 .

Tsuyoshi Ito
fonte
5

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 1P 2P 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).PPP1P2P3

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 nGnXnnx,yXnGnGnVn, considere o problema de órbita da ação induzida de (por conjugação) em X n = V n( V n ) .GnXn=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 aFGn=SnVn=RnGn=GLn(F)Vn=FnGn=GLuma×GLb×GLc .Vn=FumaFbFc

Joshua Grochow
fonte