<p>The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).</p>

<p>There's a <a href="https://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix" rel="nofollow noreferrer">nice article</a> that covers this on Wikipedia, based on a simpler proof published later [2].</p>

<p>As you mentioned sparse matrices particularly you may wish to know that if the matrix is the biadjacency matrix of a planar graph then the permanent can be computed in polynomial-time using the <a href="https://en.wikipedia.org/wiki/FKT_algorithm" rel="nofollow noreferrer">FKT algorithm</a>. This is a consequence of the permanent of the biadjacency matrix of a bipartite graph being equal to the weighted sum of perfect matchings, as explained <a href="https://en.wikipedia.org/wiki/Permanent#Perfect_matchings" rel="nofollow noreferrer">here</a>. There's a <a href="https://cstheory.stackexchange.com/questions/10140/a-question-to-the-p-complete-proof-of-the-permanent-from-ben-dor-halevi">previous question</a> related to this.</p>

<p>[1] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci.,
8:189-201, 1979. Available <a href="http://www.sciencedirect.com/science/article/pii/0304397579900446" rel="nofollow noreferrer">here</a>.<br>
[2] A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pages 108–117, 1993. Available from the author's webpage <a href="http://people.csail.mit.edu/shaih/pubs/01perm.pdf" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 3.0
2013-09-04T21:12:56.483Z
2013-09-05T19:50:24.143Z
2017-04-13T12:32:28.053Z
William Whistler
<p>More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and negative integers (but still sparsely).</p>

<p>I am not sure how hard this is. Clearly the permanent of a general matrix can be negative so it cannot be written as the permanent of a matrix with non-negative entries.</p>

<p>However, there may be some kind of way to re-represent the permanent of the general matrix in terms of other permanents.</p>

<p>That is, Per(A) = Per(A1) +/- Per(A2) +/- Per(A3) +/-... for some matrices A1,A2,A3, or something like that.</p>

<p>This is related to the problem of rerepresenting weighted graphs as non-weighted graphs through the connection of the permanent and cycle covers on the adjacency graph.</p>

<graph-theory><graph-algorithms><matrices>
What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?
Eric Bahr
# What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?

(Asked by: username_0 on 2013-09-02)

More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and negative integers (but still sparsely).

I am not sure how hard this is. Clearly the permanent of a general matrix can be negative so it cannot be written as the permanent of a matrix with non-negative entries.

However, there may be some kind of way to re-represent the permanent of the general matrix in terms of other permanents.

That is, Per(A) = Per(A1) +/- Per(A2) +/- Per(A3) +/-... for some matrices A1,A2,A3, or something like that.

This is related to the problem of rerepresenting weighted graphs as non-weighted graphs through the connection of the permanent and cycle covers on the adjacency graph.

**Tags:** graph-theory, graph-algorithms, matrices

---

## 1 answers

### Answer by username_1 on 2013-09-04. Score: 7 | Accepted answer

The problem of computing the permanent of general matrices can indeed be reduced to the problem of computing the permanent of 0-1 matrices. This was shown in the paper that introduced the complexity class #P in 1979 [1] (which also showed that the problem is #P-complete).

There's a [nice article](https://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix) that covers this on Wikipedia, based on a simpler proof published later [2].

As you mentioned sparse matrices particularly you may wish to know that if the matrix is the biadjacency matrix of a planar graph then the permanent can be computed in polynomial-time using the [FKT algorithm](https://en.wikipedia.org/wiki/FKT_algorithm). This is a consequence of the permanent of the biadjacency matrix of a bipartite graph being equal to the weighted sum of perfect matchings, as explained [here](https://en.wikipedia.org/wiki/Permanent#Perfect_matchings). There's a [previous question](https://cstheory.stackexchange.com/questions/10140/a-question-to-the-p-complete-proof-of-the-permanent-from-ben-dor-halevi) related to this.

[1] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci.,
8:189-201, 1979. Available [here](http://www.sciencedirect.com/science/article/pii/0304397579900446).  
[2] A. Ben-Dor and S. Halevi. Zero-one permanent is #P-complete, a simpler proof. Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pages 108–117, 1993. Available from the author's webpage [here](http://people.csail.mit.edu/shaih/pubs/01perm.pdf).


---

