When a press skips its own light

Every light on, from every light off proved Klaus Sutner’s theorem: on any board, and any network of lights, the pattern with every light on can be reached from the pattern with every light off. The proof was a parity argument that used one feature of the rules in an essential way. Pressing a light toggles that light as well as its neighbours, so the press matrix has ones all down its diagonal. The essay ended by asking what happens without that feature, when a press toggles the neighbours and leaves the pressed light alone.

The answer is that the guarantee disappears and something more interesting replaces it. Some boards can be lit and some cannot, and which is which follows a rule simple enough to state in a sentence and not obvious from anything in the setup. On general networks the answer depends on whether the number of lights is even or odd, and that dependence never fades, however large the network.

The same algebra with an empty diagonal #

The setting is the linear algebra of the earlier boards. Each light is a coordinate in a vector over the field with two elements, where $1 + 1 = 0$. Each press adds a fixed vector — the set of lights it toggles — and pressing a set of lights adds their vectors. The patterns reachable from all off are the column space of the press matrix. With the original rule that matrix is the graph’s adjacency matrix plus the identity. With the new rule it is the adjacency matrix $A$ alone, with nought on the diagonal.

All on is reachable exactly when the all-ones vector $\mathbf 1$ lies in the column space of $A$. Because $A$ is symmetric, a standard duality turns that into a statement about the kernel: $\mathbf 1$ is in the column space exactly when it is orthogonal to every vector $x$ with $Ax = 0$, which means every such $x$ has an even number of ones.

A vector with $Ax = 0$ is a set of lights $S$ such that every light on the board, in $S$ or not, has an even number of neighbours in $S$. Call it a silent set: pressing all of it changes nothing. The silent sets form a subspace, the kernel of $A$, and like the cycle and cut spaces of the cycles and the cuts its dimension is read from a rank over this field. If some silent set has an odd number of members, all on is unreachable, and the reason can be checked by counting. Every press toggles an even number of the lights in $S$ — that is what silence means, read the other way — so the number of lit lights inside $S$ is always even. All on would make it odd.

The hero figure’s five-by-five board has such a set, five lights placed on a diagonal pattern, each light on the board seeing nought or two of them. That one count is a complete proof that the board can never be lit. The four-by-four board has silent sets too, but every one of them is even. Its ten presses work.

Why the old proof no longer applies #

Sutner’s proof was short. For any vector $x$, the number $x^{\mathsf T}(A + I)x$ counts, modulo two, the pairs of lights in $x$ joined by an edge — each counted twice, so contributing nothing — plus the lights of $x$ themselves. So it equals the size of $x$ modulo two. If $x$ is silent for the original rules, $(A + I)x = 0$, so $x^{\mathsf T}(A + I)x = 0$, so $x$ has even size. Every silent set is even, and all on is always reachable.

With the identity removed, the same computation gives $x^{\mathsf T} A x = 0$ for every vector $x$, silent or not, since the diagonal that used to contribute the size is gone. The quantity that carried the proof now carries no information. Matrices with this property, symmetric with nought on the diagonal over the two-element field, are called alternating, and nothing forces their silent sets to be even. Whether all on is reachable has to be decided board by board.

Every board to sixty by sixty #

For rectangular boards the decision is fast, by the light-chasing method of the earlier boards. Treat the presses in the top row as unknowns. Each light in the top row has exactly one neighbour in the second row, the light directly below it, and that press is forced: it must be made exactly when the top light would otherwise end in the wrong state. The second row’s presses then force the third’s, and so on to the bottom. The only conditions left are on the bottom row, $m$ equations in the $m$ unknowns of the top row. A board of 3,600 lights becomes a system of sixty equations.

The picture has a structure that is visible before anything is measured. No board with an even number of rows or columns ever fails. Among the odd-by-odd boards the failures sit on a lattice. The $1 \times 1$ board fails, since its single press touches nothing. So do $1 \times 5$, $1 \times 9$ and every board whose two sides both leave remainder 1 on division by 4. Then $3 \times 3$, $3 \times 11$, $11 \times 11$: both sides leaving remainder 3 on division by 8. Then $7 \times 7$ and $7 \times 23$: remainder 7 on division by 16.

The pattern has a compact statement. Write $v_2(k)$ for the exponent of the largest power of two dividing $k$. Then an $n \times m$ board fails exactly when $n$ and $m$ are both odd and

$$v_2(n + 1) = v_2(m + 1).$$

The figure’s computation checks this on every one of the 3,600 boards, and it holds on all of them.

The rule as a table of powers #

Sorting the odd-by-odd boards by the two exponents makes the rule unmistakable.

The diagonal cells hold every failure and contain nothing else: 225 boards where both $n + 1$ and $m + 1$ are twice an odd number, 64 where both are four times an odd number, then 16, 4 and the single $31 \times 31$ board. Off the diagonal, every board in every cell can be lit. The whole table of 3,600 boards is described by comparing two numbers’ powers of two.

Why powers of two should govern a board game is a fact about polynomials over the two-element field, the same algebra that decided the original boards, and the same field that the field with four elements began from. Light chasing on a board of width $m$ produces, row by row, a sequence of polynomials in the shift that moves a row along itself — Chebyshev polynomials reduced modulo two. Over the two-element field squaring is additive, $(a + b)^2 = a^2 + b^2$, so these polynomials obey identities that relate the index $k$ to the index $2k + 1$, and that is where powers of two enter. Whether two boards fail together comes down to whether their polynomials share a particular factor, and the measured rule says this happens exactly when the binary expansions of $n + 1$ and $m + 1$ end in the same number of zeros. This essay checks the rule on every board to sixty and does not prove it in general; the polynomial identities are the route a proof would take.

Paths and cycles #

The simplest networks show the same phenomenon in one dimension.

A path is a board with one row, so the grid rule applies with $n = 1$: a path on $k$ vertices fails exactly when $v_2(k+1) = 1$, which is to say $k \equiv 1 \pmod 4$. The single vertex fails; so do five, nine and thirteen. The witness on a path of five is the first, third and fifth lights. Each light has an even number of these as neighbours, nought or two, and there are three of them.

Cycles are stricter. On a cycle of odd length the whole ring is a silent set: every light has exactly two neighbours, both in the ring, and the ring is odd. On a cycle whose length is twice an odd number, every other light makes a silent set of odd size — each light sees either nought or two of them. Only when the length is a multiple of four are all silent sets even, and only then can the cycle be lit. A cycle of six lights, which is about the simplest network one could draw, cannot be lit.

The same matrix as rule 90 #

On a path, the neighbours-only press matrix is a familiar object under another name. A row of cells in which each cell’s next state is the sum, modulo two, of its two neighbours’ current states is the cellular automaton called rule 90. Its one-step update is exactly the matrix $A$ of a path, and run from a single live cell it draws the Sierpiński triangle of eight rules and a triangle. The original Lights Out press on a path, which adds the cell itself, is rule 150.

So the question this essay asks of a path is a question about rule 90 run for one step on a finite row with dead cells beyond each end. Can the row of all live cells be produced from some earlier row? A configuration that no earlier row produces is called a Garden of Eden, and the answer measured above is that the all-live row of length $k$ is one exactly when $k$ leaves remainder 1 on division by 4. Sutner, who proved the theorem about the original game, came to it from exactly this direction: he studied which configurations of linear cellular automata like these have predecessors, and the press-matrix language and the automaton language are two descriptions of one computation over the two-element field.

The correspondence also explains why linearity makes the question decidable at all. For a general automaton, deciding whether a configuration has a predecessor means searching; for a linear one it is the rank computation of a grid of bits whose rank stops at the state, done once for the whole matrix. The difference between rule 90 and rule 150, which is the difference between the two games, is one entry on each row of that matrix, and it is the entry that decides whether every pattern can be built.

Every network, by parity #

For a general network the question has no rule of this kind, but the share of networks that can be lit can be measured exactly for small sizes and by sampling for larger ones.

There are $2^{21} = 2{,}097{,}152$ labelled networks on seven vertices, and 914,067 of them can be lit, a share of $0.436$. On six vertices the share is $18{,}259$ out of $32{,}768$, or $0.557$. On five it is $0.425$, on four $0.547$. The shares alternate, and random networks up to forty vertices keep alternating: about $0.56$ on even sizes and about $0.44$ on odd ones, with no sign of converging to a common value.

The parity of the number of lights never stops mattering. That is unusual. Most properties of large random networks depend smoothly on their size, and the networks here have no structure that cares whether they have twenty or twenty-one vertices. The cause is in the algebra rather than the networks.

Alternating matrices have even rank #

The cause is a classical fact about alternating matrices: over any field, an alternating matrix has even rank. Such a matrix describes a form that pairs coordinates, and a pairing of a space can only be nondegenerate on a space of even dimension. A symmetric matrix with nought on its diagonal over the two-element field is alternating, so its rank is even.

On twenty vertices the rank can be twenty, and it is in 42% of random networks; then $A$ is invertible, every pattern of lights can be reached, and all on in particular. On twenty-one vertices the rank can be at most twenty. The matrix is never invertible, the kernel always contains a nonzero silent set, and all on is reachable only when every silent set happens to be even. The figure confirms that no rank is ever odd in 6,000 random networks.

The difference between 0.56 and 0.44 is exactly this. An even network can be lit either because its matrix is invertible or because its silent sets are all even. An odd network has only the second way. The original Lights Out has no such effect, because the identity added to the adjacency matrix destroys the alternating property. Its matrices can have any rank, and Sutner’s argument shows that all on is reachable regardless.

What the computation cannot establish #

The board rule is checked on 3,600 boards and stated as a rule; the polynomial argument sketched above is how it would be proved, and the essay does not carry that proof through. The network shares beyond seven vertices are sampled, with a few per cent of sampling error at each size, and their limits are not computed. Whether the even and odd shares converge to definite constants, and what those constants are, is a question about random alternating matrices that the figures only estimate.

Nor do the figures say anything about the number of presses needed. When all on is reachable, the press patterns that reach it form a translate of the kernel. The smallest one is an odd open dominating set of the network — every light having an odd number of pressed neighbours — and finding the smallest is computationally hard in general, as the corresponding problem for the original rules is.

Still open: which networks can be lit #

For the original rules there is nothing to ask. Sutner’s theorem answers every network at once. For the neighbours-only rules there is no comparable criterion. The question is equivalent to asking whether a network has an odd open dominating set, a set of vertices such that every vertex has an odd number of neighbours in it. The answer is known for grids, paths, cycles, trees, and several other families, each by its own argument. A characterisation in terms of simple properties of the network, of the kind that makes the original game trivial, is not known and may not exist.

The probabilistic version is open too. For random networks the chance of being litable is close to $0.56$ on even sizes and $0.44$ on odd ones, and these numbers should be computable from the theory of random matrices over finite fields, in which the distribution of the rank of a random alternating matrix is known exactly. What that theory does not directly give is the chance that the all-ones vector lies in the column space. That vector is not random, and how it sits relative to the kernel is not captured by the rank alone. A clean formula for the limiting shares would need to describe that position, and none is known.

A rule hidden in the diagonal #

One change to the rules — a press no longer toggles its own light — removes the identity from the press matrix, and with it the parity argument that made every board solvable. What replaces it is a rule for grids stated by powers of two: an $n \times m$ board fails exactly when $n + 1$ and $m + 1$ are both even and divisible by the same power of two. For networks it is a permanent split between even and odd sizes, inherited from the even rank of alternating matrices.

Whenever all on cannot be reached there is a short proof that it cannot, a silent set of odd size. The five lights on the five-by-five board are one such proof: a count that anyone can check, and that no sequence of presses can get around.