7
$\begingroup$

The permanent $P(M)$ of a matrix $M$ of size $n$ is defined to be: $$ P(M) := \sum_{\sigma \in S_n}\prod_{i=1}^n M_{i\sigma(i)} $$

If you have a matrix of the form $$ M_{ij} := A_i + B_j $$ where $A$ and $B$ are indexed sets of numbers and if $x_k(S)$ is the sum of all products of $k$ elements taken from the set $S$, then: $$ P(M) = \sum_{k=0}^n k! (n-k)! x_k(A) x_{n-k}(B) $$

This gives a polynomial-time algorithm for computing the Permanents of matrices such as: $$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$ Here, $A_i = i$ and $B_i = 3*(i-1)$, and the Permanent is $450$.

What other classes of matrices are known to have efficiently computable or otherwise interesting formulas for their Permanents?

$\endgroup$

4 Answers 4

7
$\begingroup$

The permanent of the biadjacency matrix of a bipartite graph counts the number of perfect matchings of that graph. By the biadjacency matrix, I mean the matrix with rows indexed by one of the independent sets and the columns indexed by the other. An entry is 1 if the vertex represented by the row and the vertex represented by the column are adjacent and 0 otherwise.

It is known that counting the number of perfect matchings of planar bipartite graphs is computable in polynomial time. So computing the permanent of any matrix representing a planar bipartite graph when viewed as a biadjacency matrix can be done in polynomial time.

$\endgroup$
3
  • $\begingroup$ Hmm... computing the number of perfect matchings is actually in the #P complete class. There is a randomized algorithm for computing approximations to the permanent, though, which is probably what you meant.See also the remarks on counting in en.wikipedia.org/wiki/Matching_(graph_theory) $\endgroup$ Oct 17, 2013 at 6:10
  • 1
    $\begingroup$ @oferzeitouni For planar graphs, the number of perfect matchings can be found much easier than for general graphs... $\endgroup$
    – j.c.
    Oct 17, 2013 at 13:35
  • $\begingroup$ you are right, sorry I missed the important word planar. $\endgroup$ Oct 18, 2013 at 2:32
2
$\begingroup$

A large class of matrices for which the permanent can be efficiently computed has been constructed by Klaus Meer:

An extended tree-width notion for directed graphs related to the computation of permanents: presentation and publication

$\endgroup$
1
$\begingroup$

This is somewhat of a digression, but I thought it worthwhile to point out that in the tropical case, actually the permanent (equivalently determinant) is much easier to compute, and requires solving an assignment problem. Specifically, (see pg. 19 of this book by Maclagan and Sturmfels, the tropical permanent is \begin{equation*} \text{tp}(X) := \bigoplus_{\pi \in S_n} x_{1\pi(1)}\odot \cdots \odot x_{n\pi(n)}, \end{equation*} and this number is given by the solution to the minimization problem \begin{equation*} \min\lbrace x_{1\pi(1)}\odot \cdots \odot x_{n\pi(n)} \mid \pi \in S_n\rbrace, \end{equation*} which can be computed in $O(n^3)$ time (Hungarian assignment method).

$\endgroup$
0
1
$\begingroup$

You of example is a particular case of a slightly more general well known(and almost equally simple) situation when the rank is bounded by a fixed constant.

$\endgroup$
2
  • 2
    $\begingroup$ could you expand this answer with more specific details? I think this would be helpful. $\endgroup$ Feb 24, 2014 at 8:08
  • $\begingroup$ Do you have a reference for this more general result? $\endgroup$ Mar 22, 2014 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.