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)&gt;per(\hat M)$?

Is this problem in the polynomial hierarchy?
Your problem is equivalent to testing, given $M$, whether $PER(M) &gt; 0$.

Proof: Assume you are given $M$ and you want to decide whether $PER(M) &gt; 0$. We construct $M'$ as follows:
\begin{bmatrix}
    1 &amp; 0 &amp; \dots &amp; 0 \\
    0 &amp; &amp; &amp; &amp; \\
    \dots &amp; &amp; M &amp; &amp;\\
    0 &amp; &amp; &amp; &amp;
\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) &gt; 0$ if and only if $PER(M') &gt; 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) &gt; &amp; PER(\hat{M}) \text{ iff} \\
\sum_{\sigma} \prod_{k=1}^n M[k,\sigma(k)] &gt; &amp;\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)] &gt; &amp;\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)] &gt; &amp; 0 \text{ iff}\\
(M[i,j]-a) \cdot PER(M') &gt; 0
\end{align}

where $M'$ is the $(n-1) \times (n-1)$ matrix obtained from $M$ by removing line $i$ and column $j$. $\square$