The Full Wiki

Permanent: Wikis

  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

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 permanent and determinant are special cases of a more general function of a matrix called the immanant.

Contents

Definition

The permanent of an n-by-n matrix A = (ai,j) is defined as

 \operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.

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,

\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc.

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.

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.

Cycle covers

Any square matrix A = (aij) can be viewed as the adjacency matrix of a directed graph, with aij representing the weight of the edge from vertex i to vertex j. A cycle cover of a weighted directed graph is a collection of vertex-disjoint directed cycles in the graph that covers all nodes in the graph. Thus, each vertex i in the graph has a unique "successor" σ(i) in the cycle cover, and σ is a permutation on \{1,2,\dots,n\} where n is the number of vertices in the graph. Conversely, any permutation σ on \{1,2,\dots,n\} corresponds to a cycle cover in which there is an edge from vertex i to vertex σ(i) for each i.

If the weight of a cycle-cover is defined to be the product of the weights of the edges in each cycle, then

 \operatorname{Weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)}.

The permanent of an n \times n matrix A is defined as

 \operatorname{Perm}(A)=\sum_\sigma \prod_{i=1}^{n} a_{i,\sigma(i)}

where σ is a permutation over \{1,2,\dots,n\}. Thus the permanent of A is equal to the sum of the weights of all cycle-covers of the graph.

Perfect matchings

A square matrix A = (aij) can also be viewed as the biadjacency matrix of a bipartite graph which has vertices x_1, x_2, \dots, x_n on one side and y_1, y_2, \dots, y_n on the other side, with aij representing the weight of the edge from vertex xi to vertex yj. If the weight of a perfect matching σ that matches xi to yσ(i) is defined to be the product of the weights of the edges in the matching, then

 \operatorname{Weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)}.

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 aij 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 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 xi and yj 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.[1]

Computation of the permanent

The permanent is also 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.

See also

References

  1. ^ Dexter Kozen. The Design and Analysis of Algorithms. Springer-Verlag, New York, 1991. ISBN 9780387976877; pp. 141–142
  • 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  

External links


Simple English

Permanent used as an adjective usually means that something is very hard to get rid of or destroy. Permanent may also mean other things.









Got something to say? Make a comment.
Your name
Your email address
Message