Pfaffian Trickery

26Apr10

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,

$\displaystyle \det\begin{pmatrix}0 & 3 & -4& 5 \\ -3& 0& 2& -1 \\ 4 &-2& 0 &-6 \\ -5& 1& 6 &0\end{pmatrix}$

equals 144, which is indeed a square number.

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

$\displaystyle \det\begin{pmatrix}0& a& b& c \\ -a& 0& d& e \\ -b& -d &0 &f \\ -c& -e& -f& 0\end{pmatrix} = (af - be + cd)^2$

The determinant is the square of a polynomial in the variable which is called the Pfaffian (here the Pfaffian is afbe + 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, …, 2n} is associated with some variable, which we denote by x{i, j}.

Theorem. The Pfaffian equals

$\displaystyle \sum_M \mathrm{sgn}(M) \prod_{\{i, j\} \in M} x_{\{i, j\}}$

where M ranges over all perfect matchings of {1, 2, …, 2n} 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!

Hasenpfeffer

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