Exprimer le déterminant comme permanent

12

Un problème majeur du TCS est le problème de l'expression d'un permanent comme déterminant. Je lisais le document d'Agrawal Determinant Versus Permanent et dans un paragraphe, il affirme que le problème inverse est facile.

Il est facile de voir que le déterminant d'une matrice peut être exprimé comme le permanent d'une matrice liée X dont les entrées sont 0, 1, ou x i , j s et qui est de taille O ( n ) (mis en place d' entrées de X telle que det X = det X et le produit correspondant à chaque permutation qui a un cycle pair est égal à zéro).XXˆxi,jO(n)XˆX

Tout d'abord, je ne pense pas que les variables 0, 1 et soient suffisantes car il nous manquerait des termes négatifs. Mais même si nous autorisons également les variables -1 et - x i , j , je ne vois pas pourquoi la croissance de la taille peut être rendue linéaire. Quelqu'un pourrait-il m'expliquer la construction?xi,jxi,j

Farnak
la source
1
xijsxijs=±1
1
@GeoffreyIrving, cette interprétation ne me semble pas juste ... pour autant que je sache, "s" est composé en mode texte, pas en mode mathématique; "s" n'est jamais défini comme une variable; et "s" n'est indexé par rien. Je pense que cela indique simplement le pluriel.
usul
2
xij
1
Je dois souligner que les termes négatifs associés au signe de la permutation sont traités par son commentaire qui dit que vous configurez la matrice de sorte que les termes associés aux cycles pairs se réduisent à zéro.
Suresh Venkat
1
@SureshVenkat: Cela semble plus facile à dire qu'à faire (du moins pour moi). Pourriez-vous s'il vous plaît démontrer cela sur, disons, une matrice 4x4?
Farnak

Réponses:

8

n×nO(n3)

Joshua Grochow
la source
1
Qu'est-ce qu'un ABP?
Suresh Venkat
1
@SureshVenkat: J'ai mis à jour la réponse avec leur nom complet et un lien vers d'autres références. Si vous avez des questions sur les ABP, n'hésitez pas à poster ici ou à m'envoyer un e-mail.
Joshua Grochow