In linear algebra, the permanent of a square matrix 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 are special cases of a more general function of a matrix called the immanant.
Definition
The permanent of an matrix 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.
For example,
and
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. Minc uses Per(A) for the permanent of rectangular matrices, and per(A) when A is a square matrix. Muir and Metzler use the notation .
The word, permanent, originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function, and was used by Muir and Metzler in the modern, more specific, sense.
Properties
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). Furthermore, given a square matrix of order n: perm(A) is invariant under arbitrary permutations of the rows and/or columns of A. This property may be written symbolically as perm(A) = perm(PAQ) for any appropriately sized permutation matrices P and Q, multiplying any single row or column of A by a scalar s changes perm(A) to s⋅perm(A), perm(A) is invariant under transposition, that is, perm(A) = perm(AT). If and are square matrices of order n then, where s and t are subsets of the same size of { 1,2,...,n} and are their respective complements in that set. If is a triangular matrix, i.e. , whenever or, alternatively, whenever , then its permanent (and determinant as well) equals the product of the diagonal entries:
Relation to determinants
Laplace's expansion by minors for computing the determinant along a row, column or diagonal extends to the permanent by ignoring all signs.
For every ,
where is the entry of the ith row and the jth column of B, and is the permanent of the submatrix obtained by removing the ith row and the jth column of B.
For example, expanding along the first column,
while expanding along the last row gives,
On the other hand, the basic multiplicative property of determinants is not valid for permanents. A simple example shows that this is so.
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. 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.
Applications
Symmetric tensors
The permanent arises naturally in the study of the symmetric tensor power of Hilbert spaces. In particular, for a Hilbert space , let denote the th symmetric tensor power of , which is the space of symmetric tensors. Note in particular that is spanned by the symmetric products of elements in . For , we define the symmetric product of these elements by
If we consider (as a subspace of , the kth tensor power of ) and define the inner product on accordingly, we find that for
Applying the Cauchy–Schwarz inequality, we find that , and that
Cycle covers
Any square matrix can be viewed as the adjacency matrix of a weighted directed graph on vertex set , 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 so represents a permutation on V. Conversely, any permutation on V corresponds to a cycle cover with arcs from each vertex i to vertex .
If the weight of a cycle-cover is defined to be the product of the weights of the arcs in each cycle, then
implying that
Thus the permanent of A is equal to the sum of the weights of all cycle-covers of the digraph.