Skip to content

The Permanent of Stable Matrices with Few Negative Entries

September 9, 2009


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

images

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?

About these ads
4 Comments leave one →
  1. Zelah permalink
    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?

    Thankyou in advance

    • rjlipton permalink*
      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.

  2. Zelah permalink
    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

    • subruk permalink
      September 14, 2009 10:52 am

      Thanks for your comment. The entries below the first entry (the 1) does not matter in the permanent computation, since the first row is all 0′s otherwise. So it does not matter if they are 0′s or the original entries. The version in the blog is not an error. The expansion is close to the standard Laplace expansion, but we decompose to only 2 terms per row/column. If there were three -1′s in the row, I would still use only 2 terms.

      But when we have arbitrary negative entries, when the entries are not all equal to each other, we would have to use one split for each negative entry. In that sense, this is not desirable.

      Finally, it is a nice trick to multiply the row/column by a constant. But I don’t see how the permanent becomes stable/unstable by multiplying a row/column by a factor. This should multiply all the terms in the expansion by the same constant, so I don’t think the stability condition changes by this trick.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,245 other followers