5
$\begingroup$

Valiant's theorem says that computing the permanent of an $n\times n$ matrix is #P-hard. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence A006063 in the OEIS, where membership is determined by the sign (0 or nonzero) of a certain permanent. (A solution to the restricted problem would be enough for me.)

$\endgroup$
  • 2
    $\begingroup$ Closely related question, that I think contains the answer to your question: cstheory.stackexchange.com/questions/115/… $\endgroup$ – Joshua Grochow Oct 23 '15 at 20:27
  • 3
    $\begingroup$ If all the entries in the matrix are non-negative, then there is a polynomial time algorithm for determining whether the permanent is nonzero. Note that computing the permanent of a matrix with all entries being either 0 or 1 is still #P-hard. $\endgroup$ – Thomas Oct 23 '15 at 20:53
  • $\begingroup$ @Thomas: They are -- please give this answer! (A reference would be good....) $\endgroup$ – Charles Oct 23 '15 at 20:55
17
$\begingroup$

Expanding my comment:

Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1.

We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a bipartite graph $G$ with left vertices $[n]$ and right vertices $[n]$, where the edge $(i,j)$ is present if and only if $M_{i,j}=1$. A perfect matching is a subset of the edges of $G$ such that every left and right vertex is incident to exactly one vertex in this subset. Now the permanent of the matrix $M$ is simply the number of perfect matchings in $G$.

To see why this is the case, note that each perfect matching in $G$ can be uniquely specified by a permutation $\sigma : [n] \to [n]$. So that the matching is the set of edges $\{(i,\sigma(i)) : i \in [n]\}$. That is each left vertex $i$ is matched to right vertex $\sigma(i)$. A permutation $\sigma$ is a valid matching if and only if all the edges $(i,\sigma(i))$ are present in $G$. By the definition of $G$, a permutation $\sigma$ gives a valid matching if and only if $\prod_{i=1}^n M_{i,\sigma(i)}=1$. Thus the number of valid matchings in $G$ is exactly $$\sum_{\sigma \in S_n} \mathbb{I}[\sigma \text{ specifies a valid matching}] = \sum_{\sigma \in S_n} \prod_{i=1}^n M_{i,\sigma(i)} = \mathrm{Permanent}(M).$$

As a consequence $\mathrm{Permanent}(M) \ne 0$ if and only if $G$ has a perfect matching. There are simple polynomial-time algorithms to find a perfect matching in a bipartite graph. Thus there is a polynomial-time algorithm to determine whether the permanent of a matrix is nonzero.

This works for all matrices with non-negative entries: Simply replace each nonzero entry with 1. This will distort the permanent but will not change whether or not it is nonzero.

The simplest algorithm for finding a perfect matching is augmenting paths and runs in $O(n^4)$ time.

We can actually do better and approximate the permanent for matrices with non-negative entries.

$\endgroup$
6
$\begingroup$

If it suffices to know the parity of the permanent, you can compute it in polynomial time by computing the determinant of the matrix over the field of size 2.

$\endgroup$
  • $\begingroup$ Why does it suffice to know the parity? What if the permanent is even? After all this is equivalent to deciding if a bipartite graph has a perfect matching. The closest algorithm I know to what you are suggesting is Lovasz's idea of introducing formal variables for each matrix entry and deciding if the determinant is identically zero as a polynomial. $\endgroup$ – Sasho Nikolov Oct 26 '15 at 18:03
  • 2
    $\begingroup$ @SashoNikolov: Notice that the answer starts with If. (That is, it is answering a different question.) $\endgroup$ – Emil Jeřábek Oct 26 '15 at 18:24
  • 2
    $\begingroup$ This is an interesting answer to a question I didn't ask, +1. $\endgroup$ – Charles Oct 26 '15 at 19:29

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.