Permanent

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. maj 2020; checks kræver 2 redigeringer .

En permanent i matematik er en numerisk funktion defineret på mængden af alle matricer ; for kvadratiske matricer ligner den determinanten , og adskiller sig kun fra den ved, at der i udvidelsen til permutationer (eller til mindre ), ikke tages vekslende fortegn, men alle plusserne . I modsætning til determinanten udvides definitionen af det permanente også til ikke-kvadratiske matricer.

I litteraturen bruges en af følgende notationer normalt til at betegne en permanent: , eller . $\mathrm {Pr.} (A)$ $\mathrm {per} A$ $\mathrm {perm} A$

Definition

Firkantet matrix permanent

Lade være en firkantet matrix af størrelse , hvis elementer tilhører nogle felt . Et tal kaldes en matrix permanent : $EN$ $n\ gange n$ ${\displaystyle a_{i,j))$ $K$ $EN$

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

hvor summen overtages alle permutationer af tal fra 1 til . $\pi$ $n$

For eksempel for en matrix af størrelse : $2\ gange 2$

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

Denne definition adskiller sig kun fra den tilsvarende definition af determinanten ved, at i determinanten har nogle termer af summen et negativt fortegn, afhængigt af permutationens fortegn . $\pi$

Rektangulær matrix permanent

Begrebet permanent udvides undertiden til tilfældet med en vilkårlig rektangulær matrix af størrelse på følgende måde. Hvis , så: $EN$ $m\ gange n$ $m<n$

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

hvor summen overtages alle -elementplaceringer fra mængden af tal fra 1 til . $m$ $n$

Hvis , så: $m>n$

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

Eller tilsvarende kan permanenten af en rektangulær matrix defineres som summen af permanenterne af alle dens kvadratiske submatricer af orden . ${\displaystyle \min\{\,n,m\,\))$

Egenskaber

Det permanente af enhver diagonal eller trekantet matrix er lig med produktet af elementerne på dens diagonal. Især nulmatricens permanente er lig med nul, og permanenten af identitetsmatricen er lig med én.

Permanenten ændres ikke ved transponering : . I modsætning til determinanten ændres permanenten af en matrix ikke fra permutation af rækkerne eller kolonnerne i matrixen. $\mathrm {Per} (A^{T})=\mathrm {Per} (A)$

Den permanente er en lineær funktion af rækkerne (eller kolonnerne) i matrixen, det vil sige:

hvis du multiplicerer en række (kolonne) med et vist tal , så vil værdien af den permanente stige med en faktor på; $c$ $c$
permanenten af summen af to matricer, der kun adskiller sig med én række (kolonne), er lig med summen af deres permanenter.

En analog af Laplace-udvidelsen for den første række af matrixen for den permanente:

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

hvor er den permanente matrix opnået ved at slette den -th række og den -th kolonne. Så for eksempel for en matrix af størrelse gælder følgende: ${\displaystyle B_{i,j))$ $EN$ $jeg$ $j$ $3 gange 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}}

Ordrematrixen permanent er en homogen ordensfunktion : $n$ $n$

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

, hvor er en skalar.

c\in K

Hvis er en permutationsmatrix , så: $P$

\mathrm {Per} (P)=1

;

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

for enhver matrix af samme rækkefølge.

EN

Hvis matricen består af ikke-negative reelle tal, så . $EN$ $\mathrm {Per} (A)\geqslant \det A$

Hvis og er to øvre (eller nedre) trekantede matricer , så: $EN$ $B$

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

(i det generelle tilfælde gælder ligheden ikke for vilkårlig og i modsætning til determinanternes analoge egenskab). $EN$ $B$

Det permanente af en dobbelt stokastisk matrix af orden i det mindste ( van der Waerdens formodning , bevist i 1980). $n$ $n!/n^{n}$

Beregning af en permanent

I modsætning til determinanten, som nemt kan beregnes, for eksempel ved Gauss-metoden , er beregningen af permanenten en meget tidskrævende beregningsopgave, der hører til kompleksitetsklassen af #P-komplette problemer. Den forbliver #P-komplet selv for matricer, der kun består af nuller og enere [1] .

I øjeblikket[ klargør ] der er ingen kendt algoritme til at løse sådanne problemer i tid, der er polynomisk i størrelsen af matrixen. Eksistensen af en sådan polynomial algoritme ville være endnu stærkere end den berømte P=NP .

I december 2012 foreslog fire uafhængige forskerhold en prototype af en kvantefotonisk enhed, der beregner matrixen permanent [2] .

Raisers formel

At beregne en permanent er per definition kompleks (eller endda "groft" implementeret). Estimatet kan forbedres væsentligt ved at bruge Raiser-formlen [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}

med det kan en permanent beregnes i tid eller endda ved at optælle delmængder med grå kode . $O(2^{n}n^{2})$ $O(2^{n}n)$

Ansøgninger

Den permanente har ringe eller ingen brug i lineær algebra , men har anvendelser i diskret matematik og kombinatorik.

Permanenten af matricen , der består af nuller og enere, kan fortolkes som antallet af komplette matchninger i en todelt graf med en tilstødende matrix (det vil sige en kant mellem -th vertex af en del og -th vertex af anden del eksisterer, hvis ). $EN$ $EN$ $jeg$ $j$ $a_{{ij}}=1$

Permanenten af en vilkårlig matrix kan betragtes som summen af vægtene af alle komplette matchninger i en komplet todelt graf, hvor vægten af en matchning er produktet af vægten af dens kanter, og vægten af kanterne er skrevet i elementerne i tilstødende matrix . $EN$

Noter

↑ Leslie G. Valiant . The Complexity of Computing the Permanent (engelsk) // Theoretical Computer Science . - Elsevier, 1979. - Vol. 8 . - S. 189-201 . - doi : 10.1016/0304-3975(79)90044-6 .
↑ Fysikere har udviklet en fotonisk kvantecomputer . Lenta.ru (24. december 2012). Hentet 25. december 2012. Arkiveret fra originalen 26. december 2012. (Russisk)
↑ Ryser HJ, "Combinatorial Mathematics", The Carus matematiske monografier , udgivet af Mathematical Association of America , 1963 (der er en russisk oversættelse af 1966)
↑ Weisstein, Eric W. Ryser Formula på Wolfram MathWorld -webstedet .

Litteratur

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