12

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?

Alessandro Cosentino
  • 4,000
  • 35
  • 43
Farnak
  • 131
  • 3
  • 1
    Note that he says $x_{ij} s$, not $x_{ij}$. $s = \pm 1$ provides the necessary signs. – Geoffrey Irving Mar 03 '14 at 01:25
  • 1
    @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. – usul Mar 03 '14 at 02:16
  • Well, that would mean it's both grammatically inconsistent and wrong. Your interpretation of the world sounds less nice than mine. :) – Geoffrey Irving Mar 03 '14 at 02:22
  • 2
    I think @usul is correct. he's using the 's' as a plural (i.e many $x_{ij}$). – Suresh Venkat Mar 03 '14 at 03:44
  • 1
    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. – Suresh Venkat Mar 03 '14 at 03:46
  • 1
    @SureshVenkat: That sounds easier said than done (at least to me). Could you please demonstrate this on say, a 4x4 matrix? – Farnak Mar 03 '14 at 19:11

1 Answers1

8

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.

Community
  • 1
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228