Computing the permanent

In linear algebra, the computation of the permanent of a matrix is a problem that is known to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.

The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign.

While the determinant can be computed in polynomial time by Gaussian elimination, the permanent cannot. In computational complexity theory, a theorem of Valiant states that computing permanents is #P-hard, and even #P-complete for matrices in which all entries are 0 or 1.Valiant (1979) This puts the computation of the permanent in a class of problems believed to be even more difficult to compute than NP. It is known that computing the permanent is impossible for logspace-uniform ACC⁰ circuits.(Allender & Gore 1994)

The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research.

Definition and naive algorithm

The permanent of an n-by-n matrix A = (a_i,j) is defined as

\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.

The sum here extends over all elements σ of the symmetric group S_n, i.e. over all permutations of the numbers 1, 2, ..., n. This formula differs from the corresponding formula for the determinant only in that, in the determinant, each product is multiplied by the sign of the permutation σ while in this formula each product is unsigned. The formula may be directly translated into an algorithm that naively expands the formula, summing over all permutations and within the sum multiplying out each matrix entry. This requires n! n arithmetic operations.

Ryser formula

The best known^[1] general exact algorithm is due to H. J. Ryser (1963). Ryser’s method is based on an inclusion–exclusion formula that can be given^[2] as follows: Let $A_{k}$ be obtained from A by deleting k columns, let $P(A_k)$ be the product of the row-sums of $A_{k}$ , and let $\Sigma _{k}$ be the sum of the values of $P(A_k)$ over all possible $A_{k}$ . Then

\operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k}\Sigma_k.

It may be rewritten in terms of the matrix entries as follows^[3]

\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.

Ryser’s formula can be evaluated using $O(2^nn^2)$ arithmetic operations, or $O(2^{n}n)$ by processing the sets $S$ in Gray code order.

Balasubramanian–Bax–Franklin–Glynn formula

Another formula that appears to be as fast as Ryser's (or perhaps even twice as fast) is to be found in the two Ph.D. theses; see (Balasubramanian 1980), (Bax 1998); also (Bax & Franklin 1996). The methods to find the formula are quite different, being related to the combinatorics of the Muir algebra, and to finite difference theory respectively. Another way, connected with invariant theory is via the polarization identity for a symmetric tensor (Glynn 2010). The formula generalizes to infinitely many others, as found by all these authors, although it is not clear if they are any faster than the basic one. See (Glynn 2013).

The simplest known formula of this type (when the characteristic of the field is not two) is

\operatorname {perm} (A)=\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right]/2^{n-1},

where the outer sum is over all $2^{n-1}$ vectors $\delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}$ .

Special cases

Planar and K_3,3-free

The number of perfect matchings in a bipartite graph is counted by the permanent of the graph's biadjacency matrix, and the permanent of any 0-1 matrix can be interpreted in this way as the number of perfect matchings in a graph. For planar graphs (regardless of bipartiteness), the FKT algorithm computes the number of perfect matchings in polynomial time by changing the signs of a carefully chosen subset of the entries in the Tutte matrix of the graph, so that the Pfaffian of the resulting skew-symmetric matrix (the square root of its determinant) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph homeomorphic to the complete bipartite graph K_3,3.^[4]

George Pólya had asked the question^[5] of when it is possible to change the signs of some of the entries of a 01 matrix A so that the determinant of the new matrix is the permanent of A. Not all 01 matrices are "convertible" in this manner; in fact it is known (Marcus & Minc (1961)) that there is no linear map $T$ such that $\operatorname{per}\,T(A) = \det A$ for all $n\times n$ matrices $A$ . The characterization of "convertible" matrices was given by Little (1975) who showed that such matrices are precisely those that are the biadjacency matrix of bipartite graphs that have a Pfaffian orientation: an orientation of the edges such that for every even cycle $C$ for which $G\setminus C$ has a perfect matching, there are an odd number of edges directed along C (and thus an odd number with the opposite orientation). It was also shown that these graphs are exactly those that do not contain a subgraph homeomorphic to $K_{3,3}$ , as above.

Computation modulo a number

Modulo 2, the permanent is the same as the determinant, as $(-1) \equiv 1 \pmod 2.$ It can also be computed modulo $2^{k}$ in time $O(n^{4k-3})$ for $k\geq 2$ . However, it is UP-hard to compute the permanent modulo any number that is not a power of 2. Valiant (1979)

There are various formulae given by Glynn (2010) for the computation modulo a prime $p$ . Firstly, there is one using symbolic calculations with partial derivatives.

Secondly, for $p$ =3 there is the following formula (Grigoriy Kogan, 1996) using the matrix's principal minors:

\operatorname {perm} (A)=(-1)^{m}\Sigma _{J\subseteq \{1,\dots ,m\}}\det(A_{J})\det(A_{\bar {J}}),

where $A_{J}$ is the submatrix of $A$ induced by the rows and columns of $A$ indexed by $J$ , and ${\bar {J}}$ is the complement of $J$ in $\{1,\dots,m\}.$

(The determinant of the empty submatrix is defined to be 1).

This formula implies the following identities over fields of Characteristic 3 (Grigoriy Kogan, 1996):

for any invertible $A$

\operatorname{perm}(A^{-1})\det(A)^2 = \operatorname{perm}(A)

;

for any unitary $U$ , i.e. a square matrix $U$ such that $U^{T} U = I \,$ where $I$ is the identity matrix,

\operatorname {perm} (U)^{2}=\det(U+V)\det(-U)

where $V$ is the matrix whose entries are the cubes of the corresponding entries of $U$ .

It was also shown (Grigoriy Kogan, 1996) that, if we define a matrix A as k-semi-unitary when rank ( $A^{T}A-I\,$ ) = $k$ , the permanent of a 1-semi-unitary matrix is computable in a polynomial time over fields of Characteristic 3, while for $k$ >1 the problem becomes #3-P-complete.

Approximate computation

When the entries of A are nonnegative, the permanent can be computed approximately in probabilistic polynomial time, up to an error of εM, where M is the value of the permanent and ε > 0 is arbitrary. In other words, there exists a fully polynomial-time randomized approximation scheme (FPRAS) (Jerrum, Vigoda & Sinclair (2001)).

The most difficult step in the computation is the construction of an algorithm to sample almost uniformly from the set of all perfect matchings in a given bipartite graph: in other words, a fully polynomial almost uniform sampler (FPAUS). This can be done using a Markov chain Monte Carlo algorithm that uses a Metropolis rule to define and run a Markov chain whose distribution is close to uniform, and whose mixing time is polynomial.

It is possible to approximately count the number of perfect matchings in a graph via the self-reducibility of the permanent, by using the FPAUS in combination with a well-known reduction from sampling to counting due to Jerrum, Valiant & Vazirani (1986). Let $M(G)$ denote the number of perfect matchings in $G$ . Roughly, for any particular edge $e$ in $G$ , by sampling many matchings in $G$ and counting how many of them are matchings in $G \setminus e$ , one can obtain an estimate of the ratio $\rho=\frac{M(G)}{M(G\setminus e)}$ . The number $M(G)$ is then $\rho M(G \setminus e)$ , where $M(G \setminus e)$ can be approximated by applying the same method recursively.

Notes

↑ As of 2008, see Rempala & Wesolowski (2008)
↑ van Lint & Wilson (2001) p. 99
↑ CRC Concise Encyclopedia of Mathematics
↑ Little (1974), Vazirani (1988)
↑ Pólya (1913), Reich (1971)

References

Allender, Eric; Gore, Vivec (1994), "A uniform circuit lower bound for the permanent", SIAM Journal on Computing, 23 (5): 1026–1049, doi:10.1137/s0097539792233907

Balasubramanian, K. (1980), Combinatorics and Diagonals of Matrices, Ph.D. Thesis, Department of Statistics, Loyola College, Madras, India, T073, Indian Statistical Institute, Calcutta

Bax, Eric (1998), Finite-difference Algorithms for Counting Problems, Ph.D. Dissertation, 223, California Institute of Technology

Bax, Eric; Franklin, J. (1996), A finite-difference sieve to compute the permanent, Caltech-CS-TR-96-04, California Institute of Technology

Glynn, David G. (2010), "The permanent of a square matrix", European Journal of Combinatorics, 31 (7): 1887–1891, doi:10.1016/j.ejc.2010.01.010

Glynn, David G. (2013), "Permanent formulae from the Veronesean", Designs, Codes and Cryptography, 68 (1-3): 39–47, doi:10.1007/s10623-012-9618-1

Jerrum, M.; Sinclair, A.; Vigoda, E. (2001), "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries", Proc. 33rd Symposium on Theory of Computing, pp. 712–721, doi:10.1145/380752.380877, ECCC TR00-079
Mark Jerrum; Leslie Valiant; Vijay Vazirani (1986), "Random generation of combinatorial structures from a uniform distribution", Theoretical Computer Science, 43: 169–188, doi:10.1016/0304-3975(86)90174-X

Kogan, Grigoriy (1996), "Computing permanents over fields of characteristic 3: where and why it becomes difficult", 37th Annual Symposium on Foundations of Computer Science (FOCS '96)

van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), A Course in Combinatorics, ISBN 0-521-00601-5
Little, C. H. C. (1974), "An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs", in Holton, D., Proc. 2nd Australian Conf. Combinatorial Mathematics, Lecture Notes in Mathematics, 403, Springer-Verlag, pp. 63–72
Little, C. H. C. (1975), "A characterization of convertible (0, 1)-matrices", Journal of Combinatorial Theory, Series B, 18 (3): 187–208, doi:10.1016/0095-8956(75)90048-9
Marcus, M.; Minc, H. (1961), "On the relation between the determinant and the permanent", Illinois Journal of Mathematics, 5: 376–381
Pólya, G. (1913), "Aufgabe 424", Arch. Math. Phys., 20 (3): 27
Reich, Simeon (1971), "Another solution of an old problem of pólya", American Mathematical Monthly, 78 (6): 649–650, JSTOR 2316574, doi:10.2307/2316574
Rempała, Grzegorz A.; Wesolowski, Jacek (2008), Symmetric Functionals on Random Matrices and Random Matchings Problems, p. 4, ISBN 0-387-75145-9
Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus mathematical monographs, Mathematical Association of America
Vazirani, Vijay V. (1988), "NC algorithms for computing the number of perfect matchings in K_3,3-free graphs and related problems", Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT '88), Lecture Notes in Computer Science, 318, Springer-Verlag, pp. 233–242, doi:10.1007/3-540-19487-8_27
Valiant, Leslie G. (1979), "The Complexity of Computing the Permanent", Theoretical Computer Science, Elsevier, 8 (2): 189–201, doi:10.1016/0304-3975(79)90044-6
"Permanent", CRC Concise Encyclopedia of Mathematics, Chapman & Hall/CRC, 2002