Matrix permanent is 0

Question

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.)

Answer 1

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.

Answer 2

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.