Every light on, from every light off

Lights Out is linear algebra over the field with two elements. Each press is a vector — the set of lights it toggles — and pressing a set of lights adds their vectors, with $1 + 1 = 0$ because toggling twice changes nothing. Which patterns can be produced from an empty board is the image of the press matrix, and on most board sizes that image is everything: any pattern can be made, and any pattern cleared. On some sizes it is not. The five-by-five board has a two-dimensional space of quiet patterns — press sets that change nothing — and so it reaches only one pattern in four.

So here is a question with no reason to have a clean answer. On a board that cannot reach most patterns, can it at least reach the one with every light on?

It always can. Klaus Sutner proved in 1989 that on every board, and on every network of lights in which pressing a light toggles it and its neighbours, the all-on pattern is reachable from all off. The reason is shorter than the statement.

Fifteen presses on the five-by-five board #

Solving the system — twenty-five equations over the field with two elements, one per light, asking that each light be toggled an odd number of times — gives a solution, and since the board has two independent quiet patterns, four solutions in all: any one, plus any combination of the quiet patterns. The fewest presses among the four is fifteen. The solution is not obvious by hand, and nothing in the rules of the game suggests that all on should be easier to reach than a single light in a corner, which on this board cannot be reached at all. A corner light lies in two of the three quiet patterns, and a pattern can be produced only if it overlaps every quiet pattern an even number of times; a single corner overlaps two of them once each, so it is out of reach. The all-on pattern overlaps the quiet patterns in sixteen, twelve and twelve lights — the whole of each — and passes.

The fifteen presses also have a shape worth noticing. They are not symmetric under the board’s own symmetries, although the problem is: turning the board a quarter turn carries the all-on pattern to itself, so it carries a solution to a solution, and the four solutions are permuted among themselves. The one drawn has the fewest presses, and its rotations and reflections are solutions with the same number.

The three-by-three board by hand #

On a board with no quiet patterns the answer is unique, and the three-by-three board is small enough to find it without a computer. Press the four corners and the centre. Each corner press toggles the corner and its two edge neighbours; the centre press toggles the centre and the four edge lights. A corner is toggled once, by its own press. An edge light is toggled by the two corners beside it and by the centre: three times, so it ends on. The centre is toggled once, by its own press. Every light ends on, after five presses.

Because the three-by-three board has no quiet patterns, this is the only solution, and every pattern on the board can be reached in exactly one way. That is the situation on most boards. The five-by-five board is different: its quiet patterns mean that some patterns cannot be reached and those that can be reached in four ways each. The question of this essay only has content on boards of that second kind, and the next figure shows how common they are.

Every square board to thirty #

The quiet dimension is erratic in the size of the board: nought for most sizes, but 4 for the four-by-four, 8 for nine-by-nine, 16 for nineteen-by-nineteen and 20 for thirty-by-thirty. A thirty-by-thirty board reaches only one pattern in about a million. Its all-on pattern is among them, as it is on every other size. The size pattern is a question about polynomials over the field with two elements, settled in principle by a greatest common divisor — Euclid’s algorithm run on polynomials — and in practice only by computing it; the all-on question has no such complexity, because the answer is always yes.

The sizes that fail are not rare curiosities. Of the first thirty boards, twelve have quiet patterns, and the ones that do have many: nineteen-by-nineteen has sixteen independent quiet patterns, so $2^{16} = 65{,}536$ different press sets all turn every light on, and the fewest of them is a needle in that haystack. On such a board the puzzle of clearing a random scramble usually has no solution at all, and a player who knows only the rules would have no reason to expect the all-on target to behave any differently from a random one. It is the structure of the target — overlapping every quiet pattern completely — that makes it special.

Why the answer is always yes #

The image of a matrix is everything that can be produced. For a matrix that is symmetric — where the effect of light $i$ on light $j$ equals the effect of light $j$ on light $i$ — the image has a clean description: it consists of exactly the patterns that are orthogonal to every quiet pattern, orthogonal meaning that they overlap in an even number of lights. So all on is reachable exactly when every quiet pattern has an even number of lights in it.

And every quiet pattern does. Take a quiet set of presses $q$ and count, over all pairs of a pressed light and a light it toggles, how many pairs there are. Counted by the toggled light, every light is toggled an even number of times, since the pattern is quiet; so the total is even. Counted by pairs: each pressed light toggles itself, contributing one pair per pressed light, and toggles its pressed neighbours, contributing pairs that come in twos — light $i$ toggling light $j$ and light $j$ toggling light $i$, both pressed. So the total is the number of pressed lights plus an even number. Hence the number of pressed lights is even.

In the language of matrices: for a symmetric matrix $M$ over the two-element field, $q^{\mathsf T} M q = \sum_i M_{ii} q_i$, because the off-diagonal terms pair off and cancel; with every diagonal entry 1, that is the number of presses; and with $Mq = 0$ it is nought. The all-on vector is orthogonal to every quiet pattern, so it is in the image. Nothing about grids was used — only that the influence is symmetric and that every light affects itself.

Why the image is what it is #

The step from “every quiet pattern is even” to “all on can be reached” deserves a word, because it is where symmetry is used the first time. A pattern $b$ can be produced exactly when the equations $Mx = b$ have a solution, and there is a standard test: $b$ must be orthogonal to every vector $y$ with $y^{\mathsf T} M = 0$ — every way of combining the equations that makes their left sides vanish must make the right side vanish too. For a symmetric $M$ those vectors $y$ are the same as the quiet patterns, and so the test reads: a pattern can be produced exactly when it overlaps every quiet pattern in an even number of lights. That the test is not only necessary but sufficient is a dimension count — the patterns passing it form a space of the same size as the image.

Over the real numbers this would be unremarkable. What makes it bite here is the second use of symmetry, which needs the field to have two elements: the pairing that makes $q^{\mathsf T} M q$ equal to the number of presses works because $x + x = 0$. Over the field of three elements a pair of equal off-diagonal terms adds to $2x$, not to nought, and the argument has nothing to say. It is the same distinction that makes the field with four elements behave so differently from arithmetic modulo four.

Every network, not only boards #

The argument never mentioned rows and columns, so it applies to any network of lights.

Most of the random networks — 927 of 1,500 — are of the deficient kind, on which some patterns cannot be reached. They are small, finite cousins of the graph that infinitely many coin tosses make, and like most random symmetric matrices over the two-element field, their press matrices are singular more often than not. Every one of them can be turned all on. In graph theory the set of lights pressed is called an odd dominating set: a set of vertices such that every vertex is in it or adjacent to it an odd number of times. Sutner’s theorem is the statement that every graph has one — a fact that is easy to state, has no obvious combinatorial proof, and falls out of linear algebra in a paragraph.

The density pattern in the figure has a plain reason. In a dense network each press reaches many lights, so fewer presses suffice; in a sparse one, a network of isolated lights needs every light pressed, and the share approaches one. In between, the shares cluster around a half, and the singular networks (cool) are spread through the same range as the others: being unable to reach most patterns has no visible effect on how hard all on is to reach. The theorem is blind to rank, and so, apparently, is the fewest number of presses.

When influence runs one way #

The proof used symmetry twice: once for the description of the image, once for the pairing of off-diagonal terms. Remove it and the theorem fails.

The counterexample is small enough to check by hand. Lights 3 and 4 influence each other; light 2 influences light 3 but not the reverse; light 1 is alone. Turning all on needs light 1 pressed and light 2 pressed, since nothing else reaches them. Then light 4 must be toggled once in total, by pressing exactly one of 3 and 4; but light 3, already toggled by the press of 2, must be toggled an even number of times more, which needs both or neither of 3 and 4. The two demands contradict each other, and all on is out of reach. One one-way arrow is enough to break a theorem that holds for every symmetric network.

Random one-way networks fail often: 865 of the 4,000 drawn could not be turned all on, more than one in five. The reason is visible in the proof’s second step. With one-way arrows, a quiet pattern can press an odd number of lights, because the influences no longer come in matched pairs; and then the all-on pattern, which overlaps every press set completely, fails the evenness test. Symmetry is not a convenience of the argument but the substance of the theorem — which is why it holds for every friendship network and fails for a network of followers.

Three states instead of two #

The failure over three elements is not hypothetical. Give each light three states — off, dim, bright — and let a press advance the light and its neighbours one state, cycling back to off. The all-on question becomes: can every light be advanced exactly one state? On the three-by-three board, yes. On the two-by-two board, no: each press advances three of the four lights, so the four presses together advance each light three times, and any combination advances the lights by amounts whose total is a multiple of three, while advancing all four by one needs a total of four. On the eight-by-eight board the answer is also no, for reasons a computation shows and a sentence does not. Over three elements there is no theorem, only a table — exactly what the parity argument predicts by its silence. The version with self-toggling and two states is, in this sense, the unique place where the question has a one-line answer: any change to the field or to the symmetry turns it back into a computation.

Parity as a certificate #

The argument belongs to a family of parity proofs that has appeared before. Tseitin’s contradictions are sets of parity demands on the edges of a graph that add up to an odd total and so cannot all be met; their unsatisfiability is a single sum. Here the situation is reversed: a sum that is always even guarantees that a system can be satisfied. The cycles and cuts of a graph are the same kind of object — the kernel and image of a matrix over two elements, and the statement that they are orthogonal complements is the statement used here.

In both directions the mechanism is the one that makes finite fields useful in combinatorics: a count that would be hopeless to organise becomes a dot product, and a dot product over two elements is a parity. Counting solutions modulo a prime is the same idea with more elements. And holes in a shape are counted by the same algebra — cycles modulo boundaries, over two elements — which is why the methods that find quiet patterns on a board also compute the holes of a surface.

Sixteen press sets, thirty boards, fifteen hundred networks #

The board computations solve each system exactly, by elimination over the two-element field, and check each solution by multiplying it back. The random networks are a sample: fifteen hundred networks of fourteen lights demonstrate the theorem’s reach and the share of singular matrices, but they prove nothing the paragraph above does not already prove for every network.

What the figures cannot show is the fewest presses for large boards. Finding the smallest odd dominating set of a graph is a hard problem in general, and the fewest presses here are found by trying every solution in the coset of quiet patterns, which is feasible only when the quiet dimension is small. For the thirty-by-thirty board, with a million solutions, the fewest is not drawn. The random networks also stop at fourteen lights for this reason: the fewest presses for each is found exactly, by trying every solution, and that is cheap only when the networks are small. Larger networks would show the same universal solvability and a fewest-press curve that could only be estimated.

Still open: the smallest odd dominating sets #

Sutner’s theorem guarantees an odd dominating set; it says nothing about how small one can be. For grids, the minimum size grows roughly in proportion to the area, and the constant is known only approximately from computation. For general graphs, deciding whether there is an odd dominating set of a given size is known to be computationally hard, and good bounds in terms of simple graph parameters are not known.

A second direction is the variant where pressing a light toggles only its neighbours and not itself. There the diagonal of the matrix is nought, the parity argument gives nothing, and indeed all on is not always reachable: on some graphs, every press set leaves a light off. Which graphs admit the all-on pattern in that version — the graphs with an “odd open dominating set” — has partial characterisations, but no criterion as clean as the one-line answer for the version with self-toggling. Even for the grid boards in that version, which sizes allow all on is known only by computation, size by size, much as the sizes that allow every pattern are in the original game.

A pattern that cannot be refused #

On a board where three patterns in four cannot be produced, the one with every light on is always among those that can. The reason is that the press matrix is symmetric over a field where $1 + 1 = 0$: the patterns that change nothing then always press an even number of lights, and so they never stand in the way of the pattern that lights everything. The same holds on every network where each light affects itself and its neighbours affect it back, and fails on a network of four lights with a single one-way arrow.

The theorem is a small instance of a pattern that runs through finite-field arguments in combinatorics: a question about existence, hard to attack by construction, becomes a question about a space of obstructions, and the obstructions turn out to have a property — here, evenness — that the target cannot violate. The construction is never written down. On the five-by-five board it happens to need fifteen presses; on the thirty-by-thirty board nobody has looked for the fewest; and on every board, the theorem guarantees there is one.