Pfaffian - Pfaffian

v matematika, určující a šikmo symetrická matice lze vždy psát jako čtverec a polynomiální v položkách matice polynom s celočíselnými koeficienty, které závisí pouze na velikosti matice. Hodnota tohoto polynomu, když je aplikována na koeficienty zešikmené symetrické matice, se nazývá Pfaffian té matice. Termín Pfaffian byl představen Cayley  (1852 ), který je nepřímo pojmenoval Johann Friedrich Pfaff. Pfaffian (považovaný za polynom) není jen pro 2n × 2n šikmé symetrické matice, v takovém případě se jedná o polynom stupně n.

Výslovně, pro symetrickou matici zkosení A,

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

což bylo poprvé prokázáno Cayley  (1849 ), práce založená na dřívější práci na Pfaffianových systémech obyčejných diferenciálních rovnic od Jacobi.

Skutečnost, že determinantem jakékoli šikmé symetrické matice je čtverec polynomu, lze ukázat tak, že matici zapíšeme jako blokovou matici a poté použijeme indukci a zkoumáme Schurův doplněk, což je také symetrické zkosení.^[1]

Příklady

${ displaystyle A = { begin {bmatrix} 0 & a - a & 0 end {bmatrix}}. qquad operatorname {pf} (A) = a.}$

${ displaystyle B = { begin {bmatrix} 0 & a & b - a & 0 & c - b & -c & 0 end {bmatrix}}. qquad operatorname {pf} (B) = 0.}$

(3 je liché, takže Pfaffian z B je 0)

${ displaystyle 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 2n × 2n šikmo symetrický tridiagonální matice je uveden jako

${ displaystyle 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}.}$

(Všimněte si, že jakoukoli symetrickou matici zkosení lze do této podoby redukovat se všemi ${ displaystyle b_ {i}}$ rovno nule; vidět Spektrální teorie symetrické matice zkosení.)

Formální definice

Nechat A = (A_{já, j}) být 2n × 2n šikmo symetrická matice. Pfaffian z A je výslovně definován vzorcem

${ displaystyle operatorname {pf} (A) = { frac {1} {2 ^ {n} n!}} sum _ { sigma v S_ {2n}} operatorname {sgn} ( sigma) prod _ {i = 1} ^ {n} a _ { sigma (2i-1), sigma (2i)}}$

kde S_2n je symetrická skupina objednávky (2n)! a sgn (σ) je podpis z σ.

Lze využít šikmou symetrii A vyhnout se možnému sčítání obměny. Nechť Π je množina všech oddíly z {1, 2, ..., 2n} do dvojic bez ohledu na pořadí. Existují (2n)!/(2ⁿn!) = (2n - 1)!! takové oddíly. Prvek α ∈ Π lze zapsat jako

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

s i_k < j_k a ${ displaystyle i_ {1}$. Nechat

${ displaystyle 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}}}$

být odpovídající permutace. Vzhledem k rozdělení α, jak je uvedeno výše, definujte

${ displaystyle A _ { alpha} = operatorname {sgn} ( pi _ { alpha}) a_ {i_ {1}, j_ {1}} a_ {i_ {2}, j_ {2}} cdots a_ {i_ {n}, j_ {n}}.}$

Pfaffian z A je pak dáno

${ displaystyle operatorname {pf} (A) = součet _ { alfa v Pi} A _ { alpha}.}$

Pfaffian a n×n zkosená symetrická matice pro n lichá je definována jako nula, protože determinant liché symetrické matice je nula, protože pro symetrickou matici zkosení,

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

a pro n zvláštní, to naznačuje ${ displaystyle det , A = 0}$.

Rekurzivní definice

Podle konvence je Pfaffian matice 0 × 0 roven jedné. Pfaffian zešikmení symetrický 2n×2n matice A s n> 0 lze vypočítat rekurzivně jako

${ displaystyle operatorname {pf} (A) = součet _ {{j = 1} na vrcholu {j neq i}} ^ {2n} (- 1) ^ {i + j + 1 + theta (ij )} a_ {ij} operatorname {pf} (A _ {{ hat { imath}} { hat { jmath}}}),}$

kde index i lze zvolit libovolně, ${ displaystyle theta (i-j)}$ je Funkce Heaviside step, a ${ displaystyle A _ {{ hat { imath}} { hat { jmath}}}}$ označuje matici A s oběma i-th a j-té řádky a sloupce odstraněny.^[2] Všimněte si, jak pro speciální volbu ${ displaystyle i = 1}$ to redukuje na jednodušší výraz:

${ displaystyle operatorname {pf} (A) = součet _ {j = 2} ^ {2n} (- 1) ^ {j} a_ {1j} operatorname {pf} (A _ {{ hat {1} } { hat { jmath}}}).}$

Alternativní definice

Lze přidružit k libovolné symetrii zešikmení 2n×2n matice A =(A_ij) a bivektor

${ displaystyle omega = součet _ {i$

kde {E₁, E₂, ..., E_2n} je standardní základ R²ⁿ. Pfaffian je pak definován rovnicí

${ displaystyle { frac {1} {n!}} omega ^ {n} = operatorname {pf} (A) ; e_ {1} klín e_ {2} klín cdots klín e_ {2n },}$

tady ωⁿ označuje klínový produkt z n kopie ω.

Nenulová generalizace Pfaffianových na liché dimenzionální matice je uvedena v práci de Bruijna o více integrálech zahrnujících determinanty.^[3] Zejména pro všechny m X m matice A, použijeme výše uvedenou formální definici, ale množinu ${ displaystyle n = lpodlaha m / 2 rpodlaha}$. Pro m zvláštní, pak lze ukázat, že se to rovná obvyklému Pfaffianovi z (m +1) x (m +1) rozměrová zkosená symetrická matice, kde jsme přidali (m +1) th sloupec skládající se z m prvky 1, an (m +1) th řádek se skládá z m prvky -1 a rohový prvek je nula. Obvyklé vlastnosti Pfaffianů, například vztah k determinantu, pak platí pro tuto rozšířenou matici.

Vlastnosti a identity

Pfaffiani mají následující vlastnosti, které jsou podobné vlastnostem determinantů.

• Násobení řádku a sloupce konstantou je ekvivalentní násobení Pfaffianu stejnou konstantou.
• Současná výměna dvou různých řádků a odpovídajících sloupců mění znaménko Pfaffian.
• Násobek řádku a odpovídajícího sloupce přidaného do jiného řádku a odpovídajícího sloupce nezmění hodnotu Pfaffian.

Pomocí těchto vlastností lze Pfaffiany rychle vypočítat, podobně jako výpočet determinantů.

Smíšený

Pro 2n × 2n šikmo symetrická matice A

${ displaystyle operatorname {pf} (A ^ { text {T}}) = (- 1) ^ {n} operatorname {pf} (A).}$

${ displaystyle operatorname {pf} ( lambda A) = lambda ^ {n} operatorname {pf} (A).}$

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

Pro libovolné 2n × 2n matice B,

${ displaystyle operatorname {pf} (BAB ^ { text {T}}) = det (B) operatorname {pf} (A).}$

Nahrazení v této rovnici B = A^m, jeden dostane za celé číslo m

${ displaystyle operatorname {pf} (A ^ {2m + 1}) = (- 1) ^ {nm} operatorname {pf} (A) ^ {2m + 1}.}$

Derivativní identity

Li A záleží na nějaké proměnné X_i, pak je gradient Pfaffianu dán vztahem

${ displaystyle { frac {1} { operatorname {pf} (A)}} { frac { částečné operatorname {pf} (A)} { částečné x_ {i}}} = { frac {1 } {2}} operatorname {tr} vlevo (A ^ {- 1} { frac { částečné A} { částečné x_ {i}}} vpravo),}$

a Hesián Pfaffian je dán

${ displaystyle { frac {1} { operatorname {pf} (A)}} { frac { částečné ^ {2} operatorname {pf} (A)} { částečné x_ {i} částečné x_ { j}}} = { frac {1} {2}} operatorname {tr} left (A ^ {- 1} { frac { částečné ^ {2} A} { částečné x_ {i} částečné x_ {j}}} vpravo) - { frac {1} {2}} operatorname {tr} vlevo (A ^ {- 1} { frac { částečné A} { částečné x_ {i}} } A ^ {- 1} { frac { částečné A} { částečné x_ {j}}} pravé) + { frac {1} {4}} operatorname {tr} levé (A ^ {- 1} { frac { částečné A} { částečné x_ {i}}} pravé) operatorname {tr} levé (A ^ {- 1} { frac { částečné A} { částečné x_ {j }}}že jo).}$

Stopové identity

Produkt Pfaffianů zešikmených symetrických matic A a B za podmínky, že A^TB je pozitivně definitivní matice mohou být reprezentovány ve formě exponenciálu

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

Předpokládat A a B jsou 2n × 2n tedy symetrické matice zešikmení

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

a B_n(s₁,s₂,...,s_n) jsou Polynomy zvonu.

Blokové matice

Pro blokovou diagonální matici

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

${ displaystyle operatorname {pf} (A_ {1} oplus A_ {2}) = operatorname {pf} (A_ {1}) operatorname {pf} (A_ {2}).}$

Pro svévolné n × n matice M:

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

Často se vyžaduje výpočet pfaffianu zešikmené symetrické matice ${ displaystyle S}$ s blokovou strukturou

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

kde ${ displaystyle M}$ a ${ displaystyle N}$ jsou šikmo symetrické matice a ${ displaystyle Q}$ je obecná obdélníková matice.

Když ${ displaystyle M}$ je invertibilní, jeden má

${ displaystyle operatorname {pf} (S) = operatorname {pf} (M) operatorname {pf} (N + Q ^ {T} M ^ {- 1} Q).}$

To je patrné z Aitkenova vzorce pro diagonalizaci bloků,^[4][5][6]

${ displaystyle { 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}}.}$

Tento rozklad zahrnuje a kongruenční transformace které umožňují použít vlastnost pfaffian ${ displaystyle operatorname {pf} (BAB ^ {T}) = operatorname {det} (B) operatorname {pf} (A)}$.

Podobně, když ${ displaystyle N}$ je invertibilní, jeden má

${ displaystyle operatorname {pf} (S) = operatorname {pf} (N) operatorname {pf} (M + QN ^ {- 1} Q ^ {T}),}$

jak je vidět při použití rozkladu

${ displaystyle { 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 konec {pmatrix}}.}$

Výpočet Pfaffian numericky

Předpokládat A je 2n × 2n tedy symetrické matice zešikmení

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

kde ${ displaystyle sigma _ {y}}$ je druhá Pauliho matice, ${ displaystyle I_ {n}}$ je matice identity dimenze n a stopu jsme převzali a maticový logaritmus.

Tato rovnost je založena na sledovat identitu

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

a na pozorování, že ${ displaystyle { textrm {pf}} ( sigma _ {y} další I_ {n}) = (- i) ^ {n ^ {2}}}$.

Od výpočtu Logaritmus matice je výpočetně náročný úkol, lze místo toho vypočítat všechna vlastní čísla z ${ displaystyle (( sigma _ {y} krát I_ {n}) ^ {T} cdot A)}$, vezměte protokol všech těchto a shrňte je. Tento postup pouze využívá vlastnictví ${ displaystyle operatorname {tr} { log {(AB)}} = operatorname {tr} { log {(A)}} + operatorname {tr} { log {(B)}}}$. To lze implementovat v Mathematica v jednom řádku:

Pf [x_]: = Modul [{n = Rozměry [x] [[1]] / 2}, I ^ (n ^ 2) Exp [1/2 Celkem [Log [Vlastní čísla [Dot [KroneckerProduct [PauliMatrix [2]] , IdentityMatrix [n]], x]]]]]]]

Pro další efektivní algoritmy viz (Wimmer 2012 ).

Aplikace

• Existují programy pro numerický výpočet Pfaffian na různých platformách (Python, Matlab, Mathematica) (Wimmer 2012 ).
• Pfaffian je invariantní polynom symetrické matice zešikmení pod řádkem ortogonální změna základny. Proto je to důležité v teorii charakteristické třídy. Zejména jej lze použít k definování Eulerova třída a Riemannovo potrubí který se používá v zobecněná věta Gauss – Bonnet.
• Počet perfektní párování v rovinný graf je dán Pfaffianem, proto je polynomiální čas vypočítatelný pomocí Algoritmus FKT. To je překvapivé vzhledem k tomu, že u obecných grafů je problém velmi obtížný (tzv # P-kompletní ). Tento výsledek se používá k výpočtu počtu domino obklady obdélníku, funkce oddílu z Ising modely ve fyzice nebo Markovova náhodná pole v strojové učení (Globerson & Jaakkola 2007; Schraudolph & Kamenetsky 2009 ), kde je podkladový graf rovinný. Používá se také k odvození efektivních algoritmů pro některé jinak zdánlivě neřešitelné problémy, včetně efektivní simulace určitých typů omezený kvantový výpočet. Číst Holografický algoritmus Pro více informací.

Viz také

• Rozhodující
• Dimer model
• Hafnian
• Polyomino
• Statistická mechanika

Poznámky

Reference

• Cayley, Arthur (1849). „Sur les déterminants gauches“. Journal für die reine und angewandte Mathematik. 38: 93–96.CS1 maint: ref = harv (odkaz)
• Cayley, Arthur (1852). „K teorii permutantů“. Cambridge a Dublin Mathematical Journal. VII: 40–51.CS1 maint: ref = harv (odkaz) Přetištěno v Sebrané matematické práce, svazek 2.
• Kasteleyn, P. W. (1961). „Statistika dimerů na mřížce. I. Počet uspořádání dimerů na kvadratické mřížce“. Physica. 27 (12): 1209–1225. Bibcode:1961Phy .... 27.1209K. doi:10.1016/0031-8914(61)90063-5.CS1 maint: ref = harv (odkaz)
• Propp, James (2004). "Lambda-determinanty a dominové obklady". arXiv:matematika / 0406301.CS1 maint: ref = harv (odkaz)
• Globerson, Amir; Jaakkola, Tommi (2007). „Přibližný závěr pomocí rozkladu planárního grafu“ (PDF). Pokroky v systémech zpracování neurálních informací 19. MIT Stiskněte.CS1 maint: ref = harv (odkaz).
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Efektivní přesný závěr v planárních Isingových modelech" (PDF). Pokroky v systémech zpracování neurálních informací 21. MIT Stiskněte.CS1 maint: ref = harv (odkaz).
• Jeliss, G.P .; Chapman, Robin J. (1996). "Ovládnutí šachovnice". Deník her a hádanek. 2 (14): 204–5.CS1 maint: ref = harv (odkaz)
• Sellers, James A. (2002). „Domino obklady a výrobky z Fibonacciho a Pellova čísla“. Journal of Integer Sequences. 5 (1): 02.1.2.CS1 maint: ref = harv (odkaz)
• Wells, David (1997). Slovník tučňáků zvědavých a zajímavých čísel (přepracované vydání). p. 182. ISBN  0-14-026149-4.CS1 maint: ref = harv (odkaz)
• Muir, Thomas (1882). Pojednání o teorii determinantů. Macmillan a spol.CS1 maint: ref = harv (odkaz) Online
• Parameswaran, S. (1954). "Skew-symetrické determinanty". Americký matematický měsíčník. 61 (2): 116. doi:10.2307/2307800. JSTOR  2307800.CS1 maint: ref = harv (odkaz)
• Wimmer, M. (2012). "Efektivní numerický výpočet Pfaffianu pro husté a pruhované šikmé symetrické matice". ACM Trans. Matematika. Softw. 38: 30. arXiv:1102.3440. doi:10.1145/2331130.2331138.CS1 maint: ref = harv (odkaz)
• de Bruijn, N. G. (1955). "Na několika vícenásobných integrálech zahrnujících determinanty". J. Indian Math. Soc. 19: 131–151.CS1 maint: ref = harv (odkaz)

externí odkazy

• "Pfaffian", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Pfaffian na PlanetMath.org
• T. Jones, Produkt Pfaffian a Wedge (demonstrace důkazu vztahu Pfaffian / determinant)
• R. Kenyon a A. Okounkov, Co je ... dimer?
• OEIS sekvence A004003 (počet domino obkladů (nebo krytů dimeru))
• W. Ledermann „Poznámka o zkosených symetrických determinantech“ https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants