<p>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.</p>

CC BY-SA 3.0
2015-10-26T18:03:46.943Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-10-26T18:24:47.917Z
@SashoNikolov: Notice that the answer starts with **If**. (That is, it is answering a different question.)
Emil Jeřábek
CC BY-SA 3.0
2015-10-26T19:29:44.977Z
This is an interesting answer to a question I didn't ask, +1.
Charles
CC BY-SA 3.0
2015-10-26T17:59:13.957Z
2015-10-26T17:59:13.957Z
Rasmus Pagh
<p>Expanding <a href="https://cstheory.stackexchange.com/posts/comments/75330?noredirect=1">my comment</a>:</p>

<p>Computing the permanent of a matrix is <a href="https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent" rel="nofollow noreferrer">#P-hard</a> <a href="https://dx.doi.org/10.1016%2F0304-3975%2879%2990044-6" rel="nofollow noreferrer">(Valiant 1979)</a> even if the matrix entries are all either 0 or 1.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)" rel="nofollow noreferrer">perfect matching</a> 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$.</p>

<p>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).$$</p>

<p>As a consequence $\mathrm{Permanent}(M) \ne 0$ if and only if $G$ has a perfect matching. There are <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs" rel="nofollow noreferrer">simple polynomial-time algorithms</a> 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.</p>

<p>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.</p>

<p>The simplest algorithm for finding a perfect matching is <a href="https://en.wikipedia.org/wiki/Berge%27s_lemma" rel="nofollow noreferrer">augmenting paths</a> and runs in $O(n^4)$ time.</p>

<p>We can actually do better and <a href="https://en.wikipedia.org/wiki/Computing_the_permanent#Approximate_computation" rel="nofollow noreferrer">approximate the permanent</a> for matrices with non-negative entries.</p>

CC BY-SA 3.0
2015-10-23T21:32:33.040Z
2015-10-23T21:32:33.040Z
2017-04-13T12:32:28.077Z
Thomas Steinke
<p>Valiant's theorem says that computing the permanent of an $n\times n$ matrix is <a href="https://en.wikipedia.org/wiki/Sharp-P-complete">#P-hard</a>. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence <a href="https://oeis.org/A006063">A006063</a> in the <a href="http://oeis.org/">OEIS</a>, 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.)</p>

CC BY-SA 3.0
2015-10-23T20:27:27.300Z
Closely related question, that I think contains the answer to your question: http://cstheory.stackexchange.com/questions/115/complexity-of-testing-for-a-value-versus-computing-a-function
Joshua Grochow
CC BY-SA 3.0
2015-10-23T20:53:41.360Z
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.
Thomas Steinke
CC BY-SA 3.0
2015-10-23T20:55:55.167Z
@Thomas: They are -- please give this answer! (A reference would be good....)
Charles
<cc.complexity-theory><ds.algorithms><matrices><permutations><permanent>
Matrix permanent is 0
Charles
# Matrix permanent is 0

(Asked by: username_0 on 2015-10-23)

Valiant's theorem says that computing the permanent of an $n\times n$ matrix is [#P-hard](https://en.wikipedia.org/wiki/Sharp-P-complete). Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence [A006063](https://oeis.org/A006063) in the [OEIS](http://oeis.org/), 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.)

**Tags:** cc.complexity-theory, ds.algorithms, matrices, permutations, permanent
> **Comments:**
> **username_1**: Closely related question, that I think contains the answer to your question: http://cstheory.stackexchange.com/questions/115/complexity-of-testing-for-a-value-versus-computing-a-function  
> **username_2**: 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.  
> **username_0**: @Thomas: They are -- please give this answer! (A reference would be good....)  

---

## 2 answers

### Answer by username_2 on 2015-10-23. Score: 17 | Accepted answer

Expanding [my comment](https://cstheory.stackexchange.com/posts/comments/75330?noredirect=1):

Computing the permanent of a matrix is [#P-hard](https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent) [(Valiant 1979)](https://dx.doi.org/10.1016%2F0304-3975%2879%2990044-6) 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](https://en.wikipedia.org/wiki/Matching_(graph_theory)) 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](https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs) 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](https://en.wikipedia.org/wiki/Berge%27s_lemma) and runs in $O(n^4)$ time.

We can actually do better and [approximate the permanent](https://en.wikipedia.org/wiki/Computing_the_permanent#Approximate_computation) for matrices with non-negative entries.


---

### Answer by username_3 on 2015-10-26. Score: 6

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.

> **Comments:**
> **username_4**: 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.  
> **username_5**: @SashoNikolov: Notice that the answer starts with **If**. (That is, it is answering a different question.)  
> **username_0**: This is an interesting answer to a question I didn't ask, +1.  

---

