Permanent

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 maj 2020; kontroller kräver 2 redigeringar .

En permanent i matematik är en numerisk funktion definierad på mängden av alla matriser ; för kvadratiska matriser liknar den determinanten , och skiljer sig från den endast genom att i expansionen till permutationer (eller till mindre ), tas inte alternerande tecken, utan alla plus. Till skillnad från determinanten utvidgas definitionen av permanent till icke-kvadratmatriser.

I litteraturen används vanligtvis en av följande notationer för att beteckna en permanent: , eller . $\mathrm {Per} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Definition

Kvadratisk matris permanent

Låta vara en kvadratisk matris av storlek , vars element tillhör något fält . Ett nummer kallas en matris permanent : $A$ $n\ gånger n$ ${\displaystyle 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}}

där summan tas över alla permutationer av tal från 1 till . $\pi$ $n$

Till exempel, för en matris med storlek : $2\times 2$

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

Denna definition skiljer sig från den liknande definitionen av determinanten endast genom att i determinanten har vissa termer av summan ett negativt tecken, beroende på permutationens tecken . $\pi$

Rektangulär matris permanent

Begreppet permanent utvidgas ibland till fallet med en godtycklig rektangulär matris av storlek på följande sätt. Om , då: $A$ $m\ gånger n$ $m<n$

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

där summan tas över alla elementplaceringar från uppsättningen siffror från 1 till . $m$ $n$

Om , då: $m>n$

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

Eller på motsvarande sätt kan permanenten av en rektangulär matris definieras som summan av permanenterna av alla dess kvadratiska submatriser av ordning . ${\displaystyle \min\{\,n,m\,\))$

Egenskaper

Permanenten av en diagonal eller triangulär matris är lika med produkten av elementen på dess diagonal. I synnerhet är nollmatrisens permanenta lika med noll, och identitetsmatrisens permanenta är lika med en.

Permanenten ändras inte vid transponering : . Till skillnad från determinanten ändras inte en matris permanent från permutation av matrisens rader eller kolumner. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Permanenten är en linjär funktion av raderna (eller kolumnerna) i matrisen, det vill säga:

om du multiplicerar en rad (kolumn) med ett visst tal , kommer värdet på permanenten att öka med en faktor på; $c$ $c$
permanenten av summan av två matriser som skiljer sig med endast en rad (kolumn) är lika med summan av deras permanenter.

En analog till Laplace-expansionen för den första raden i matrisen för den permanenta:

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

där är den permanenta matrisen som erhålls genom att ta bort den -th raden och den -th kolumnen. Så, till exempel, för en matris med storlek , gäller följande: ${\displaystyle B_{i,j))$ $A$ $i$ $j$ $3 gånger 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}}

Ordningsmatrisen permanent är en homogen ordningsfunktion : $n$ $n$

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

, var är en skalär.

c\in K

Om är en permutationsmatris , då: $P$

\mathrm {Per} (P)=1

;

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

för valfri matris av samma ordning.

A

Om matrisen består av icke-negativa reella tal, då . $A$ $\mathrm {Per} (A)\geqslant \det A$

Om och är två övre (eller nedre) triangulära matriser , då: $A$ $B$

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

(i det allmänna fallet gäller inte jämlikheten för godtyckliga och , i motsats till den analoga egenskapen hos determinanterna). $A$ $B$

Det permanenta av en dubbel stokastisk matris av ordning åtminstone ( van der Waerdens gissning , bevisad 1980). $n$ $n!/n^{n}$

Beräknar en permanent

Till skillnad från determinanten, som enkelt kan beräknas, till exempel med Gauss-metoden , är beräkningen av permanenten en mycket tidskrävande beräkningsuppgift som tillhör komplexitetsklassen av #P-kompletta problem. Den förblir #P-komplett även för matriser som endast består av nollor och ettor [1] .

För närvarande[ förtydliga ] det finns ingen känd algoritm för att lösa sådana problem i tid som är polynom i storleken på matrisen. Förekomsten av en sådan polynomalgoritm skulle vara ännu starkare än den berömda P=NP .

I december 2012 föreslog fyra oberoende forskarlag en prototyp av en kvantfotonisk enhet som beräknar matrisen permanent [2] .

Raisers formel

Att beräkna en permanent är per definition komplext (eller till och med "ungefär" implementerat). Uppskattningen kan förbättras avsevärt genom att använda Raiser-formeln [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}

med den kan en permanent beräknas i tid eller till och med genom att räkna upp delmängder med grå kod . $O(2^{n}n^{2})$ $O(2^{n}n)$

Applikationer

Den permanenta har liten eller ingen användning i linjär algebra , men har användningsområden i diskret matematik och kombinatorik.

Matrisens permanenta , bestående av nollor och ettor, kan tolkas som antalet fullständiga matchningar i en tvådelad graf med en närliggande matris (det vill säga en kant mellan -th vertex av en del och -th vertex av annan del finns om ). $A$ $A$ $i$ $j$ $a_{{ij}}=1$

Permanenten av en godtycklig matris kan betraktas som summan av vikterna av alla fullständiga matchningar i en komplett tvådelad graf, där vikten av en matchning är produkten av vikterna av dess kanter, och kanternas vikter skrivs i elementen i närliggande matris . $A$

Anteckningar

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (engelska) // Theoretical Computer Science . - Elsevier, 1979. - Vol. 8 . - S. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Fysiker har utvecklat en fotonisk kvantdator . Lenta.ru (24 december 2012). Hämtad 25 december 2012. Arkiverad från originalet 26 december 2012. (ryska)
↑ Ryser HJ, "Combinatorial Mathematics", The Carus matematiska monografier , publicerad av Mathematical Association of America , 1963 (det finns en rysk översättning från 1966)
↑ Weisstein, Eric W. Ryser Formula på Wolfram MathWorld- webbplatsen .

Litteratur

Mink H. Permanenter. — M .: Mir, 1982. — 211 sid.

Länkar

Weisstein, Eric W. Permanent (engelska) på Wolfram MathWorld- webbplatsen .
Permanent (engelska) på PlanetMath-webbplatsen .