1. 高校数学の美しい物語
  2. 行列のパフィアン,パーマネント,ハフニアン

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

更新日時 2021/03/07

正方行列 AA に関して定義されるいろいろな量について紹介します。AAijij 成分を aija_{ij} と書きます。

目次
  • 行列のパフィアン

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

  • 行列のパーマネント

  • 行列のハフニアン

行列のパフィアン

2n×2n2n\times 2n の歪対称行列(反対称行列,A=AA^{\top}=-A となる行列)AA に対して定義される以下の量をパフィアン(pfaffian)と言います:

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

MM{1,2,,2n}\{1,2,\cdots,2n\}nn 個のペアへの分割 {(i1,j1),,(in,jn)}\{(i_1,j_1),\cdots,(i_n,j_n)\} 全体を動きます(i1<<ini_1 <\cdots < i_n かつ i1<j1,,in<jni_1< j_1,\cdots, i_n< j_n )。sgn(M)\mathrm{sgn}(M) は,置換 (122n12ni1j1injn)\begin{pmatrix}1&2&\cdots &2n-1&2n\\i_1&j_1&\cdots&i_n&j_n\end{pmatrix}

の符号を表します。

4×44\times 4 の正方行列についてパフィアンを考える。 MM{(1,2),(3,4)}\{(1,2),(3,4)\}{(1,3),(2,4)}\{(1,3),(2,4)\}{(1,4),(2,3)}\{(1,4),(2,3)\} を動く。置換の符号についても考慮すると,

pfA=a12a34a13a24+a14a23\mathrm{pf}\:A=a_{12}a_{34}-a_{13}a_{24}+a_{14}a_{23}

を得る。

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

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

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

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

行列のパーマネント

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

の符号部分を除いたものを行列のパーマネント(permanent)と言います:

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

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

行列のハフニアン

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

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

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

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

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

pfaffianと書いてパフィアンと読む,なかなか印象的ですね。

人気記事
  1. 高校数学の美しい物語
  2. 行列のパフィアン,パーマネント,ハフニアン