[1] Both are special cases of a more general function of a matrix called the immanant.
The sum here extends over all elements σ of the symmetric group Sn; i.e. over all permutations of the numbers 1, 2, ..., n. For example,
The definition of the permanent of A differs from that of the determinant of A in that the signatures of the permutations are not taken into account.
The permanent of a matrix A is denoted per A, perm A, or Per A, sometimes with parentheses around the argument.
[3] The word, permanent, originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function,[4] and was used by Muir and Metzler[5] in the modern, more specific, sense.
[6] If one views the permanent as a map that takes n vectors as arguments, then it is a multilinear map and it is symmetric (meaning that any order of the vectors results in the same permanent).
of order n:[7] Laplace's expansion by minors for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs.
is the permanent of the submatrix obtained by removing the ith row and the jth column of B.
On the other hand, the basic multiplicative property of determinants is not valid for permanents.
Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics, in treating boson Green's functions in quantum field theory, and in determining state probabilities of boson sampling systems.
[11] However, it has two graph-theoretic interpretations: as the sum of weights of cycle covers of a directed graph, and as the sum of weights of perfect matchings in a bipartite graph.
The permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces.
can be viewed as the adjacency matrix of a weighted directed graph on vertex set
Thus the permanent of A is equal to the sum of the weights of all perfect matchings of the graph.
The answers to many counting questions can be computed as permanents of matrices that only have 0 and 1 as entries.
[13] The incidence matrices of projective planes are in the class Ω(n2 + n + 1, n + 1) for n an integer > 1.
The permanents corresponding to the smallest projective planes have been calculated.
This is a consequence of Z being a circulant matrix and the theorem:[14] Permanents can also be used to calculate the number of permutations with restricted (prohibited) positions.
Then perm(A) is equal to the number of permutations of the n-set that satisfy all the restrictions.
Permanent of n×n all 1's matrix is a number of possible arrangements of n mutually non-attacking rooks in the positions of the board of size n×n.
[15] The Bregman–Minc inequality, conjectured by H. Minc in 1963[16] and proved by L. M. Brégman in 1973,[17] gives an upper bound for the permanent of an n × n (0, 1)-matrix.
In 1926, Van der Waerden conjectured that the minimum permanent among all n × n doubly stochastic matrices is n!/nn, achieved by the matrix for which all entries are equal to 1/n.
Thus, if the permanent can be computed in polynomial time by any method, then FP = #P, which is an even stronger statement than P = NP.
When the entries of A are nonnegative, however, the permanent can be computed approximately in probabilistic polynomial time, up to an error of
[26] The permanent of a certain set of positive semidefinite matrices is NP-hard to approximate within any subexponential factor.
[28] The hardness in these instances is closely linked with difficulty of simulating boson sampling experiments.
MacMahon's master theorem relating permanents and determinants is:[30]
Indeed, several authors make this the definition of a permanent and consider the restriction to square matrices a special case.
The generalization of the definition of a permanent to non-square matrices allows the concept to be used in a more natural way in some applications.
The number of systems of distinct representatives (SDR's) of this collection is perm(A).