# Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants

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$.

• @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 the entries of $B$ to be affine linear functions of the variables in $A$. – Tyson Williams Jun 8 '11 at 20:21

[EDIT]

1. For consistency, I switched the notations from $c(n)$ to $dc(n)$.
2. It was asked by 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.

[/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$.

If you read French, you can also have a look to my slides on this subject: Permanent versus Déterminant.

• 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 Jun 8 '11 at 21:53
• 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 [arxiv.org/abs/1007.3804]). – Bruno Jun 10 '11 at 15:19
• 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 Jun 10 '11 at 15:29
• I had a new look at J-Y Cai's paper. Theorem 3 gives a better bound: $c(n)\le O(2^n)$. – Bruno Jun 15 '11 at 16:12
• @Bruno: excellent answer! – Dai Le Jul 13 '11 at 2:58