行列のパフィアン，パーマネント，ハフニアン

$2n\times 2n$ の歪対称行列（反対称行列，$A^{\top}=-A$ となる行列）$A$ に対して定義される以下の量をパフィアン（pfaffian）と言います：

$\mathrm{pf}\:A=\displaystyle\sum_{M}\mathrm{sgn}(M)\prod_{(i,j)\in M}a_{ij}$

$M$ は $\{1,2,\cdots,2n\}$ の $n$ 個のペアへの分割 $\{(i_1,j_1),\cdots,(i_n,j_n)\}$ 全体を動きます（$i_1 <\cdots < i_n$ かつ $i_1< j_1,\cdots, i_n< j_n$ ）。$\mathrm{sgn}(M)$ は，置換 $\begin{pmatrix}1&2&\cdots &2n-1&2n\\i_1&j_1&\cdots&i_n&j_n\end{pmatrix}$

の符号を表します。

パフィアンと行列式の関係

任意の $2n\times 2n$ 歪対称行列 $A$ に対して $\det A=(\mathrm{pf}\:A)^2$ が成立します（証明はよい練習問題レベル）。つまり，行列のパフィアンは行列式の計算と同じくらいの手間で計算できるということが分かります。

行列のパフィアンを用いることで平面グラフの完全マッチングを数え上げることができます（pfaffian orientation）。

これはとあるモデルの分配関数を計算するのにも役立ちます。つまりパフィアンは物理にも応用がある素晴らしいものなのです。

行列式： $\det A=\displaystyle\sum_{\sigma}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i\sigma(i)}$

の符号部分を除いたものを行列のパーマネント（permanent）と言います：

$\mathrm{perm}\:A=\displaystyle\sum_{\sigma}\prod_{i=1}^na_{i\sigma(i)}$

符号部分がないため，行列式より定義は簡単に見えますが，パーマネントの計算はとても難しいです。実際，行列式の計算は掃き出し法を使えば $O(n^3)$ でできます（もっと頑張ればオーダーをもう少し下げることもできる）が，パーマネントを多項式時間で計算することは絶望視されています。

パフィアンの符号部分を除いたものを行列のハフニアン（hafnian）と言います：

$\mathrm{haf}\:A=\displaystyle\sum_{M}\prod_{(i,j)\in M}a_{ij}$

ハフニアンはパフィアンと同じく行列の右上部分だけで決まりますが，対角成分が $0$ である $2n\times 2n$ の対称行列に対して定義される量と考えることが多いです。

符号部分がないため，パフィアンより定義は簡単に見えますが，ハフニアンの計算は非常に難しいです。実際，$\mathrm{perm}\:A=\mathrm{haf}\begin{pmatrix}O &A\\A^{\top}&O\end{pmatrix}$

という関係があり，少なくともパーマネントの計算以上には難しそうです。