The boards on which every light goes out

The finite fields in this sequence have so far been objects of number theory: a field with four elements, powers that run through every element, counts of solutions to equations, sets of cards. The smallest of them, the field with two elements, where $1 + 1 = 0$, is also the arithmetic of switches. A switch flipped twice is back where it started; two flips cancel. A puzzle made of switches is a problem in linear algebra over that field, whether or not it looks like one.

The puzzle in this essay was sold in 1995 as a handheld game called Lights Out: a 5 × 5 grid of lit buttons. Pressing a button toggles it and the buttons directly above, below and to either side of it. The goal is to turn every light off.

Presses are vectors #

Two facts make the puzzle linear. Pressing a button twice toggles each affected light twice, which leaves it as it was, so a button is either pressed once or not at all. And the order of presses does not matter, because each light simply flips once for every press that touches it. A solution is therefore not a sequence but a set of buttons — a vector of 25 entries, each 0 or 1, over the field with two elements.

The effect of a set of presses is a sum. Each press contributes the pattern of lights it toggles, and the patterns add with $1 + 1 = 0$: a light toggled by two of the chosen presses ends as it began. So the lights produced by a set of presses $x$ are $Ax$, where $A$ is a 25 × 25 matrix of 0s and 1s whose $j$-th column is the pattern that press $j$ toggles. Clearing a board with lights $b$ means solving $Ax = b$, a system of 25 linear equations in 25 unknowns, and the figures solve it by Gaussian elimination, done with additions that are exclusive ors.

The board in the figure has four solutions, of 7, 11, 13 and 17 presses. That there are exactly four, and not one, is the first sign that the 5 × 5 matrix is not invertible: when a linear system has more than one solution, the differences between solutions form a space of their own, and here that space has two dimensions and four elements.

The matrix of a small board #

On a 3 × 3 board the matrix is small enough to draw. Each column has three, four or five entries, for a corner, edge or centre press. The table is symmetric — press $i$ toggles light $j$ exactly when press $j$ toggles light $i$, since both say the two cells are neighbours or the same cell — and over the two-element field it has full rank 9. So every one of the $2^9 = 512$ patterns of lights on a 3 × 3 board can be cleared, and in exactly one way. A 3 × 3 version of the puzzle, Merlin’s Magic Square, was sold in the 1970s on that guarantee.

The arithmetic matters here. The same table read over the ordinary integers or rationals would be a different matrix with a different rank, because cancellations that happen modulo 2 do not happen otherwise. Whether a board can always be cleared is a question about the field, not only about the pattern of 0s and 1s.

Patterns that change nothing #

On the 5 × 5 board, some sets of presses change nothing. The figure shows the three that are not empty: pressing the 16, 12 or 12 marked buttons toggles every light an even number of times, so the board ends exactly as it started. These are the quiet patterns, the nonzero vectors in the kernel of $A$ — the space a linear map throws away. Together with pressing nothing they form a space of dimension two, and any two of the three add, with $1 + 1 = 0$, to the third.

A kernel of dimension two means two things at once. Every solvable board has four solutions, since adding a quiet pattern to a solution gives another. And not every board is solvable: the matrix maps a 25-dimensional space of press sets onto a 23-dimensional space of reachable boards, so only $2^{23}$ of the $2^{25}$ boards — one in four — can be cleared.

Because the matrix is symmetric, the quiet patterns also say which boards. A board is solvable exactly when each quiet pattern covers an even number of its lit cells. Each pattern is a parity test, a single equation the board must satisfy, and there are two independent ones. The figure checks this against direct solution on 4,000 random boards, and exactly 1,000 of them pass both tests and turn out solvable — the quarter that the dimension count predicts.

Chasing the lights #

There is a faster way to see the dimension than eliminating 25 unknowns. If a light in the top row is on, the only press that can turn it off without disturbing anything above it is the one directly below. Pressing that cell for every lit light in the top row clears the top row; repeating for each row sweeps all the lights down to the bottom row. Whatever is left there decides the board. This is light chasing, and players use it to solve the puzzle by hand.

Chasing makes everything below the top row forced, so the only free choices are which buttons of the top row to press first: 5 unknowns instead of 25. The lights left on the bottom row depend linearly on those 5 choices, through a 5 × 5 matrix, and the board is solvable exactly when some choice of top-row presses leaves the bottom row dark. That matrix turns out to be a polynomial in a simpler matrix. Write $T$ for the 5 × 5 matrix with 1s on its diagonal and on the two diagonals beside it — the pattern of one press restricted to one row. Then the bottom-row matrix is $p_5(T)$, where the polynomials $p_n$ over the two-element field are defined by

$$p_0 = 1, \qquad p_1 = x, \qquad p_{k+1} = x\,p_k + p_{k-1}.$$

Each step of the chase multiplies by $T$ and adds the row before, which is exactly that recurrence. For $n = 5$ the polynomial is $x^5 + x$, and $p_5(T)$ has rank 3 over the two-element field: the 2 missing dimensions are the 2 quiet patterns.

The recurrence is the one that defines Chebyshev’s polynomials of the second kind, read modulo 2. Over the real numbers those polynomials describe how errors oscillate; over the two-element field they describe how lights propagate down a board, and the same three-term recurrence does both jobs.

Solving it by hand #

The algebra explains the method that experienced players use without knowing any algebra. Chase the lights to the bottom row. If the board is solvable, what is left there is one of only eight patterns, because the bottom-row matrix has rank 3 and $2^3 = 8$. Each of the eight has a remedy in the top row. If the bottom row reads lit, lit, lit, dark, dark — the three leftmost lights on — press the second button of the top row; if it reads dark, lit, dark, lit, dark, press the first three; if it reads lit, dark, dark, dark, lit, press the first two. Then chase again from the top, and the board ends dark. A player memorises a table of seven entries and the puzzle becomes routine.

Each of those remedies is one of four that work, because adding a quiet pattern’s top row to a remedy gives another. The table players learn lists one remedy per pattern, usually the one with fewest presses, and the other three are equally correct. A bottom row that is not one of the eight — 24 of the 32 possible rows — means the board was never solvable, and no amount of chasing will help. The two parity tests of the quiet patterns detect those boards before the chase begins.

The hardest board #

The figures’ first board took 7 presses. Over all $2^{23} = 8{,}388{,}608$ solvable 5 × 5 boards, the fewest presses that clear a board range from 0, for the dark board, up to 15. Exactly 7,350 boards need 15, and none needs more. The count comes from enumerating all $2^{25}$ sets of presses, recording for each board the lightest of its four solutions.

Fifteen is less than it might be, and the comparison with the 3 × 3 board shows why. There the matrix is invertible, every board has exactly one solution, and the board produced by pressing all nine buttons can only be cleared by pressing all nine again: the hardest 3 × 3 board needs every press there is. On the 5 × 5 board every solvable board has four solutions to choose from, differing by quiet patterns of 12 or 16 presses, and a heavy solution always has a much lighter partner among the four. The kernel that makes three quarters of the boards unsolvable is what keeps the solvable ones from needing more than 15 of the 25 presses.

Which sizes fail #

Running the chase for every square board up to 40 × 40 gives the figure. Twenty-three of the forty sizes have no quiet patterns at all, and on those boards every pattern of lights can be cleared in exactly one way. The others are irregular: dimension 4 on the 4 × 4 board, 2 on 5 × 5, 8 on 9 × 9, 16 on 19 × 19, 20 on 30 × 30 and 32 × 32, and 32 on 39 × 39, where only one board in $2^{32}$ — one in about four billion — can be cleared. The sequence has no visible pattern, and it is not monotone: a board one row larger can be completely solvable or almost completely not.

The 4 × 4 board is a good example of how much a dimension costs. Its four independent quiet patterns mean that only one board in $2^4 = 16$ can be cleared, and every board that can be cleared can be cleared in sixteen different ways. A game built on a 4 × 4 grid with random starting positions would be unwinnable fifteen times out of sixteen. The 5 × 5 size of the commercial game is one of the better choices near it, but even there only one board in four is solvable, so a game on this board has to choose its starting positions with care. The simplest safe method is to start from a dark board and press buttons at random, which produces only solvable boards, and produces each of them equally often.

The pattern is in the polynomials. The bottom-row matrix is $p_n(T)$, and $T$ is itself a matrix whose characteristic polynomial, over the two-element field, is $p_n(x + 1)$. A polynomial in a matrix loses rank exactly where it shares roots with the matrix’s characteristic polynomial, so the number of quiet patterns is the degree of the greatest common divisor

$$\gcd\big(p_n(x),\ p_n(x + 1)\big).$$

Klaus Sutner proved this in 1989, and the figure checks it for every size shown: the dimension found by chasing equals the degree of the gcd, computed by Euclid’s algorithm for polynomials. A board can always be cleared exactly when $p_n(x)$ and $p_n(x + 1)$ have no common factor.

The irregularity of the sequence is the irregularity of factorisation. Whether $p_n(x)$ and its shift share a factor depends on how $p_n$ factors into irreducible polynomials over the two-element field, and that changes erratically with $n$, much as the factorisations of ordinary whole numbers do. The question “which boards can always be cleared?” is a question about factoring a sequence of polynomials, and it has the character of number theory rather than of geometry.

Rectangles #

The same chase works on a rectangle with $m$ rows and $n$ columns, and the same reasoning gives the dimension as the degree of $\gcd(p_m(x), p_n(x + 1))$, which the figure checks for all 400 rectangles up to 20 × 20. Of those 400, 248 can always be cleared. The table is symmetric, as it must be, since turning a board on its side changes nothing; and its non-blank cells form lines, because a size $m$ whose polynomial has a particular irreducible factor shares it with every $n$ whose polynomial has the matching one. The row for $m = 4$, for example, is non-blank at $n = 4, 9, 14, 19$, every fifth size.

The lines are periodic for a reason that is itself a finite-field fact. The polynomials $p_n$, reduced modulo any fixed irreducible polynomial, repeat with a period, as any linear recurrence over a finite field must; a factor that divides $p_n$ divides $p_{n+k}$ for the right period $k$. That is the same pigeonhole that forces a linear recurrence over two elements to repeat, seen here in the sizes of a game board.

Puzzles that are linear algebra #

Lights Out is one example of a pattern this sequence has met before: a combinatorial question that becomes linear algebra over a finite field, and is then settled by a rank. The polynomial that bounds the caps settled a question about sets of cards by the rank of a polynomial’s coefficients; the cycles and the cuts of a graph are the kernel and image of a matrix over two elements. Here the answer to “can this board be cleared?” is a membership test in the image of $A$, and the answer to “can every board be cleared?” is whether $A$ is invertible.

Variants follow the same rules. On a torus, where the board wraps round, the matrix changes and so does the list of good sizes. With three states per light, cycling off, red and green, the field becomes the integers modulo 3 and the polynomials change. If pressing a light toggles only its neighbours and not itself, the matrix is the adjacency matrix of the grid instead of adjacency plus identity, and the solvable sizes are different again. Each variant is a new matrix over a finite field, and each has its own sequence of polynomial gcds.

What the figures establish #

The figures solve the 5 × 5 and 3 × 3 systems by elimination over the two-element field, find the quiet patterns as the kernel, and check the parity criterion against direct solution on 4,000 random boards. They compute the dimension of the silent patterns for every square board to 40 × 40 and every rectangle to 20 × 20 by chasing, check the chase against full elimination for the small sizes, and check every value against the degree of the polynomial gcd. Sutner’s theorem that the two are always equal is a proof; the figures confirm it on the sizes drawn.

Still open: which sizes are good #

There is no simple description of the board sizes $n$ for which every $n \times n$ pattern can be cleared — the sizes where $p_n(x)$ and $p_n(x + 1)$ are coprime — beyond computing the gcd for each $n$. Some infinite families are understood. Over the two-element field the polynomials satisfy $p_{2n+1} = x\,p_n^2$, which the figures check up to $n = 39$, so a common factor at size $n$ appears squared at size $2n+1$, and the number of quiet patterns at least doubles: the sizes 4, 9, 19 and 39 have dimensions 4, 8, 16 and 32, and the chain goes on to 79, 159 and beyond. Every bad size starts such a chain. Which sizes start one, and what share of all sizes is good, is not described by any known rule.

The difficulty is the one that makes factoring hard in general. The gcd is decided by the irreducible factors of $p_n$ over the two-element field, and how those factors are distributed as $n$ varies — which irreducible polynomials divide which $p_n$, and with what regularity — is a question about the arithmetic of a sequence of polynomials, of the same kind as questions about which primes divide which terms of a sequence of integers. Among the first forty sizes, twenty-three are good. Whether that proportion settles down, and to what, is open.