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 &sigma; 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]]&nbsp;=&nbsp;[[sharp-P|#P]]''' which is an even stronger statement than '''[[P = NP problem|P&nbsp;=&nbsp; 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 &epsilon;''M'', where ''M'' is the value of the permanent and &epsilon; > 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]]