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.
(Allender & Gore 1994) The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research.
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 Sn, 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.
Then It may be rewritten in terms of the matrix entries as follows[3] Ryser's formula can be evaluated using
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.
The simplest known formula of this type (when the characteristic of the field is not two) is where the outer sum is over all
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.
Not all 01 matrices are "convertible" in this manner; in fact it is known (Marcus & Minc (1961)) that there is no linear map
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
Valiant (1979) There are various formulae given by Glynn (2010) for the computation modulo a prime p. First, there is one using symbolic calculations with partial derivatives.
The expansion above can be generalized in an arbitrary characteristic p as the following pair of dual identities:
Moreover, in characteristic zero a similar convolution sum expression involving both the permanent and the determinant yields the Hamiltonian cycle polynomial (defined as
what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary
, the permanent of a 1-semi-unitary matrix is computable in polynomial time over fields of characteristic 3, while for k > 1 the problem becomes #3-P-complete.
(A parallel theory concerns the Hamiltonian cycle polynomial in characteristic 2: while computing it on the unitary matrices is polynomial-time feasible, the problem is #2-P-complete for the k-semi-unitary ones for any k > 0).
The latter result was essentially extended in 2017 (Knezevic & Cohen (2017)) and it was proven that in characteristic 3 there is a simple formula relating the permanents of a square matrix and its partial inverse (for
and it allows to polynomial-time reduce the computation of the permanent of an n×n-matrix with a subset of k or k − 1 rows expressible as linear combinations of another (disjoint) subset of k rows to the computation of the permanent of an (n − k)×(n − k)- or (n − k + 1)×(n − k + 1)-matrix correspondingly, hence having introduced a compression operator (analogical to the Gaussian modification applied for calculating the determinant) that "preserves" the permanent in characteristic 3.
(Analogically, it would be worth noting that the Hamiltonian cycle polynomial in characteristic 2 does possess its invariant matrix compressions as well, taking into account the fact that ham(A) = 0 for any n×n-matrix A having three equal rows or, if n > 2, a pair of indexes i,j such that its i-th and j-th rows are identical and its i-th and j-th columns are identical too.)
While the compression operator maps the class of 1-semi-unitary matrices to itself and the classes of unitary and 2-semi-unitary ones, the compression-closure of the 1-semi-unitary class (as well as the class of matrices received from unitary ones through replacing one row by an arbitrary row vector — the permanent of such a matrix is, via the Laplace expansion, the sum of the permanents of 1-semi-unitary matrices and, accordingly, polynomial-time computable) is yet unknown and tensely related to the general problem of the permanent's computational complexity in characteristic 3 and the chief question of P versus NP: as it was shown in (Knezevic & Cohen (2017)), if such a compression-closure is the set of all square matrices over a field of characteristic 3 or, at least, contains a matrix class the permanent's computation on is #3-P-complete (like the class of 2-semi-unitary matrices) then the permanent is computable in polynomial time in this characteristic.
Besides, the problem of finding and classifying any possible analogs of the permanent-preserving compressions existing in characteristic 3 for other prime characteristics was formulated (Knezevic & Cohen (2017)), while giving the following identity for an n×n matrix
This identity is an exact analog of the classical formula expressing a matrix's minor through a minor of its inverse and hence demonstrates (once more) a kind of duality between the determinant and the permanent as relative immanants.
And, as an even wider generalization for the partial inverse case in a prime characteristic p, for
In other words, there exists a fully polynomial-time randomized approximation scheme (FPRAS) (Jerrum, Sinclair & Vigoda (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).
It is NP-hard to approximate permanents of PSD matrices within a subexponential factor, and it is conjectured to be
One randomized algorithm is based on the model of boson sampling and it uses the tools proper to quantum optics, to represent the permanent of positive-semidefinite matrices as the expected value of a specific random variable.
[9] This algorithm, for a certain set of positive-semidefinite matrices, approximates their permanent in polynomial time up to an additive error, which is more reliable than that of the standard classical polynomial-time algorithm by Gurvits.