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)."[1]

Definition

edit

The hafnian of a   symmetric matrix   is defined as

 

where   is the set of all partitions of the set   into subsets of size  .[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]

Basic properties

edit

The hafnian may also be defined as

 

where   is the symmetric group on  .[5] The two definitions are equivalent because if  , then   is a partition of   into subsets of size 2, and as   ranges over  , each such partition is counted exactly   times. Note that this argument relies on the symmetry of  , without which the original definition is not well-defined.

The hafnian of an adjacency matrix of a graph is the number of perfect matchings (also known as 1-factors) in the graph. This is because a partition of   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

 .[2]

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   symmetric matrix may expressed as

 

where   is any number large enough to make   positive semi-definite. 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  .

Generating function

edit

Let   be an arbitrary complex symmetric   matrix composed of four   blocks  ,  ,   and  . Let   be a set of   independent variables, and let   be an antidiagonal block matrix composed of entries   (each one is presented twice, one time per nonzero block). Let   denote the identity matrix. Then the following identity holds:[4]

 

where the right-hand side involves hafnians of   matrices  , whose blocks  ,  ,   and   are built from the blocks  ,  ,   and   respectively in the way introduced in MacMahon's Master theorem. In particular,   is a matrix built by replacing each entry   in the matrix   with a   block filled with  ; the same scheme is applied to  ,   and  . The sum   runs over all  -tuples of non-negative integers, and it is assumed that  .

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

The expression in the left-hand side,  , 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   matrix   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  .

Non-negativity

edit

If   is a Hermitian positive semi-definite   matrix and   is a complex symmetric   matrix, then

 

where   denotes the complex conjugate of  .[6]

A simple way to see this when   is positive semi-definite is to observe that, by Wick's probability theorem,   when   is a complex normal random vector with mean  , covariance matrix   and relation matrix  .

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   using the relation  .

Loop hafnian

edit

The loop hafnian of an   symmetric matrix is defined as

 

where   is the set of all perfect matchings of the complete graph on   vertices with loops, i.e., the set of all ways to partition the set   into pairs or singletons (treating a singleton   as the pair  ).[7] Thus the loop hafnian depends on the diagonal entries of the matrix, unlike the hafnian.[7] Furthermore, the loop hafnian can be non-zero when   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.[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   symmetric matrix can be expressed as

 

where   is any number large enough to make   positive semi-definite.

Computation

edit

Computing the hafnian of a (0,1)-matrix is #P-complete, because computing the permanent of a (0,1)-matrix is #P-complete.[4][7]

The hafnian of a   matrix can be computed in   time.[7]

If the entries of a matrix are non-negative, then its hafnian can be approximated to within an exponential factor in polynomial time.[8]

See also

edit

References

edit
  1. ^ F. Guerra, in Imagination and Rigor: Essays on Eduardo R. Caianiello's Scientific Heritage, edited by Settimo Termini, Springer Science & Business Media, 2006, page 98
  2. ^ a b Alexander Barvinok (13 March 2017). Combinatorics and Complexity of Partition Functions. Springer. p. 93. ISBN 9783319518299.
  3. ^ Barvinok, Alexander; Regts, Guus (2019). "Weighted counting of integer points in a subspace". Combinator. Probab. Comp. 28: 696–719. arXiv:1706.05423. doi:10.1017/S0963548319000105. S2CID 126185737.
  4. ^ a b c d Kocharovsky, Vitaly V.; Kocharovsky, Vladimir V.; Tarasov, Sergey V. (2022). "The Hafnian Master Theorem". Linear Algebra and Its Applications. 651. Elsevier BV: 144–161. doi:10.1016/j.laa.2022.06.021. ISSN 0024-3795. S2CID 249935016.
  5. ^ Rudelson, Mark; Samorodnitsky, Alex; Zeitouni, Ofer (2016). "Hafnians, perfect matchings and Gaussian matrices". The Annals of Probability. 44 (4): 2858–2888. arXiv:1409.3905. doi:10.1214/15-AOP1036. S2CID 14458608.
  6. ^ Brádler, Kamil; Friedland, Shmuel; Israel, Robert B. (2021-02-24). "Nonnegativity for hafnians of certain matrices". Linear and Multilinear Algebra. 70 (19). Informa UK Limited: 4615–4619. arXiv:1811.10342. doi:10.1080/03081087.2021.1892022. ISSN 0308-1087. S2CID 119601142.
  7. ^ a b c d e Björklund, Andreas; Gupt, Brajesh; Quesada, Nicolás (2018). "A faster hafnian formula for complex matrices and its benchmarking on a supercomputer". arXiv:1805.12498 [cs.DS].
  8. ^ Barvinok, Alexander (1999). "Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor". Random Structures and Algorithms. 14 (1). Wiley: 29–61. doi:10.1002/(sici)1098-2418(1999010)14:1<29::aid-rsa2>3.0.co;2-x. hdl:2027.42/35110. ISSN 1042-9832.