Added to Favorites

Related Searches

Definitions

Nearby Words

Related Questions

In linear algebra, the permanent of a matrix is a function of a matrix related to the determinant. The permanent as well as the determinant are polynomials of the entries of the matrix.
## Definition

The permanent of an n-by-n matrix A = (a_{i,j}) is defined as## Applications

Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in combinatorics. The permanent describes the number of perfect matchings in a bipartite graph. More specifically, let G be a bipartite graph with vertices A_{1}, A_{2}, ..., A_{n} on one side and B_{1}, B_{2}, ..., B_{n} on the other side. Then, G can be described by an n-by-n matrix A = (a_{i,j}) where a_{i,j} = 1 if there is an edge between the vertices A_{i} and B_{j} and a_{i,j} = 0 otherwise. The permanent of this matrix is equal to the number of perfect matchings in the graph.
## Complexity

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 (proof). 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. Because the permanent is random self-reducible, these results hold out even for average-case inputs.
## Immanant

## See also

## References

## External links

- $operatorname\{perm\}(A)=sum\_\{sigmain\; S\_n\}prod\_\{i=1\}^n\; a\_\{i,sigma(i)\}.$

The sum here extends over all elements σ of the symmetric group S_{n}, i.e. over all permutations of the numbers 1, 2, ..., n.

For example,

- $operatorname\{perm\}begin\{pmatrix\}a\&b\; c\&dend\{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.

The permanent and the determinant are both special cases of the immanant: Given a complex character $chi:\; S\_nrightarrowmathbb\{C\}$ of the symmetric group $S\_n$, the immanant corresponding to $chi$ of an n-by-n matrix A is

- $operatorname\{imm\}\_chi(A)=sum\_\{sigmain\; S\_n\}chi(sigma)prod\_\{i=1\}^n\; a\_\{i,sigma(i)\}.$

The permanent is recovered from this definition by taking $chi$ to be the trivial character $sigmamapsto\; 1$, and the determinant is recovered by taking $chi$ to be the sign function $sgn$, which is the unique nontrivial one-dimensional irreducible character of $S\_n$.

- Determinant
- Immanant
- Bapat-Beg theorem, an application of permanent in order statistics

- Mark Jerrum, Alistair Sinclair, Eric Vigoda (2004) "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", Journal of the ACM, Volume 51, Pages 671--697

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday June 17, 2008 at 14:53:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday June 17, 2008 at 14:53:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.