5
$\begingroup$

I am looking for explicit examples where permanent of a given matrix $A$ is given by a determinant of a larger matrix $B$ (projection in the sense of Valiant). Is there any reference where I can find such an example for $n \times n$ matrix $A$ for say $n \le 5$.

Also are there examples where permanent of a given matrix $A$ is given by permanent of a larger matrix $A$? Again any explicit example for $n \times n$ matrix $A$ for say $n \le 5$ would help.

$\endgroup$
  • 1
    $\begingroup$ For the second question, doesn't adding a diagonal of 1s to the matrix work? $\begin{array}{} A & 0 \\ 0 & I \\ \end{array} $ $\endgroup$ – Kaveh Jun 8 '11 at 3:06
  • $\begingroup$ good point.... I was thinking may be something nontrivial might be known. $\endgroup$ – v s Jun 8 '11 at 3:54
4
$\begingroup$

A way to have such an explicit example is the following: Consider a matrix $A$ full of indeterminates (you can specialize the entries if you wish). Then use some formula for the permanent of this matrix (Ryser's or Glynn's for example). From this formula, you can build another matrix $B$, of quite huge dimensions, whose determinant equals the formula, thus the permanent of $A$.

Another thing you can do is to consider a matrix A whose determinant and permanent are the same (adjacency matrix of a graph whose cycles are of odd length). Then you can use different constructions to build a new matrix B with the same determinant. For instance, in our paper Symmetric Determinantal Representation of Formulas and Weakly-Skew Circuits, we give an algorithm that given a matrix $A$ builds a symmetric matrix $B$ such that $\det A=\det B$ (Section 3.2).

You can have a look at our paper for the classical techniques to do what you want (if I am not mistaken). For the second part, it is easy to change the constructions giving a matrix $B$ whose determinant equals some other determinant or formula, in such a way that you obtain another matrix $C$ such that $\operatorname{per} C=\det B$.

A last word to be more explicit:

$$\operatorname{per}\begin{pmatrix} x&y\\ 1&1\end{pmatrix} = \det\begin{pmatrix} x&0&0&1 \\ 0&y&0&1 \\ 0&0&1&0 \\ 1&1&0&0\end{pmatrix}$$

I hope this helps, even though I am not quite sure to exactly understand what you mean by "explicit example". If you are looking for an explicit example where for some $(n\times n)$ matrix $A$, the smallest matrix $B$ such that $\operatorname{per} A=\det B$ has dimensions $>n$, then you should look at Mignon & Ressayre's paper "A quadratic bound for the determinant and permanent problem" or subsequent works by Jin-Yi Cai and coauthors.

$\endgroup$
  • $\begingroup$ Thank you. Glancing at "Symmetric Determinantal ...." and corroborating with what you have wrote here, if I understand, given $A$ you find a polynomial sized $C$ such that $per(C) = det(A)$ which is somewhat like a converse to the real problem which is given $C$ provide a polynomial sized $A$ such that $det(A) = per(C)$.How about given: $Csm$ is $n \times n$ with entries $1,2,3,\cdots,n^{2}$, is there a 'non-trivial' polynomial size $Cbg$ so that $per(Csm)=per(Cbg)$? One example of'trivial' is Kaveh's $Cbg =[I 0;0 Csm;]$ - $I$ is $n \times n$ identity, $0$ is $n \times n$ zero matrix. $\endgroup$ – v s Jun 8 '11 at 17:31
  • $\begingroup$ Using the classical results or our results can help, but I am not aware of any specific result of this kind. I should say I do not really understand where you wanna go with this problem of finding a larger matrix with the same permanent. It seems very artificial for me. Your other question about Perm vs Det is much clearer to me... $\endgroup$ – Bruno Jun 8 '11 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.