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?

  • 4
    $\begingroup$ 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. $\endgroup$
    – Tayfun Pay
    Commented Feb 15, 2017 at 5:35
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Feb 15, 2017 at 9:08
  • 8
    $\begingroup$ 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. $\endgroup$
    – Gamow
    Commented Feb 15, 2017 at 9:10
  • 2
    $\begingroup$ @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. $\endgroup$
    – holf
    Commented Feb 15, 2017 at 12:39
  • $\begingroup$ @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. $\endgroup$ Commented Sep 30, 2018 at 16:57

1 Answer 1


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$

  • $\begingroup$ Good answer, but it’s probably worth explicitly stating the answer to the OP’s question as well. $\endgroup$ Commented Oct 6, 2018 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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