Computing the permanent
Encyclopedia
In mathematics
, the computation of the permanent
of a matrix
is a problem that is believed to be more complex 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 assigns a ±1 sign to each of these products, the permanent does not.
While the determinant can be computed in polynomial time by Gaussian elimination
, Gaussian elimination cannot be used to compute the permanent. In computational complexity theory
, a theorem of Valiant
states that computing permanents, even of matrices in which all entries are 0 or 1, is #P-complete putting 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 ACC0 circuits .
Despite, or perhaps because of, its computational difficulty, there has been much research on exponential-time exact algorithms and polynomial time approximation algorithms for the permanent, both for the case of the 0-1 matrices arising in the graph matching problems and more generally.
The sum here extends over all elements σ of the symmetric group
Sn, i.e. over all permutation
s 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’s method is based on an inclusion–exclusion
formula that can be given as follows: Let
be obtained from A by deleting k columns, let 
be the product of the row-sums of 
, and let 
be the sum of the values of 
over all possible 
. Then
It may be rewritten in terms of the matrix entries as follows
Ryser’s formula can be evaluated using
arithmetic operations, or 
by processing the sets 
in Gray code
order.
for a symmetric tensor .
It has the formula (when the characteristic of the field is not two)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the computation of the permanent
Permanent
The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...
of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
is a problem that is believed to be more complex than the computation of the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
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 assigns a ±1 sign to each of these products, the permanent does not.
While the determinant can be computed in polynomial time by Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
, Gaussian elimination cannot be used to compute the permanent. In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a theorem of Valiant
Permanent is sharp-P-complete
In a 1979 paper Leslie Valiant proved that the problem of computing the permanent of a matrix is #P-hard, and remains #P-complete even if the matrix is restricted to have entries that are all 0 or 1. This result is sometimes known as Valiant's theorem and is considered a seminal result in...
states that computing permanents, even of matrices in which all entries are 0 or 1, is #P-complete putting the computation of the permanent in a class of problems believed to be even more difficult to compute than NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
. It is known that computing the permanent is impossible for logspace-uniform ACC0 circuits .
Despite, or perhaps because of, its computational difficulty, there has been much research on exponential-time exact algorithms and polynomial time approximation algorithms for the permanent, both for the case of the 0-1 matrices arising in the graph matching problems and more generally.
Definition and naive algorithm
The permanent of an n-by-n matrix A = (ai,j) is defined as
The sum here extends over all elements σ of the symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
Sn, i.e. over all permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s 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 fastest known general exact algorithm is due to Herbert John RyserHerbert John Ryser
Herbert John Ryser was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century...
.
Ryser’s method is based on an inclusion–exclusion
Inclusion-exclusion principle
In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...
formula that can be given as follows: Let
be obtained from A by deleting k columns, let be the product of the row-sums of , and let be the sum of the values of over all possible . ThenIt may be rewritten in terms of the matrix entries as follows
Ryser’s formula can be evaluated using
arithmetic operations, or by processing the sets in Gray codeGray code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code....
order.
Glynn formula
Another formula that appears to be as fast as Ryser's is closely related to the polarization identityPolarization identity
In mathematics, the polarization identity is any one of a family of formulas that express the inner product of two vectors in terms of the norm of a normed vector space. Let \|x\| \, denote the norm of vector x and \langle x, \ y \rangle \, the inner product of vectors x and y...
for a symmetric tensor .
It has the formula (when the characteristic of the field is not two)
-
where the outer sum is over all
vectors 
.
Special cases
The number of perfect matchings in a bipartite graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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 graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s (regardless of bipartiteness), the FKT algorithmFKT algorithmThe FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. Counting the number of matchings, even for planar graphs, is also #P-complete...
computes the number of perfect matchings in polynomial time by changing the signs of a carefully chosen subset of the entries in the Tutte matrixTutte matrixIn graph theory, the Tutte matrix A of a graph G = is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once....
of the graph, so that the PfaffianPfaffianIn mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix, The term Pfaffian was introduced by who named them after Johann Friedrich Pfaff...
of the resulting skew-symmetric matrixSkew-symmetric matrixIn mathematics, and in particular linear algebra, a skew-symmetric matrix is a square matrix A whose transpose is also its negative; that is, it satisfies the equation If the entry in the and is aij, i.e...
(the square rootSquare rootIn mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
of its determinantDeterminantIn linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph homeomorphicHomeomorphism (graph theory)In graph theory, two graphs G and G' are homeomorphic if there is an isomorphism from some subdivision of G to some subdivision of G'...
to the complete bipartite graphComplete bipartite graphIn the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K3,3.
George PólyaGeorge PólyaGeorge Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
had asked the question 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 that
there is no linear map
such that 
for all 
matrices 
. The characterization of "convertible" matrices was given by 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 
for which 
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 
, as above.
Computation modulo a number
ModuloModular arithmeticIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
2, the permanent is the same as the determinant, as
It can also be computed modulo 
in time 
for 
. However, it is UP-hardUP (complexity)In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input...
to compute the permanent modulo any number that is not a power of 2.
There are various formulae given by for the computation modulo a prime
.
Firstly there is one using symbolic calculations with partial derivatives.
Secondly for
there is the following formula using the determinants of the principal
submatrices of the matrix:
where
is the principal submatrix of 
induced by the rows and columns of 
indexed by
, and 
is the complement of 
in 
Approximate computation
When the entries of A are nonnegative, the permanent can be computed approximatelyApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
in probabilisticRandomized algorithmA randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
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) .
The main part of the computation is the construction of an algorithm to sampleSampling (statistics)In statistics and survey methodology, sampling is concerned with the selection of a subset of individuals from within a population to estimate characteristics of the whole population....
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 is a Markov chain Monte CarloMarkov chain Monte CarloMarkov chain Monte Carlo methods are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the...
algorithm: it consists of running a Markov chainMarkov chainA Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
whose distribution is close to uniform (achieved using a Metropolis rule), and whose mixing timeMarkov chain mixing timeIn probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution.More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and,...
is polynomial.
Once there is a FPAUS, it is possible to approximately count the number of perfect matchings using the self-reducibility of the permanent, using a well-known reduction from sampling to counting due to . Let
be the number of perfect matchings in 
. Roughly, for any particular edge 
in 
, by sampling many matchings in 
and counting how many of them are matchings in 
, one can obtain an estimate of the ratio 
. The number 
is then 
, where 
is found recursively by the same method.