Expressando determinante como permanente

12

Um grande problema no TCS é o problema de expressar uma permanente como determinante. Eu estava lendo o artigo de Agrawal, Determinant Versus Permanent, e em um parágrafo ele afirma que o problema inverso é fácil.

É fácil de ver que o determinante de uma matriz pode ser expresso como o permanente de uma matriz relacionada X cujas entradas são 0, 1, ou x i , j s e que é de tamanho O ( n ) (configurar entradas de X tal que det X = det X e o produto correspondente a cada permutação que tem um ciclo mesmo é zero).XXˆxi,jO(n)XˆX

Primeiro de tudo, eu não acho que 0, 1, e variáveis são suficientes porque estaria faltando termos negativos. Mas mesmo se permitimos variáveis -1 e - x i , j , também não vejo por que o crescimento no tamanho pode ser linear. Alguém poderia me explicar a construção?xi,jxi,j

Farnak
fonte
1
xijsxijs=±1
1
@GeoffreyIrving, essa interpretação não me parece correta ... até onde eu sei, "s" está tipificado no modo texto, não no modo matemático; "s" nunca é definido como uma variável; e "s" não é indexado por nada. Eu acho que isso apenas indica o plural.
usul
2
xij
1
Devo salientar que os termos negativos associados ao sinal da permutação são tratados pelo seu comentário, que diz que você configura a matriz para que os termos associados aos ciclos pares se reduzam a zero.
precisa saber é o seguinte
1
@SureshVenkat: Parece mais fácil falar do que fazer (pelo menos para mim). Você poderia demonstrar isso em uma matriz 4x4?
precisa saber é

Respostas:

8

n×nO(n3)

Joshua Grochow
fonte
1
O que é um ABP?
Suresh Venkat
1
@SureshVenkat: atualizei a resposta com o nome completo e um link para outras referências. Se você tiver dúvidas sobre os ABPs, sinta-se à vontade para postar aqui ou me enviar um e-mail.
Joshua Grochow