The hafnian

Section author: Nicolás Quesada <nicolas@xanadu.ai>

The hafnian

The hafnian of an \(n \times n\), symmetric matrix \(\mathbf{A} =\mathbf{A}^T\) is defined as [27]

\[\label{eq:hafA} \haf(\mathbf{A}) = \sum_{M \in \text{PMP}(n)} \prod_{\scriptscriptstyle (i, j) \in M} A_{i, j},\]

where \(\text{PMP}(n)\) stands for the set of perfect matching permutations of \(n\) (even) objects, i.e., permutations \(\sigma:[n]\rightarrow [n]\) such that \(\forall i:\sigma(2i-1)<\sigma(2i)\) and \(\forall i:\sigma(2i-1)<\sigma(2i+1)\).

It was so named by Eduardo R. Caianiello [28] “to mark the fruitful period of stay in Copenhagen (Hafnia in Latin).” [29]

The set PMP(\(n\)) used to define the hafnian contains

\[\label{eq:haf1} |\text{PMP}(n)|=(n-1)!! = 1 \times 3 \times 5 \times \ldots \times (n -1),\]

elements and thus as defined it takes \((n-1)!!\) additions of products of \(n/2\) numbers to calculate the hafnian of an \(n \times n\) matrix. Note that the diagonal elements of the matrix \(\mathbf{A}\) do not appear in the calculation of the hafnian and are (conventionally) taken to be zero.

For \(n=4\) the set of perfect matchings is

\[\label{eq:PMP4} \text{PMP}(4) = \big\{ (0,1)(2,3),\ (0,2)(1,3),\ (0,3),(1,2) \big\},\]

and the hafnian of a \(4 \times 4\) matrix \(\mathbf{B}\) is

\[\label{eq:hafB} \haf(\mathbf{B}) = B_{0,1} B_{2,3}+B_{0,2}B_{1,3}+B_{0,3} B_{1,2}.\]

The hafnian of an odd sized matrix is defined to be zero; if \(\mathbf{A}=\mathbf{A}^T\) is \(M\) dimensional and \(M\) is odd then \(\haf(\mathbf{A}) = 0\). Note that, for convenience, we define the hafnian of an empty matrix, i.e., a matrix of dimension zero by zero, to be 1.

The hafnian is a homogeneous function of degree \(n/2\) in the matrix entries of an \(n \times n\) matrix \(\mathbf{A}\). This implies that

\[\haf(\mu \mathbf{A}) = \mu ^{n/2} \haf(\mathbf{A}),\]

where \(\mu\) is a scalar. More generally, if \(\mathbf{W} = \text{diag}(w_0,\ldots,w_{n-1})\), then it holds that ( see proposition 4.2.3 of [27])

\[\haf( \mathbf{W} \mathbf{A} \mathbf{W} ) = \left(\prod_{i=0}^{n-1} w_i\right) \haf(\mathbf{A}).\]

The definition used to introduce the hafnian is rather algebraic and brings little intuition. To gain more insight in the next section we introduce some graph theory language and use it to present a more intuitive vision of what the hafnian “counts”.

Basics of graphs

A graph is an ordered pair \(G=(V,E)\) where \(V\) is the set of vertices, and \(E\) is the set of edges linking the vertices of the graph, i.e., if \(e \in E\) then \(e=(i,j)\) where \(i,j \in V\). In this section we consider graphs without loops (we relax this in the next section), thus we do not allow for edges \(e = (i,i)\) connecting a given vertex to itself. A 6 vertex graph is shown here

_images/graph.svg

the vertices are labelled \(V = \{1,2,3,4,5,6 \}\) and the edges are \(E=\{(1,4),(2,4),(2,5),(3,4),(3,5),(3,6),(5,5) \}\).

A matching \(M\) is a subset of the edges in which no two edges share a vertex. An example of matching is \(M=(1,4)(3,6)\) represented by the blue lines in the following figure

_images/matching.svg

In the figure above we know we have a matching because none of the highlighted edges shares a vertex.

A perfect matching is a matching which matches all the vertices of the graph, such as for example \(M=(1,4)(2,5)(3,6)\), which is represented again by the blue lines in the following figure

_images/pm.svg

The blue lines represent a perfect matching because, they are a matching, i.e., the edges do no overlap on any vertex and all the vertices are covered by one and only edge.

A complete graph is a graph where every vertex is connected to every other vertex. For loopless graphs having \(n\) vertices, the number of perfect matchings is precisely [27]

\[|\text{PMP}(n)|=(n-1)!! = 1 \times 3 \times \ldots \times (n-1).\]

where we use \(\text{PMP}(n)\) to indicate the set of perfect matchings of introduced in the previous section, and the notation \(|V|\) to indicate the number of elements in the set \(V\). Note that this number is nonzero only for even \(n\), since for odd \(n\) there will always be one unmatched vertex.

In the following figure we illustrate the 3 perfect matchings of a complete graph with 4 vertices

_images/pmp4.svg

Perfect matchings and hafnians

An important question concerning a given graph \(G=(V,E)\) is the number of perfect matchings it has. One possible way to answer this question is to iterate over the perfect matchings of a complete graph and at each step check if the given perfect matching of the complete graph is also a perfect matching of the given graph. A simple way to automatize this process is by constructing the adjacency matrix of the graph. The adjacency matrix \(\mathbf{A}\) of a graph \(G=(V,E)\) is a 0-1 matrix that has \(\mathbf{A}_{i,j} = \mathbf{A}_{j,i}=1\) if, and only if, \((i,j) \in E\) and 0 otherwise. For the example graph in the previous section, the adjacency matrix is

\[\begin{split}\mathbf{A}' = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}.\end{split}\]

The number of perfect matchings of a (loopless) graph is simply given by the hafnian of its adjacency matrix

\[\text{haf}(\mathbf{A}) = \sum_{M \in \text{PMP}(n)} \prod_{\scriptscriptstyle (i,j) \in M} {A}_{i,j}.\]

For the graph in the previous section we can easily confirm that the perfect matching we found is the only perfect matching since

\[\text{haf}(\mathbf{A}') = 1.\]

The definition of the hafnian immediately generalizes to weighted graphs, where we assign a real or complex number to the entries of the symmetric matrix \(\mathbf{A}\).

Special values of the hafnian

Here we list some special values of the hafnian for certain special matrices.

  • If the matrix \(\mathbf{A}\) has the following block form

\[\begin{split}\mathbf{A}_{\text{block}} = \left[\begin{array}{c|c} 0 & \mathbf{C} \\ \hline \mathbf{C}^T & 0 \\ \end{array}\right]\end{split}\]

then it holds that \(\text{haf}\left( \mathbf{A}_{\text{block}} \right) = \text{per}(\mathbf{C})\) where \(\text{per}\) is the permanent matrix function defined as [27]

\[\text{per}(\mathbf{C})=\sum_{\sigma\in S_n}\prod_{i=1}^n C_{i,\sigma(i)}.\]

The sum here extends over all elements \(\sigma\) of the symmetric group \(S_n\).

  • If \(\mathbf{A}_{\text{rank-one}} = \mathbf{e} \mathbf{e}^T\) is a rank one matrix of size \(n\) then

\[\text{haf}\left( \mathbf{A}_{\text{rank-one}} \right) = (n-1)!! \prod_{i=1}^{n-1} e_i\]

In particular, the hafnian of the all ones matrix is precisely \((n-1)!!\).

  • If \(\mathbf{A}_{\text{direct sum}} = \mathbf{A}_1 \oplus \mathbf{A}_2\) is a block diagonal matrix then

\[\text{haf}\left(\mathbf{A}_{\text{direct sum}}\right) = \text{haf}\left( \mathbf{A}_1 \oplus \mathbf{A}_2 \right) = \text{haf}\left( \mathbf{A}_1 \right) \text{haf}\left( \mathbf{A}_2 \right)\]

This identity simply expresses the fact that the number of perfect matchings of a graph that is made of two disjoint subgraphs is simply the product of the number of perfect matchings of the two disjoint subgraphs.