# Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$

For each #$$k$$SAT instance one can build a matrix $$A$$ such that $$\mathrm{perm}(A) = F(\Sigma)$$, where $$\Sigma$$ is the solution count of the $$k$$SAT formula and $$F$$ an easy to invert function.

My question is whether there is a similar reduction in the opposite direction: given an integer valued matrix $$A$$ with $$\mathrm{perm}(A)>0$$, is there a systematic way to build a #$$k$$SAT formula such that $$\Sigma=F(\mathrm{perm}(A))$$, where $$F$$ an easy to invert function?

• If the entries of $A$ are nonnegative, then yes, just because #kSAT is #P-complete and perm of nonnegative integer matrices is in #P. If you allow negative entries, this seems closely related to GapP vs #P. – Joshua Grochow May 18 at 3:16
• @JoshuaGrochow What if I have negative entries but I am somehow guaranteed that $\mathrm{perm}(A)>0$? Also, how does the reduction in the case of only nonnegative entries? – delete000 May 18 at 12:36