# Basics of Hafnians and Loop Hafnians¶

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.

[1]:

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

[2]:

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$$

[3]:

haf_ref(A) # Using the reference implementation

[3]:

1

[4]:

hafnian(A) # Using the default recursive method

[4]:

1


Let’s see what happens if we rescale the adjacency matrix by a scalar $$a$$. We’ll use the SymPy library for symbolic manipulation:

[5]:

from sympy import symbols

[6]:

a = symbols("a")
haf_ref(a*A)

[6]:

a**3


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:

[7]:

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)

[8]:

haf_ref(At, loop=True) # Using the reference implementation

[8]:

2

[9]:

hafnian(At, loop=True) # Using the default recursive method

[9]:

2.0000000000000107


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

[10]:

haf_ref(A+np.diag([1,1,1,1,1,1]), loop=True)

[10]:

15


Note

Click here to download this gallery page as an interactive Jupyter notebook.