Permanent

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 mai 2020; verificările necesită 2 modificări .

Un permanent în matematică este o funcție numerică definită pe mulțimea tuturor matricelor ; pentru matricele pătrate este asemănător cu determinantul , și diferă de acesta doar prin faptul că în expansiunea în permutări (sau în minore ), nu se iau semne alternante, ci toate plusurile. Spre deosebire de determinant, definiția permanentului este extinsă și asupra matricilor nepătrate.

În literatură, una dintre următoarele notații este de obicei folosită pentru a desemna un permanent: , sau . $\mathrm {Per} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Definiție

Matrice pătrată permanentă

Fie o matrice pătrată de dimensiune , ale cărei elemente aparțin unui câmp . Un număr se numește matrice permanentă : $A$ $n\ ori n$ $a_{i,j}$ $K$ $A$

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

unde suma este preluată peste toate permutările numerelor de la 1 la . $\pi$ $n$

De exemplu, pentru o matrice de dimensiune : $2\times 2$

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

Această definiție diferă de definiția similară a determinantului doar prin aceea că în determinant unii termeni ai sumei au semn negativ, în funcție de semnul permutației . $\pi$

Matrice dreptunghiulară permanentă

Conceptul de permanent este uneori extins la cazul unei matrice dreptunghiulare arbitrare de dimensiune în felul următor. Dacă , atunci: $A$ $m\ori n$ $m<n$

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

unde suma este preluată peste toate plasările de elemente din mulțimea numerelor de la 1 la . $m$ $n$

Dacă , atunci: $m>n$

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

Sau, în mod echivalent, permanenta unei matrici dreptunghiulare poate fi definită ca suma permanentelor tuturor submatricelor sale pătrate de ordin . $\min\{\,n,m\,\}$

Proprietăți

Permanentul oricărei matrice diagonală sau triunghiulară este egal cu produsul elementelor de pe diagonala sa. În special, permanentul matricei zero este egal cu zero, iar permanentul matricei identitare este egal cu unu.

Permanentul nu se schimbă la transpunerea : . Spre deosebire de determinant, permanentul unei matrice nu se modifică din permutarea rândurilor sau coloanelor matricei. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Permanentul este o funcție liniară a rândurilor (sau coloanelor) matricei, adică:

dacă înmulțiți orice rând (coloană) cu un anumit număr , atunci valoarea permanentului va crește cu un factor de; $c$ $c$
permanenta sumei a două matrice care diferă doar printr-un singur rând (coloană) este egală cu suma permanentelor lor.

Un analog al expansiunii Laplace pentru primul rând al matricei pentru permanent:

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

unde este permanenta matricei obtinuta prin stergerea randului --lea si a coloanei --lea. Deci, de exemplu, pentru o matrice de dimensiune , este valabil următoarele: $B_{i,j)$ $A$ $i$ $j$ $de 3 ori 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}}

Matricea de ordine permanentă este o funcție de ordine omogenă : $n$ $n$

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

, unde este un scalar.

c\în K

Dacă este o matrice de permutare , atunci: $P$

\mathrm {Per} (P)=1

;

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

pentru orice matrice de același ordin.

A

Dacă matricea constă din numere reale nenegative, atunci . $A$ $\mathrm {Per} (A)\geqslant \det A$

Dacă și sunt două matrici triunghiulare superioare (sau inferioare) , atunci: $A$ $B$

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

(în cazul general, egalitatea nu este valabilă pentru arbitrare și , spre deosebire de proprietatea analogă a determinanților). $A$ $B$

Permanenta unei matrice de ordine dublu stocastică cel puțin ( conjectura lui van der Waerden , dovedită în 1980). $n$ $n!/n^{n}$

Calcularea unui permanent

Spre deosebire de determinant, care poate fi calculat cu ușurință, de exemplu, prin metoda Gaussiană , calculul permanentului este o sarcină de calcul foarte consumatoare de timp aparținând clasei de complexitate a problemelor #P-complete . Rămâne #P-complet chiar și pentru matrici formate doar din zerouri și unu [1] .

În prezent[ clarifica ] nu există un algoritm cunoscut pentru rezolvarea unor astfel de probleme în timp care să fie polinom în dimensiunea matricei. Existența unui astfel de algoritm polinom ar fi chiar mai puternică decât celebrul P=NP .

În decembrie 2012, patru echipe de cercetare independente au propus un prototip de dispozitiv fotonic cuantic care calculează matricea permanentă [2] .

Formula lui Raiser

Calcularea unui permanent este, prin definiție , complexă (sau chiar „aproximativ” implementată). Estimarea poate fi îmbunătățită semnificativ prin utilizarea formulei Raiser [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}\sum _{j\in S}a_{ij}

cu el, un permanent poate fi calculat în timp sau chiar prin enumerarea submulților prin codul Gray . $O(2^{n}n^{2})$ $O(2^{n}n)$

Aplicații

Permanentul are puțină sau deloc folosire în algebra liniară , dar are utilizări în matematică discretă și combinatorică.

Permanenta matricei , constând din zerouri și unu, poate fi interpretată ca numărul de potriviri complete dintr-un graf bipartit cu o matrice de adiacență (adică o muchie între cel de -al -lea vârf al unei părți și cel de -al -lea vârf al altă parte există dacă ). $A$ $A$ $i$ $j$ $a_{{ij}}=1$

Permanenta unei matrice arbitrare poate fi considerată ca suma ponderilor tuturor potrivirilor complete dintr-un grafic bipartit complet, unde ponderea unei potriviri este produsul dintre ponderile muchiilor sale, iar ponderile muchiilor sunt scrise în elementele matricei de adiacenta . $A$

Note

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (engleză) // Theoretical Computer Science . - Elsevier, 1979. - Vol. 8 . - P. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Fizicienii au dezvoltat un computer cuantic fotonic . Lenta.ru (24 decembrie 2012). Consultat la 25 decembrie 2012. Arhivat din original pe 26 decembrie 2012. (Rusă)
↑ Ryser HJ, „Combinatorial Mathematics”, seria de monografii matematice Carus , publicată de Mathematical Association of America , 1963 (există o traducere în limba rusă din 1966)
^ Weisstein, Eric W. Ryser Formula pe site- ul Wolfram MathWorld .

Literatură

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

Link -uri

Weisstein, Eric W. Permanent (engleză) pe site-ul web Wolfram MathWorld .
Permanent (engleză) pe site-ul PlanetMath .