In mathematics, the hafnian of an

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in

Copenhagen Copenhagen ( or .; da, København ) is the capital and most populous city of Denmark, with a proper population of around 815.000 in the last quarter of 2022; and some 1.370,000 in the urban area; and the wider Copenhagen metropolitan ar ...

(Hafnia in Latin)." The hafnian of a

2n\times 2n

symmetric matrix is computed as :

\operatorname(A) = \frac \sum_ \prod_^n A_,

where

S_

is the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...

n = \

. Equivalently, :

\operatorname(A) = \sum_ \prod_ A_

where

\mathcal

is the set of all 1-factors (

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...

s) on the complete graph

K_

, namely the set of all

(2n)!/(n!2^n)

ways to partition the set

\

into

n

subsets of size

2

. The permanent and the hafnian are related as

\operatorname(A)=\operatorname\begin
& A \\
A^T &\\
\end

References

Algebraic graph theory Matching (graph theory) Combinatorics {{algebra-stub