At the end of Chapter 5, we found our escape hatch.

Pieter Kasteleyn proved that if we build an Adjacency Matrix for our checkerboard—using $1$s for horizontal dominoes and $i$s for vertical dominoes—the square root of the determinant will exactly equal the number of perfect tilings.

But for a large board, calculating the determinant directly is a nightmare. Instead, we use a fundamental law of linear algebra: the determinant of a matrix is equal to the product of all its eigenvalues.

To find the eigenvalues, we have to pull back the curtain and look at the matrix itself.

The 18x18 Matrix Reveal

Let’s look at a $6 \times 6$ checkerboard. It has 36 squares (18 black, 18 white). If we organize our nodes row by row, from top to bottom, our bi-adjacency matrix is an $18 \times 18$ grid of numbers.

If we write it out, it forms what mathematicians call a Block-Tridiagonal Matrix.

It looks exactly like this:

$$K = \begin{pmatrix} H_1 & iI & 0 & 0 & 0 & 0 \cr iI & H_2 & iI & 0 & 0 & 0 \cr 0 & iI & H_1 & iI & 0 & 0 \cr 0 & 0 & iI & H_2 & iI & 0 \cr 0 & 0 & 0 & iI & H_1 & iI \cr 0 & 0 & 0 & 0 & iI & H_2 \end{pmatrix}$$

Look closely at the structure. This $18 \times 18$ matrix is made of smaller $3 \times 3$ matrices!

  • The $H_1$ and $H_2$ blocks along the main diagonal represent the Horizontal edges within each row. Why are there two different $H$ blocks? Because the checkerboard alternates! Row 1 starts with a White square, but Row 2 starts with a Black square, which slightly shifts the geometry of the connections.
  • The $iI$ blocks just off the diagonal represent the Vertical edges connecting the rows together. They are Identity matrices multiplied by $i$.
  • The $0$ blocks simply mean that row 1 doesn’t magically touch row 4.

To truly appreciate how beautiful this is, we have to unfold it.

Here is the exact, uncompressed $18 \times 18$ matrix. I have added grid lines so you can see exactly where the 6 rows of the board live. Look at how the $1$s inside the $H$ blocks alternate between leaning left and leaning right, perfectly mimicking the staggering of a checkerboard. Meanwhile, the imaginary $i$s form perfect diagonal bridges between the rows.

$$ \left( \begin{array}{ccc|ccc|ccc|ccc|ccc|ccc} 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 1 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr \hline i & 0 & 0 & 1 & 1 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & i & 0 & 0 & 1 & 1 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & i & 0 & 0 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & i & 0 & 0 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & i & 0 & 1 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & 0 & i & 0 & 1 & 1 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 1 & 0 & i & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 1 & 0 & i & 0 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 0 & 0 & i & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 0 & 0 & i & 0 & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 1 & 1 & 0 & 0 & i & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 1 & 1 & 0 & 0 & i \cr \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 1 & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 & 1 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & i & 0 & 0 & 1 \end{array} \right) $$

By writing it this way, we expose a massive geometric truth: a 2D checkerboard is not a single, complex shape. It is just a 1D horizontal line of squares intersecting with a 1D vertical line of squares.

Because they are independent, we can split the math. To find the eigenvalues of the 2D board, we just need to find the eigenvalues of a simple 1D line.

The Origin of Pi (Eigenvalues of a 1D Line)

Imagine a single 1D row of squares. What are its eigenvalues?

In physics and linear algebra, a 1D line of connected nodes is identical to a vibrating guitar string. When you pluck a string, it doesn’t vibrate chaotically; it vibrates in discrete, perfect waves (harmonics). The eigenvalues of this system are the frequencies of those waves.

And what mathematical function perfectly describes a wave? The Cosine function.

This is the exact moment the trigonometry enters the room. It has nothing to do with circles or angles. It appears because the mathematical “frequencies” of a 1D line form standing waves.

For a 1D line of length $L$, the eigenvalues ($\lambda$) are known to be exactly:

$$\lambda_k = 2 \cos \frac{\pi k}{L+1}$$

Crossing the Waves

Because our 2D grid is just two 1D lines crossing, the eigenvalues of our massive Kasteleyn matrix are simply the horizontal waves added to the vertical waves.

But remember Kasteleyn’s Magic Trick from Chapter 5! We weighted the horizontal edges with $1$, and the vertical edges with $i$.

Therefore, every single eigenvalue of our $M \times N$ matrix takes the form of a complex number:

$$\lambda_{j,k} = 2 \cos \left( \frac{\pi j}{M+1} \right) + i \cdot 2 \cos \left( \frac{\pi k}{N+1} \right)$$

We have the horizontal wave (real), and the vertical wave (imaginary).

The Final Multiplication (Folding the Matrix)

We are at the finish line.

To find the determinant, we must multiply every single eigenvalue together. We must multiply all $M \times N$ of these complex numbers.

At first glance, this seems like it would leave us with a massive, imaginary mess. But graphs are highly symmetric. Think about a cosine wave: it perfectly mirrors itself ($\cos(\pi - x) = -\cos x$). Because of this, every complex eigenvalue in our matrix has an exact twin—its complex conjugate.

If we have an eigenvalue of $(a + bi)$, somewhere else in the matrix there is an eigenvalue of $(a - bi)$.

When we pair these twins up and multiply them together, something beautiful happens:

$$(a + bi)(a - bi) = a^2 - abi + abi - b^2 i^2$$

The $+abi$ and $-abi$ cancel each other out. The imaginary numbers vanish. And because $i^2 = -1$, the $-b^2 i^2$ flips into a positive $+b^2$.

The entire expression cleanly collapses into:

$$a^2 + b^2$$

Let’s apply this to our cosine eigenvalues. When we multiply the complex conjugates together, the imaginary $i$ vanishes, the negative sign flips to a positive, the $2$s square into $4$s, and the cosines square into $\cos^2$.

Because we paired the roots up, we don’t have to multiply all $M$ and $N$ terms anymore. The pairings fold the product perfectly in half! We only have to iterate up to $\lceil M/2 \rceil$ and $\lceil N/2 \rceil$. Finally, taking the square root of the determinant completes the formula.

The universal equation crystallizes:

$$\text{Tilings} = \prod_{j=1}^{\lceil M/2 \rceil} \prod_{k=1}^{\lceil N/2 \rceil} \left( 4 \cos^2 \frac{\pi j}{M+1} + 4 \cos^2 \frac{\pi k}{N+1} \right)$$

No bitmasks. No $8.4$ trillion operation for loops. No Berlekamp-Massey arrays.

By stepping out of computer science and into the geometry of matrices, Pieter Kasteleyn reduced a problem with 18 quintillion states into an elegant, closed-form equation that can be calculated in $O(1)$ time.

The $64 \times 64$ board is solved.