Permanent
215889
220015323
2008-06-17T21:53:19Z
Army1987
98802
wfy
{{otheruses}}
In [[linear algebra]], the '''permanent''' of a [[matrix (mathematics)|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''<sub>''i,j''</sub>) is defined as
:<math>\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.</math>
The sum here extends over all elements σ of the [[symmetric group]] S<sub>''n''</sub>, i.e. over all [[permutation]]s of the numbers 1, 2, ..., ''n''.
For example,
:<math>\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc.</math>
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 [[Expansion_by_minors|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.
== Applications ==
Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in [[combinatorics]]. The permanent describes the number of [[perfect matching]]s in a [[bipartite graph]]. More specifically, let ''G'' be a bipartite graph with [[vertex (graph theory)|vertices]] ''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>''n''</sub> on one side and ''B''<sub>1</sub>, ''B''<sub>2</sub>, ..., ''B''<sub>''n''</sub> on the other side. Then, ''G'' can be described by an ''n''-by-''n'' matrix ''A'' = (''a''<sub>''i,j''</sub>) where ''a''<sub>''i,j''</sub> = 1 if there is an [[graph theory|edge]] between the vertices ''A''<sub>''i''</sub> and ''B''<sub>''j''</sub> and ''a''<sub>''i,j''</sub> = 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 [[sharp-P-complete|#P-complete]] ([[Permanent is sharp-P-complete|proof]]). Thus, if the permanent can be computed in [[polynomial time]] by any method, then '''[[FP (complexity)|FP]] = [[sharp-P|#P]]''' which is an even stronger statement than '''[[P = NP problem|P = NP]]'''. When the entries of ''A'' are nonnegative, however, the permanent can be computed [[approximation algorithm|approximately]] in [[randomized algorithm|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==
The permanent and the [[determinant|determinant]] are both special cases of the '''[[immanant of a matrix|immanant]]''': Given a [[character theory|complex character]] <math>\chi: S_n\rightarrow\mathbb{C}</math> of the symmetric group <math>S_n</math>, the immanant corresponding to <math>\chi</math> of an ''n''-by-''n'' matrix ''A'' is
:<math>\operatorname{imm}_\chi(A)=\sum_{\sigma\in S_n}\chi(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}.</math>
The permanent is recovered from this definition by taking <math>\chi</math> to be the trivial character <math>\sigma\mapsto 1</math>, and the determinant is recovered by taking <math>\chi</math> to be the [[even and odd permutations|sign function]] <math>sgn</math>, which is the unique nontrivial one-dimensional [[character theory|irreducible character]] of <math>S_n</math>.
==See also==
*[[Determinant]]
*[[Immanant_of_a_matrix | Immanant]]
*[[Bapat-Beg theorem]], an application of permanent in [[order statistics]]
==References==
* Mark Jerrum, Alistair Sinclair, Eric Vigoda (2004) [http://doi.acm.org/10.1145/1008731.1008738 "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries"], ''Journal of the ACM,'' Volume 51, Pages 671--697
==External links==
*[http://mathworld.wolfram.com/Permanent.html Permanent at Mathworld]
*[http://planetmath.org/encyclopedia/Immanent.html Immanent at PlanetMath]
[[Category:Algebra]]
[[Category:Linear algebra]]
[[Category:Matrix theory]]
[[Category:Permutations]]
[[de:Permanente]]
[[fr:Permanent (mathématiques)]]
[[he:פרמננטה]]
[[pl:Permanent]]