Állandó

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. május 24-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A permanens a matematikában egy numerikus függvény , amely az összes mátrix halmazán van definiálva ; négyzetes mátrixoknál hasonló a determinánshoz , és csak abban különbözik tőle, hogy a permutációkra (vagy mollokra ) történő bővítésnél nem váltakozó jeleket veszünk, hanem az összes pluszt. A determinánstól eltérően a permanens definíciója a nem négyzetes mátrixokra is kiterjed.

A szakirodalomban az állandó jelölésére általában a következő jelölések valamelyikét használják: , vagy . $\mathrm {Per} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Definíció

Négyzetmátrix állandó

Legyen egy méretű négyzetmátrix , melynek elemei valamilyen mezőhöz tartoznak . Egy számot állandó mátrixnak nevezünk : $A$ $n\szer n$ ${\displaystyle a_{i,j))$ $K$ $A$

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

ahol az összeget átveszi a számok összes permutációja 1-től . $\pi$ $n$

Például egy méretű mátrixhoz : $2\times 2$

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

Ez a definíció csak annyiban tér el a determináns hasonló definíciójától , hogy a determinánsban az összeg egyes tagjai negatív előjelűek, a permutáció előjelétől függően . $\pi$

Téglalap mátrix állandó

A permanens fogalmát néha kiterjesztik egy tetszőleges méretű téglalap alakú mátrix esetére a következő módon. Ha , akkor: $A$ $m\szer n$ $m<n$

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

ahol az összeget átveszi az összes elemű elhelyezés az 1-től ig terjedő számhalmazból . $m$ $n$

Ha , akkor: $m>n$

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

Vagy ezzel egyenértékűen egy téglalap alakú mátrix állandója definiálható az összes négyzetes rendű részmátrix állandójának összegeként . ${\displaystyle \min\{\,n,m\,\))$

Tulajdonságok

Bármely átlós vagy háromszög alakú mátrix állandója megegyezik az átlóján lévő elemek szorzatával. Különösen a nulla mátrix állandója egyenlő nullával, az azonosságmátrix állandója pedig eggyel.

Az állandó nem változik transzponáláskor : . A determinánssal ellentétben a mátrix állandója nem változik a mátrix sorainak vagy oszlopainak permutációjától. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Az állandó a mátrix sorainak (vagy oszlopainak) lineáris függvénye , azaz:

ha egy sort (oszlopot) megszoroz egy bizonyos számmal , akkor a permanens értéke a szorzóval nő; $c$ $c$
két olyan mátrix összegének állandója, amelyek csak egy sorral (oszloppal) különböznek egymástól, megegyezik állandójaik összegével.

A Laplace-kiterjesztés analógja a permanens mátrix első sorában:

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

ahol a -edik sor és -edik oszlop törlésével kapott mátrix állandója. Tehát például egy méretű mátrixra a következők érvényesek: ${\megjelenítési stílus B_{i,j))$ $A$ $én$ $j$ $3 alkalommal 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}}

Az állandó mátrix egy homogén sorrendfüggvény : $n$ $n$

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

, hol van egy skalár.

c\in K

Ha egy permutációs mátrix , akkor: $P$

\mathrm {Per} (P)=1

;

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

bármely azonos rendű mátrixra.

A

Ha a mátrix nemnegatív valós számokból áll, akkor . $A$ $\mathrm {Per} (A)\geqslant \det A$

Ha és két felső (vagy alsó) háromszögmátrix , akkor: $A$ $B$

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

(általános esetben az egyenlőség nem áll fenn tetszőleges és -re , ellentétben a determinánsok analóg tulajdonságával). $A$ $B$

Legalábbis egy kétszeresen sztochasztikus mátrix állandója ( van der Waerden sejtése , 1980-ban bebizonyosodott). $n$ $n!/n^{n}$

Állandó

Ellentétben a determinánssal, amely például a Gauss-módszerrel könnyen kiszámítható, a permanens kiszámítása nagyon időigényes számítási feladat, amely a #P-teljes problémák összetettségi osztályába tartozik . #P-teljes marad még a csak nullákból és egyesekből álló mátrixok esetében is [1] .

Jelenleg[ tisztázza ] nincs ismert algoritmus olyan problémák időbeni megoldására, amelyek polinomiális méretűek a mátrixban. Egy ilyen polinomiális algoritmus létezése még erősebb lenne, mint a híres P=NP .

2012 decemberében négy független kutatócsoport javasolta egy kvantumfotonikus eszköz prototípusát, amely az állandó mátrixot számítja ki [2] .

Raiser képlete

A permanens számítása definíció szerint összetett (vagy akár "nagyjából" megvalósított). A becslés jelentősen javítható a Raiser formula [3] [4] használatával : $O(n!)$ $O(n\cdot n!)$

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

Ezzel a permanens kiszámítható időben, vagy akár részhalmazok Gray kóddal történő felsorolásával . $O(2^{n}n^{2})$ $O(2^{n}n)$

Alkalmazások

A permanensnek alig vagy egyáltalán nem használható a lineáris algebrában , de a diszkrét matematikában és a kombinatorikában használható.

A nullákból és egyesekből álló mátrix állandója úgy értelmezhető, mint a teljes egyezések száma egy bipartit gráfban egy szomszédsági mátrixszal (vagyis az egyik rész -edik csúcsa és a -edik csúcsa közötti éllel). másik rész létezik, ha ). $A$ $A$ $én$ $j$ $a_{{ij}}=1$

Egy tetszőleges mátrix állandójának tekinthető egy teljes kétrészes gráfban lévő teljes illesztések súlyának összege, ahol az illesztés súlya az élei súlyainak szorzata, az élek súlya pedig a szomszédsági mátrix elemei . $A$

Jegyzetek

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (angol) // Theoretical Computer Science . - Elsevier, 1979. - 1. évf. 8 . - P. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ A fizikusok kifejlesztettek egy fotonikus kvantumszámítógépet . Lenta.ru (2012. december 24.). Letöltve: 2012. december 25. Az eredetiből archiválva : 2012. december 26.. (Orosz)
↑ Ryser HJ, "Combinatorial Mathematics", The Carus matematikai monográfiák sorozata, az Amerikai Matematikai Szövetség kiadása , 1963 (1966-ból van orosz fordítás)
↑ Weisstein, Eric W. Ryser Formula a Wolfram MathWorld weboldalán .

Irodalom

Mink H. Permanens. — M .: Mir, 1982. — 211 p.

Linkek

Weisstein, Eric W. Állandó (angol) a Wolfram MathWorld webhelyén .
Állandó (angol nyelven) a PlanetMath webhelyen .