In mathematics, the hafnian is a scalar function of a symmetric matrix that generalizes the permanent.
The hafnian was named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin).
[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.
Note that this argument relies on the symmetry of
The hafnian of an adjacency matrix of a graph is the number of perfect matchings (also known as 1-factors) in the graph.
into subsets of size 2 can also be thought of as a perfect matching in the complete graph
The hafnian can also be thought of as a generalization of the permanent, since the permanent can be expressed as Just as the hafnian counts the number of perfect matchings in a graph given its adjacency matrix, the permanent counts the number of matchings in a bipartite graph given its biadjacency matrix.
The hafnian is also related to moments of multivariate Gaussian distributions.
By Wick's probability theorem, the hafnian of a real
Note that the hafnian does not depend on the diagonal entries of the matrix, and the expectation on the right-hand side does not depend on
be an antidiagonal block matrix composed of entries
(each one is presented twice, one time per nonzero block).
Then the following identity holds:[4] where the right-hand side involves hafnians of
respectively in the way introduced in MacMahon's Master theorem.
is a matrix built by replacing each entry
The identity can be proved[4] by means of multivariate Gaussian integrals and Wick's probability theorem.
, 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
As a consequence of the given relation, the hafnian of a symmetric
can be represented as the following mixed derivative of the order
: 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: Note that MacMahon's Master theorem comes as a simple corollary from the hafnian generating function identity due to the relation
is positive semi-definite is to observe that, by Wick's probability theorem,
is a complex normal random vector with mean
This result is a generalization of the fact that the permanent of a Hermitian positive semi-definite matrix is non-negative.
is the set of all perfect matchings of the complete graph on
[7] Thus the loop hafnian depends on the diagonal entries of the matrix, unlike the hafnian.
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.
[7] 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
[7] If the entries of a matrix are non-negative, then its hafnian can be approximated to within an exponential factor in polynomial time.