Permanent

Permanent

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

: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}egin{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.

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

The permanent and the determinant are both special cases of the immanant: Given a complex character chi: S_n ightarrowmathbb{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.

ee also

*Determinant
* 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]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?
Synonyms:

Look at other dictionaries:

  • permanent — permanent …   Deutsch Wörterbuch

  • permanent — permanent, ente [ pɛrmanɑ̃, ɑ̃t ] adj. et n. • 1370; permegnant « stable » 1120; lat. permanens, p. prés. de permanere « demeurer jusqu au bout » 1 ♦ Qui dure, demeure sans discontinuer ni changer. ⇒ constant, stable. L essence permanente des… …   Encyclopédie Universelle

  • permanent — PERMANÉNT, Ă, permanenţi, te, adj. Care există, care durează mereu sau mult timp fără a se schimba, care se petrece fără întrerupere; necontenit, neîntrerupt. ♢ Ondulaţie permanentă (şi substantivat, n.) = ondulaţie a părului făcută printr un… …   Dicționar Român

  • permanent — per‧ma‧nent [ˈpɜːmənənt ǁ ˈpɜːr ] adjective 1. permanent contract/​job/​employment HUMAN RESOURCES a contract, job etc that is intended to continue for a long time or for ever: • The company has created 650 permanent jobs. • He is acting chief… …   Financial and business terms

  • Permanent — Сборник …   Википедия

  • permanent — permanent, ente (pèr ma nan, nan t ) adj. 1°   Qui dure sans changer. •   Vois tu, passant, couler cette onde, Et s écouler incontinent ? Ainsi fait la gloire du monde, Et rien que Dieu n est permanent, MALH. VI, 23. •   L homme n a point ici de… …   Dictionnaire de la Langue Française d'Émile Littré

  • Permanent — Per ma*nent, a. [L. permanens, entis, p. pr. of permanere to stay or remain to the end, to last; per + manere to remain: cf. F. permanent. See {Per }, and {Mansion}.] Continuing in the same state, or without any change that destroys form or… …   The Collaborative International Dictionary of English

  • permanent — Adj ständig, anhaltend erw. fach. (17. Jh.) Entlehnung. Entlehnt aus frz. permanent, dieses aus l. permanēns, dem PPräs. von l. permanēre ausharren, verbleiben , zu l. manēre bleiben und gr. per .    Ebenso nndl. permanent, ne. permanent, nschw.… …   Etymologisches Wörterbuch der deutschen sprache

  • permanent — I adjective abiding, ageless, ceaseless, changeless, chronic, confirmed, constant, continued, continuing, dateless, deep seated, durable, endless, enduring, engrafted, entrenched, established, eternal, everlasting, fast, fixed, immortal,… …   Law dictionary

  • permanent — early 15c., from M.Fr. permanent (14c.), from L. permanentem (nom. permanens) remaining, prp. of permanere endure, continue, stay to the end, from per through + manere stay (see MANSION (Cf. mansion)) …   Etymology dictionary

  • permanent — Adj. (Mittelstufe) ununterbrochen, die ganze Zeit dauernd Synonyme: fortwährend, pausenlos, ständig, unablässig, unentwegt, kontinuierlich (geh.) Beispiele: Sie haben permanente finanzielle Probleme. Er kommt permanent zu spät zur Schule …   Extremes Deutsch

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”