# Permanents of Matrices With Negative Coefficients?

* Can the permanent of stable negative matrices be approximated?*

Eric Vigoda is one of the top experts in the world in the area of Markov Chain Monte Carlo methods. He shared the prestigious Fulkerson Prize with Mark Jerrum and Alistair Sinclair for their brilliant work (JSV) on approximations to the permanent.

Today I would like to talk about JSV, and raise an open problem that I have thought about. The problem is an attempt to slightly generalize this famous theorem.

I have worked years ago on much more naive approaches to computing the permanent, than JSV’s approach. For example, with Narendra Karmarkar, Richard Karp, László Lovász, and Michael Luby we showed that a simple random algorithm could approximate the permanent, but unfortunately the variance of the method was in general exponential.

Eric is part of the theory group at Georgia Tech, and can always be counted on to add a wry comment to any discussion the group has. Yet I do not have any really cool stories about Eric. I could make one up, but so far all my stories are true. Well, what I mean exactly is that “I believe that all my stories are true.” This is an important difference: as I get older my memory for events could be wrong, but I can say that I think that all the stories that I have written are true.

Raymond Smullyan is a logician who has written many popular books on the theory of lying such as “What Is the Name of This Book?” His definition of lying is:

A person is lying if they say a statement that they

believeis false.

Smullyan says there was once this poor fellow who was locked up for decades in a psychiatric hospital because he was sure that he was Napoleon. Every few years there was a sanity hearing to determine if he could be released. Each time he failed the part of the hearing where they asked him various questions, while checking his veracity with a lie detector.

Finally at one hearing, they were giving him his lie detector test and asking him various questions, when they asked him, “do you think that you are Napoleon?” He answered “no.” But, the needle on the detector jumped: he was lying. This is Smullyan’s definition of lying: saying something you *know* is false. The poor fellow knew he really was Napoleon.

In Smullyan’s sense I am clear. Let’s turn to approximations of the permanent.

** Approximation of the Permanent **

The permanent of a square matrix of order is, of course, equal to

where the summation is over all permutations of .

Even though this looks similar to the determinant, the complexities of computing both could not be more different. While there is a polynomial time algorithm to compute the determinant, the computation of the permanent is P-complete. See here and here for more details. JSV’s great theorem is:

Theorem:For any , there is a random polynomial time algorithm that computes the to with a multiplicative factor of , provided is non-negative matrix.

I will not explain the proof or even sketch it—see their paper for the details. I will, however, point out that there is an amplifier lurking here too. If instead the theorem proved a multiplicative factor of , then that could easily be amplified to a multiplicative factor of for any .

The key is a simple repetition amplifier. Suppose that is given, then create the matrix ,

Then, note that , which implies that knowing to within a factor of implies an approximation to of at most . This can be done for more copies of , which yields the claim. I find it interesting how powerful even such trivial amplifiers are. Do you agree?

** Negative Entries are Hard **

JSV points out that even allowing *one* negative entry would make their approximation problem NP-hard. This is because the negative entry allows cancellation, which allows the encoding of SAT. The method they use, is clever, but simple. I have a rule:

“Beware of simple counterexamples.”

What I mean is that often a simple counterexample may be hiding a theorem—the theorem will require some additional restriction, but may still be quite interesting.

Here is a classic example of my rule: the polynomial equation shows that an equation can have less roots than its degree. This shows that the simple claim that a polynomial of degree has roots is *wrong*. But, there is a fix: if we count the roots properly, then we can restore the claim that a polynomial has roots.

I think that this type of behavior occurs throughout theory and mathematics. So if you see an almost trivial counterexample to something, stop and see if you can modify the theorem you are trying to prove. You may be pleasantly surprised.

I have decided to add this update:

Even allowing *one* negative entry would make the approximation problem equivalent to computing the permanent exactly.

The argument is simple: Let be a matrix and let be the matrix with the entry set to . Then, where is the sub-matrix that results after removing the first row and column from . An approximation method gives at least the sign of . Then, by binary search you can get the root of the equation . The permanent of itself follows from a recursion on this idea.

** Can Negative Entries be Easy? **

I think that we may be able to add negative entries to a matrix and still be able to compute an approximation to its permanent. This is in direct conflict with the fact that even one negative entry makes the problem NP-hard. Right. My idea is to add an extra condition to the matrix that will possibly allow the theorem to be true. Thus, our goal is to be able to prove:

“Theorem”:For any , there is a random polynomial time algorithm that computes the to with a multiplicative factor of , provided is a matrix with property .

The key is what is the property ? I have a suggestion—why else would I raise this anyway? Consider a matrix with exactly one entry that is negative and further assume that entry is . Call such a matrix a –*negative matrix*. A -negative matrix would have negative entries; a -negative matrix is a non-negative matrix.

Suppose that is a -negative matrix, and let . Define the matrix to be with the replaced by . Of course, .

The key property , I think, is this: Say that is *stable* provided

for small enough. The point is the permanent of the matrix does not change much as the value of is perturbed slightly.

I believe that there is a good approximation algorithm that will work for such stable matrices. This hunch is based on: intuition, the observation that JSV’s counterexample is not stable, and finally on a nice connection to extrapolation.

** Polynomial Extrapolation **

The main idea is really simple. Again let be a -non-negative stable matrix. Define, to be . Note, is a linear polynomial: the entry can only be used at most once in any term of the permanent.

We want the value of . However, using the JSV’s theorem we can get for any natural number to within a small error. Thus, we are faced with an extrapolation problem:

Can we compute with small error from good approximations to and and so on?

Since is stable there seems to be some hope that this problem can be solved. It is an extrapolation problem because the point we want is not in the interval of the points that we can evaluate.

** Open Problems **

The clear open problem is prove that a stable matrix with one negative entry has an approximation algorithm. Then, try to extend this to multiple negative entries. I really believe that this should be possible at least for a constant number of negative entries.

Another “meta” problem is: do matrices that arise in practice have the stability property? Or when do matrices have this property?

Here is an interesting paper that is related to the ideas here on stable. It’s by Yonatan Bilu and Nathan Linial, and is at http://www.cs.huji.ac.il/~nati/PAPERS/stable_instance.pdf

Why is it hopeless to have a poly-time approximation algorithm for matrices with negative elements? The fact that it is an NP-hard problem is not, by itself, a barrier…

I am confused. I was just saying that finding a polynomial time approximate to matrices with negative coefficients would show that P=NP. I added an update to the post that says the following:

Actually, they show even more. If you could approximate even one negative entry then you could

exactlyevaluate the permanent. The argument is simple: Let A be a matrix and let A(x) be the matrix with the (1,1) entry set to A(1,1)-x. Then, perm(A(x)) = perm(A)-xperm(B) where B is the sub-matrix that results after removing the first row and column from A. An approximation method given the sign at least of perm(A(x)). Then, by binary search you can get the root of the equation perm(A)-xperm(B)=0. The permanent of A itself follows from a recursion on this idea.Note, these matrices will not be stable in the sense that I use later on.

Read the seminal paper by Valiant. Exact calculation of the permanent would mean the exact calculation of the satisfying assignments of a 3CNF. Which actually would mean more than P = NP, it would imply that #P is in FP.

What is funny is the Karp-reduction from integer matrices to non-negative matrices and then 0-1 matrices. The reduction uses modulo prime number calculations, and it seems to be crucial: the relative error is not preserved during mod p calculations, and this is an explanation why there is an FPRAS for calculating the permanent of non-negative matrices while it is still #P-complete.

Does JSV’s theorem only work on 0-1 matrices? If not, isn’t B=kA (k>1) a much better amplifier, i.e. knowing an approximation to perm(B) within a factor of c will yield an approximation to perm(A) within a factor of c/(k^n).

Yes they can handle integers but the matrix size blows up with the size of the coefficients. I should have stated a more careful theorem. Thus, uses a coefficient of size n in matrix will cost n in the size of the matrix, roughly.

Checking whether Per(A) = 0 is already “hard” for general matrices,

so multiplicative approximation is a rarity, unless…

BTW, what is currently known about multiplicative approximations

of Per(A) for positive semidefinite A? Looks like the

most natural next challenge.