12
$\begingroup$

One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is easy.

It is easy to see that the determinant of a matrix $X$ can be expressed as the permanent of a related matrix $Xˆ$ whose entries are 0, 1, or $x_{i,j}$ s and which is of size $O(n)$ (set up entries of Xˆ such that det $Xˆ$ = det $X$ and the product corresponding to every permutation that has an even cycle is zero).

First of all, I don't think 0, 1, and $x_{i,j}$ variables are enough because we would be missing negative terms. But even if we allowed -1 and $-x_{i,j}$ variables as well, I don't see why the growth in size can be made linear. Could someone please explain the construction to me?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Note that he says $x_{ij} s$, not $x_{ij}$. $s = \pm 1$ provides the necessary signs. $\endgroup$ – Geoffrey Irving Mar 3 '14 at 1:25
  • 1
    $\begingroup$ @GeoffreyIrving, that interpretation doesn't seem right to me ... as far as I can tell, "s" is typeset in text mode, not math mode; "s" is never defined as a variable; and "s" is not indexed by anything. I think it just indicates the plural. $\endgroup$ – usul Mar 3 '14 at 2:16
  • 2
    $\begingroup$ I think @usul is correct. he's using the 's' as a plural (i.e many $x_{ij}$). $\endgroup$ – Suresh Venkat Mar 3 '14 at 3:44
  • 1
    $\begingroup$ I should point out that the negative terms associated with the sign of the permutation are dealt with by his comment that says that you set up the matrix so that the terms associated with even cycles reduce to zero. $\endgroup$ – Suresh Venkat Mar 3 '14 at 3:46
  • 1
    $\begingroup$ @SureshVenkat: That sounds easier said than done (at least to me). Could you please demonstrate this on say, a 4x4 matrix? $\endgroup$ – Farnak Mar 3 '14 at 19:11
8
$\begingroup$

I think this may have been a typo in Agrawal's paper. The best I know is how to write an $n \times n$ determinant as a projection of an $O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ What's an ABP ? $\endgroup$ – Suresh Venkat Mar 3 '14 at 22:18
  • 1
    $\begingroup$ @SureshVenkat: I updated the answer with their full name and a link to further references. If you have questions about ABPs feel free to post here or email me. $\endgroup$ – Joshua Grochow Mar 3 '14 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.