Pysyvä (matematiikka)
Pysyvä on lineaarialgebraa työkalu . Määritelmän mukaan pysyvä on neliömatriisi järjestyksen n on yhtä suuri kuin on:
AT=(kloij){\ displaystyle A = (a_ {ij})}
per(AT)=∑σ∈Sei∏i=1eikloi,σ(i).{\ displaystyle \ operaattorinimi {per} (A) = \ summa _ {\ sigma \ muodossa {\ mathfrak {S}} _ {n}} \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}.}Sei{\ displaystyle {\ mathfrak {S}} _ {n}}tarkoittaa indeksin n symmetristä ryhmää . Esimerkiksi :
per(klobvs.d)=klod+bvs..{\ displaystyle \ operaattorin nimi {per} {\ begin {pmatrix} a & b \\ c & d \ end {pmatrix}} = ad + bc.}
Yhteys determinanttiin
Määritelmä on hyvin lähellä matriisin determinantin määritelmää :
det(AT)=∑σ∈Seie(σ)∏i=1eikloi,σ(i){\ displaystyle \ operaattorinimi {det} (A) = \ summa _ {\ sigma \ in {\ mathfrak {S}} _ {n}} \ varepsilon (\ sigma) \ prod _ {i = 1} ^ {n} a_ {i, \ sigma (i)}}jossa ε (σ) on allekirjoitus on permutaatio σ. Huomaamme, että kaikilla n , allekirjoitus ja Vakiofunktion on 1 ovat (jopa jotta isomorfismi ) ainoa morphisms ryhmien ja käytettäessä Abelin ryhmä .
Sei{\ displaystyle {\ mathfrak {S}} _ {n}}
Ominaisuudet
Yhtäläisyydet ja erot determinantin kanssa
Pysyvä voidaan nähdä muodossa n- lineaarinen symmetrinen, jossa argumentteina otetaan n vektoria (matriisin sarakkeet). Pysyvälle on olemassa kaavat, jotka ovat analogisia determinantin kanssa:
- Matriisin transposion pysyvyys on yhtä suuri kuin matriisin pysyvä.
- On samanlainen kaava laajentamiseen pysyvä pitkin sarake: jos , ja on matriisi saadaan poistamalla i- nnen rivin ja J : nnen sarakkeen, sitten .AT=(kloij){\ displaystyle A = (a_ {ij})}ATij{\ displaystyle A_ {ij}}ser(AT)=∑i=1eikloijser(ATij){\ displaystyle {\ rm {per}} (A) = \ summa _ {i = 1} ^ {n} a_ {ij} {\ rm {per}} (A_ {ij})}
- Kolmion muotoisen lohkomatriisin pysyvä arvo on .AT=(AT1(0)AT2⋅(∗)ATk){\ displaystyle A = \ left ({\ begin {matrix} A_ {1} &&& (0) \\ & A_ {2} && \\ && \ cdot & \\ (*) &&& A_ {k} \\\ end {matriisi}} \ oikea)}ser(AT)=∏i=1kser(ATi){\ displaystyle {\ rm {per}} (A) = \ prod _ {i = 1} ^ {k} {\ rm {per}} (A_ {i})}
Mutta toisin kuin determinantti, pysyvä ei ole kerrottava.
Kuvaajateoria
Kahdenvälisen kuvaajan vierekkäisyysmatriisin pysyvyys on yhtä suuri kuin tämän kaavion kytkentöjen lukumäärä.
Van der Waerdenin rajat ja oletus
Vuonna 1926 van der Waerden arveli, että ulottuvuuden n bistokastisen matriisin pysyvyys on suurempi kuin n ! / N n , arvo, jonka matriisi saavuttaa vain 1 / n . Osoituksia tästä tuloksesta julkaisi vuonna 1980 B. Gyires ja vuonna 1981 GP Egorychev (käyttäen Alexandrov-Fenchelin eriarvoisuutta (en) ) ja DI Falikman. Egorychev ja Falikman voittivat Fulkerson-palkinnon vuonna 1982 tästä todisteesta.
Algoritmiset näkökohdat
Pysyvä on paljon vaikeampi laskea kuin determinantti. Pysyville ei ole analogia Gauss-Jordan-eliminaatiosta . Tarkemmin sanottuna matriisin pysyvän 0-1 laskemisen ongelma voidaan nähdä laskentaongelmana ja se kuuluu # P-täydellinen- ongelmien luokkaan . Se voidaan lähestyä sisään polynomiajassa mukaan todennäköisyyspohjaista algoritmit tapauksessa matriisit positiivisia kertoimia .
Ryserin kaava
Kaava Ryser vuoksi Herbert Ryser on pysyvä laskenta-algoritmin, joka perustuu sisällyttäminen-kieltosääntö , joka voidaan muotoilla seuraavasti: Jos matriisi , joka on saatu poistamalla sarakkeita joko tuotteen summien linjat . Antaa olla kaikkien matriisien summa . Niin
ATk{\ displaystyle A_ {k}}k{\ displaystyle k}AT{\ displaystyle A}P(ATk){\ displaystyle P (A_ {k})}ATk{\ displaystyle A_ {k}}Σk{\ displaystyle \ Sigma _ {k}}P(ATk){\ displaystyle P (A_ {k})}ATk{\ displaystyle A_ {k}}
Permanentti(AT)=∑k=0ei-1(-1)kΣk{\ displaystyle \ operaattorin nimi {perm} (A) = \ summa _ {k = 0} ^ {n-1} (- 1) ^ {k} \ Sigma _ {k}}.
Voimme kirjoittaa kaavan uudelleen matriisin tulojen mukaan seuraavasti:
Permanentti(AT)=(-1)ei∑S⊆{1,...,ei}(-1)|S|∏i=1ei∑j∈Skloij.{\ displaystyle \ operaattorin nimi {perm} (A) = (- 1) ^ {n} \ summa _ {S \ subseteq \ {1, \ pisteet, n \}} (- 1) ^ {| S |} \ prod _ {i = 1} ^ {n} \ summa _ {j \ S} a_ {ij}.}Ryserin kaava voidaan arvioida arteettisissa operaatioissa tai käsittelemällä sarjoja Gray-koodin antamassa järjestyksessä .
O(2ei-1ei2){\ displaystyle O (2 ^ {n-1} n ^ {2})}O(2ei-1ei){\ displaystyle O (2 ^ {n-1} n)}S{\ displaystyle S}
Käyttö ja sovellukset
Toisin kuin determinantti, pysyvällä ei ole luonnollista geometrista merkitystä. Sitä käytetään yhdistelmissä , esimerkiksi avioliittojen lemman todistamiseksi , ja myös graafiteoriassa .
Pysyvä esiintyy myös teoreettisessa fysiikassa , erityisesti adsorptiotutkimuksessa ( dimeerimalli ), sekä tilastollisessa fysiikassa , kristallografiassa ja fysikaalisessa kemiassa .
Huomautuksia ja viitteitä
(fr) Tämä artikkeli on osittain tai kokonaan otettu Wikipedian
englanninkielisestä artikkelista
" Pysyvä " ( katso kirjoittajaluettelo ) .
-
(in) BL van der Waerden , " Aufgabe 45 " , Jber. Deutsch. Math.-Verein. , voi. 35,
1926, s. 117.
-
(in) B. Gyires , " yhteinen lähde on useita eroja concernant kaksinkertaisesti stokastisia matriiseja " , Publicationes Mathematicae Universitatis Institutum Mathematicum Debreceniensis , voi. 27 Ei luita 3-4,
1980, s. 291-304 ( matemaattiset arvostelut 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 ( Matemaattiarvostelut 602332 ).
-
(ru) GP Egorychev , " Todiste van der Waerdenin oletuksista pysyville " , Akademiya Nauk SSSR , voi. 22, n ° 6,
yhdeksäntoista kahdeksankymmentäyksi, s. 65-71, 225 ( matemaattiset arvostelut 638007 ).
-
(sisään) GP Egorychev , " Van der Waerdenin ongelman ratkaisu pysyväksi " , Advances in Mathematics , voi. 42, n ° 3,
yhdeksäntoista kahdeksankymmentäyksi, s. 299-305 ( DOI 10.1016 / 0001-8708 (81) 90044-X , matemaattiset arvostelut 642395 ).
-
(ru) DI Falikman , " Todiste kaksinkertaisen stokastisen matriisin pysyvyydestä tehdystä van der Waerdenin olettamuksesta " , Akademiya Nauk Soyuza SSR , voi. 29, n ° 6,yhdeksäntoista kahdeksankymmentäyksi, s. 931-938, 957 ( matemaattiset arvostelut 625097 ).
-
(in) " Past voittajat Fulkerson palkinnon " on matemaattisen optimoinnin Society ,19. elokuuta 2012.
-
(in) Leslie G. Valiant , " monimutkaisuus Computing pysyvän " , Tietojenkäsittelyteorian , Elsevier, vol. 8, n o 21979, s. 189-201 ( DOI 10.1016 / 0304-3975 (79) 90044-6 ).
-
(in) Mark Jerrum Alistair Sinclair ja Eric Vigoda , " polynomiaikainen approksimaatio algoritmi pysyvästä on matriisi, jossa on positiivinen merkinnät " , Journal of ACM , voi. 51, n o 4,2004, s. 671-697. Tämä artikkeli voitti Fulkerson-palkinnon vuonna 2006 Mark Jerrumille , Alistair Sinclairille ja Eric Vigodalle. Katso (in) " Delbert Ray Fulkerson -palkinto " AMS : n sivustolta .
-
Herbert John Ryser , Combinatorial matematiikka , matemaattinen Association of America , Coll. "Carus Matemaattinen Monographs" ( n o 14),1963
-
Jacobus Hendricus van Lint ja Richard Michale Wilson , kurssi kombinaattoreissa ,2001( ISBN 0-521-00601-5 ) , s. 99
-
(in) Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics , Boca Raton / Lontoo / New York jne Chapman & Hall - CRC Press,2002( 1 st toim. 1998), 3252 s. ( ISBN 1-58488-347-2 ) , "Pysyvä"
-
Albert Nijenhuis ja Herbert S. Wilf , yhdistävät algoritmit , Academic Press ,1978
-
(in) VE Tarakanov , "pysyvä" in Michiel Hazewinkel , Encyclopedia of Matematiikka , Springer ,2002( ISBN 978-1556080104 , lue verkossa ).
Katso myös
Emaaminen matriisista
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">