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 believe is 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.
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.
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?