In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, the computation of the
permanent
Permanent may refer to:
Art and entertainment
* ''Permanent'' (film), a 2017 American film
* ''Permanent'' (Joy Division album)
* "Permanent" (song), by David Cook
Other uses
* Permanent (mathematics), a concept in linear algebra
* Permanent (cy ...
of a
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
is a problem that is thought to be more difficult than the computation of the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
, it is generally believed that the permanent cannot be computed in polynomial time. In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
,
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 . 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
ACC0 circuits.
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
:
The sum here extends over all elements σ of the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
''S''
''n'', i.e. over all
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
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 best known general exact algorithm is due to .
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
The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).
For example, the representati ...
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 , ; also
. 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
In linear algebra, a branch of 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.
If a norm arises from an inner product then t ...
for a
symmetric tensor
In mathematics, a symmetric tensor is a tensor that is invariant under a permutation of its vector arguments:
:T(v_1,v_2,\ldots,v_r) = T(v_,v_,\ldots,v_)
for every permutation ''σ'' of the symbols Alternatively, a symmetric tensor of orde ...
. 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 .
The simplest known formula of this type (when the characteristic of the field is not two) is
:
where the outer sum is over all
vectors
.
Special cases
Planar and ''K''3,3-free
The number of
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s in a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
is counted by the permanent of the graph's
biadjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simpl ...
, 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 graph
In 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. In other words, it can be drawn in such a way that no edges cross ...
s (regardless of bipartiteness), the
FKT algorithm
The 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. For matchings that are not required to be perfect, co ...
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 In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') 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.
If the set of vert ...
of the graph, so that the
Pfaffian
In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
of the resulting
skew-symmetric matrix
In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition
In terms of the entries of the matrix, if a_ ...
(the
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
of its
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
) is the number of perfect matchings. This technique can be generalized to graphs that contain no subgraph
homeomorphic
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...
to the
complete bipartite graph
In 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..Electronic edition page 17.
Graph theory ...
''K''
3,3.
George Pólya
George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) 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 ...
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 In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientati ...
: 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
Modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
2, the permanent is the same as the determinant, as
It can also be computed modulo
in time
for
. However, it is
UP-hard 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 .
First, there is one using symbolic calculations with partial derivatives.
Second, for = 3 there is the following formula for an n×n-matrix
, involving the matrix's principal
minors ():
:
where
is the submatrix of
induced by the rows and columns of
indexed by
, and
is the complement of
in
, while the determinant of the empty submatrix is defined to be 1.
The expansion above can be generalized in an arbitrary
characteristic ''p'' as the following pair of dual identities:
where in both formulas the sum is taken over all the (''p'' − 1)-tuples
that are partitions of the set
into ''p'' − 1 subsets, some of them possibly empty.
The former formula possesses an analog for the hafnian of a symmetric
and an odd p:
with the sum taken over the same set of indexes. Moreover, in characteristic zero a similar convolution sum expression involving both the permanent and the determinant yields the
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
polynomial (defined as
where
is the set of n-permutations having only one cycle):
In characteristic 2 the latter equality turns into
what therefore provides an opportunity to polynomial-time calculate the
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
polynomial of any
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigroup ...
(i.e. such that
where
is the identity ''n''×''n''-matrix), because each minor of such a matrix coincides with its algebraic complement:
where
is the identity ''n''×''n''-matrix with the entry of indexes 1,1 replaced by 0. Moreover, it may, in turn, be further generalized for a unitary ''n''×''n''-matrix
as
where
is a subset of ,
is the identity ''n''×''n''-matrix with the entries of indexes ''k'',''k'' replaced by 0 for all ''k'' belonging to
, and we define
where
is the set of n-permutations whose each cycle contains at least one element of
.
This formula also implies the following identities over fields of characteristic 3:
for any
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
:
for any
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigroup ...
, that is, a square matrix
such that
where
is the identity matrix of the corresponding size,
:
where
is the matrix whose entries are the cubes of the corresponding entries of
.
It was also shown () that, if we define a square matrix
as k-semi-unitary when
, the permanent of a 1-semi-unitary matrix is computable in polynomial time over fields of characteristic 3, while for > 1 the problem becomes
#3-P-complete. (A parallel theory concerns the
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
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 () 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
being square,
being
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
):
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
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
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.) The closure of that operator defined as the limit of its sequential application together with the transpose transformation (utilized each time the operator leaves the matrix intact) is also an operator mapping, when applied to classes of matrices, one class to another. While the compression operator maps the class of 1-semi-unitary matrices to itself and the classes of
unitary
Unitary may refer to:
Mathematics
* Unitary divisor
* Unitary element
* Unitary group
* Unitary matrix
* Unitary morphism
* Unitary operator
* Unitary transformation
* Unitary representation
* Unitarity (physics)
* ''E''-unitary inverse semigroup ...
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
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
: as it was shown in (), 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 (), while giving the following identity for an ''n''×''n'' matrix
and two ''n''-vectors (having all their entries from the set )
and
such that
, valid in an arbitrary prime characteristic ''p'':
where for an ''n''×''m''-matrix
, an n-vector
and an m-vector
, both vectors having all their entries from the set ,
denotes the matrix received from
via repeating
times its ''i''-th row for ''i'' = 1, ..., ''n'' and
times its ''j''-th column for ''j'' = 1, ..., ''m'' (if some row's or column's multiplicity equals zero it would mean that the row or column was removed, and thus this notion is a generalization of the notion of submatrix), and
denotes the n-vector all whose entries equal unity. 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. (Actually its own analogue for the hafnian of a symmetric
and an odd prime p is
).
And, as an even wider generalization for the partial inverse case in a prime characteristic p, for
,
being square,
being
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
and of size
x
, and
, there holds also the identity
where the common row/column multiplicity vectors
and
for the matrix
generate the corresponding row/column multiplicity vectors
and
, s,t = 1,2, for its blocks (the same concerns
's partial inverse in the equality's right side).
Approximate computation
When the entries of ''A'' are nonnegative, the permanent can be computed
approximately
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
in
probabilistic
Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
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
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an ins ...
(FPRAS) ().
The most difficult step in the computation is the construction of an algorithm to
sample
Sample or samples may refer to:
Base meaning
* Sample (statistics), a subset of a population – complete data set
* Sample (signal), a digital discrete sample of a continuous analog signal
* Sample (material), a specimen or small quantity of s ...
almost
uniformly
Uniform distribution may refer to:
* Continuous uniform distribution
* Discrete uniform distribution
* Uniform distribution (ecology)
* Equidistributed sequence In mathematics, a sequence (''s''1, ''s''2, ''s''3, ...) of real numbers is said to be ...
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
In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...
algorithm that uses a
Metropolis rule to define and run a
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
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
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
of the permanent, by using the FPAUS in combination with a well-known reduction from sampling to counting due to . Let
denote 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
can be approximated by applying the same method recursively.
Another class of matrices for which the permanent can be computed approximately, is the set of
positive-semidefinite matrices (the complexity-theoretic problem of approximating the permanent of such matrices to within a multiplicative error is considered open). The corresponding randomized algorithm is based on the model of
boson sampling
Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible usage of boson scattering to evaluat ...
and it uses the tools proper to
quantum optics
Quantum optics is a branch of atomic, molecular, and optical physics dealing with how individual quanta of light, known as photons, interact with atoms and molecules. It includes the study of the particle-like properties of photons. Photons have b ...
, to represent the permanent of positive-semidefinite matrices as the expected value of a specific random variable. The latter is then approximated by its sample mean. 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.
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Further reading
* .
{{DEFAULTSORT:Computing The Permanent
Computational complexity theory
Linear algebra
Matrix theory
Permutations
Computational problems