パフィアン

数学において、m行m列の歪対称行列の行列式は、常に行列要素の多項式の平方として表すことができます。多項式とは、 m のみに依存する整数係数の多項式です。m が奇数の場合、多項式はゼロになり、mが偶数の場合、 m /2次でゼロでない多項式となり、±1 を乗じない限り一意です。以下の例で示す歪対称三重対角行列の規則により、パフィアン多項式と呼ばれる特定の多項式が決定されます。この多項式の値を歪対称行列の要素に適用した場合、その値はその行列のパフィアンと呼ばれます。パフィアンという用語は、ヨハン・フリードリヒ・パフィアン にちなんで間接的に命名されたCayley (1852)によって導入されました。

具体的には、歪対称行列の場合、 ${\displaystyle A}$

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

これは、 Cayley  (1849)によって初めて証明されました。彼は、微分方程式のパフィアン系に関する研究でこれらの多項式を導入したJacobi を引用しています。Cayley はこの関係を、第 1 行と第 1 列のみで歪対称性から外れる行列のより一般的な結果を特殊化することで得ました。このような行列の行列式は、元の行列の左上隅を最初にゼロに設定し、次に第 1 行の負の転置を第 1 列に、第 1 列の負の転置を第 1 行にそれぞれコピーすることによって得られる 2 つの行列のパフィアンの積です。これは、行列式をマイナーに展開し、以下の再帰式を使用すること で、帰納的に証明されます。

${\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 は奇数なので、B のパフィアンは 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.}$

2 n × 2 nの歪対称三角行列のパフィアンは次のように与えられる。

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

(任意の歪対称行列はこの形式に簡約できることに注意してください。歪対称行列のスペクトル理論を参照してください。)

A = ( a _ij ) を 2 n × 2 n の歪対称行列とする。A のパフィアンは、次の式で明示的に定義される。

${\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 _{2 nは}2 n次の対称群であり、sgn(σ)はσの符号である。

Aの歪対称性を利用して、すべての可能な順列を足し合わせることを避けることができます。Π を、{1, 2, ..., 2 n } を順序に関係なく 2 つに分割したすべてのものの集合とします。このような分割は(2 n )!/(2 ⁿ n !) = (2 n − 1) !!個あります。要素α ∈ Π は次のように書くことができます 。

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

i _k < j _kかつとする。 ${\displaystyle i_{1}$

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

対応する順列とする。上のような分割αが与えられたとき、定義する。

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

Aのパフィアンは次のように与えられる。

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

nが奇数のときのn × n歪対称行列のパフィアンは、歪対称行列の行列式がゼロであるのと同様に、ゼロと定義されます。歪対称行列 の場合、 およびn が奇数のときは、これが成り立つからです。 $${\displaystyle \det A=\det A^{\text{T}}=\det(-A)=(-1)^{n}\det A,}$$${\displaystyle \det A=0}$

慣例により、0 × 0行列のパフィアンは1に等しい。n > 0の歪対称2 n × 2 n行列Aのパフィアンは、次のように再帰的に計算できる。

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

ここで、添え字i は任意に選択でき、はヘヴィサイドのステップ関数であり、i番目とj番目の行と列が削除された行列Aを表します。 ^[1]特別な選択により、これがより単純な式に簡略化されることに注意してください。 ${\displaystyle \theta (ij)}$${\displaystyle A_{{\hat {\imath }}{\hat {\jmath }}}}$${\displaystyle i=1}$

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

任意の歪対称2 n × 2 n行列A = ( a _ij )にバイベクトルを関連付けることができる。

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

ここで、{ e ₁ , e ₂ , ..., e _{2 n} }はR ^{2 n}の標準基底である。パフィアンは次式で定義される。

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

ここでω ^{n は}ωのn 個のコピーのウェッジ積を表します。 

同様に、バイベクトル（和の制約を課したくない場合に便利です） を考慮すると、 次のようになります。${\displaystyle i<j}$$${\displaystyle \omega '=2\omega =\sum _{i,j}a_{ij}\;e_{i}\wedge e_{j},}$$${\displaystyle \omega '^{n}=2^{n}n!\operatorname {pf} (A)\;e_{1}\wedge e_{2}\wedge \cdots \wedge e_{2n}.}$

パフィアンの奇数次元行列への非ゼロの一般化は、行列式を含む多重積分に関する de Bruijn の研究で与えられている。^[2]特に、任意のm  ×  m行列Aに対して、上記の正式な定義を使用するが、 と設定する。m が奇数の場合、これは、m 個の要素 1 からなる ( m +1 ) 番目の列と、 m個の要素 −1 からなる ( m +1) 番目の行を追加し、コーナー要素が 0 である、(m +1) × (m +1) 次元の歪対称行列の通常のパフィアンに等しいことが示される。パフィアンの通常のプロパティ、たとえば行列式との関係は、この拡張された行列に適用されます。 ${\displaystyle n=\lfloor m/2\rfloor }$

パフィアンには、行列式と同様の以下の特性があります。

• 行と列に定数を掛けることは、パフィアンに同じ定数を掛けることと同じです。
• 2 つの異なる行と対応する列を同時に交換すると、パフィアンの符号が変わります。
• ある行とそれに対応する列の倍数を別の行とそれに対応する列に追加しても、Pfaffian の値は変わりません。

これらの特性を利用すると、行列式の計算と同様に、パフィアンを素早く計算できます。

2 n × 2 nの歪対称行列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).}$

任意の2 n × 2 n行列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}.}$

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

前述のように、 も同様です。 ここでは を定義しました。 ${\displaystyle A\rightarrow \sum _{ij}A_{ij}e_{i}\wedge e_{j}{\xrightarrow[{}]{\wedge n}}{2^{n}n!}Pf(A)e_{1}\wedge \cdots \wedge e_{2n}.}$${\displaystyle BAB^{\mathrm {T} }}$$${\displaystyle {\begin{aligned}&BAB^{\mathrm {T} }\rightarrow \sum _{ijkl}B_{ik}B_{jl}A_{kl}e_{i}\wedge e_{j}=\sum _{kl}A_{kl}f_{k}\wedge f_{l}\\&\xrightarrow {\wedge n} {2^{n}n!}Pf(A)f_{1}\wedge \cdots \wedge f_{2n}={2^{n}n!}Pf(BAB^{\mathrm {T} })e_{1}\wedge \cdots \wedge e_{2n},\end{aligned}}}$$${\displaystyle f_{k}=\sum _{i}B_{ik}e_{i}}$

証明は終わった ので。${\displaystyle f_{1}\wedge \cdots \wedge f_{2n}=\det(B)e_{1}\wedge \cdots \wedge e_{2n},}$

証明：${\displaystyle \operatorname {pf} (A)^{2}=\det(A)}$

は多項式の方程式なので、実数行列に対して証明すれば十分であり、複素数行列にも自動的に適用されます。 ${\displaystyle \operatorname {pf} (A)^{2}=\det(A)}$

歪対称実行行列のスペクトル理論により、が成り立ちます。ここで は直交し、 実数 に対して となります。ここで前の定理を適用すると、 が得られます。 ${\displaystyle A=Q\Sigma Q^{\mathrm {T} }}$${\displaystyle Q}$$${\displaystyle \Sigma ={\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}}}$$${\displaystyle a_{k}}$${\displaystyle pf(A)^{2}=pf(\Sigma )^{2}\det(Q)^{2}=pf(\Sigma )^{2}=\left(\prod a_{i}\right)^{2}=\det(A)}$

Aが何らかの変数x _iに依存する場合、パフィアンの勾配は次のように表される。

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

歪対称行列AとBのパフィアンの積は指数関数の形で表すことができる。

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

AとBが2n ×2nの歪対称行列 であるとすると、

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

そしてBn ( s1 , s2 _, ..., _sn )は_ベル多項式_である。

ブロック対角行列の場合

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

ブロック構造を持つ 歪対称行列のパフィアンを計算することがしばしば必要となる。${\displaystyle S}$

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

ここで、およびは歪対称行列であり、は一般的な長方形行列です。 ${\displaystyle M}$${\displaystyle N}$${\displaystyle Q}$

が逆であるとき、 ${\displaystyle M}$

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

^{これはエイトケンのブロック対角化公式[3] [4] [5]}からわかる。

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

この分解には、パフィアン特性を使用できる合同変換が含まれます。 ${\displaystyle \operatorname {pf} (BAB^{\mathrm {T} })=\operatorname {det} (B)\operatorname {pf} (A)}$

同様に、が逆数であるとき、 ${\displaystyle N}$

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

分解するとわかるように

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

Aが2n×2nの歪対称行列 であるとすると、

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

ここで、は 2 番目のパウリ行列、はn次元の単位行列であり、行列対数上のトレースを取得しました。 ${\displaystyle \sigma _{y}}$${\displaystyle I_{n}}$

この等式はトレースの同一性に基づいている

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

そして、次の観察に基づいて。 ${\displaystyle {\textrm {pf}}(\sigma _{y}\otimes I_{n})=(-i)^{n^{2}}}$

行列の対数を計算するのは計算量の多い作業なので、代わりにのすべての固有値を計算し、これらすべての対数を取って合計することができます。この手順は、単に という特性を利用しています。これは、 Mathematicaで1 つのステートメントで 実装できます。${\displaystyle ((\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A)}$ ${\displaystyle \operatorname {tr} {\log {(AB)}}=\operatorname {tr} {\log {(A)}}+\operatorname {tr} {\log {(B)}}}$

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

しかし、このアルゴリズムは、パフィアンが大きい場合、不安定になります。 の固有値は一般に複素数であり、これらの複素固有値の対数は一般に であるとみなされます。 総和の下では、実数値のパフィアンの場合、指数の引数は、ある整数 に対して の形式で与えられます。が非常に大きい場合、複素位相から得られる符号を計算する際の丸め誤差により、虚数部がゼロ以外の値になる可能性があります。 ${\displaystyle (\sigma _{y}\otimes I_{n})^{\mathrm {T} }\cdot A}$${\displaystyle [-\pi ,\pi ]}$${\displaystyle x+k\pi /2}$${\displaystyle k}$${\displaystyle x}$

他の（より）効率的なアルゴリズムについては、Wimmer 2012 を参照してください。

• さまざまなプラットフォーム (Python、Matlab、Mathematica) 上で Pfaffian の数値計算を行うプログラムが存在します (Wimmer 2012)。
• パフィアンは、基底の適切な直交変換の下での歪対称行列の不変多項式です。そのため、特性類の理論では重要です。特に、一般化されたガウス・ボネの定理で使用されるリーマン多様体のオイラー類を定義するために使用できます。
• 平面グラフの完全マッチングの数はパフィアンで与えられるため、FKT アルゴリズムで多項式時間で計算できます。一般的なグラフでは、この問題は非常に難しい (いわゆる#P 完全) ことを考えると、これは驚くべきことです。この結果は、基礎となるグラフが平面である場合、長方形のドミノタイルの数、物理学のイジングモデルの分割関数、または機械学習のマルコフランダムフィールド(Globerson & Jaakkola 2007; Schraudolph & Kamenetsky 2009) の計算に使用されます。また、これは、ある種の制限された量子計算の効率的なシミュレーションなど、一見解決不可能な問題に対する効率的なアルゴリズムを導出するためにも使用されます。詳細については、ホログラフィックアルゴリズムを参照してください。

• 決定要因
• 二量体モデル
• ハフニアン
• ポリオミノ
• 統計力学