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

1

hafnian(A) # Using the default recursive method

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:

from sympy import symbols

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

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:

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

2

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

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

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

15

Note

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

gallery/basics

 

Download Python script

 

Download Notebook

 

View on GitHub