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$.
Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants
cc.complexity theory;algebraic complexity;permanent
[EDIT]For consistency, I switched the notations from $c(n)$ to $dc(n)$.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 Dterminant.