Basics of Hafnians and Loop Hafnians¶
Author: Nicolás Quesada
In the background section of the The Walrus documentation, some basic ideas related to (loop) hafnians were introduced. This tutorial is a computational exploration of the same ideas.
from thewalrus.reference import hafnian as haf_ref from thewalrus import hafnian import numpy as np import matplotlib.pyplot as plt %config InlineBackend.figure_formats=['svg']
A simple loopless graph and the hafnian¶
Let’s consider the following graph
with adjacency matrix
A = np.array([[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]])
It is easy to verify by inspection that the graph in Fig. 1 has only one perfect matching given by the edges (1,4)(2,5)(3,6). We can verify this by calculating the hafnian of the adjacency matrix \(A\)
haf_ref(A) # Using the reference implementation
hafnian(A) # Using the default recursive method
Let’s see what happens if we rescale the adjacency matrix by a scalar \(a\). We’ll use the SymPy library for symbolic manipulation:
from sympy import symbols
a = symbols("a") haf_ref(a*A)
The example above shows that one can use the reference implementation not only with numpy arrays but also with symbolic sympy expressions.
A graph with loops and the loop hafnian¶
Now let’s consider a graph with loops:
The adjacency matrix is now
At = np.array([[1,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,1,0], [0,0,1,0,0,0]])
Note that now the adjacency matrix has non zero elements in the diagonal. It is also strightforward to see that the graph in Fig. 2 has two perfect matchings, namely, (1,4)(2,5)(3,6) and (1,1)(5,5)(2,4)(3,6)
haf_ref(At, loop=True) # Using the reference implementation
hafnian(At, loop=True) # Using the default recursive method
We can also use the loop hafnian to count the number of matching (perfect or otherwise) by taking the adjacency matrix of the loop less graph, putting ones on its diagonal and calculating the loop hafnian of the resulting matrix. For the graph in Fig. 1 we find
Click here to download this gallery page as an interactive Jupyter notebook.