Hafnian

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

${\displaystyle \operatorname {haf} (A)=\sum _{\rho \in P_{2n}^{2}}\prod _{\{i,j\}\in \rho }A_{i,j},}$

where ${\displaystyle P_{2n}^{2}}$ is the set of all partitions of the set ${\displaystyle \{1,2,\dots ,2n\}}$ into subsets of size ${\displaystyle 2}$.^[2][3]

This definition 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.^[4]

Summarize Timeline Top Qs Fact Check

Besides its definition as a sum over perfect pairings, the hafnian of a ${\displaystyle 2n\times 2n}$ symmetric matrix ${\displaystyle A}$ can equivalently be written as

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

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

An equivalent Levi-Civita representation holds for any even-dimensional symmetric matrix ${\displaystyle V=(V_{ij})_{i,j=1}^{N}}$:

${\displaystyle \operatorname {haf} (V)={\frac {1}{2^{N/2}(N/2)!}}\sum _{i_{1},\dots ,i_{N}=1}^{N}\epsilon ^{i_{1}\cdots i_{N}}\epsilon ^{i_{1}\cdots i_{N}}V_{i_{1}i_{2}}\cdots V_{i_{N-1}i_{N}},}$

where ${\displaystyle N}$ is even.^[6]

The hafnian also admits a fermionic (Berezin integral) representation. If ${\displaystyle V}$ is a symmetric ${\displaystyle 2L\times 2L}$ matrix and ${\displaystyle \chi _{i},{\bar {\chi }}_{i}}$ are Grassmann variables, then

${\displaystyle \int D(\chi ,{\bar {\chi }})\,\exp \!\left[{\frac {1}{2}}(\chi {\bar {\chi }})^{\mathsf {T}}V(\chi {\bar {\chi }})\right]=\operatorname {haf} (V),}$

where

${\displaystyle (\chi {\bar {\chi }})^{\mathsf {T}}={\bigl (}{\bar {\chi }}_{1}\chi _{1},\dots ,{\bar {\chi }}_{2L}\chi _{2L}{\bigr )}}$

and

${\displaystyle D(\chi ,{\bar {\chi }})=d\chi _{1}\,d{\bar {\chi }}_{1}\cdots d\chi _{2L}\,d{\bar {\chi }}_{2L}.}$^[6]

For low-dimensional examples,

${\displaystyle \operatorname {haf} \!{\begin{pmatrix}V_{11}&V_{12}\\V_{12}&V_{22}\end{pmatrix}}=V_{12},}$

and for a ${\displaystyle 4\times 4}$ symmetric matrix,

${\displaystyle \operatorname {haf} \!{\begin{pmatrix}V_{11}&V_{12}&V_{13}&V_{14}\\V_{12}&V_{22}&V_{23}&V_{24}\\V_{13}&V_{23}&V_{33}&V_{34}\\V_{14}&V_{24}&V_{34}&V_{44}\end{pmatrix}}=V_{12}V_{34}+V_{13}V_{24}+V_{14}V_{23}.}$^[6]

A useful scaling property is the following. If ${\displaystyle V=(V_{ij})}$ and ${\displaystyle S=(S_{ij})}$ are symmetric matrices such that

${\displaystyle V_{ij}=g_{i}g_{j}S_{ij},}$

then, for even ${\displaystyle N}$,

${\displaystyle \operatorname {haf} (V)=\left(\prod _{i=1}^{N}g_{i}\right)\operatorname {haf} (S).}$

In particular, if ${\displaystyle V=gS}$ for a scalar ${\displaystyle g}$, then

${\displaystyle \operatorname {haf} (gS)=g^{N/2}\operatorname {haf} (S).}$^[6]

The hafnian of the adjacency matrix of a graph counts its perfect matchings (also known as 1-factors). Indeed, a partition of ${\displaystyle \{1,2,\dots ,2n\}}$ into subsets of size 2 is equivalent to a perfect matching of the complete graph ${\displaystyle K_{2n}}$.

The hafnian is closely related to the permanent. In particular,

${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{\mathsf {T}}&0\end{pmatrix}}}$.^[2]

Thus, just as the hafnian counts perfect matchings in a graph from its adjacency matrix, the permanent counts matchings in a bipartite graph from its biadjacency matrix.

The hafnian is also related to moments of multivariate Gaussian distributions. By Wick's probability theorem, for a real ${\displaystyle 2n\times 2n}$ symmetric matrix ${\displaystyle A}$,

${\displaystyle \operatorname {haf} (A)=\mathbb {E} _{\left(X_{1},\dots ,X_{2n}\right)\sim {\mathcal {N}}\left(0,A+\lambda I\right)}\left[X_{1}\cdots X_{2n}\right],}$

where ${\displaystyle \lambda }$ is any number large enough that ${\displaystyle A+\lambda I}$ is positive semi-definite. Since the hafnian does not depend on the diagonal entries of the matrix, the expectation on the right-hand side is independent of the choice of ${\displaystyle \lambda }$.

Summarize Timeline Top Qs Fact Check

Let ${\displaystyle S={\begin{pmatrix}A&C\\C^{\mathsf {T}}&B\end{pmatrix}}=S^{\mathsf {T}}}$ be an arbitrary complex symmetric ${\displaystyle 2m\times 2m}$ matrix composed of four ${\displaystyle m\times m}$ blocks ${\displaystyle A=A^{\mathsf {T}}}$, ${\displaystyle B=B^{\mathsf {T}}}$, ${\displaystyle C}$ and ${\displaystyle C^{\mathsf {T}}}$. Let ${\displaystyle z_{1},\ldots ,z_{m}}$ be a set of ${\displaystyle m}$ independent variables, and let ${\displaystyle Z={\begin{pmatrix}0&{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})\\{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})&0\end{pmatrix}}}$ be an antidiagonal block matrix composed of entries ${\displaystyle z_{j}}$ (each one is presented twice, one time per nonzero block). Let ${\displaystyle I}$ denote the identity matrix. Then the following identity holds:^[4]

${\displaystyle {\frac {1}{\sqrt {\det {\big (}I-ZS{\big )}}}}=\sum _{\{n_{k}\}}\operatorname {haf} {\tilde {S}}(\{n_{k}\})\prod _{k=1}^{m}{\frac {z_{k}^{n_{k}}}{n_{k}!}}}$

where the right-hand side involves hafnians of ${\displaystyle {\Big (}2\sum _{k}n_{k}{\Big )}\times {\Big (}2\sum _{k}n_{k}{\Big )}}$ matrices ${\displaystyle {\tilde {S}}(\{n_{k}\})={\begin{pmatrix}{\tilde {A}}(\{n_{k}\})&{\tilde {C}}(\{n_{k}\})\\{\tilde {C}}^{\mathsf {T}}(\{n_{k}\})&{\tilde {B}}(\{n_{k}\})\\\end{pmatrix}}}$, whose blocks ${\displaystyle {\tilde {A}}(\{n_{k}\})}$, ${\displaystyle {\tilde {B}}(\{n_{k}\})}$, ${\displaystyle {\tilde {C}}(\{n_{k}\})}$ and ${\displaystyle {\tilde {C}}^{\mathsf {T}}(\{n_{k}\})}$ are built from the blocks ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$ and ${\displaystyle C^{\mathsf {T}}}$ respectively in the way introduced in MacMahon's Master theorem. In particular, ${\displaystyle {\tilde {A}}(\{n_{k}\})}$ is a matrix built by replacing each entry ${\displaystyle A_{k,t}}$ in the matrix ${\displaystyle A}$ with a ${\displaystyle n_{k}\times n_{t}}$ block filled with ${\displaystyle A_{k,t}}$; the same scheme is applied to ${\displaystyle B}$, ${\displaystyle C}$ and ${\displaystyle C^{\mathsf {T}}}$. The sum ${\displaystyle \sum _{\{n_{k}\}}}$ runs over all ${\displaystyle k}$-tuples of non-negative integers, and it is assumed that ${\displaystyle \operatorname {haf} {\tilde {S}}(\{n_{k}=0|k=1\ldots m\})=1}$.

The identity can be proved^[4] by means of multivariate Gaussian integrals and Wick's probability theorem.

The expression in the left-hand side, ${\displaystyle 1{\Big /}{\sqrt {\det {\big (}I-ZS{\big )}}}{\Big .}}$, is in fact a multivariate generating function for a series of hafnians, and the right-hand side constitutes its multivariable Taylor expansion in the vicinity of the point ${\displaystyle z_{1}=\ldots =z_{m}=0.}$ As a consequence of the given relation, the hafnian of a symmetric ${\displaystyle 2m\times 2m}$ matrix ${\displaystyle S}$ can be represented as the following mixed derivative of the order ${\displaystyle m}$:

${\displaystyle \operatorname {haf} S={\bigg (}\prod _{k=1}^{m}{\frac {\partial }{\partial z_{k}}}{\bigg )}{\Bigg .}{\frac {1}{\sqrt {\det {\big (}I-ZS{\big )}}}}{\Bigg \vert }_{z_{j}=0}.}$

The hafnian generating function identity written above can be considered as a hafnian generalization of MacMahon's Master theorem, which introduces the generating function for matrix permanents and has the following form in terms of the introduced notation:

${\displaystyle {\frac {1}{\det {\big (}I-{\textrm {diag}}(z_{1},z_{2},\ldots ,z_{m})C{\big )}}}=\sum _{\{n_{k}\}}\operatorname {per} {\tilde {C}}(\{n_{k}\})\prod _{k=1}^{m}{\frac {z_{k}^{n_{k}}}{n_{k}!}}}$

Note that MacMahon's Master theorem comes as a simple corollary from the hafnian generating function identity due to the relation ${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{\mathsf {T}}&0\end{pmatrix}}}$.

Summarize Timeline Top Qs Fact Check

If ${\displaystyle C}$ is a Hermitian positive semi-definite ${\displaystyle n\times n}$ matrix and ${\displaystyle B}$ is a complex symmetric ${\displaystyle n\times n}$ matrix, then

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

where ${\displaystyle {\overline {C}}}$ denotes the complex conjugate of ${\displaystyle C}$.^[7]

A simple way to see this when ${\displaystyle {\begin{pmatrix}C&B\\{\overline {B}}&{\overline {C}}\\\end{pmatrix}}}$ is positive semi-definite is to observe that, by Wick's probability theorem, ${\displaystyle \operatorname {haf} {\begin{pmatrix}B&C\\{\overline {C}}&{\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 C}$ and relation matrix ${\displaystyle B}$.

This result is a generalization of the fact that the permanent of a Hermitian positive semi-definite matrix is non-negative. This corresponds to the special case ${\displaystyle B=0}$ using the relation ${\displaystyle \operatorname {per} (C)=\operatorname {haf} {\begin{pmatrix}0&C\\C^{\mathsf {T}}&0\end{pmatrix}}}$.

Summarize Timeline Fact Check

The loop hafnian of an ${\displaystyle m\times m}$ symmetric matrix is defined as

${\displaystyle \operatorname {lhaf} (A)=\sum _{\rho \in {\mathcal {M}}}\prod _{(i,j)\in \rho }A_{i,j}}$

where ${\displaystyle {\mathcal {M}}}$ is the set of all perfect matchings of the complete graph on ${\displaystyle m}$ vertices with loops, i.e., the set of all ways to partition the set ${\displaystyle \{1,2,\dots ,m\}}$ into pairs or singletons (treating a singleton ${\displaystyle (i)}$ as the pair ${\displaystyle (i,i)}$).^[8] Thus the loop hafnian depends on the diagonal entries of the matrix, unlike the hafnian.^[8] Furthermore, the loop hafnian can be non-zero when ${\displaystyle m}$ is odd.

The loop hafnian can be used to count the total number of matchings in a graph (perfect or non-perfect), also known as its Hosoya index. Specifically, if one takes the adjacency matrix of a graph and sets the diagonal elements to 1, then the loop hafnian of the resulting matrix is equal to the total number of matchings in the graph.^[8]

The loop hafnian can also be thought of as incorporating a mean into the interpretation of the hafnian as a multivariate Gaussian moment. Specifically, by Wick's probability theorem again, the loop hafnian of a real ${\displaystyle m\times m}$ symmetric matrix can be expressed as

${\displaystyle \operatorname {lhaf} (A)=\mathbb {E} _{\left(X_{1},\dots ,X_{m}\right)\sim {\mathcal {N}}\left(\operatorname {diag} \left(A\right),A+\lambda I\right)}\left[X_{1}\dots X_{m}\right],}$

where ${\displaystyle \lambda }$ is any number large enough to make ${\displaystyle A+\lambda I}$ positive semi-definite.