# Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

Consider the following problem: given a matrix $M\in\{-m,\dots,0,\dots,m\}^{n\times n}$, indices $i,j\in\{1,\dots,n\}$ and an integer $a$. Replace $M[i,j]$ by $a$ and call new matrix $\hat M$. Is $per(M)>per(\hat M)$?

Is this problem in the polynomial hierarchy?

• It can be solved by two calls to a #P oracle... If it was in PH, then it would imply that PP is also in PH... However, if PP is in PH, then PH collapses. So I think it is unlikely that it is in PH. – Tayfun Pay Feb 15 '17 at 5:35
• @TayfunPay I don't think that argument is correct. The problem can be solved with 2 calls to #P, but it cannot be ruled out so easily that there's a simpler algorithm that might show it's in PH. You'd have to show it's hard for #P for that, e.g. by reducing Permanent to it. – Jan Johannsen Feb 15 '17 at 9:08
• If you plug in the definition of the permanent and simplify the resulting inequality, your problem boils down to the question whether the permanent of a given (n-1)-by-(n-1) matrix is strictly positive. – Gamow Feb 15 '17 at 9:10
• @Gamow, and the other way around, ie deciding if $PER(M) > 0$ can be reduced to this problem. Given a matrix $M$, construct $M'$ by adding a line on top and a column on the left with a 1 in the top-left corner and 0 otherwise. Now let $M''$ be the matrix $M'$ where the top left entry has been replaced by $-1$. Then $PER(M'') = -PER(M') = -PER(M)$ by multilinearity and developing the first column. Thus $PER(M) > 0$ iff the problem of Turbo on $M'$, $(i,j) = (0,0)$ and $a = -1$ returns true. – holf Feb 15 '17 at 12:39
• @holf: I think you should post this as an answer. It pretty definitively answers the question, and then the question won't appear as "unanswered" any more. – Joshua Grochow Sep 30 '18 at 16:57

Your problem is equivalent to testing, given $$M$$, whether $$PER(M) > 0$$.
Proof: Assume you are given $$M$$ and you want to decide whether $$PER(M) > 0$$. We construct $$M'$$ as follows: $$\begin{bmatrix} 1 & 0 & \dots & 0 \\ 0 & & & & \\ \dots & & M & &\\ 0 & & & & \end{bmatrix}$$ It is easy to see that $$PER(M) = PER(M')$$. Now, define $$\hat{M'}$$ to be $$M'$$ where we replace the $$(0,0)$$ entry of $$M'$$ by $$-1$$. By multilinearity, it follows that $$PER(M) = PER(M') = -PER(\hat{M'})$$. Thus $$PER(M) > 0$$ if and only if $$PER(M') > PER(\hat{M'})$$.
Now assume you are given $$M$$, $$(i,j)$$ and $$a$$ and define $$\hat{M}$$ as in your question, that is, by changing $$M[i,j]$$ to $$a$$. We have \begin{align} PER(M) > & PER(\hat{M}) \text{ iff} \\ \sum_{\sigma} \prod_{k=1}^n M[k,\sigma(k)] > &\sum_{\sigma} \prod_{k=1}^n \hat{M}[k,\sigma(k)] \text{ iff} \\ \sum_{\sigma, \sigma(i)=j} M[i,j] \prod_{k \neq i}^n M[k,\sigma(k)] > &\sum_{\sigma, \sigma(i)=j} a \prod_{k \neq i}^n M[k,\sigma(k)] \text{ iff}\\ (M[i,j]-a) \cdot \sum_{\sigma, \sigma(i)=j} \prod_{k \neq i}^n M[k,\sigma(k)] > & 0 \text{ iff}\\ (M[i,j]-a) \cdot PER(M') > 0 \end{align}
where $$M'$$ is the $$(n-1) \times (n-1)$$ matrix obtained from $$M$$ by removing line $$i$$ and column $$j$$. $$\square$$