Signs that make a determinant count

Hall’s theorem answers a yes-or-no question. Given a set of jobs and a set of people, each person qualified for some jobs, can every job be filled by a different person? Yes, unless some group of jobs has too few candidates between them. The essays since have asked how to find the matching, how to certify that none larger exists, what changes when the sides are taken away, and what happens when the people arrive one at a time. Every one of them was about whether a matching exists, or how good a matching can be found.

This essay asks how many there are. The question sounds like a small step from the existence question — if a matching can be found quickly, surely the matchings can be counted — and it is in fact a step off a cliff. For a general bipartite graph, counting perfect matchings is as hard as any counting problem whose answers can be checked, and nobody expects an efficient method. Yet for one large family of graphs, the ones that can be drawn on a flat sheet without crossings, the count is a determinant, and a determinant can be computed in a moment. The difference between the two is a choice of signs, and the whole essay is about that choice: what the signs are for, why they exist on a flat board, why a hole in the board needs one more of them, and why on a graph that cannot be drawn flat they do not exist at all.

The objects counted are domino tilings. A rectangular board of squares, coloured like a chessboard, is a bipartite graph: one vertex per square, black squares on one side and white on the other, an edge wherever two squares share a side. A domino covers one black and one white neighbour, so a covering of the board by dominoes is exactly a perfect matching of that graph.

Deciding and counting are different questions #

Write the board’s graph as a matrix $A$ with a row for each black square and a column for each white one, the entry 1 where the two squares are neighbours and 0 otherwise. A perfect matching assigns to each black square $i$ a different white square $\sigma(i)$, so it is a permutation $\sigma$ with every entry $A_{i\sigma(i)}$ equal to 1. The number of perfect matchings is therefore

$$\operatorname{per} A = \sum_{\sigma} \prod_i A_{i\sigma(i)},$$

the permanent of $A$. It is the determinant’s formula with the signs left off:

$$\det A = \sum_{\sigma} \operatorname{sgn}(\sigma) \prod_i A_{i\sigma(i)}.$$

The two look almost identical, and they could hardly be more different to compute. The determinant can be found by elimination — subtract multiples of rows from one another until the matrix is triangular, and multiply the diagonal — in a number of steps that grows like the cube of the size. Nothing of the kind is known for the permanent. Elimination works because subtracting one row from another does not change the determinant, and that is a property of the signs; the permanent has no such property, and every known method for it takes a number of steps that grows exponentially. Leslie Valiant proved in 1979 that computing the permanent of a matrix of 0s and 1s is complete for the class of counting problems called #P, which means an efficient method for it would give an efficient method for counting the solutions of every problem whose solutions can be checked quickly — the satisfying assignments of a formula, the colourings of a graph, the Hamiltonian cycles. Nobody believes that exists.

What makes this striking is that the existence question for the same graphs is easy. The search that finds a largest matching runs in polynomial time and hands back a certificate when it fails. Deciding is cheap and counting is hopeless, for one and the same family of objects. Counting the colourings of a graph is the more familiar example of a count that knows far more than the yes-or-no answer, but there the yes-or-no answer was already hard. Here it is not, and the gap opens between two questions about matchings alone.

The determinant cannot simply be used instead, and the four-by-four board shows why. With every entry of the matrix equal to 1, each tiling contributes the sign of its permutation, and the hero figure shows those signs: eighteen tilings contribute $+1$, eighteen contribute $-1$, and the determinant is 0. The determinant has counted something, but it is the difference between two kinds of tiling, not their total.

Why the plain determinant gives nought #

The reason the terms split so evenly is a single move. Find two dominoes lying side by side in a two-by-two block — two horizontal dominoes stacked, say — and turn the pair a quarter turn so they become two vertical dominoes. The result is another tiling, and every tiling of a rectangle can be reached from every other by a sequence of these turns, a fact William Thurston made precise in 1990 with a height function that the turns raise and lower one step at a time.

In the language of permutations, a turn is a swap. The two black squares of the block were matched to the two white squares one way, and after the turn they are matched the other way; everything else is unchanged. A permutation followed by a single swap has the opposite sign, so every turn reverses the sign of the term. The tilings of the board therefore fall into two classes by the parity of the number of turns needed to reach them from a fixed one, and the plain determinant is the number in one class minus the number in the other. On the four-by-four board the two classes are the same size. On a two-by-four board they are not, and the plain determinant is 1 while the board has five tilings. The number has nothing to do with the count.

This is the reverse of the problem the determinant that counts trees solved. There, a determinant’s signs were exactly what cancelled the unwanted terms — every subset of edges that was not a spanning tree was paired with another of the opposite sign, and only the trees survived. Here every term is wanted, and the signs are cancelling them anyway. What is needed is a way to make the sign of every term the same.

One minus sign on every square #

Pieter Kasteleyn found it in 1961, and at the same time Harold Temperley and Michael Fisher found the count by another route. The idea is to change some entries of the matrix from $1$ to $-1$, so that each term picks up the product of the signs on its dominoes, and to choose those signs so that the product always cancels the permutation’s sign.

The turn in a two-by-two block shows what is required. Before the turn the term has two dominoes, after it two others, and the permutation sign flips. If the product of the signs on the four edges round the block is $-1$, the product over the two old dominoes and the product over the two new ones differ by exactly that factor, and the flip in the permutation sign is cancelled. So the condition is local: every unit square of the board’s graph — every face of the drawing — must carry an odd number of minus signs.

On a rectangle one rule does it: put $-1$ on every vertical edge in the even-numbered columns and $+1$ everywhere else. A unit face has two horizontal edges, both $+1$, and two vertical edges in neighbouring columns, exactly one of which is in an even column. Every face has one minus sign, every turn preserves the term, and since every tiling can be reached by turns, every tiling contributes the same sign. The absolute value of the determinant is the number of tilings.

The hero figure shows it on the four-by-four board, tiling by tiling: the second sign under each tiling is the term with Kasteleyn’s signs, and all thirty-six are $+1$. On the four-by-five board in the figure above, the plain determinant is 1, the signed determinant is 95, and a direct listing of the tilings finds 95.

The construction does not depend on dominoes. Kasteleyn’s theorem is that every bipartite graph drawn in the plane without crossings has such a signing, with the condition stated for every face: a face bounded by $2k$ edges needs a sign product of $(-1)^{k+1}$, which for the unit squares of a board is $-1$. The proof builds the signs one face at a time, working inward from the outside, each new face having at least one edge not yet signed. The determinant of the signed matrix then counts the perfect matchings.

Three counts that must agree #

A determinant that counts is a strong claim, and the figures do not take it on trust.

Each entry in the table was computed three ways. The first lists the tilings column by column, keeping track of which squares of the next column are already covered by dominoes sticking out of the last — a method that knows nothing about matrices. The second is the signed determinant, computed exactly with whole numbers. The third is a formula Kasteleyn and Temperley–Fisher derived from the determinant by finding its eigenvalues, which on a grid are sums of cosines: the number of tilings of an $m \times n$ board is

$$\prod_{j=1}^{m} \prod_{k=1}^{n} \left( 4\cos^2 \frac{\pi j}{m+1} + 4\cos^2 \frac{\pi k}{n+1} \right)^{1/4}.$$

A product of irrational numbers that comes out to a whole number is surprising enough that it is worth seeing computed, and for the chessboard it gives 12,988,816 to within the rounding of the arithmetic. All three methods agree on every rectangle in the table. The corner numbers are the plain determinants: 0 on seventeen of the thirty-six rectangles, 1 on the other nineteen, whatever the true count. Along the second row the counts are the Fibonacci numbers, which a polynomial that counts derived from a generating function for the narrowest boards; the signed determinant gets them with no special treatment at all.

A hole is a face too #

The rule of one minus sign per square was justified by turns, and turns connect all the tilings of a board with no holes in it. Cut a square out of the middle of the board and that argument quietly stops working.

The question the figure answers is an old one. Remove two squares of the same colour from a chessboard — two opposite corners, in the famous version — and no tiling exists, because every domino covers one square of each colour and the board now has thirty squares of one colour and thirty-two of the other. The signed determinant duly comes out 0. Remove two squares of opposite colours and the colour count balances, and Ralph Gomory showed that a tiling then always exists: the board’s squares lie along a single closed path through all sixty-four, the two removed squares cut it into two pieces of even length, and each piece can be covered by dominoes laid along it. The figure confirms every case with the corner removed — all thirty-two boards can be tiled — and adds what Gomory’s argument does not give, the number of ways. It varies by a factor of almost ten, from 684,760 when the second square sits next to the far corner to 6,494,408 when it sits beside the first.

The first time those counts were computed for this essay, the column rule was applied unchanged, and eighteen of them were wrong. The checking count, made by listing, disagreed with the determinant on exactly the boards whose second square is interior. With the square at the second row and seventh column, the determinant gave 432,480; the board has 1,487,200 tilings.

The reason is that an interior hole is a new face. Removing a square removes its vertex and the four edges at it, and the four unit faces that met there merge into one face bounded by eight edges. Kasteleyn’s condition for a face of eight edges asks for a sign product of $(-1)^{5} = -1$. The product the column rule leaves on it is the product of the four old faces’ products, each $-1$, which is $+1$ — the four removed edges each appear twice and drop out. The face that the hole created has the wrong parity, and the tilings that differ by a rotation of dominoes round the hole, which no sequence of two-by-two turns can produce, contribute terms of opposite sign and cancel.

The repair is Kasteleyn’s own. Draw a cut from the hole straight to the edge of the board and reverse the sign of every edge it crosses. The cut enters and leaves each unit face it passes through, so it changes two of that face’s signs and leaves its product alone; it crosses only one edge of the hole’s face, so it flips that product to $-1$. With the cut, all eighteen counts agree with the listing. It is a small episode, but it is the clearest demonstration available of what the signs are actually tracking: not the squares, and not the dominoes, but the faces of a drawing in the plane.

No signs for a graph that cannot be drawn flat #

If every face needs a parity, a graph with no faces — one that cannot be drawn in the plane at all — has nothing for the signs to be about. The smallest bipartite example is $K_{3,3}$: three vertices on each side, each joined to all three on the other.

The matrix of $K_{3,3}$ is three-by-three with every entry 1, and its permanent is $3! = 6$, one for each perfect matching. A signing that counted would make the determinant $\pm 6$. With nine edges there are $2^9 = 512$ signings, few enough to try every one, and none of them works: the determinant’s absolute value is 0 for 320 of them and 4 for the other 192. Six is never reached. Of the six terms, the best any signing can do is to make five agree and one disagree, which leaves four.

That $K_{3,3}$ cannot be drawn in the plane is an old fact about crossings, and the essay that established it showed that every drawing needs at least one. What the determinant adds is that the obstruction to drawing is also an obstruction to counting. Charles Little showed in 1975 that this is the only one, in a precise sense: a bipartite graph has a signing that makes its determinant count its perfect matchings exactly when it does not contain $K_{3,3}$ in a particular way that respects the matchings. Flat graphs never contain it; some graphs that cannot be drawn flat still escape it and can still be counted. But Valiant’s theorem says the escape is not general: for all bipartite graphs together there is no shortcut.

Choices per square #

The counts in the table grow fast — the chessboard’s sixty-four squares have nearly thirteen million tilings — and the natural question is how fast.

If a board of $n^2$ squares has $T$ tilings, then $T^{1/n^2}$ is the number of choices each square would have to contribute, independently, to produce that many. For the two-by-two board it is $2^{1/4} \approx 1.189$, since two tilings are spread over four squares. For the chessboard it is about 1.292. As the board grows, the product formula turns into an integral, and the integral evaluates to a constant:

$$\lim_{n\to\infty} T_n^{1/n^2} = e^{G/\pi} \approx 1.33851,$$

where $G = 1 - \tfrac{1}{9} + \tfrac{1}{25} - \tfrac{1}{49} + \cdots \approx 0.91597$ is Catalan’s constant. The approach is slow. At a thousand squares on a side the rate is still 1.3381, and the figure shows why it climbs from below: squares along the edge have fewer neighbours to pair with, and the edge is a share $4/n$ of a square board, so the boundary drags the average down by an amount that shrinks only like $1/n$.

That remark about the boundary is the seed of the next essay. Here it looks like a small correction that vanishes in the limit. For other shapes of region it does not vanish at all.

Why the planar case is special #

It is worth asking why flatness should matter to a sign. The determinant is the alternating sum over permutations, and the sign of a permutation is a parity — whether it is an even or odd number of swaps from the identity. The crossings that will not come out even used exactly that parity to show some rearrangements cannot be reached. For matchings in a drawing, two perfect matchings laid on top of each other form a collection of disjoint cycles, and the relative sign of the two terms is determined by those cycles: each cycle of length $2k$ contributes a factor $(-1)^{k+1}$ to the ratio of permutation signs. The signing’s job is to make the product of edge signs round every such cycle cancel that factor.

In a flat drawing, a cycle encloses a region, and the region is made of faces. If every face has the right parity, the parity of a cycle is fixed by the faces and vertices inside it — and here a pleasant fact about matchings enters: the vertices strictly inside a cycle formed by two perfect matchings are themselves perfectly matched among themselves, so there is an even number of them, and the parity comes out right for every cycle at once. That is the whole proof, and it uses the drawing twice: once to say a cycle has an inside, and once to say the inside is made of faces. A graph that cannot be drawn flat has cycles with no inside, and nothing prevents two of them from demanding contradictory signs, which is what the 512 signings of $K_{3,3}$ find.

For graphs whose sides have been taken away — the general graphs of the piece that cannot pair off, where an odd component blocks a matching — the determinant is replaced by its square root, the Pfaffian of a skew-symmetric matrix, and Kasteleyn’s theorem holds in the same form: every flat graph has an orientation of its edges for which the Pfaffian counts the perfect matchings. That version is the one Kasteleyn used for the dimer problem in physics, where molecules occupying pairs of neighbouring sites on a crystal surface are dominoes by another name.

Still open: which graphs can be counted #

For bipartite graphs the question of which ones admit a counting signing is settled in principle by Little’s theorem, and Neil Robertson, Paul Seymour and Robin Thomas — and independently William McCuaig — showed in 1999 that it can be decided in polynomial time whether a given bipartite graph has one. That answered a question George Pólya had asked in 1913: for which matrices of 0s and 1s can the permanent be turned into a determinant by changing signs?

For general graphs, with Pfaffians in place of determinants, the corresponding question is open. No efficient method is known for deciding whether a given graph has an orientation that makes its Pfaffian count its perfect matchings, and no proof is known that the problem is hard. Between the flat graphs, which always can be counted, and the general case, which cannot be counted quickly unless almost every counting problem can, there is a large family of graphs whose status is decided case by case. Graphs that can be drawn on a torus are an instructive middle: there one determinant does not suffice but four, combined with signs, do, and on a surface with more handles the number of determinants needed grows as a power of four with each handle — a count that still works, at a price set by the topology of the surface.

A sign for every face #

The essay began with a yes-or-no theorem and ended with a number. The bridge between them was not a cleverer search but a reinterpretation: the count of matchings is the permanent, the permanent is the determinant with its signs removed, and on a flat graph signs can be put back in a way that makes every term agree. The four-by-four board’s thirty-six tilings cancel to nothing under the plain determinant and add to thirty-six under the signed one; the chessboard’s 12,988,816 come out of elimination on a thirty-two by thirty-two matrix; and the eighteen boards with interior holes showed, by going wrong, that what the signs encode is the faces of the drawing. Take the drawing away and the signs have nothing to encode — $K_{3,3}$ tries all 512 of them and never reaches six.