Pfaffian

Ej att förväxla med Pfaffian funktion , Pfaffian system , eller Pfaffian orientering .

Inom matematik kan determinanten för en skevsymmetrisk matris alltid skrivas som kvadraten på ett polynom i matrisposterna, ett polynom med heltalskoefficienter som bara beror på matrisens storlek . Värdet av detta polynom, när det tillämpas på koefficienterna för en skevsymmetrisk matris, kallas Pfaffian för den matrisen. Termen Pfaffian introducerades av Cayley ( 1852 ) som indirekt döpte dem efter Johann Friedrich Pfaff . Pfaffian (betraktad som ett polynom) är icke-försvinnande endast för 2 n × 2 n skevsymmetriska matriser, i vilket fall det är ett polynom med grad n .

Explicit, för en skevsymmetrisk matris $A$ ,

$\operatorname {pf} (A)^{2}=\det(A),$

vilket först bevisades av Cayley ( 1849 ), som citerar Jacobi för att ha introducerat dessa polynom i arbetet med Pfaffian system av differentialekvationer. Cayley erhåller denna relation genom att specialisera ett mer generellt resultat på matriser som avviker från skevsymmetri endast i den första raden och den första kolumnen. Determinanten för en sådan matris är produkten av Pfaffians av de två matriserna som erhålls genom att först sätta den övre vänstra posten till noll i originalmatrisen och sedan kopiera den negativa transponeringen av den första raden till den första kolumnen respektive den negativa överföra den första kolumnen till den första raden. Detta bevisas genom induktion genom att utöka determinanten för minderåriga och använda rekursionsformeln nedan.

Exempel

$A={\begin{bmatrix}0&a\\-a&0\end{bmatrix}}.\qquad \operatörsnamn {pf} (A)=a.$

$B={\begin{bmatrix}0&a&b\\-a&0&c\\-b&-c&0\end{bmatrix}}.\qquad \operatörsnamn {pf} (B)=0.$

(3 är udda, så Pfaffian för B är 0)

$\operatorname {pf} {\begin{bmatrix}0&a&b&c\\-a&0&d&e\\-b&-d&0&f\\-c&-e&-f&0\end{bmatrix}}=af-be+dc.$

Pfaffian för en 2 n × 2 n snedsymmetrisk tridiagonal matris ges som

$\operatorname {pf} {\begin{bmatrix}0&a_{1}&0&0\\-a_{1}&0&0&0\\0&0&0&a_{2}\\0&0&-a_{2}&0&\ddots \\&&&\ddots & \ddots &\\&&&&&0&a_{n}\\&&&&&-a_{n}&0\end{bmatrix}}=a_{1}a_{2}\cdots a_{n}.$

(Observera att vilken snedsymmetrisk matris som helst kan reduceras till denna form med alla $b_{i}$ lika med noll; se Spektralteori för en skevsymmetrisk matris .)

Formell definition

Låt A = ( ai _,j ) vara en 2 n × 2 n snedsymmetrisk matris. Pfaffian av A definieras uttryckligen av formeln

$\operatorname {pf} (A)={\frac {1}{ 2^{n}n!}}\summa _{\sigma \in S_{2n}}\operatörsnamn {sgn} (\sigma )\prod _{i=1}^{n}a_{\sigma (2i- 1),\sigma (2i)}\,,$

där S _{2 n} är den symmetriska gruppen av ordning (2 n )! och sgn(σ) är signaturen för σ.

Man kan använda skevsymmetrin hos A för att undvika summering över alla möjliga permutationer . Låt Π vara mängden av alla partitioner av {1, 2, ..., 2 n } i par utan hänsyn till ordningen. Det finns (2 n )!/(2 ⁿ n !) = (2 n - 1) !! sådana partitioner. Ett element α ∈ Π kan skrivas som

$\alpha =\{(i_{1},j_{1}),( i_{2},j_{2}),\cdots ,(i_{n},j_{n})\}$

med i _k < j _k och $i_{1}<i_{2}<\cdots <i_{n}$ . Låta

$\pi _{\alpha }={\begin{bmatrix}1&2&3&4&\cdots &2n -1&2n\\i_{1}&j_{1}&i_{2}&j_{2}&\cdots &i_{n}&j_{n}\end{bmatrix}}$

vara motsvarande permutation. Givet en partition α enligt ovan, definiera

$A_{\alpha }=\operatörsnamn {sgn} (\pi _{\alpha })a_{i_{1},j_{1}}a_{i_{2},j_{2}}\cdots a_ {i_{n},j_{n}}.$

Pfaffian av A ges sedan av

$\operatorname {pf} (A)=\summa _{\alpha \in \Pi }A_{\alpha }.$

Pfaffian för en n × n snedsymmetrisk matris för n udda definieras som noll, eftersom determinanten för en udda skevsymmetrisk matris är noll, eftersom för en skevsymmetrisk matris,

$$\det \,A=\det \,A^{\text{T}}=\det \left(- A\right)=(-1)^{n}\det \,A,$$

och för n udda innebär detta $\det \,A=0$ .

Rekursiv definition

Enligt konvention är Pfaffian för 0×0-matrisen lika med ett. Pfaffian för en skevsymmetrisk 2 n × 2 n matris A med n >0 kan beräknas rekursivt som

$\operatorname { pf} (A)=\summa _{{j=1} \atop {j\neq i}}^{2n}(-1)^{i+j+1+\theta (ij)}a_{ij} \operatörsnamn {pf} (A_{{\hat {\imath }}{\hat {\jmath }}}),$

där index i kan väljas godtyckligt, $\theta (ij)$ är Heaviside-stegfunktionen och $A_{{\hat {\imath }}{\ hat {\jmath }}}$ betecknar matrisen A med både i -: te och j -te raden och kolumnerna borttagna. Notera hur detta för det speciella valet $i=1$ reduceras till det enklare uttrycket:

$\operatörsnamn {pf} (A)=\sum _{j=2}^{2n}(-1)^{j}a_{1j}\operatörsnamn {pf} (A_{{\hat {1} }{\hat {\jmath }}}).$

Alternativa definitioner

Man kan associera till vilken skev-symmetrisk 2 n × 2 n matris A =( a _ij ) en bivector

$\omega =\sum _{i<j}a_{ij}\;e_{i}\wedge e_{j}.$

där { _{e e2n} 1 _, e2 , _... , } är standardbasen för R2n ^. Pfaffian definieras sedan av ekvationen

${\frac {1}{n!}}\omega ^{n}=\operatörsnamn {pf} (A)\ ;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n},$

här betecknar ω ⁿ kilprodukten av n kopior av ω.

En generalisering som inte är noll av Pfaffian till udda dimensionella matriser ges i de Bruijns arbete om multipla integraler som involverar determinanter. I synnerhet för valfri m x m matris A använder vi den formella definitionen ovan men sätter $n=\lfloor m/2\rfloor$ . För m udda kan man då visa att detta är lika med den vanliga Pfaffian för en ( m+ 1) x ( m+ 1) dimensionell snedsymmetrisk matris där vi har lagt till en ( m+ 1) kolumn bestående av m element 1, en ( m+ 1):e raden som består av m element -1, och hörnelementet är noll. Pfaffians vanliga egenskaper, till exempel relationen till determinanten, gäller då för denna utökade matris.

Egenskaper och identiteter

Pfaffians har följande egenskaper, som liknar determinanters.

• Multiplicering av en rad och en kolumn med en konstant är ekvivalent med multiplikation av Pfaffian med samma konstant.
• Samtidigt utbyte av två olika rader och motsvarande kolumner ändrar tecknet för Pfaffian.
• En multipel av en rad och motsvarande kolumn som läggs till en annan rad och motsvarande kolumn ändrar inte värdet på Pfaffian.

Med hjälp av dessa egenskaper kan Pfaffians beräknas snabbt, i likhet med beräkningen av determinanter.

Diverse

För en 2 n × 2 n snedsymmetrisk matris A

$\operatörsnamn {pf} (A^{\text{T}})=(-1)^{n}\operatörsnamn {pf} (A).$

$\operatörsnamn {pf} (\lambda A)=\lambda ^{n}\operatörsnamn {pf} (A).$

$\operatorname {pf} (A)^{2}=\det(A).$

För en godtycklig 2 n × 2 n matris B ,

$\operatörsnamn {pf} (BAB^{\text{T}})=\det(B)\operatörsnamn {pf} (A).$

Ersätter man i denna ekvation B = A ^m , får man för alla heltal m

$\operatörsnamn {pf} (A^{2m+1})=(-1)^{nm}\operatörsnamn {pf} (A)^{2m+1}.$

Härledda identiteter

Om A beror på någon variabel x _i , så ges gradienten för en Pfaffian av

${\frac {1}{\operatörsnamn {pf} (A)} }{\frac {\partial \operatörsnamn {pf} (A)}{\partial x_{i}}}={\frac {1}{2}}\operatörsnamn {tr} \left(A^{-1} {\frac {\partial A}{\partial x_{i}}}\right),$

och hessian av en Pfaffian ges av

${\frac {1}{\operatörsnamn {pf} (A)}}{\frac {\partial ^{2}\operatörsnamn {pf} (A)}{\partial x_{i}\partial x_{ j}}}={\frac {1}{2}}\operatörsnamn {tr} \left(A^{-1}{\frac {\partial ^{2}A}{\partial x_{i}\partial x_{j}}}\right)-{\frac {1}{2}}\operatörsnamn {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}} }A^{-1}{\frac {\partial A}{\partial x_{j}}}\right)+{\frac {1}{4}}\operatörsnamn {tr} \left(A^{- 1}{\frac {\partial A}{\partial x_{i}}}\right)\operatörsnamn {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{j }}}\höger).$

Spåra identiteter

Produkten av Pfaffians av skevsymmetriska matriser A och B kan representeras i form av en exponentiell

${\textrm {pf}}(A)\,{\textrm {pf}}(B)=\exp({\tfrac {1}{2}}\mathrm {tr} \log(A^{ \text{T}}B)).$

Antag då att A och B är 2n × 2n snedsymmetriska matriser

$\mathrm {pf} (A)\,\mathrm {pf} (B)={\tfrac {1}{n!}}B_{n}(s_{1 },s_{2},\ldots ,s_{n}),\qquad \mathrm {där} \qquad s_{l}=-{\tfrac {1}{2}}(l-1)!\,\ mathrm {tr} ((AB)^{l})$

och B _n ( s ₁ , s ₂ , ..., s _n ) är Bell polynom .

Blockmatriser

För en blockdiagonal matris

$A_{1}\oplus A_{2}={\begin{bmatrix}A_{1}&0\\0&A_{2}\end{bmatrix}} ,$

$\operatörsnamn {pf} (A_{1}\oplus A_{2})=\operatörsnamn {pf} (A_{1})\operatörsnamn {pf} (A_{2}).$

För en godtycklig n × n matris M :

$\operatorname {pf} {\begin{bmatrix}0&M\\-M^{\text{T}}&0\end{bmatrix}}=(-1)^{n(n-1)/2} \det M.$

Det krävs ofta att man beräknar pfaffian för en skevsymmetrisk matris $S$ med blockstrukturen

$S={\begin{pmatrix}M&Q\\-Q^{T}&N\end{pmatrix}}\,$

där $M$ och $N$ är snedsymmetriska matriser och $Q$ är en allmän rektangulär matris.

När $M$ är inverterbar har man

$\operatörsnamn {pf} (S)=\operatörsnamn {pf} (M)\operatörsnamn {pf} (N+Q^{T}M^{-1}Q).$

Detta kan ses från Aitkens blockdiagonaliseringsformel,

${\begin{pmatrix}M&0\\0&N+Q^{T}M^{-1}Q\end{pmatrix}}={\begin{pmatrix}I&0\\Q^{T}M^{ -1}&I\end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{T}&N\end{pmatrix}}{\begin{pmatrix}I&-M^{-1}Q\\0&I \end{pmatrix}}.$

Denna nedbrytning involverar kongruenstransformationer som gör det möjligt att använda egenskapen pfaffian $\operatorname {pf} (BAB^{T})=\operatörsnamn {det} (B)\operatörsnamn {pf} (A)$ .

På liknande sätt, när $N$ är inverterbar, har man

$\operatörsnamn {pf} (S)=\operatörsnamn {pf} (N)\operatörsnamn {pf} ( M+QN^{-1}Q^{T}),$

som kan ses genom att använda nedbrytningen

${\begin{pmatrix}M+QN^{-1}Q^{T}&0\\0&N\end{pmatrix}}={\begin{pmatrix}I&-QN^{-1}\\0&I \end{pmatrix}}{\begin{pmatrix}M&Q\\-Q^{T}&N\end{pmatrix}}{\begin{pmatrix}I&0\\N^{-1}Q^{T}&I\ slut{pmatrix}}.$

Beräknar Pfaffian numeriskt

Antag att A är en 2n × 2n snedsymmetrisk matris

${\textrm {pf}}(A)=i^{ (n^{2})}\exp \left({\tfrac {1}{2}}\mathrm {tr} \log((\sigma _{y}\ibland I_{n})^{T}\ cdot A)\right),$

där $\sigma _{y}$ är den andra Pauli-matrisen , $I_{n}$ är en identitetsmatris av dimension n och vi tog spåret över en matrislogaritm .

Denna jämlikhet bygger på spåridentiteten

${\textrm {pf}}(A)\,{\textrm {pf}}(B)= \exp \left({\tfrac {1}{2}}\mathrm {tr} \log(A^{\text{T}}B)\right)$

och på observationen att ${\textrm {pf}}(\sigma _{y}\otimes I_{n})=(-i)^ {n^{2}}$ .

Eftersom att beräkna logaritmen för en matris är en beräkningskrävande uppgift kan man istället beräkna alla egenvärden för $((\sigma _{y}\otimes I_{n}) ^{T}\cdot A)$ , ta loggen över alla dessa och summera dem. Denna procedur utnyttjar bara egenskapen $\operatorname {tr} {\log {(AB)}}=\operatörsnamn {tr} {\log {(A)}}+\operatörsnamn {tr} {\log {(B)}}$ . Detta kan implementeras i Mathematica inom en enda rad:

Pf[x_] := Modul[{n = Dimensioner[x][[1]] / 2}, I^(n^2) Exp[ 1/2 Total[ Log[Eigenvalues[ Dot[Transponera[KroneckerProduct[PauliMatrix[ 2], IdentityMatrix[n]]], x] ]]]]]

Denna algoritm är dock instabil när Pfaffian är stor. Egenvärdena för $(\sigma _{y}\otimes I_{n})^{T}\cdot A$ kommer i allmänhet att vara komplexa, och logaritmen för dessa komplexa egenvärden antas i allmänhet vara i $[-\pi ,\pi ]$ . Under summeringen, för en verkligt värderad Pfaffian, kommer argumentet för exponentialen att ges i formen $x+k\pi /2$ för något heltal $k$ . När $x$ är mycket stor, kan avrundningsfel vid beräkning av det resulterande tecknet från den komplexa fasen leda till en imaginär komponent som inte är noll.

För andra (mer) effektiva algoritmer se ( Wimmer 2012) .

Ansökningar

• Det finns program för numerisk beräkning av Pfaffian på olika plattformar (Python, Matlab, Mathematica) ( Wimmer 2012) .
• Pfaffian är ett invariant polynom av en skevsymmetrisk matris under en korrekt ortogonal förändring av grunden. Som sådan är det viktigt i teorin om karakteristiska klasser . I synnerhet kan den användas för att definiera Euler-klassen för ett Riemann-grenrör som används i den generaliserade Gauss-Bonnet-satsen .
• Antalet perfekta matchningar i en plan graf ges av en Pfaffian, och är därför polynomisk tidsberäkning via FKT-algoritmen . Detta är förvånande med tanke på att för generella grafer är problemet mycket svårt (så kallat #P-komplett ) . Detta resultat används för att beräkna antalet dominoplattor för en rektangel, partitionsfunktionen för Ising-modeller i fysik, eller Markovs slumpmässiga fält i maskininlärning ( Globerson & Jaakkola 2007 ; Schraudolph & Kamenetsky 2009) , där den underliggande grafen är planär . Det används också för att härleda effektiva algoritmer för vissa annars till synes svårlösta problem, inklusive effektiv simulering av vissa typer av begränsad kvantberäkning. Läs holografisk algoritm för mer information.

Se även

• Determinant
• Dimer modell
• Hafnian
• Polyomino
• Statistisk mekanik

Anteckningar

• Cayley, Arthur (1849). "Sur les déterminants gauches" . Journal für die reine und angewandte Mathematik . 38 : 93–96.
• Cayley, Arthur (1852). "Om teorin om permutanter" . Cambridge och Dublin Mathematical Journal . VII : 40–51. Omtryckt i Samlade matematiska papper, volym 2.
• Kasteleyn, PW (1961). "Statistiken för dimerer på ett gitter. I. Antalet dimerarrangemang på ett kvadratiskt gitter". Physica . 27 (12): 1209–1225. Bibcode : 1961Phy....27.1209K . doi : 10.1016/0031-8914(61)90063-5 .
• Propp, James (2004). "Lambda-determinanter och domino-plattor". arXiv : math/0406301 .
• Globerson, Amir; Jaakkola, Tommi (2007). "Ungefärlig slutledning med hjälp av planar grafsönderdelning" (PDF) . Framsteg inom neurala informationsbehandlingssystem 19 . MIT Press.
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Effektiv exakt slutledning i plana Ising-modeller" (PDF) . Framsteg inom neurala informationsbehandlingssystem 21 . MIT Press.
• Jeliss, GP; Chapman, Robin J. (1996). "Dominerar schackbrädet". The Games and Puzzles Journal . 2 (14): 204–5.
• Sellers, James A. (2002). "Domino plattsättningar och produkter av Fibonacci och Pell nummer" . Journal of Integer Sequences . 5 (1): 02.1.2. Bibcode : 2002JIntS...5...12S .
•   Wells, David (1997). Penguin Dictionary of Curious and Interesting Numbers (reviderad utgåva). sid. 182. ISBN 0-14-026149-4 .
• Muir, Thomas (1882). En avhandling om teorin om determinanter . Macmillan och Co. Online
•   Parameswaran, S. (1954). "Skev-symmetriska determinanter". American Mathematical Monthly . 61 (2): 116. doi : 10.2307/2307800 . JSTOR 2307800 .
•   Wimmer, M. (2012). "Effektiv numerisk beräkning av Pfaffian för täta och bandade skev-symmetriska matriser". ACM Trans. Matematik. Softw. 38 : 30. arXiv : 1102.3440 . doi : 10.1145/2331130.2331138 . S2CID 15331538 .
• de Bruijn, NG (1955). "På några multipla integraler som involverar determinanter". J. Indian Math. Soc. 19 : 131–151.

externa länkar

• "Pfaffian" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Pfaffian på PlanetMath.org
• T. Jones, The Pfaffian and the Wedge Product (en demonstration av beviset på förhållandet Pfaffian/determinant)
• R. Kenyon och A. Okounkov , Vad är ... en dimer?
• OEIS -sekvens A004003 (Antal dominoplattor (eller dimerbeläggningar))
• W. Ledermann "A note on skew-symmetric determinants" https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants