Permanent (matematik)
Den permanente er et lineært algebraværktøj . Per definition er permanent af en firkantet matrix af rækkefølge n lig med:
PÅ=(påjegj){\ displaystyle A = (a_ {ij})}
om(PÅ)=∑σ∈Sikke∏jeg=1ikkepåjeg,σ(jeg).{\ displaystyle \ operatorname {per} (A) = \ sum _ {\ sigma \ in {\ mathfrak {S}} _ {n}} \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (jeg)}.}Sikke{\ displaystyle {\ mathfrak {S}} _ {n}}betegner den symmetriske gruppe af indeks n . For eksempel :
om(påbvs.d)=påd+bvs..{\ displaystyle \ operatorname {per} {\ begin {pmatrix} a & b \\ c & d \ end {pmatrix}} = annonce + bc.}
Forbind med determinanten
Definitionen er meget tæt på en matrixs determinant :
det(PÅ)=∑σ∈Sikkeε(σ)∏jeg=1ikkepåjeg,σ(jeg){\ displaystyle \ operatorname {det} (A) = \ sum _ {\ sigma \ in {\ mathfrak {S}} _ {n}} \ varepsilon (\ sigma) \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}}hvor ε (σ) er signaturen for permutationen σ. Vi kan bemærke, at for alle n , signaturen og konstant funktion lig med 1 er (op til isomorfi ) de eneste morfier på grupper af i en abelsk gruppe .
Sikke{\ displaystyle {\ mathfrak {S}} _ {n}}
Ejendomme
Ligheder og forskelle med determinanten
Det permanente kan ses som en form n - lineær symmetrisk, der tager n vektorer som argumenter (kolonnerne i en matrix). Der er formler for den permanente, analoge med determinantens:
- Det permanente ved transponering af en matrix er lig med det permanente i matrixen.
- Der er en lignende formel til at udvide en permanent langs en søjle: hvis , og er matricen opnået fra A ved at fjerne den i. Række og j. Søjle, så .PÅ=(påjegj){\ displaystyle A = (a_ {ij})}PÅjegj{\ displaystyle A_ {ij}}ser(PÅ)=∑jeg=1ikkepåjegjser(PÅjegj){\ displaystyle {\ rm {per}} (A) = \ sum _ {i = 1} ^ {n} a_ {ij} {\ rm {per}} (A_ {ij})}
- Det permanente i en trekantet blokmatrix er værd .PÅ=(PÅ1(0)PÅ2⋅(∗)PÅk){\ displaystyle A = \ left ({\ begin {matrix} A_ {1} &&& (0) \\ & A_ {2} && \\ && \ cdot & \\ (*) &&& A_ {k} \\\ end {matrix}} \ højre)}ser(PÅ)=∏jeg=1kser(PÅjeg){\ displaystyle {\ rm {per}} (A) = \ prod _ {i = 1} ^ {k} {\ rm {per}} (A_ {i})}
Men i modsætning til determinanten er den permanente ikke multiplikativ.
Grafteori
Den permanente af adjacency matrix af en bipartit graf er lig med antallet af koblinger i denne graf.
Van der Waerden's grænser og formodninger
I 1926 formodede van der Waerden, at den permanente i en bistokastisk matrix af dimension n er større end n ! / N n , en værdi, der nås af matrixen, og som kun indeholder 1 / n . Demonstrationer af dette resultat blev offentliggjort i 1980 af B. Gyires og i 1981 af GP Egorychev (ved hjælp af ulighed Alexandrov-Fenchel (en) ) og DI Falikman. Egorychev og Falikman vandt Fulkerson- prisen i 1982 for dette bevis.
Algoritmiske aspekter
Det permanente er meget sværere at beregne end determinanten. Der er ingen analog med Gauss-Jordan eliminering for permanente. Mere præcist kan problemet med beregning af matrixen permanent 0-1 ses som et tælleproblem og tilhører klassen af # P-komplette problemer . Det kan kontaktes i polynomisk tid af sandsynlige algoritmer i tilfælde af matricer med positive koefficienter .
Rysers formel
Den formel Ryser grund Herbert Ryser er en permanent beregning algoritme baseret på princippet inklusion-eksklusion , som kan formuleres på følgende måde: For en matrix opnået ved at slette kolonner i enten produktet af summerne af linjerne . Lad være summen af for alle matricer . Så
PÅk{\ displaystyle A_ {k}}k{\ displaystyle k}PÅ{\ displaystyle A}P(PÅk){\ displaystyle P (A_ {k})}PÅk{\ displaystyle A_ {k}}Σk{\ displaystyle \ Sigma _ {k}}P(PÅk){\ displaystyle P (A_ {k})}PÅk{\ displaystyle A_ {k}}
Perm(PÅ)=∑k=0ikke-1(-1)kΣk{\ displaystyle \ operatorname {perm} (A) = \ sum _ {k = 0} ^ {n-1} (- 1) ^ {k} \ Sigma _ {k}}.
Vi kan omskrive formlen i henhold til matrixens input som følger:
Perm(PÅ)=(-1)ikke∑S⊆{1,...,ikke}(-1)|S|∏jeg=1ikke∑j∈Spåjegj.{\ displaystyle \ operatorname {perm} (A) = (- 1) ^ {n} \ sum _ {S \ subseteq \ {1, \ dots, n \}} (- 1) ^ {| S |} \ prod _ {i = 1} ^ {n} \ sum _ {j \ i S} a_ {ij}.}Rysers formel kan evalueres i artihmetiske operationer eller ved at behandle sætene i den rækkefølge, der er angivet med den grå kode .
O(2ikke-1ikke2){\ displaystyle O (2 ^ {n-1} n ^ {2})}O(2ikke-1ikke){\ displaystyle O (2 ^ {n-1} n)}S{\ displaystyle S}
Brug og applikationer
I modsætning til determinanten har den permanente ingen naturlig geometrisk betydning. Det bruges i kombinatorik , for eksempel til at bevise ægteskabets lemma , og også i grafteori .
Den permanente forekommer også i teoretisk fysik , især til undersøgelse af adsorption ( dimermodel ) såvel som i statistisk fysik , krystallografi og fysisk kemi .
Noter og referencer
(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på
engelsk med titlen
" Permanent " ( se listen over forfattere ) .
-
(i) BL van der Waerden , " Aufgabe 45 " , Jber. Deutsch. Math.-Verein. , Vol. 35,
1926, s. 117.
-
(in) B. Gyires , " Den fælles kilde til flere uligheder, der vedrører dobbelt stokastiske matricer " , Publikationer Mathematicae Universitatis Institutum Mathematicum Debreceniensis , bind. 27 Ingen knogler 3-4,
1980, s. 291-304 ( Matematikanmeldelser 604006 ).
-
(ru) GP Egoryčev , " Reshenie problemy van-der-Vardena dlya permanentov " , Akademiya Nauk Soyuza SSR , Krasnoyarsk, Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz.,
1980, s. 12 ( Matematikanmeldelser 602332 ).
-
(ru) GP Egorychev , ” Bevis for van der Waerden formodninger for permanente ” , Akademiya Nauk SSSR , vol. 22, nr . 6,
nitten og firs, s. 65-71, 225 ( matematikanmeldelser 638007 ).
-
(in) GP Egorychev , " Løsningen af van der Waerden's problem for permanent " , Advances in Mathematics , bind. 42, nr . 3,
nitten og firs, s. 299-305 ( DOI 10.1016 / 0001-8708 (81) 90044-X , matematikanmeldelser 642395 ).
-
(ru) DI Falikman , " Bevis for van der Waerden-formodningen om permanent af en dobbelt stokastisk matrix " , Akademiya Nauk Soyuza SSR , bind. 29, nr . 6,nitten og firs, s. 931-938, 957 ( matematikanmeldelser 625097 ).
-
(i) " Tidligere Vindere af Fulkerson Prize " på Matematisk optimering Society ,19. august 2012.
-
(i) Leslie G. Valiant , " Kompleks Computing den permanente " , Teoretisk datalogi , Elsevier, vol. 8, nr . 21979, s. 189-201 ( DOI 10.1016 / 0304-3975 (79) 90044-6 ).
-
(i) Mark Jerrum Alistair Sinclair og Eric Vigoda , " Et polynomium-tid tilnærmelse algoritme til endelig af en matrix med nonnegative firmaer " , Journal of ACM , vol. 51, nr . 4,2004, s. 671-697. Denne artikel vandt Fulkersonprisen i 2006 til Mark Jerrum , Alistair Sinclair og Eric Vigoda. Se (i) " Delbert Ray Fulkerson Prize " , på det sted, hvor AMS .
-
Herbert John Ryser , Combinatorial Mathematics , Mathematical Association of America , koll. "The Carus Mathematical Monographs" ( nr . 14),1963
-
Jacobus Hendricus van Lint og Richard Michale Wilson , et kursus i kombinatorik ,2001( ISBN 0-521-00601-5 ) , s. 99
-
(i) Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics , Boca Raton / London / New York osv, Chapman & Hall - CRC Press,2002( 1 st ed. 1998), 3252 s. ( ISBN 1-58488-347-2 ) , "Permanent"
-
Albert Nijenhuis og Herbert S. Wilf , kombinatoriske algoritmer , Academic Press ,1978
-
(in) VE Tarakanov , "Permanent" i Michiel Hazewinkel , Encyclopedia of Mathematics , Springer ,2002( ISBN 978-1556080104 , læs online ).
Se også
Emanererende fra en matrix
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">