Permanent (matematică)
Permanentă este o algebră liniară instrument . Prin definiție, permanenta unei matrice pătrate de ordinul n este egală cu:
LA=(laeuj){\ displaystyle A = (a_ {ij})}
pe(LA)=∑σ∈Snu∏eu=1nulaeu,σ(eu).{\ displaystyle \ operatorname {per} (A) = \ sum _ {\ sigma \ in {\ mathfrak {S}} _ {n}} \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}.}Snu{\ displaystyle {\ mathfrak {S}} _ {n}}denotă grupul simetric al indicelui n . De exemplu :
pe(labvs.d)=lad+bvs..{\ displaystyle \ operatorname {per} {\ begin {pmatrix} a & b \\ c & d \ end {pmatrix}} = ad + bc.}
Legătură cu determinantul
Definiția este foarte apropiată de cea a determinantului unei matrice:
det(LA)=∑σ∈Snuε(σ)∏eu=1nulaeu,σ(eu){\ displaystyle \ operatorname {det} (A) = \ sum _ {\ sigma \ in {\ mathfrak {S}} _ {n}} \ varepsilon (\ sigma) \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}}unde ε (σ) este semnătura de permutare sigma. Putem observa că pentru toate n , semnătura și funcția constantă egale cu 1 sunt (până la izomorfism ) singurele morfisme ale grupurilor dintr- un grup abelian .
Snu{\ displaystyle {\ mathfrak {S}} _ {n}}
Proprietăți
Asemănări și diferențe cu determinantul
Permanentul poate fi văzut ca o formă n- liniară simetrică luând n vectori ca argumente (coloanele unei matrice). Există formule pentru permanent analoage cu cele ale determinantului:
- Permanenta transpunerii unei matrice este egală cu permanentul matricei.
- Există o formulă similară pentru extinderea unei permanente de-a lungul unei coloane: dacă , și este matricea obținută de la A prin îndepărtarea j- rândul lea și j- coloana a, atunci .LA=(laeuj){\ displaystyle A = (a_ {ij})}LAeuj{\ displaystyle A_ {ij}}per(LA)=∑eu=1nulaeujper(LAeuj){\ displaystyle {\ rm {per}} (A) = \ sum _ {i = 1} ^ {n} a_ {ij} {\ rm {per}} (A_ {ij})}
- Merită permanenta unei matrice de blocuri triunghiulare .LA=(LA1(0)LA2⋅(∗)LAk){\ displaystyle A = \ left ({\ begin {matrix} A_ {1} &&& (0) \\ & A_ {2} && \\ && \ cdot & \\ (*) &&& A_ {k} \\\ end {matrice}} \ dreapta)}per(LA)=∏eu=1kper(LAeu){\ displaystyle {\ rm {per}} (A) = \ prod _ {i = 1} ^ {k} {\ rm {per}} (A_ {i})}
Dar, spre deosebire de determinant, permanentul nu este multiplicativ.
Teoria graficelor
Permanenta matricei de adiacență a unui grafic bipartit este egală cu numărul de cuplări ale acestui grafic.
Limitele și conjectura lui Van der Waerden
În 1926, van der Waerden a conjecturat că permanența unei matrice bistochastice cu dimensiunea n este mai mare decât n ! / N n , valoare atinsă de matricea conținând doar 1 / n . Demonstrațiile acestui rezultat au fost publicate, în 1980 de B. Gyires, și în 1981 de GP Egorychev (folosind inegalitatea Alexandrov-Fenchel (en) ) și DI Falikman. Egorychev și Falikman au câștigat Premiul Fulkerson în 1982 pentru această dovadă.
Aspecte algoritmice
Permanentul este mult mai dificil de calculat decât determinantul. Nu există un analog al eliminării Gauss-Jordan pentru permanenți. Mai precis, problema calculării matricei permanente 0-1 poate fi văzută ca o problemă de numărare și aparține clasei de probleme # P-complete . Poate fi abordat în timp polinomial prin algoritmi probabilistici în cazul matricilor cu coeficienți pozitivi .
Formula lui Ryser
Formula Ryser datorită Herbert Ryser este un algoritm de calcul permanent bazat pe principiul incluziunii excludere , care poate fi formulată după cum urmează: Pentru o matrice obținută prin ștergerea coloanelor din oricare produsul sumelor liniilor . Fie suma pentru toate matricile . Asa de
LAk{\ displaystyle A_ {k}}k{\ displaystyle k}LA{\ displaystyle A}P(LAk){\ displaystyle P (A_ {k})}LAk{\ displaystyle A_ {k}}Σk{\ displaystyle \ Sigma _ {k}}P(LAk){\ displaystyle P (A_ {k})}LAk{\ displaystyle A_ {k}}
Permanent(LA)=∑k=0nu-1(-1)kΣk{\ displaystyle \ operatorname {perm} (A) = \ sum _ {k = 0} ^ {n-1} (- 1) ^ {k} \ Sigma _ {k}}.
Putem rescrie formula în funcție de intrările matricei după cum urmează:
Permanent(LA)=(-1)nu∑S⊆{1,...,nu}(-1)|S|∏eu=1nu∑j∈Slaeuj.{\ displaystyle \ operatorname {perm} (A) = (- 1) ^ {n} \ sum _ {S \ subseteq \ {1, \ dots, n \}} (- 1) ^ {| S |} \ prod _ {i = 1} ^ {n} \ sum _ {j \ in S} a_ {ij}.}Formula Ryser poate fi evaluată în operații artihmetice sau prin tratarea seturilor în ordinea dată de codul Gray .
O(2nu-1nu2){\ displaystyle O (2 ^ {n-1} n ^ {2})}O(2nu-1nu){\ displaystyle O (2 ^ {n-1} n)}S{\ displaystyle S}
Utilizare și aplicații
Spre deosebire de determinant, permanentul nu are o semnificație geometrică naturală. Se folosește în combinatorie , de exemplu pentru a demonstra lema căsătoriilor , și, de asemenea, în teoria graficelor .
Permanentul apare și în fizica teoretică , în special pentru studiul adsorbției ( modelul dimerului ), precum și în fizica statistică , cristalografia și chimia fizică .
Note și referințe
(fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia în
limba engleză intitulat
„ Permanent ” ( vezi lista autorilor ) .
-
(în) BL van der Waerden , „ Aufgabe 45 ” , Jber. Deutsch. Math.-Verein. , vol. 35,
1926, p. 117.
-
(în) B. Gyires , „ Sursa comună a mai multor inegalități referitoare la matrici dublu stochastice ” , Publicationses Mathematicae Universitatis Institutum Mathematicum Debreceniensis , vol. 27 Fără oase 3-4,
1980, p. 291-304 ( Recenzii matematice 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, p. 12 ( Recenzii matematice 602332 ).
-
(ru) GP Egorychev , „ Dovada conjecturii van der Waerden pentru permanenți ” , Akademiya Nauk SSSR , vol. 22, nr . 6,
nouăsprezece optzeci și unu, p. 65-71, 225 ( Recenzii matematice 638007 ).
-
(în) GP Egorychev , „ Soluția problemei lui van der Waerden pentru permanent ” , Advances in Mathematics , vol. 42, n o 3,
nouăsprezece optzeci și unu, p. 299-305 ( DOI 10.1016 / 0001-8708 (81) 90044-X , Recenzii matematice 642395 ).
-
(ru) DI Falikman , „ Dovada conjecturii van der Waerden privind permanentul unei matrici dublu stochastice ” , Akademiya Nauk Soyuza SSR , vol. 29, nr . 6,nouăsprezece optzeci și unu, p. 931-938, 957 ( Recenzii matematice 625097 ).
-
(în) „ Câștigătorii anteriori ai Premiului Fulkerson ” privind Societatea de Optimizare Matematică ,19 august 2012.
-
(în) Leslie G. Valiant , „ Complexitatea calculului permanentului ” , Informatică teoretică , Elsevier, vol. 8, n o 21979, p. 189-201 ( DOI 10.1016 / 0304-3975 (79) 90044-6 ).
-
(în) Mark Jerrum Alistair Sinclair și Eric Vigoda , " Un algoritm de aproximare a timpului polinomial pentru permanența unei matrice cu intrări non-negative " , Jurnalul ACM , vol. 51, nr . 4,2004, p. 671-697. Acest articol a câștigat Premiul Fulkerson în 2006 pentru Mark Jerrum , Alistair Sinclair și Eric Vigoda. A se vedea (în) „ Premiul Delbert Ray Fulkerson ” , pe site-ul AMS .
-
Herbert John Ryser , Matematică combinatorie , Mathematical Association of America , col. „Monografiile matematice Carus” ( nr . 14),1963
-
Jacobus Hendricus van Lint și Richard Michale Wilson , Un curs de combinatorie ,2001( ISBN 0-521-00601-5 ) , p. 99
-
(în) Eric W. Weisstein, Enciclopedia Concisă a Matematicii CRC , Boca Raton / Londra / New York etc., Chapman & Hall - CRC Press,2002( 1 st ed. 1998), 3252 p. ( ISBN 1-58488-347-2 ) , „Permanent”
-
Albert Nijenhuis și Herbert S. Wilf , Algoritmi combinatori , Academic Press ,1978
-
(în) VE Tarakanov , „Permanent” în Michiel Hazewinkel , Enciclopedia Matematicii , Springer ,2002( ISBN 978-1556080104 , citit online ).
Vezi și tu
Emanând dintr-o matrice
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">