An approximation method for the permanent of matrices with few negative entries

Subrahmanyam Kalyanasundaram—Subruk—is one of my wonderful current graduate students at Georgia Tech. He is working mostly in the area of computational complexity; for example, he is working on a draft of the promised paper on a faster method for the simulation of nondeterministic Turing machines.

One of the great things about Subruk is that he is the reason that this blog does not have as many typos as it should. He makes the last pass, usually, on each post, and finds all the tiny bugs that I have missed. Actually, he does much more: he often finds the not so tiny bugs that I have missed.

Today I want to give a short post on a problem that I raised a bit ago. It has to do with the approximation of the permanent of a matrix with negative entries. I think that Subruk has found an interesting path that could solve the problem.

Another reason to make this a shorter post than usual, is that I have been out of pocket for the last few days—a visit from my daughter and her family. So I hope that you understand if this post is a bit short.

Mostly it is a report on the work that Subruk has done on the problem, as mentioned in one of the previous posts, is to try and extend Mark Jerrum, Alistair Sinclair and Eric Vigoda’s (JSV) theorem on approximating the permanent of non-negative matrices, to matrices with negative entries.

Suppose ${A}$ is a matrix with negative entries. Recall JSV allows us to compute the permanent of a non negative matrix within a factor of ${(1 + 1/n^c)}$ for a constant ${c}$. But, unless the permanent can be exactly computed in polynomial time, one cannot hope to approximately compute the permanent of a matrix with even one negative entry. So in order to prove any approximation with negative entries, we need a further restriction on the entries.

The new idea here is to break down ${A}$ into a number of non negative matrices, such that the permanent of ${A}$ is the sum/difference of the permanents of these matrices. This method used here is related directly to Herbert Ryser method for the evaluation of the permanent.

One Negative Entry

Let us first consider the case where the matrix ${A}$ has exactly one negative entry. We shall use ${\mathsf{perm}(A)}$ to denote the permanent of the matrix ${A}$. For the sake of simplicity of the argument, let us assume that the negative entry is ${-1}$. Since the value of the permanent is independent of the order of rows and columns, we can assume, without loss of generality, that the ${-1}$ is the first entry—in the first row and first column of ${A}$.

That is

$\displaystyle A = \begin{pmatrix} -1 & * & * & \ldots \\ * & * & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

where each ${*}$ denotes a non negative entry of the matrix.

We can write the permanent of ${A}$ as a difference of permanents as follows. ${ \mathsf{perm}(A) = \mathsf{perm}(A_1) - \mathsf{perm}(B_1)}$ where ${A_1}$ and ${B_1}$ are as shown below.

$\displaystyle A_1 = \begin{pmatrix} 0 & * & * & \ldots \\ * & * & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \;\; B_1 = \begin{pmatrix} 1 & 0 & 0 & \ldots \\ * & * & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

Here ${A_1}$ is the same as ${A}$ but has the ${-1}$ replaced with 0. ${B_1}$ is the same as ${A}$ but for the first row. The ${-1}$ remains intact, but the rest of the row is replaced with 0’s. But note that both ${A_1}$ and ${B_1}$ are matrices with only nonnegative entries.

JSV can help us determine the values ${ \mathsf{perm}(A_1), \mathsf{perm}(B_1)}$ up to a factor ${(1 + 1/n^c)}$. So we can determine ${ \mathsf{perm}(A)}$ to a multiplicative factor, as long as the values ${ \mathsf{perm}(A_1)}$ and ${ \mathsf{perm}(B_1)}$ are not close enough. This is the condition that we require.

Theorem: The permanent of a matrix ${A}$, with exactly one negative entry, can be computed up to a factor ${(1 + 1/n^c)}$, in polynomial time, provided ${| \mathsf{perm}(A_1) - \mathsf{perm}(B_1)| \geq \Omega( \mathsf{perm}(B_1))}$.

Now, we shall show that the stability condition that we defined last time is related to this. Let us recall the condition. Let ${A^{(t)}}$ be the matrix where we replace the ${-1}$ in ${A}$ with ${t}$. The stability condition was that ${A}$ is stable provided

$\displaystyle \left | \mathsf{perm}(A) - \mathsf{perm}(A^{(-1+\delta)}) \right | \le O(\mathsf{perm}(A))$

for ${\delta}$ small enough.

In terms of the matrices ${A_1}$ and ${B_1}$, the above stability condition reduces to

$\displaystyle \left |\delta \cdot \mathsf{perm}(B_1) \right| \le O\left( \left | \mathsf{perm}(A_1) - \mathsf{perm}(B_1) \right | \right)$

This is the same as

$\displaystyle \Omega (\mathsf{perm}(B_1)) \le \left | \mathsf{perm}(A_1) - \mathsf{perm}(B_1) \right |$

which is the condition that we have on the above theorem. So we can restate the above theorem as,

Theorem: The permanent of a matrix ${A}$, with exactly one negative entry, can be computed up to a factor ${(1 + 1/n^c)}$, in polynomial time, provided that the stability condition is met.

Multiple Negative Entries

This can be done when the matrix has two ${-1}$ entries as well. If the two ${-1}$‘s are in the same row or column, we could take care of them using just two matrices as before. If the two ${-1}$‘s are in different rows and columns, we can permute the rows and columns to get

$\displaystyle A = \begin{pmatrix} -1 & * & * & \ldots \\ * & -1 & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

We can define

$\displaystyle A_1 = \begin{pmatrix} 1 & 0 & 0 & \ldots \\ 0 & 1 & 0 & \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \;\; B_1 = \begin{pmatrix} 0 & * & * & \ldots \\ 0 & 1 & 0 & \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

$\displaystyle A_2 = \begin{pmatrix} 0 & * & * & \ldots \\ * & 0 & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \;\; B_2 = \begin{pmatrix} 1 & 0 & 0 & \ldots \\ * & 0 & *& \ldots \\ * & * & * & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

As before, we get ${ \mathsf{perm}(A) = [ \mathsf{perm}(A_1) + \mathsf{perm}(A_2) ] - [ \mathsf{perm}(B_1) + \mathsf{perm}(B_2)]}$. Again we need a condition, that the two quantities ${ \mathsf{perm}(A_1) + \mathsf{perm}(A_2)}$ and ${ \mathsf{perm}(B_1) + \mathsf{perm}(B_2)}$ are not close to each other. That is,

$\displaystyle \left |( \mathsf{perm}(A_1) + \mathsf{perm}(A_2)) - ( \mathsf{perm}(B_1) + \mathsf{perm}(B_2)) \right | \geq \Omega\left( \mathsf{perm}(B_1) + \mathsf{perm}(B_2)\right)$

We could extend this argument to the case where there are ${k}$ negative entries. In that case, we could write ${ \mathsf{perm}(A) = \sum_i \mathsf{perm}(A_i) - \sum_i \mathsf{perm}(B_i)}$, where each summation contains ${2^{k-1}}$ terms. So we need a total of ${2^k}$ permanent computations by the JSV method. We need a condition similar to last time, that is

$\displaystyle \left|\sum_i \mathsf{perm}(A_i) - \sum_i \mathsf{perm}(B_i) \right| \geq \Omega \left(\sum_i \mathsf{perm}(B_i)\right)$

So we can conclude the following theorem.

Theorem: We can compute the permanent of a matrix ${A}$ with ${O(\log n)}$ negative entries, in polynomial time, up to a factor of ${(1 + 1/n^c)}$, as long as the above condition is met.

Open Problems

Can we do better than ${O(\log n)}$ negative entries? Also, we need to complete the case of multiple entries. Right now, we have a condition for which the permanent can be computed. But it is not clear how this condition is connected to the stability condition of the previous post. Can we define the stability condition appropriately, so that it reduces to the condition given here?

September 10, 2009 9:16 am

In the inequality for the condition of approximating the permanent, there is a constant which looks like the greek omega.
Please can you explain the role that omega has in this discussion?

September 10, 2009 2:26 pm

It is a kind of inverse to the big O notation. If f(n)=O(g(n)) then f(n) is bounded by a constant*g(n) as n grows. The Omega notation f(n) = Omega(g(n)) means that f(n) is lower bounded by a constant*g(n) where the constant is positive.

I hope that helps. Look at this for more details.

September 14, 2009 4:12 am

Hi, I believe that there is a error in your blog.

At the line:
We can write the permanent of as a difference of permanents as follows
Perm(A) = Perm(A1) – Perm(B1)

Your description of Matrix B1 I believe is incorrect.

B1 should be:
|1000000… |
|0*******…. |
|0*******…. |
|0…. |
|0…. |
|0**********|

Notice the zeros in the first row and column
this is just classical Laplace expansion

Finally, I have a criticism of your Stable Permanent Conjecture. What stops one utilising simple row and column multiplication (multiplication factor Polynomially Bounded of course) to make ANY matrix with one negative value Stable? Of course when you have calculated the permanent by bisection iteration you put back in the multiplication factors!

Zelah