파피안

수학에서, 스큐 대칭 행렬의 결정 인자는 항상 행렬의 크기에만 의존하는 정수 계수를 가진 다항식인 행렬 항목의 다항식의 제곱으로 쓸 수 있다.이 다항식의 값은, 스큐 대칭 행렬의 계수에 적용되었을 때, 그 행렬의 Pafeian이라고 불린다.파피안이라는 용어는 케일리(1852년)가 요한 프리드리히 파프의 이름을 간접적으로 따서 붙인 말이다.Pafeian(다항식으로서 고려됨)은 2n × 2n 스큐 대칭 행렬에 대해서만 비바니싱되며, 이 경우 도 n의 다항식이다.

명시적으로, 스큐 대칭 행렬 A의 경우,

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

그것은 자코비의 일반적인 미분 방정식의 파피안 시스템에 대한 초기 연구에 기초한 작품인 Cayley(1849년)에 의해 처음 증명되었다.

모든 스큐 대칭 행렬의 결정요인이 다항 행렬의 제곱이라는 사실은 행렬을 블록 행렬로 작성한 다음 유도를 사용하고 스큐 대칭인 슈르 보완을 조사함으로써 알 수 있다.^[1]

예

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

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

(3은 홀수이므로 B의 Papiian은 0)

${\displaystyle \be+dc.} {\displaysty}{bmatrix}0&a&c\-a&d&e\\-b&d&d&f\\\-c&e&f&f&f&#end{bmatrix}=af-be+dc.}$

2n × 2n 스큐 대칭 3지각 행렬의 Pafeian은 다음과 같이 주어진다.

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

(모든 skew-대칭 $행렬$은 ${\displaystyle {모든}_{}}$ b$$i {\$displaystyle b_{$i}가 0인$$ 상태에서 이 형태로 축소될 수 있다는 점에 유의하십시오. skew-대칭 행렬의 스펙트럼 이론을 참조하십시오.)

형식 정의

A = (a_i,j) 2n × 2n 스큐 대칭 행렬이 되게 한다.A의 Paffian은 공식에 의해 명시적으로 정의된다.

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

여기서 S는_2n 순서(2n)의 대칭 그룹이고, sgn(sn)은 σ의 서명이다.또는 (그러나 동등하게), Pafeian은 다음과^[2] 같이 쓰일 수 있다.

${\displaystyle \operatorname {pf}(A)={\frac {1}{2^{n}n!}}}\varepsilon _{i_{1}j_{1}i_{2}j_{2}\ldots i_{n}}\,a_{i_{1}j_{1}a_{1}:{2}}:\ldots a_{i_{n_{n}}}}.$

여기서 Levi-Civita 기호를 사용하고 반복 지수에 대한 합계를 암시한다.

A의 스큐 대칭성을 이용하여 가능한 모든 순열의 합계를 피할 수 있다.π은 순서와 관계없이 모든 {1, 2, ..., 2n} 파티션의 집합이 되도록 한다.(2n)!/(2nⁿ!) = (2n - 1)!!그런 칸막이원소 α ∈ π as은 다음과 같이 쓸 수 있다.

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

i_k < j와_k < i< n ${\$ .let.

${\displaystyle \pi _{\n1}={\bmatrix}1&2&3&4&\cdots &2n\i_{1}{1}j_{1}&i_{2}&j_{n}&dots &i_{n}&j_{n}}\end{bmatrix}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

같은 순열이다위와 같이 파티션 α가 주어지면 정의한다.

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

A의 Paffian은 다음에 의해 주어진다.

${\displaystyle \operatorname {pf}(A)=\sum _{\alpha \in \Pi }A_{\alpha }}}$

홀수 n×n 스큐 대칭 행렬의 파피안은 스큐 대칭 행렬의 경우, 스큐 대칭 행렬의 경우, 홀수 대칭 행렬의 결정 요인이 0이기 때문에 0으로 정의된다.

그리고 n 홀수인 경우, 이는 ${\displaystyle 데트}$ A${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \det \,A=0}$을(를) 의미한다$.$

재귀적 정의

관례상 0×0 행렬의 파피안은 1과 같다.n>0이 있는 스큐 대칭 2n×2n 매트릭스 A의 Pafeian은 다음과 같이 재귀적으로 계산할 수 있다.

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

여기서 색인 i를 임의로 선택할 수 있는 ${\displaystyle {\theta \stackrel{}{}}_{}}$${\displaystyle (i}$- $){\displaystyle \theta(i-j)}$는 Hubidiside step 함수로서, $A{\displaystyle {}_{}}$ ${\displaystyle {\stackrel{}{^^}}_{}}$ $^{\data${\$imath }}}}}{\hat{\jmath{}}}}}}}}}}}}$는 i번째 행과 열이 모두 제거된 매트릭스 A를 나타낸다.^[3]특수 선택 $i{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle i=1}$의 경우$$ 이 값이 더 간단한 식으로 감소하는 방법을 참고하십시오.

${\displaystyle \operatorname {pf}(A)=\sum _{j=2}^{2n(-1)^{j}a_{1j}\operatorname {pf}(A_{1}{1}:{\hat{\jmath }}})}$

대체 정의

모든 스큐 대칭 2n×2n 행렬 A = (a_ij) 이벡터에 연결할 수 있다.

${\displaystyle \omega =\sum _{ij}\;e_{i}\displaystyle e_{j}.}$

여기서 {e₁, e₂, ..., e_2n}은(는) R의²ⁿ 표준 기준이다.그런 다음 Pafeian은 방정식으로 정의된다.

${\displaystyle {\frac {1}{n!}}}\오메가^{n}=\operatorname {pf}(A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n}}}$

여기서 Ω은ⁿ n개의 Ω 복사본의 쐐기 곱을 의미한다.

결정자를 포함하는 다중 통합에 대한 de Bruijn의 작업에서 Paffian을 홀수 치수 행렬에 대해 0이 아닌 일반화한다.^[4]In particular for any m x m matrix A, we use the formal definition above but set ${\displaystyle n=\lfloor m/2\rfloor }$. For m odd, one can then show that this is equal to the usual Pfaffian of an (m+1) x (m+1) dimensional skew symmetric matrix where we have added an (m+1)th column consisting of m elements 1, an (m+1)th rowm 원소 -1로 구성되며, 코너 원소는 0이다.예를 들어 결정인자에 대한 관계와 같은 Paffians의 일반적인 속성은 이 확장 행렬에 적용된다.

속성 및 ID

파피안에는 다음과 같은 성질이 있는데, 이는 결정요인의 성질과 유사하다.

• 행과 열을 상수로 곱하는 것은 같은 상수로 파피안을 곱하는 것과 같다.
• 두 개의 다른 행과 해당 열의 동시 교환은 Pafeian의 기호를 변경한다.
• 행의 배수와 해당 열을 다른 행과 해당 열에 추가해도 Pafeian 값은 변경되지 않는다.

이러한 특성을 이용하여 Pafeians는 결정인자 계산과 유사하게 빠르게 계산될 수 있다.

잡다한

2n × 2n 스큐 대칭 행렬 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)}$

임의 2n × 2n 행렬 B의 경우,

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

이 방정식 B = A에서^m 대체하면 모든 정수 m을 얻게 된다.

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

파생아이덴티

A가 일부 변수 x에_i 의존하는 경우 다음과 같이 Paffian의 그라데이션이 주어진다.

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

그리고 파피안의 헤시안은 다음과 같이 주어진다.

${\displaystyle {\frac {1}{\operatorname {pf} (A)}}{\frac {\partial ^{2}\operatorname {pf} (A)}{\partial x_{i}\partial x_{j}}}={\frac {1}{2}}\operatorname {tr} \left(A^{-1}{\frac {\partial ^{2}A}{\partial x_{i}\partial x_{j}}}\right)-{\frac {1}{2}}\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}}}A^{-1}{\frac {\partial A}{\partial x_{j}}}\right)+{\frac {1}{4}}\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{i}}}\right)\operatorname {tr} \left(A^{-1}{\frac {\partial A}{\partial x_{j}}}\right).}$

추적 신원

AB가^T 양의 확정 행렬이라는 조건 하에 Skew-대칭 행렬 A와 B의 Paffians 산물은 지수 형태로 나타낼 수 있다.

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

A와 B가 2n × 2n 스큐 대칭 행렬이라고 가정하자.

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

및 B_n(s₁,s₂,s,...s_n)는 Bell 다항식이다.

블록 행렬

블록-대각 행렬의 경우

${\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})}$

임의 n × n 행렬 M의 경우:

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

종종 블록 구조를 사용하여$$ 스큐 대칭 $매트릭스$ S {\$displaystyle{\displaystyle }$ $S}$의 파피안을 계산해야 한다.

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

여기서 $M{\displaystyle }$ ${\displaystyle M}$ 및$$ $N{\displaystyle }$ ${\displaystyle N}$은(는) 스큐 대칭 행렬이고$$ $Q{\displaystyle }$ ${\displaystyle Q}$은 일반적인 직사각형 행렬이다.

$M{\displaystyle }$ ${\displaystyle M}$을(를) 변환할 수 없는 경우

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

이것은 아이트켄 블록-대각형화 공식에서 볼 수 있다.^[5][6][7]

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

이 분해는 ${\displaystyle \mathrm{pf}}$(${\displaystyle B}$ ${\displaystyle A}$ B ${\displaystyle T^{}}$)${\displaystyle }$= ${\displaystyle \det }$ ${\displaystyle }$ (${\displaystyle B}$ ${\displaystyle )}$ ${\displaystyle \mathrm{pf}}$ (${\displaystyle A}$) ${\displaystyle \operatorname {pf}(BAB^{)$를 사용할 수 있는 결합 변환을 포함한다.$T}=\operatorname {det}(B)\operatorname {pf}(A)}$.

마찬가지로, $N{\displaystyle }$ ${\displaystyle N}$이(가) 변환 불가능한 경우$$

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

분해를 채용하여 알 수 있는 바와 같이.

${\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\end{pmatrix}.}$

Paffian을 숫자로 계산

A가 2n × 2n 스큐 대칭 행렬이라고 가정해 보십시오.

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

여기서 $\sigma {\displaystyle {}_{}}$ ${\displaystyle y_{}}$ ${\$는 두$$ 번째 Pauli 행렬이고, ${\displaystyle {In}_{}}$ ${\$는 차원 n의 ID 행렬이며, 행렬$$ 로그 위에 추적을 했다.

이 평등은 추적 정체성에 기초한다.

${\displaystyle {\textrm {pf}(A)\,{\textrm {pf}}(B)=\exp \left({\tfrac {1}{2}}\mathrm {tr}\log(A^{\text}){\ext}T}}B)\오른쪽)$

그리고 ${\displaystyle \text{pf}}$ (${\displaystyle {}_{}}$ ${\displaystyle y_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle I_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$=${\displaystyle }$(${\displaystyle }$- i${\displaystyle {}^{}}$) ${\displaystyle {{n\mathrm{}}^{}}^{}}$ 2 ${\$pf})(\sigma _{$y}\otimes I_{n}=(-i)^{n^{$2$\}\}.$

행렬의 로그 계산은 계산적으로 까다로운 작업이기 때문에$,$ 대신 ( (${\displaystyle y_{}}$ y${\displaystyle {}_{}{i}_{}}$ I${\displaystyle {}_{}{}^{}}$n ) ${\displaystyle T^{}}$⋅${\displaystyle A}$ )의 모든 고유값을 계산할 수 있다$(\sigma _{y}\otimes I_{n}).$$T}\cdot A)},$이 모든 것의 일지를 취합하여 요약하시오.This procedure merely exploits the property ${\displaystyle \operatorname {tr} {\log {(AB)}}=\operatorname {tr} {\log {(A)}}+\operatorname {tr} {\log {(B)}}}$. This can be implemented in Mathematica within a single line:

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

기타 효율적인 알고리즘은 (Wimmer 2012)를 참조하십시오.

적용들

• 다양한 플랫폼(Python, Mattlab, Mathematica)에서 Pafeian의 수치 계산을 위한 프로그램이 존재한다(Wimmer 2012).
• Pafeian은 적절한 직교 기준 변화 하에서 스큐 대칭 행렬의 불변 다항식이다.그만큼 특성계급 이론에서도 중요하다.특히 일반화된 가우스-보넷 정리에 사용되는 리만 다지관의 오일러 계급을 규정하는 데 사용할 수 있다.
• 평면 그래프의 완벽한 일치 수는 Paffian에 의해 제공되므로 FKT 알고리즘을 통해 계산할 수 있는 다항식 시간이다.일반 그래프의 경우 문제가 매우 어렵다는 점을 감안하면 놀라운 일이다(일명 #P-완전함).이 결과는 직사각형의 도미노 기울기 수, 물리학에서 Ising 모델의 파티션 함수 또는 기계 학습에서 마르코프 무작위 필드의 파티션 함수(Globerson & Jaakkola 2007; Schrudolph & Kamenetsky 2009)를 계산하는 데 사용된다. 여기서 기초 그래프는 평면이다.그것은 또한 제한된 양자 계산의 특정 유형의 효율적인 시뮬레이션을 포함하여, 겉보기에는 다루기 어려운 몇몇 문제에 대한 효율적인 알고리즘을 도출하는데 사용된다.자세한 내용은 홀로그래픽 알고리즘을 참조하십시오.

참고 항목

• 결정인자
• 디머 모델
• 하프니아어
• 폴리오미노
• 통계역학

메모들

참조

• Cayley, Arthur (1849). "Sur les déterminants gauches". Journal für die reine und angewandte Mathematik. 38: 93–96.
• Cayley, Arthur (1852). "On the theory of permutants". Cambridge and Dublin Mathematical Journal. VII: 40–51. 수집된 수학 논문에 재인쇄, 제2권.
• Kasteleyn, P. W. (1961). "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice". Physica. 27 (12): 1209–1225. Bibcode:1961Phy....27.1209K. doi:10.1016/0031-8914(61)90063-5.
• Propp, James (2004). "Lambda-determinants and domino-tilings". arXiv:math/0406301.
• Globerson, Amir; Jaakkola, Tommi (2007). "Approximate inference using planar graph decomposition" (PDF). Advances in Neural Information Processing Systems 19. MIT Press..
• Schraudolph, Nicol; Kamenetsky, Dmitry (2009). "Efficient exact inference in planar Ising models" (PDF). Advances in Neural Information Processing Systems 21. MIT Press..
• Jeliss, G.P.; Chapman, Robin J. (1996). "Dominizing the Chessboard". The Games and Puzzles Journal. 2 (14): 204–5.
• Sellers, James A. (2002). "Domino Tilings and Products of Fibonacci and Pell numbers". Journal of Integer Sequences. 5 (1): 02.1.2. Bibcode:2002JIntS...5...12S.
• Wells, David (1997). The Penguin Dictionary of Curious and Interesting Numbers (revised ed.). p. 182. ISBN 0-14-026149-4.
• Muir, Thomas (1882). A Treatise on the Theory of Determinants. Macmillan and Co. 온라인.
• Parameswaran, S. (1954). "Skew-Symmetric Determinants". The American Mathematical Monthly. 61 (2): 116. doi:10.2307/2307800. JSTOR 2307800.
• Wimmer, M. (2012). "Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices". ACM Trans. Math. Softw. 38: 30. arXiv:1102.3440. doi:10.1145/2331130.2331138. S2CID 15331538.
• de Bruijn, N. G. (1955). "On some multiple integrals involving determinants". J. Indian Math. Soc. 19: 131–151.

외부 링크

• "Pfaffian", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• PlanetMath.org의 Papiian.
• T. Jones, The Paffian 및 Wege Product(Paffian/결정적 관계의 증거)
• Kenyon과 A. 오쿤코프, 어둑어둑한 게 뭐야?
• OEIS 시퀀스 A004003(도미노 기울기(또는 조광기 커버) 수)
• W. 레더만 "꼬치-편향 결정요인에 대한 참고서" https://www.researchgate.net/publication/231827602_A_note_on_skew-symmetric_determinants