# Basics of Hafnians and Loop Hafnians
*Author: Nicolás Quesada*

In the [background section](../hafnian.html) of the The Walrus documentation, some basic ideas related to (loop) hafnians were introduced. This tutorial is a computational exploration of the same ideas.


```python
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


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


```python
haf_ref(A) # Using the reference implementation
```




    1




```python
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](https://sympy.org) library for symbolic manipulation:


```python
from sympy import symbols
```


```python
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


```python
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)


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




    2




```python
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


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




    15



c7e62b46a4a3e3290c6e589f09d8fecd8a824017
ipynb
Jupyter Notebook
docs/gallery/basics.ipynb
BastianZim/thewalrus
28cba83b457fc068861c542f0e86d8c9d198b60b
Apache-2.0
2019-08-13T18:28:00.000Z
2022-03-07T17:37:10.000Z
docs/gallery/basics.ipynb
BastianZim/thewalrus
28cba83b457fc068861c542f0e86d8c9d198b60b
Apache-2.0
2019-08-19T00:28:31.000Z
2022-03-28T19:25:12.000Z
docs/gallery/basics.ipynb
BastianZim/thewalrus
28cba83b457fc068861c542f0e86d8c9d198b60b
Apache-2.0
2019-09-18T18:23:28.000Z
2022-02-20T07:01:29.000Z
Qwen/Qwen-72B
1. YES
2. YES