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?

  • 1
    $\begingroup$ Note that he says $x_{ij} s$, not $x_{ij}$. $s = \pm 1$ provides the necessary signs. $\endgroup$ Mar 3, 2014 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, 2014 at 2:16
  • 2
    $\begingroup$ I think @usul is correct. he's using the 's' as a plural (i.e many $x_{ij}$). $\endgroup$ Mar 3, 2014 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$ Mar 3, 2014 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, 2014 at 19:11

1 Answer 1


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.

  • 1
    $\begingroup$ What's an ABP ? $\endgroup$ Mar 3, 2014 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$ Mar 3, 2014 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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