<p><strong>[EDIT]</strong></p>

<ol>
<li>For consistency, I switched the notations from $c(n)$ to $dc(n)$.</li>
<li>It was asked by <a href="https://cstheory.stackexchange.com/users/5511/v-s">v s</a> in the comments whether my answer generalize to higher dimensions. It does and gives an upper bound over any field:
$$dc(n)\le 2^n-1.$$
See my draft on this: <a href="http://perso.ens-lyon.fr/bruno.grenet/publis/UpperBound.pdf" rel="nofollow noreferrer">An Upper Bound for the Permanent versus Determinant Problem</a>.</li>
</ol>

<p><strong>[/EDIT]</strong> </p>

<p>[A side comment: I think you could edit your previous question instead of creating a new one.]</p>

<p>I have the following answer for you: </p>

<p>$$\operatorname{per}\begin{pmatrix} a&amp;b&amp;c\\d&amp;e&amp;f\\g&amp;h&amp;i\end{pmatrix}=
    \det\begin{pmatrix}
    0 &amp; a &amp; d &amp; g &amp; 0 &amp; 0 &amp; 0 \\
    0 &amp; 1 &amp; 0 &amp; 0 &amp; i &amp; f &amp; 0 \\
    0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; c &amp; i \\
    0 &amp; 0 &amp; 0 &amp; 1 &amp; c &amp; 0 &amp; f \\
    e &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
    h &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
    b &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1
    \end{pmatrix}$$</p>

<p>Note that looking for such references about explicit examples, I could'nt find any and thus the example I give you is an example I built.</p>

<p>This question you are asking is commonly called the "Permanent vs Determinant problem". Suppose we are given an $(n\times n)$ matrix $A$, and we want the smallest matrix $B$ such that $\operatorname{per} A=\det B$. Let us denote by $dc(n)$ the dimensions of the smallest such $B$. Here are historical results:</p>

<ul>
<li>[Szegö 1913] $dc(n)\ge n+1$ </li>
<li>[von zur Gathen 1986] $dc(n)\ge n\sqrt 2-6\sqrt n$</li>
<li>[Cai 1990] $dc(n)\ge n\sqrt 2$</li>
<li>[Mignon &amp; Ressayre 2004] $dc(n)\ge n^2/2$ in characteristic $0$</li>
<li>[Cai, Chen &amp; Li 2008] $dc(n)\ge n^2/2$ in characteristic $\neq 2$.</li>
</ul>

<p>This shows that $5\le dc(3)\le 7$ (the upper bound is the matrix given above). </p>

<p>As I am lazy, I just give you one reference where you can find the other ones. It is the most recent paper I cited, by Cai, Chen and Li: <a href="http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf" rel="nofollow noreferrer" title="PDF file">A quadratic lower bound for the permanent and determinant problem over any characteristic $\neq 2$</a>.</p>

<p>If you read French, you can also have a look to my slides on this subject: <a href="http://perso.ens-lyon.fr/bruno.grenet/publis/talk_ejc11.pdf" rel="nofollow noreferrer" title="PDF file">Permanent versus Déterminant</a>.</p>

CC BY-SA 3.0
2011-06-08T21:53:32.343Z
Thankyou very much. I forgot to mention that I was familiar with the linear and quadratic lower bounds. Your example is new to me and ofcourse I will look at your French Slides:)
v s
CC BY-SA 3.0
2011-06-08T21:54:13.480Z
One followup question would be what is the motivation behind your example? Does the general structure generalize to larger matrices?
v s
CC BY-SA 3.0
2011-06-08T22:00:29.160Z
I really doubt the lower bound of $5$ is achievable.
v s
CC BY-SA 3.0
2011-06-08T22:03:13.480Z
I am also very positive that $c(3) = 6$.
v s
CC BY-SA 3.0
2011-06-08T22:10:19.190Z
There is no particular motivation: I just wanted to show an example in my slides explaining this problem to a general audience of PhD students in TCS.
Bruno
CC BY-SA 3.0
2011-06-08T22:12:54.713Z
I looked your slide. I am afraid I don't get the circuit bounds but I am familiar with the other results your have mentioned except your example. One question would be is it even known: $dc(n) < n!$?
v s
CC BY-SA 3.0
2011-06-08T22:15:31.623Z
If you know an example where $c(n) = dc(n) < n!$ please let me know. $c(n)$ is the notation to your above answer and $dc(n)$ is the notation in your French Slides. I think if one can get better than $n!$ for even a single $n \in Spec({\mathbb{Z}})$, something much better can be done for all $n \in Spec({\mathbb{Z}})$!
v s
CC BY-SA 3.0
2011-06-09T19:16:04.130Z
You are right, I used once $c(n)$ and once $dc(n)$, sorry for that! 
For your question, does'nt Ryser's or Glynn's formula answer? Both are formulas of size $O(n2^n)$ for the permanent. Thus, by Valiant's construction, you build a matrix of dimensions $O(n2^n)$ whose determinant equals the permanent of your original matrix. 
In other words, for any $n$, $c(n)\le O(n2^n)$.
Bruno
CC BY-SA 3.0
2011-06-09T23:23:17.493Z
@bruno Thank you. I just thought about it in the shower. May be I am missing something and have to modify my question. Anyways if one had to make a matrix from Ryser/glynns formula, how would one do that? I am interested more in their structures. What makes them special!!
v s
CC BY-SA 3.0
2011-06-09T23:57:43.127Z
I mean converting the formula into a determinant version - is it something canonical?
v s
CC BY-SA 3.0
2011-06-10T00:11:32.987Z
$O(n2^{n})$ at $n=3$ is $24$. But you just gave an explicit $7$ upper bound;)! (one is asymptotic and the other is just at $3$.... but in any case is your example better than Ryser's?)
v s
CC BY-SA 3.0
2011-06-10T15:19:36.600Z
To convert a formula into a determinant, it is a (classical ?) result by Valiant in 1979. We explain this result in our paper in Section 2.1 (cf [http://arxiv.org/abs/1007.3804]).
Bruno
CC BY-SA 3.0
2011-06-10T15:29:32.077Z
For $n=3$, note that there is a constant in O(n2^n) so that 24 is not the right value. Yet I think that my example is better than simply applying Ryser's formula + Valiant's construction. This is quite normal as one can imagine that going from the permanent to a formula and then back to a determinant is not the best way to do. 
I wouldn't say my example is "better than Ryser's" as the goals are not the same. Note also that Glynn'sor Ryser's formulas are not as good as the trivial formula for $n=3$, they beat it asymptotically only.
Bruno
CC BY-SA 3.0
2011-06-11T14:52:02.860Z
@Bruno, I switch the positions of A and B in the second paragraph. Does the modification make sense?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-12T05:31:30.683Z
@Hsien-Chih, you're right!
Bruno
CC BY-SA 3.0
2011-06-15T16:12:11.037Z
I had a new look at J-Y Cai's paper. Theorem 3 gives a better bound: $c(n)\le O(2^n)$.
Bruno
CC BY-SA 3.0
2011-07-13T02:58:23.727Z
@Bruno: excellent answer!
Dai Le
CC BY-SA 3.0
2011-07-24T05:27:56.493Z
@Bruno In the example you have, $Per(A) = Det(B)$, is graph of $B$ planar? You dont seem to use planarity. People usually want to have $B$ as a planar matrix and use sign changes to find orientation whose determinant would provide permanent. You don't seem to use that.
v s
CC BY-SA 3.0
2011-07-29T08:59:44.397Z
I do not use planarity at all. I think (even though I did not check it carefully) you can find a minor isomorphic to $K_{3,3}$ pretty easily.
There exist widgets sometimes to make a graph planar that could maybe work here.
Bruno
CC BY-SA 3.0
2017-08-14T02:10:01.860Z
@v s A subsequent [paper](https://arxiv.org/abs/1505.02205) by Alper, Bogart and Velasco shows that $c(3)=dc(3)=7$.
Ronald Monson
CC BY-SA 3.0
2011-06-08T21:06:13.597Z
2011-07-13T23:05:42.123Z
2017-04-13T12:32:28.053Z
Bruno
<p>Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known such that $\operatorname{per}(A) = \det(B)$? Any references on this with explicit examples?</p>

<p>Some restrictions could be the following cases:</p>

<p>Case $(1)$ Only linear functionals are allowed as entries of $B$.</p>

<p>Case $(2)$ Non-linear functionals are allowed provided each term has atmost $O(log(n))$ degree (degree is sum of degree of variables) where $n$ is the size of the matrix involved. In our case, upto degree $2$.</p>

CC BY-SA 3.0
2011-06-08T20:21:06.920Z
@v s What are the restrictions on $B$? If there are none, then $$B = \begin{pmatrix} \operatorname{per}(A)\end{pmatrix}$$ is a $1 \times 1$ matrix with $\det(B) = \operatorname{per}(A)$, but I am guessing that that is not what you had in mind. [Typically one allows](http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf) the entries of $B$ to be affine linear functions of the variables in $A$.
Tyson Williams
<cc.complexity-theory><algebraic-complexity><permanent>
Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants
v s
# Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants

(Asked by: username_0 on 2011-06-08)

Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a\_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known such that $\operatorname{per}(A) = \det(B)$? Any references on this with explicit examples?

Some restrictions could be the following cases:

Case $(1)$ Only linear functionals are allowed as entries of $B$.

Case $(2)$ Non-linear functionals are allowed provided each term has atmost $O(log(n))$ degree (degree is sum of degree of variables) where $n$ is the size of the matrix involved. In our case, upto degree $2$.

**Tags:** cc.complexity-theory, algebraic-complexity, permanent
> **Comments:**
> **username_1**: @v s What are the restrictions on $B$? If there are none, then $$B = \begin{pmatrix} \operatorname{per}(A)\end{pmatrix}$$ is a $1 \times 1$ matrix with $\det(B) = \operatorname{per}(A)$, but I am guessing that that is not what you had in mind. [Typically one allows](http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf) the entries of $B$ to be affine linear functions of the variables in $A$.  

---

## 1 answers

### Answer by username_2 on 2011-06-08. Score: 18 | Accepted answer

**[EDIT]**

1. For consistency, I switched the notations from $c(n)$ to $dc(n)$.
2. It was asked by [v s](https://cstheory.stackexchange.com/users/5511/v-s) in the comments whether my answer generalize to higher dimensions. It does and gives an upper bound over any field:
   $$dc(n)\le 2^n-1.$$
   See my draft on this: [An Upper Bound for the Permanent versus Determinant Problem](http://perso.ens-lyon.fr/bruno.grenet/publis/UpperBound.pdf).

**[/EDIT]**

[A side comment: I think you could edit your previous question instead of creating a new one.]

I have the following answer for you:

$$\operatorname{per}\begin{pmatrix} a&b&c\\d&e&f\\g&h&i\end{pmatrix}=
\det\begin{pmatrix}
0 & a & d & g & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & i & f & 0 \\
0 & 0 & 1 & 0 & 0 & c & i \\
0 & 0 & 0 & 1 & c & 0 & f \\
e & 0 & 0 & 0 & 1 & 0 & 0 \\
h & 0 & 0 & 0 & 0 & 1 & 0 \\
b & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}$$

Note that looking for such references about explicit examples, I could'nt find any and thus the example I give you is an example I built.

This question you are asking is commonly called the "Permanent vs Determinant problem". Suppose we are given an $(n\times n)$ matrix $A$, and we want the smallest matrix $B$ such that $\operatorname{per} A=\det B$. Let us denote by $dc(n)$ the dimensions of the smallest such $B$. Here are historical results:

* [Szegö 1913] $dc(n)\ge n+1$
* [von zur Gathen 1986] $dc(n)\ge n\sqrt 2-6\sqrt n$
* [Cai 1990] $dc(n)\ge n\sqrt 2$
* [Mignon & Ressayre 2004] $dc(n)\ge n^2/2$ in characteristic $0$
* [Cai, Chen & Li 2008] $dc(n)\ge n^2/2$ in characteristic $\neq 2$.

This shows that $5\le dc(3)\le 7$ (the upper bound is the matrix given above).

As I am lazy, I just give you one reference where you can find the other ones. It is the most recent paper I cited, by Cai, Chen and Li: [A quadratic lower bound for the permanent and determinant problem over any characteristic $\neq 2$](http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf "PDF file").

If you read French, you can also have a look to my slides on this subject: [Permanent versus Déterminant](http://perso.ens-lyon.fr/bruno.grenet/publis/talk_ejc11.pdf "PDF file").

> **Comments:**
> **username_0**: Thankyou very much. I forgot to mention that I was familiar with the linear and quadratic lower bounds. Your example is new to me and ofcourse I will look at your French Slides:)  
> **username_0**: One followup question would be what is the motivation behind your example? Does the general structure generalize to larger matrices?  
> **username_0**: I really doubt the lower bound of $5$ is achievable.  
> **username_0**: I am also very positive that $c(3) = 6$.  
> **username_2**: There is no particular motivation: I just wanted to show an example in my slides explaining this problem to a general audience of PhD students in TCS.  
> **username_0**: I looked your slide. I am afraid I don't get the circuit bounds but I am familiar with the other results your have mentioned except your example. One question would be is it even known: $dc(n) < n!$?  
> **username_0**: If you know an example where $c(n) = dc(n) < n!$ please let me know. $c(n)$ is the notation to your above answer and $dc(n)$ is the notation in your French Slides. I think if one can get better than $n!$ for even a single $n \in Spec({\mathbb{Z}})$, something much better can be done for all $n \in Spec({\mathbb{Z}})$!  
> **username_2**: You are right, I used once $c(n)$ and once $dc(n)$, sorry for that!  For your question, does'nt Ryser's or Glynn's formula answer? Both are formulas of size $O(n2^n)$ for the permanent. Thus, by Valiant's construction, you build a matrix of dimensions $O(n2^n)$ whose determinant equals the permanent of your original matrix.  In other words, for any $n$, $c(n)\le O(n2^n)$.  
> **username_0**: @bruno Thank you. I just thought about it in the shower. May be I am missing something and have to modify my question. Anyways if one had to make a matrix from Ryser/glynns formula, how would one do that? I am interested more in their structures. What makes them special!!  
> **username_0**: I mean converting the formula into a determinant version - is it something canonical?  
> **username_0**: $O(n2^{n})$ at $n=3$ is $24$. But you just gave an explicit $7$ upper bound;)! (one is asymptotic and the other is just at $3$.... but in any case is your example better than Ryser's?)  
> **username_2**: To convert a formula into a determinant, it is a (classical ?) result by Valiant in 1979. We explain this result in our paper in Section 2.1 (cf [http://arxiv.org/abs/1007.3804]).  
> **username_2**: For $n=3$, note that there is a constant in O(n2^n) so that 24 is not the right value. Yet I think that my example is better than simply applying Ryser's formula + Valiant's construction. This is quite normal as one can imagine that going from the permanent to a formula and then back to a determinant is not the best way to do.  I wouldn't say my example is "better than Ryser's" as the goals are not the same. Note also that Glynn'sor Ryser's formulas are not as good as the trivial formula for $n=3$, they beat it asymptotically only.  
> **username_3**: @Bruno, I switch the positions of A and B in the second paragraph. Does the modification make sense?  
> **username_2**: @Hsien-Chih, you're right!  
> **username_2**: I had a new look at J-Y Cai's paper. Theorem 3 gives a better bound: $c(n)\le O(2^n)$.  
> **username_4**: @Bruno: excellent answer!  
> **username_0**: @Bruno In the example you have, $Per(A) = Det(B)$, is graph of $B$ planar? You dont seem to use planarity. People usually want to have $B$ as a planar matrix and use sign changes to find orientation whose determinant would provide permanent. You don't seem to use that.  
> **username_2**: I do not use planarity at all. I think (even though I did not check it carefully) you can find a minor isomorphic to $K_{3,3}$ pretty easily. There exist widgets sometimes to make a graph planar that could maybe work here.  
> **username_5**: @v s A subsequent [paper](https://arxiv.org/abs/1505.02205) by Alper, Bogart and Velasco shows that $c(3)=dc(3)=7$.  

---

