hafnian

The hafnian of a $2n\backslash times\; 2n$ symmetric matrix $A$ is defined as

: $\backslash operatorname\{haf\}(A)\; =\; \backslash sum\_\{\backslash rho\; \backslash in\; P\_\{2n\}^2\}\; \backslash prod\_\{\backslash \{i,j\backslash \}\; \backslash in\; \backslash rho\}\; A\_\{i,j\},$

where $P\_\{2n\}^2$ is the set of all partitions of the set $\backslash \{1,\; 2,\; \backslash dots,\; 2n\backslash \}$ into subsets of size $2$.{{cite book | title=Combinatorics and Complexity of Partition Functions | page=93 | author=Alexander Barvinok | date=13 March 2017 | publisher=Springer | isbn=9783319518299 | url=https://books.google.com/books?id=9LlZDgAAQBAJ&pg=PA93}}{{cite journal |title=Weighted counting of integer points in a subspace | journal=Combinator. Probab. Comp. | year=2019 | volume=28 | pages=696–719 | doi=10.1017/S0963548319000105 | arxiv = 1706.05423| last1=Barvinok | first1=Alexander | last2=Regts | first2=Guus | s2cid=126185737 }}

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.{{cite journal | last1=Kocharovsky | first1=Vitaly V. | last2=Kocharovsky | first2=Vladimir V. | last3=Tarasov | first3=Sergey V. | title=The Hafnian Master Theorem | journal=Linear Algebra and Its Applications | publisher=Elsevier BV | volume=651 | year=2022 | issn=0024-3795 | doi=10.1016/j.laa.2022.06.021 | pages=144–161| s2cid=249935016 | doi-access=free }}

The hafnian may also be defined as

: $\backslash operatorname\{haf\}(A)\; =\; \backslash frac\{1\}\{n!2^n\}\; \backslash sum\_\{\backslash sigma\; \backslash in\; S\_\{2n\}\}\; \backslash prod\_\{i=1\}^n\; A\_\{\backslash sigma(2i\; -\; 1),\; \backslash sigma(2i)\},$

where $S\_\{2n\}$ is the symmetric group on $\backslash \{1,2,...,2n\backslash \}$.{{cite journal |arxiv=1409.3905 |doi=10.1214/15-AOP1036 |title=Hafnians, perfect matchings and Gaussian matrices |year=2016 |last1=Rudelson |first1=Mark |last2=Samorodnitsky |first2=Alex |last3=Zeitouni |first3=Ofer |journal=The Annals of Probability |volume=44 |issue=4 |pages=2858–2888 |s2cid=14458608 }} The two definitions are equivalent because if $\backslash sigma\backslash in\; S\_\{2n\}$, then $\backslash \{\backslash \{\backslash sigma(2i-1),\backslash sigma(2i)\backslash \}:i\backslash in\backslash \{1,...,n\backslash \}\backslash \}$ is a partition of $\backslash \{1,2,\backslash dots,2n\backslash \}$ into subsets of size 2, and as $\backslash sigma$ ranges over $S\_\{2n\}$, each such partition is counted exactly $n!2^n$ times. Note that this argument relies on the symmetry of $A$, 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 $\backslash \{1,2,\backslash dots,2n\backslash \}$ into subsets of size 2 can also be thought of as a perfect matching in the complete graph $K\_\{2n\}$.

The hafnian can also be thought of as a generalization of the permanent, since the permanent can be expressed as

: $\backslash operatorname\{per\}(C)=\backslash operatorname\{haf\}\backslash begin\{pmatrix\}$

0 & C \\

C^\mathsf{T} & 0

\end{pmatrix}.

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 $2n\; \backslash times\; 2n$ symmetric matrix may expressed as

: $$

\operatorname{haf}(A) = \mathbb E_{\left(X_1,\dots,X_{2n}\right)\sim\mathcal N\left(0,A+\lambda I\right)}\left[X_1\dots X_{2n}\right],

where $\backslash lambda$ is any number large enough to make $A\; +\; \backslash lambda\; I$ 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 $\backslash lambda$.

Let $S\; =\; \backslash begin\{pmatrix\}$

A & C \\

C^\mathsf{T} & B

\end{pmatrix} = S^\mathsf{T} be an arbitrary complex symmetric $2m\; \backslash times\; 2m$ matrix composed of four $m\; \backslash times\; m$ blocks $A\; =\; A^\backslash mathsf\{T\}$, $B\; =\; B^\backslash mathsf\{T\}$, $C$ and $C^\backslash mathsf\{T\}$. Let $z\_1,\; \backslash ldots,\; z\_m$ be a set of $m$ independent variables, and let $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 $z\_j$ (each one is presented twice, one time per nonzero block). Let $I$ denote the identity matrix. Then the following identity holds:

: $$

\frac{1}{\sqrt{\det \big(I - Z S\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 $\backslash Big(2\backslash sum\_k\; n\_k\backslash Big)\backslash times\backslash Big(2\backslash sum\_k\; n\_k\backslash Big)$ matrices $\backslash tilde\{S\}(\backslash \{n\_k\backslash \})\; =\; \backslash begin\{pmatrix\}$

\tilde{A}(\{n_k\}) & \tilde{C}(\{n_k\}) \\

\tilde{C}^\mathsf{T}(\{n_k\}) & \tilde{B}(\{n_k\}) \\

\end{pmatrix}, whose blocks $\backslash tilde\{A\}(\backslash \{n\_k\backslash \})$, $\backslash tilde\{B\}(\backslash \{n\_k\backslash \})$, $\backslash tilde\{C\}(\backslash \{n\_k\backslash \})$ and $\backslash tilde\{C\}^\backslash mathsf\{T\}(\backslash \{n\_k\backslash \})$ are built from the blocks $A$, $B$, $C$

and $C^\backslash mathsf\{T\}$ respectively in the way introduced in MacMahon's Master theorem. In particular, $\backslash tilde\{A\}(\backslash \{n\_k\backslash \})$ is a matrix built by replacing each entry $A\_\{k,t\}$ in the matrix $A$ with a $n\_k\; \backslash times\; n\_t$ block filled with $A\_\{k,t\}$; the same scheme is applied to $B$, $C$ and $C^\backslash mathsf\{T\}$. The sum $\backslash sum\_\{\backslash \{n\_k\backslash \}\}$ runs over all $k$-tuples of non-negative integers, and it is assumed that $\backslash operatorname\{haf\}\; \backslash tilde\{S\}(\backslash \{n\_k=0|k=1\backslash ldots\; m\backslash \})\; =\; 1$.

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

The expression in the left-hand side, $1\; \backslash Big/\; \backslash sqrt\{\backslash det\; \backslash big(I\; -\; Z\; S\backslash big)\}\; \backslash 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 $z\_1\; =\; \backslash ldots\; =\; z\_m\; =\; 0.$ As a consequence of the given relation, the hafnian of a symmetric $2m\; \backslash times\; 2m$ matrix $S$ can be represented as the following mixed derivative of the order $m$:

: $$

\operatorname{haf}S = \bigg(\prod_{k=1}^m \frac{\partial}{\partial z_k} \bigg) \Bigg.\frac{1}{\sqrt{\det \big(I - Z S\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:

:$$

\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 $\backslash operatorname\{per\}\; (C)\; =\; \backslash operatorname\{haf\}\; \backslash begin\{pmatrix\}$

0 & C \\

C^\mathsf{T} & 0

\end{pmatrix}.

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

: $\backslash operatorname\{haf\}\backslash begin\{pmatrix\}$

B & C \\

\overline{C} & \overline{B}

\end{pmatrix}\geq 0,

where $\backslash overline\{C\}$ denotes the complex conjugate of $C$.{{cite journal | last1=Brádler | first1=Kamil | last2=Friedland | first2=Shmuel | last3=Israel | first3=Robert B. | title=Nonnegativity for hafnians of certain matrices | journal=Linear and Multilinear Algebra | publisher=Informa UK Limited | volume=70 | issue=19 | date=2021-02-24 | issn=0308-1087 | doi=10.1080/03081087.2021.1892022 | pages=4615–4619| arxiv=1811.10342 | s2cid=119601142 }}

A simple way to see this when $\backslash begin\{pmatrix\}$

C & B \\

\overline{B} & \overline{C} \\

\end{pmatrix} is positive semi-definite is to observe that, by Wick's probability theorem, $\backslash operatorname\{haf\}\backslash begin\{pmatrix\}$

B & C \\

\overline{C} & \overline{B} \\

\end{pmatrix}=\mathbb E\left[\left|X_1\dots X_n\right|^2\right] when $\backslash left(X\_1,\backslash dots,X\_n\backslash right)$ is a complex normal random vector with mean $0$, covariance matrix $C$ and relation matrix $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 $B=0$ using the relation $\backslash operatorname\{per\}\; (C)\; =\; \backslash operatorname\{haf\}\; \backslash begin\{pmatrix\}$

0 & C \\

C^\mathsf{T} & 0

\end{pmatrix}.

The loop hafnian of an $m\backslash times\; m$ symmetric matrix is defined as

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

where $\backslash mathcal\{M\}$ is the set of all perfect matchings of the complete graph on $m$ vertices with loops, i.e., the set of all ways to partition the set $\backslash \{1,\; 2,\; \backslash dots,\; m\backslash \}$ into pairs or singletons (treating a singleton $(i)$ as the pair $(i,\; i)$). Thus the loop hafnian depends on the diagonal entries of the matrix, unlike the hafnian. Furthermore, the loop hafnian can be non-zero when $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.{{cite arXiv | last1=Björklund | first1=Andreas | last2=Gupt | first2=Brajesh | last3=Quesada | first3=Nicolás | title=A faster hafnian formula for complex matrices and its benchmarking on a supercomputer | year=2018 | eprint=1805.12498 | page=| class=cs.DS }}

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 $m\backslash times\; m$ symmetric matrix can be expressed as

: $$

\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 $\backslash lambda$ is any number large enough to make $A+\backslash lambda\; I$ positive semi-definite.

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

The hafnian of a $2n\backslash times\; 2n$ matrix can be computed in $O(n^3\; 2^n)$ time.

If the entries of a matrix are non-negative, then its hafnian can be approximated to within an exponential factor in polynomial time.{{cite journal | last=Barvinok | first=Alexander | title=Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor | journal=Random Structures and Algorithms | publisher=Wiley | volume=14 | issue=1 | year=1999 | issn=1042-9832 | doi=10.1002/(sici)1098-2418(1999010)14:1<29::aid-rsa2>3.0.co;2-x | pages=29–61| hdl=2027.42/35110 | hdl-access=free }}

• Permanent
• Pfaffian
• Boson sampling

{{reflist}}

Category:Algebraic graph theory

Category:Matching (graph theory)

Category:Combinatorics