permanent

Dictionary: per·ma·nent (pûr'mə-nənt) pronunciation

adj.

Lasting or remaining without essential change: "the universal human yearning for something permanent, enduring, without shadow of change" (Willa Cather).
Not expected to change in status, condition, or place: a permanent address; permanent secretary to the president.

n.
Any of several long-lasting hair styles usually achieved by chemical applications which straighten, curl, or wave the hair.

[Middle English, from Old French, from Latin permanēns, permanent-, present participle of permanēre, to endure : per-, throughout; see per- + manēre, to remain.]

permanently per'ma·nent·ly adv.
permanentness per'ma·nent·ness n.

Search unanswered questions...

Browse: Unanswered questions | Most-recent questions | Reference library

5min Related Video:

permanent

Top

Thesaurus:

permanent

Top

adjective

See

permanent

Top

adj

Definition: constant, lasting
Antonyms: ephemeral, fleeting, temporary

Dental Dictionary:

permanent

Top

adj

Of a lasting or durable nature (opposite of temporary).

Word Tutor:

permanent

Top

IN BRIEF: Lasting or meant to last for a very long time; not temporary or changing.

There is nothing permanent except change. — Heraclitus (c.540-c.475 BC)

Wikipedia:

Permanent

Top

For other uses, see Permanent (disambiguation).

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.

1 Definition
2 Properties and applications
3 Computation of the permanent
4 See also
5 References
6 External links

Definition

The permanent of an n-by-n matrix A = (a_i,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 S_n, 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 = (a i j)$ can be viewed as the adjacency matrix of a directed graph, with $a i j$ 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 = (a i j)$ 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 $a i j$ representing the weight of the edge from vertex $x i$ to vertex $y j$ . If the weight of a perfect matching $σ$ that matches $x i$ 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 $a i j$ 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 a_i,j = 1 if there is an edge between the vertices $x i$ and $y j$ and a_i,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

Main articles: Computation of the permanent of a matrix and Permanent is sharp-P-complete

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.

References

^ 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

Permanent at PlanetMath

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Misspellings:

permanent

Top

Common misspelling(s) of permanent

permenant

Translations:

permanent

Top

Permanent

Dansk (Danish)
adj. - varig, vedvarende
n. - fast pensionær

idioms:

permanent address fast adresse
permanent press permanent pres
permanent set permanent ændring i materiale, der har været udsat for pres
permanent tooth blivende tand
permanent wave permanentbølger

Nederlands (Dutch)
permanent, werknemer in vaste dienst

Français (French)
adj. - permanent, continuel, durable, constant, définitif, (contrat) à durée indéterminée
n. - permanente

idioms:

permanent address adresse permanente
permanent press à pli permanent
permanent set changement irréversible (d'un matériel après avoir été exposé)
permanent tooth dent permanente
permanent wave permanente

Deutsch (German)
n. - Dauerwelle
adj. - permanent, ständig, Dauer-

idioms:

permanent address feste Wohnadresse
permanent press chem. Stoffbehandlung gegen Knittern
permanent set bleibende Dehnung od. Durchbiegung
permanent tooth zweite Zähne
permanent wave Dauerwelle

Ελληνική (Greek)
n. - περμανάντ
adj. - μόνιμος, διαρκής

idioms:

permanent address (ταχυδρομική) διεύθυνση μόνιμης κατοικίας
permanent press χημική επεξεργασία υφάσματος για μόνιμες πιέτες
permanent set μόνιμη/σταθερή φόρμα
permanent tooth μόνιμο δόντι
permanent wave περμανάντ

Italiano (Italian)
permanente, durevole, fisso

idioms:

permanent address indirizzo legale, residenza
permanent press tessuto non-stiro
permanent set condizione permanente
permanent tooth dente definitivo
permanent wave permanente

Português (Portuguese)
n. - penteado permanente (m), pessoa ou coisa permanente
adj. - permanente

idioms:

permanent address endereço permanente
permanent press vinco permanente
permanent set deformação permanente
permanent tooth dentes permanentes
permanent wave penteado permanente

Русский (Russian)
постоянный, стабильный, неизменный, перманентная завивка

idioms:

permanent address постоянный адрес
permanent press не требующий глажки
permanent set постоянное искажение после травмы
permanent tooth постоянный натуральный зуб
permanent wave перманентная завивка

Español (Spanish)
adj. - permanente, estable, fijo, inalterable
n. - permanente, ondulación permanente

idioms:

permanent address domicilio fijo o permanente
permanent press (pantalones) con raya permanente, inarrugable
permanent set deformación permanente
permanent tooth diente permanente
permanent wave ondulado permanente

Svenska (Swedish)
n. - permanent
adj. - bestående, varaktig, ordinarie, fast

中文（简体）(Chinese (Simplified))
永久的, 固定的, 不变的, 烫发

idioms:

permanent address 永久地址
permanent press 免烫
permanent set 永久变形
permanent tooth 恒齿, 永久齿
permanent wave 电烫, 烫发, 永久波

中文（繁體）(Chinese (Traditional))
adj. - 永久的, 固定的, 不變的
n. - 燙髮

idioms:

permanent address 永久地址
permanent press 免燙
permanent set 永久變形
permanent tooth 恆齒, 永久齒
permanent wave 電燙, 燙髮, 永久波

한국어 (Korean)
adj. - 영속하는, 상설의, 종신의
n. - 파마

日本語 (Japanese)
adj. - 永久の, 常置の, 常設の

idioms:

permanent address パーマネントアドレス
permanent press パーマネントプレス加工
permanent set 永久ひずみ
permanent tooth 永久歯
permanent wave パーマネント, パーマ

العربيه (Arabic)
‏(الاسم) دائم, مستمر, ثابت, تمويجه دائمه لشعر المرأة (صفه) مستمر‏

עברית (Hebrew)
adj. - ‮קיים, קבוע, תמידי‬
n. - ‮סלסול תמידי‬

If you are unable to view some languages clearly, click here.

To select your translation preferences click here.

Best of the Web:

permanent

Top

Some good "permanent" pages on the web:

Math
mathworld.wolfram.com

Shopping:

permanent

Top

permanent	Color Hair Permanent Red
permanent eyelashes	Semi Permanent Hair Colors

Learn More

	erasable
	evanescent
	temporary

	How can you prove how permanent are permanent markers? Read answer...
	What makes a permanent marker permanent? Read answer...
	Is a permanent magnet permanent? Read answer...

Help us answer these

	Are permanent makers really permanent?
	What is a permanent?
	How permanent are permanents markers?

Post a question - any question - to the WikiAnswers community:

Copyrights:

		Dictionary. The American Heritage® Dictionary of the English Language, Fourth Edition Copyright © 2007, 2000 by Houghton Mifflin Company. Updated in 2009. Published by Houghton Mifflin Company. All rights reserved. Read more
		Thesaurus. Roget's II: The New Thesaurus, Third Edition by the Editors of the American Heritage® Dictionary Copyright © 1995 by Houghton Mifflin Company. Published by Houghton Mifflin Company. All rights reserved. Read more
		Antonyms. © 1999-2009 by Answers Corporation. All rights reserved. Read more
		Dental Dictionary. Mosby's Dental Dictionary. Copyright © 2004 by Elsevier, Inc. All rights reserved. Read more
		Word Tutor. Copyright © 2004-present by eSpindle Learning, a 501(c) nonprofit organization. All rights reserved. eSpindle provides personalized spelling and vocabulary tutoring online; free trial. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Permanent". Read more
		Misspellings. © 1999-2009 by Answers Corporation. All rights reserved. Read more
		Translations. Copyright © 2007, WizCom Technologies Ltd. All rights reserved. Read more

permanent

permanent

permanent

permanent

permanent

permanent

Permanent

Contents

Definition

Properties and applications

Cycle covers

Perfect matchings

0-1 permanents: counting in unweighted graphs

Computation of the permanent

See also

References

External links

permanent

permanent

permanent

permanent