Hafnian

In mathematics, the hafnian of an adjacency matrix of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin)."[1]

The hafnian of a ${\displaystyle 2n\times 2n}$ symmetric matrix is computed as

${\displaystyle \operatorname {haf} (A)={\frac {1}{n!2^{n}}}\sum _{\sigma \in S_{2n}}\prod _{j=1}^{n}A_{\sigma (2j-1),\sigma (2j)},}$

where ${\displaystyle S_{2n}}$ is the symmetric group on ${\displaystyle [2n]=\{1,2,...,2n\}}$.[2]

Equivalently,

${\displaystyle \operatorname {haf} (A)=\sum _{M\in {\mathcal {M}}}\prod _{\scriptscriptstyle (u,v)\in M}A_{u,v}}$

where ${\displaystyle {\mathcal {M}}}$ is the set of all 1-factors (perfect matchings) on the complete graph ${\displaystyle K_{2n}}$, namely the set of all ${\displaystyle (2n)!/(n!2^{n})}$ ways to partition the set ${\displaystyle \{1,2,\dots ,2n\}}$ into ${\displaystyle n}$ subsets of size ${\displaystyle 2}$.[3][4]

The definition of the hafnian is similar to that of the Pfaffian, but differs in that the signatures of the permutations are not taken into account. Thus the relationship of the hafnian to the Pfaffian is the same as relationship of the permanent to the determinant.[5]

Furthermore, the permanent and the hafnian are related as ${\displaystyle \operatorname {per} (A)=\operatorname {haf} {\begin{pmatrix}&A\\A^{T}&\\\end{pmatrix}}}$.[3]

If ${\displaystyle A}$ is a Hermitian positive semi-definite ${\displaystyle n\times n}$ matrix and ${\displaystyle B}$ is a complex symmetric ${\displaystyle n\times n}$ matrix, then we have the inequality

${\displaystyle \operatorname {haf} {\begin{pmatrix}B&A\\{\overline {A}}&{\overline {B}}\\\end{pmatrix}}\geq 0,}$

where ${\displaystyle {\overline {A}}}$ denotes the complex conjugate of ${\displaystyle A}$.[6] A simple way to see this when ${\displaystyle {\begin{pmatrix}A&B\\{\overline {B}}&{\overline {A}}\\\end{pmatrix}}}$ is positive semi-definite is to observe that, by Wick's probability theorem, ${\displaystyle \operatorname {haf} {\begin{pmatrix}B&A\\{\overline {A}}&{\overline {B}}\\\end{pmatrix}}=\mathbb {E} \left[\left|X_{1}\dots X_{n}\right|^{2}\right]}$ when ${\displaystyle \left(X_{1},\dots ,X_{n}\right)}$ is a complex normal random vector with mean ${\displaystyle 0}$, covariance matrix ${\displaystyle A}$ and relation matrix ${\displaystyle B}$.