<p>Your problem is equivalent to testing, given <span class="math-container">$M$</span>, whether <span class="math-container">$PER(M) &gt; 0$</span>.</p>

<p><strong>Proof</strong>: Assume you are given <span class="math-container">$M$</span> and you want to decide whether <span class="math-container">$PER(M) &gt; 0$</span>. We construct <span class="math-container">$M'$</span> as follows:
<span class="math-container">\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}</span>
It is easy to see that <span class="math-container">$PER(M) = PER(M')$</span>. Now, define <span class="math-container">$\hat{M'}$</span> to be <span class="math-container">$M'$</span> where we replace the <span class="math-container">$(0,0)$</span> entry of <span class="math-container">$M'$</span> by <span class="math-container">$-1$</span>. By multilinearity, it follows that <span class="math-container">$PER(M) = PER(M') = -PER(\hat{M'})$</span>. Thus <span class="math-container">$PER(M) &gt; 0$</span> if and only if <span class="math-container">$PER(M') &gt; PER(\hat{M'})$</span>.</p>

<p>Now assume you are given <span class="math-container">$M$</span>, <span class="math-container">$(i,j)$</span> and <span class="math-container">$a$</span> and define <span class="math-container">$\hat{M}$</span> as in your question, that is, by changing <span class="math-container">$M[i,j]$</span> to <span class="math-container">$a$</span>. We have
<span class="math-container">\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}</span></p>

<p>where <span class="math-container">$M'$</span> is the <span class="math-container">$(n-1) \times (n-1)$</span> matrix obtained from <span class="math-container">$M$</span> by removing line <span class="math-container">$i$</span> and column <span class="math-container">$j$</span>. <span class="math-container">$\square$</span></p>

CC BY-SA 4.0
2018-10-06T01:15:20.570Z
Good answer, but it’s probably worth explicitly stating the answer to the OP’s question as well.
Stella Biderman
CC BY-SA 4.0
2018-10-02T09:54:17.017Z
2018-10-02T10:34:28.403Z
2018-10-02T10:34:28.403Z
holf
<p>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)$?</p>

<p>Is this problem in the polynomial hierarchy?</p>

CC BY-SA 3.0
2017-02-15T05:35:13.393Z
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
CC BY-SA 3.0
2017-02-15T09:08:19.973Z
@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
CC BY-SA 3.0
2017-02-15T09:10:17.697Z
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
CC BY-SA 3.0
2017-02-15T12:39:46.887Z
@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
CC BY-SA 4.0
2018-09-30T16:57:06.337Z
@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
<permanent>
Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?
Turbo
# Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

(Asked by: username_0 on 2017-02-15)

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?

**Tags:** permanent
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_3**: 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.  
> **username_4**: @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.  
> **username_5**: @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.  

---

## 1 answers

### Answer by username_4 on 2018-10-02. Score: 10 | Accepted answer

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$

> **Comments:**
> **username_6**: Good answer, but it’s probably worth explicitly stating the answer to the OP’s question as well.  

---

