An implementation of the FKT-algorithm

This post is dedicated to give you an implementation (in SAGE) of the FKT-algorithm. I coded this while spending some time on the ideas i explained in this blog post. I searched several hours to find an existing implementation without success. Since it took me a while to code this on my own, i think it is worth to present it, therewith other can use it in their own work. It works well, but if you find an error, please leave a note.

The FKT-algorithm can be used to count the number of perfect matchings in a planar graph. And a graph is planar if and only if it does not have K$_5$ or K$_{3,3}$ as a minor.

A paper that will be presented at the CCC conference this year is called:

Counting the Number of Perfect Matchings in $K_5$-free Graphs [in polynomial time] Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University)

I did not manage to read it yet, but i am curious to see, how they circumvent the K$_{3,3}$ minor problem.

########################################################################
# AUTHOR: Dr. Christian Schridde
# E-MAIL: christianschridde [at] googlemail [dot] com
#
# DESCRIPTION: Implementation of the FKT-algorithm
#
# INPUT:  Adjacency matrix A of a undirected loop-free planar graph G
# OUTPUT: Skew matrix M, such that PerfMatch(G) = Sqrt(Determinat(M))
########################################################################