<p>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 <a href="http://eccc.hpi-web.de/search/?search=algebraic+branching+program" rel="nofollow noreferrer">algebraic branching program</a> (and I think this is currently the best known). See the comments on <a href="https://cstheory.stackexchange.com/a/16477/129">this answer</a>.</p>

CC BY-SA 3.0
2014-03-03T22:18:19.573Z
What's an ABP ?
Suresh Venkat
CC BY-SA 3.0
2014-03-03T22:51:10.773Z
@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.
Joshua Grochow
CC BY-SA 3.0
2014-03-03T19:46:53.133Z
2014-03-03T22:50:04.357Z
2017-04-13T12:32:28.167Z
Joshua Grochow
<p>One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper <a href="http://www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf">Determinant Versus Permanent</a> and in one paragraph he claims the reverse problem is easy.</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2014-03-03T01:25:04.493Z
Note that he says $x_{ij} s$, not $x_{ij}$.  $s = \pm 1$ provides the necessary signs.
Geoffrey Irving
CC BY-SA 3.0
2014-03-03T02:16:42.167Z
@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
CC BY-SA 3.0
2014-03-03T02:22:57.183Z
Well, that would mean it's both grammatically inconsistent and wrong.  Your interpretation of the world sounds less nice than mine. :)
Geoffrey Irving
CC BY-SA 3.0
2014-03-03T03:44:29.960Z
I think @usul is correct. he's using the 's' as a plural (i.e *many* $x_{ij}$).
Suresh Venkat
CC BY-SA 3.0
2014-03-03T03:46:07.030Z
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
CC BY-SA 3.0
2014-03-03T19:11:19.120Z
@SureshVenkat: That sounds easier said than done (at least to me). Could you please demonstrate this on say, a 4x4 matrix?
Farnak
<cc.complexity-theory><algebraic-complexity><permanent><determinant>
Expressing Determinant as Permanent
Farnak
# Expressing Determinant as Permanent

(Asked by: username_0 on 2014-03-03)

One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper [Determinant Versus Permanent](http://www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf) 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?

**Tags:** cc.complexity-theory, algebraic-complexity, permanent, determinant
> **Comments:**
> **username_1**: Note that he says $x_{ij} s$, not $x_{ij}$.  $s = \pm 1$ provides the necessary signs.  
> **username_2**: @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.  
> **username_1**: Well, that would mean it's both grammatically inconsistent and wrong.  Your interpretation of the world sounds less nice than mine. :)  
> **username_3**: I think @usul is correct. he's using the 's' as a plural (i.e *many* $x_{ij}$).  
> **username_3**: 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.  
> **username_0**: @SureshVenkat: That sounds easier said than done (at least to me). Could you please demonstrate this on say, a 4x4 matrix?  

---

## 1 answers

### Answer by username_4 on 2014-03-03. Score: 8 | Accepted answer

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](http://eccc.hpi-web.de/search/?search=algebraic+branching+program) (and I think this is currently the best known). See the comments on [this answer](https://cstheory.stackexchange.com/a/16477/129).

> **Comments:**
> **username_3**: What's an ABP ?  
> **username_4**: @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.  

---

