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. Both permanent and determinant are special cases of a more general function of a matrix called the immanant.
The permanent of an n-by-n matrix A = (ai,j) is defined as
For example (2×2 matrix),
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. 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). A formula similar to Laplace's for the development of a determinant along a row or column is also valid for the permanent; all signs have to be ignored for the permanent.
The permanent of a matrix A is denoted per A, perm A, or Per A, sometimes with parentheses around the argument. In his monograph, Minc (1984) uses Per(A) for the permanent of rectangular matrices, and uses per(A) when A is a square matrix. Muir (1882) uses the notation .
Properties and applications
Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics and in treating boson Green's functions in quantum field theory. 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.
Any square matrix can be viewed as the adjacency matrix of a weighted directed graph, with representing the weight of the arc from vertex i to vertex j. A cycle cover of a weighted directed graph is a collection of vertex-disjoint directed cycles in the digraph that covers all vertices in the graph. Thus, each vertex i in the digraph has a unique "successor" in the cycle cover, and is a permutation on where n is the number of vertices in the digraph. Conversely, any permutation on corresponds to a cycle cover in which there is an arc from vertex i to vertex for each i.
If the weight of a cycle-cover is defined to be the product of the weights of the arcs in each cycle, then
The permanent of an matrix A is defined as
where is a permutation over . Thus the permanent of A is equal to the sum of the weights of all cycle-covers of the digraph.
A square matrix can also be viewed as the biadjacency matrix of a bipartite graph which has vertices on one side and on the other side, with representing the weight of the edge from vertex to vertex . If the weight of a perfect matching that matches to is defined to be the product of the weights of the edges in the matching, then
Thus the permanent of A is equal to the sum of the weights of all perfect matchings of the graph.
0-1 permanents: counting in unweighted graphs
In an unweighted, directed, simple graph, if we set each to be 1 if there is an edge from vertex i to vertex j, then each nonzero cycle cover has weight 1, and the adjacency matrix has 0-1 entries. Thus the permanent of a 01-matrix is equal to the number of vertex cycle covers of an unweighted directed graph.
For an unweighted bipartite graph, if we set ai,j = 1 if there is an edge between the vertices and and ai,j = 0 otherwise, then each perfect matching has weight 1. Thus the number of perfect matchings in G is equal to the permanent of matrix A.
Of all the doubly stochastic matrices, the matrix aij = 1/n (that is, the uniform matrix) has strictly the smallest permanent. This was conjectured by van der Waerden, and proved in the late 1970s independently by Falikman and Egorychev. The proof of Egorychev is an application of the Alexandrov–Fenchel inequality.
The permanent is believed to be more difficult to compute than the determinant. While the determinant can be computed in polynomial time by Gaussian elimination, Gaussian elimination cannot be used to compute the permanent. Moreover, computing the permanent of a 0-1 matrix (matrix whose entries are 0 or 1) is #P-complete. 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 εM, where M is the value of the permanent and ε > 0 is arbitrary.
- Dexter Kozen. The Design and Analysis of Algorithms. Springer-Verlag, New York, 1991. ISBN 978-0-387-97687-7; pp. 141–142
- Brualdi (2006) p.482
- Van der Waerden's permanent conjecture, PlanetMath.org.
- Brualdi (2006) p.487
- Jerrum, M.; Sinclair, A.; Vigoda, E. (2004), "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", Journal of the ACM 51: 671–697, doi:10.1145/1008731.1008738
- Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
- Cauchy, A. L. (1815), "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment.", Journal de l'École Polytechnique 10: 91–169
- Minc, Henryk (1978). Permanents. Encyclopedia of Mathematics and its Applications 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005.
- Muir, Thomas; William H. Metzler. (1960) . A Treatise on the Theory of Determinants. New York: Dover. OCLC 535903.