9
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ @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$. $\endgroup$ Jun 8, 2011 at 20:21

1 Answer 1

18
$\begingroup$

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

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

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.