Pysyvä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24.5.2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Pysyvä matematiikassa on numeerinen funktio , joka on määritelty kaikkien matriisien joukolle ; neliömatriiseille se on samanlainen kuin determinantti , ja eroaa siitä vain siinä, että laajennuksessa permutaatioihin (tai molliin ) ei oteta vuorottelevia merkkejä, vaan kaikki plussat. Toisin kuin determinantti, pysyvän määritelmä ulotetaan myös ei-neliömatriiseihin.

Kirjallisuudessa käytetään yleensä jotakin seuraavista merkinnöistä osoittamaan pysyvää: , tai . $\mathrm {Per} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Määritelmä

Neliomatriisi pysyvä

Antaa olla kooltaan neliömatriisi , jonka alkiot kuuluvat johonkin kenttään . Lukua kutsutaan pysyväksi matriisiksi : $A$ $n\ kertaa n$ $a_{i,j}$ $K$ $A$

\mathrm {Per} (A)=\sum _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\ summa _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}}

jossa summa otetaan kaikkiin numeroiden permutaatioihin 1:stä . $\pi$ $n$

Esimerkiksi koon matriisille : ${\näyttötyyli 2\kertaa 2}$

\mathrm {Per} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

Tämä määritelmä eroaa vastaavasta determinantin määritelmästä vain siinä, että determinantissa joillakin summan termeillä on negatiivinen etumerkki, riippuen permutaation etumerkistä . $\pi$

Suorakulmamatriisi pysyvä

Pysyvän käsite laajenee joskus mielivaltaisen suorakaiteen muotoisen matriisin tapaukseen seuraavalla tavalla. Jos , niin: $A$ $m\ kertaa n$ $m<n$

\mathrm {Per} (A)=\sum _{\pi }\prod _{i=1}^{m}a_{i,\pi _{i}}

jossa summa otetaan kaikkien elementtien sijoitteluihin numerojoukosta 1 - . $m$ $n$

Jos , niin: $m>n$

\mathrm {Per} (A)=\mathrm {Per} (A^{T})

Tai vastaavasti suorakaiteen muotoisen matriisin pysyvä voidaan määritellä kaikkien sen järjestyksen neliömäisten alimatriisien pysyvien summaksi . ${\näyttötyyli \min\{\,n,m\,\))$

Ominaisuudet

Minkä tahansa diagonaalin tai kolmion matriisin pysyvä on yhtä suuri kuin sen diagonaalin elementtien tulo. Erityisesti nollamatriisin pysyvä on yhtä suuri kuin nolla ja identiteettimatriisin pysyvä on yhtä suuri kuin yksi.

Pysyvä ei muutu transponoitaessa : . Toisin kuin determinantti, matriisin pysyvä ei muutu matriisin rivien tai sarakkeiden permutaatiosta. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Pysyvä on matriisin rivien (tai sarakkeiden) lineaarinen funktio , joka on:

jos kerrot minkä tahansa rivin (sarakkeen) tietyllä luvulla , pysyvän arvo kasvaa kertoimella; $c$ $c$
kahden vain yhdellä rivillä (sarakkeella) eroavan matriisin summan pysyvä on yhtä suuri kuin niiden pysyvien summa.

Laplace-laajennuksen analogi pysyvän matriisin ensimmäiselle riville:

{\displaystyle \mathrm {Per} (A)=\sum _{j=1}^{n}a_{1,j}B_{1,j))

missä on matriisin pysyvä, joka saadaan poistamalla -. rivi ja -: s sarake. Joten esimerkiksi kokomatriisille pätee seuraava: ${\näyttötyyli B_{i,j))$ $A$ $i$ $j$ $3 kertaa 3$

\mathrm {Per} {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32} &a_{33}\end{pmatrix}}=a_{11}\mathrm {Per} {\begin{pmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{pmatrix}} +a_{12}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{23}\\a_{31}&a_{33}\end{pmatrix}}+a_{13}\mathrm {Per} {\begin{pmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{pmatrix}}

Pysyvä järjestysmatriisi on homogeeninen järjestysfunktio : $n$ $n$

\mathrm {Per} (c\cdot A)=c^{n}\cdot \mathrm {Per} (A)

, missä on skalaari.

c\in K

Jos on permutaatiomatriisi , niin: $P$

\mathrm {Per} (P)=1

;

\mathrm {Per} (AP)=\mathrm {Per} (PA)=\mathrm {Per} (A)

mille tahansa saman järjestyksen matriisille.

A

Jos matriisi koostuu ei-negatiivisista reaaliluvuista, niin . $A$ $\mathrm {Per} (A)\geqslant \det A$

Jos ja ovat kaksi ylempää (tai alempaa) kolmiomatriisia , niin: $A$ $B$

\mathrm {Per} (AB)=\mathrm {Per} (BA)=\mathrm {Per} (A)\cdot \mathrm {Per} (B)

(yleisessä tapauksessa tasa-arvo ei päde mielivaltaisille ja , toisin kuin determinanttien analoginen ominaisuus). $A$ $B$

Ainakin kaksinkertaisesti stokastisen järjestysmatriisin pysyvä ( van der Waerdenin olettamus , todistettu vuonna 1980). $n$ $n!/n^{n}$

Lasketaan pysyvää

Toisin kuin determinantti, joka voidaan helposti laskea esimerkiksi Gaussin menetelmällä , pysyvän laskenta on hyvin aikaa vievä laskentatehtävä, joka kuuluu #P-täydisten ongelmien kompleksisuusluokkaan . Se pysyy #P-täydellinen jopa matriiseille, jotka koostuvat vain noloista ja ykkösistä [1] .

Tällä hetkellä[ selventää ] ei ole tunnettua algoritmia tällaisten matriisin koon suhteen polynomisten ongelmien ratkaisemiseksi ajallisesti. Sellaisen polynomialgoritmin olemassaolo olisi jopa vahvempi kuin kuuluisa P=NP .

Joulukuussa 2012 neljä riippumatonta tutkimusryhmää ehdotti prototyyppiä kvanttifotonilaitteesta, joka laskee matriisin pysyvän [2] .

Korottajan kaava

Pysyvän laskeminen on määritelmän mukaan monimutkaista (tai jopa "karkeasti" toteutettua). Arviota voidaan merkittävästi parantaa käyttämällä korotuskaavaa [3] [4] : $O(n!)$ $O(n\cdot n!)$

\mathrm {Per} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\summa _{j\in S}a_{ij}

sen avulla pysyvä voidaan laskea ajassa tai jopa luettelemalla osajoukot harmaakoodilla . $O(2^{n}n^{2})$ $O(2^{n}n)$

Sovellukset

Pysyvällä ei ole juurikaan käyttöä lineaarisessa algebrassa , mutta sillä on käyttöä diskreetissä matematiikassa ja kombinatoriikassa.

Matriisin pysyvä , joka koostuu nollista ja ykkösistä, voidaan tulkita täydellisten täsmäysten lukumääräksi kaksiosaisessa graafissa vierekkäisyysmatriisin kanssa (eli yhden osan -:nnen kärjen ja -nnen kärjen välinen reuna ). toinen osa on olemassa, jos ). $A$ $A$ $i$ $j$ $a_{{ij}}=1$

Mielivaltaisen matriisin pysyvää voidaan pitää täydellisen kaksiosaisen graafin kaikkien täydellisten vastaavuuksien painojen summana, jossa täsmäyksen paino on sen reunojen painojen tulo ja reunojen painot kirjoitetaan viereisyysmatriisin elementit . $A$

Muistiinpanot

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (englanniksi) // Teoreettinen tietojenkäsittelytiede . - Elsevier, 1979. - Voi. 8 . - s. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Fyysikot ovat kehittäneet fotonisen kvanttitietokoneen . Lenta.ru (24. joulukuuta 2012). Haettu 25. joulukuuta 2012. Arkistoitu alkuperäisestä 26. joulukuuta 2012. (Venäjän kieli)
↑ Ryser HJ, "Combinatorial Mathematics", The Carus -matematical monographs -sarja, julkaissut Mathematical Association of America , 1963 (sillä on venäjänkielinen käännös vuodelta 1966)
↑ Weisstein, Eric W. Ryser Formula Wolfram MathWorld -verkkosivustolla .

Kirjallisuus

Mink H. Permanents. - M .: Mir, 1982. - 211 s.

Linkit

Weisstein, Eric W. Pysyvä (englanniksi) Wolfram MathWorld -verkkosivustolla .
Pysyvä (englanniksi) PlanetMath- verkkosivustolla .