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
    Feb 15 '17 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$ Feb 15 '17 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
    Feb 15 '17 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
    Feb 15 '17 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$ 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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