### Pfaffian Trickery

This week at EPFL I am presenting a recent paper by Andreas Björklund, which I found to be pretty elegant. It uses algebraic combinatorics to get a faster algorithm for a combinatorial problem: given a bunch of *k*-element subsets of {1, 2, …, *kn*}, determine if one can find a “perfect matching” of *n* subsets which are disjoint (and thus cover every point exactly once).

Björklund uses a generalization of the Pfaffian of a matrix, and the Pfaffian itself is awesome enough that you should know about it. The heart of what is so cool is the following. Suppose we have a matrix of integers which is *skew-symmetric*: the entry at row *i* and column *j* is the negative of the one at row *j* and column *i*. Then its determinant is a perfect square. For example,

equals 144, which is indeed a square number.

A similar thing holds for a skew-symmetric matrix of variables:

The determinant is the square of a polynomial in the variable which is called the Pfaffian (here the Pfaffian is *af* – *be* + *cd*).

Even better, the terms of the Pfaffian are always given in a nice combinatorial way that enumerates perfect matchings. Note that in the skew-symmetric matrix above, the variable *a* appears in row-column positions (1, 2) and (2, 1). Let’s say that we associate the unordered pair {1, 2} with the variable *a;* similarly, each unordered pair {*i*, *j*} of elements from {1, 2, …, 2*n*} is associated with some variable, which we denote by *x*_{{i, j}}.

**Theorem.** The Pfaffian equals

where *M* ranges over all perfect matchings of {1, 2, …, 2*n*} and sgn(*M*) is +1 or -1 for each *M*.

There is a nice combinatorial proof of this theorem. More precisely, in a proof we would define the right rule to compute sgn(*M*) and then show that the square of the above expression equals the determinant. The book *Algebraic Combinatorics* by Godsil, available on google books, seems to have it with a minor bug.

What Björklund did in his paper is find a cousin of this theorem, changed in two ways: first, we work modulo 2 (more precisely in a field of characteristic 2, so the signs disappear) and second, we insert diagonal entries into the matrix, which breaks skew-symmetry. The determinant is no longer a perfect square but it can be expressed using a formula much like the **Theorem** above; Björklund’s proof is short and self-contained because the characteristic 2 really simplifies things in an essential way.

This all is useful in order to compute a generating function over the field — the generating function enumerates some variant of perfect matchings that are allowed to include the loops corresponding to the diagonal variables — which is used with inclusion-exclusion to determine whether any perfect *k*-set matching exists. The paper is sort of a tour de force, also using randomization to get the desired result!

How do you pronounce Pfaffian? If you have watched enough Bugs Bunny & Elmer Fudd you should know: like Hasenpfeffer, the P is silent.

Filed under: algorithms, b.k.a.t., food | 1 Comment

Hi Dave!

As always great scientifc news i your blog. Keep the flow…

Once you made me know about the Mihill-Nerode theorem, big thanks for that. You have already help me more than the people who is supposed to do it, 😉

PS: Invitation to eat “Leberli mit Rösti” in a Zürcher beiz still holds!