§27

Lights Out — Linear algebra over GF(2)

The 1995 Tiger Electronics toy Lights Out: a 5×5 grid of buttons; pressing one toggles itself and its four orthogonal neighbours. Reach all-off from a given lit pattern. Behind this children's puzzle is one of the cleanest examples of linear algebra over $F_{2}$ : a pattern p is a vector in $F_{2}^{25}$ , each button is a fixed "press vector" $A_{i} \in F_{2}^{25}$ , and since presses commute and self-cancel mod 2, "which buttons to press" is itself a vector $x \in F_{2}^{25}$ solving

A x = p over F_{2},

where A is the symmetric 25 × 25 binary matrix with $A_{ij} = 1$ iff pressing button i toggles light j. In row-major coordinates, A is block tridiagonal:

A_{m \times n} = B_{n} I_{n} I_{n} B_{n} I_{n} I_{n} B_{n} ⋱ ⋱ ⋱, B_{n} = I_{n} + T_{n},

where $T_{n}$ is the n × n off-diagonal "adjacency" tridiagonal matrix. View A as a graph operator: it is the reflexive adjacency matrix of the m × n grid graph (a vertex plus its neighbours). All of §27 chases one question — what does this matrix's kernel look like over $F_{2}$ , because

dim ker A = m \cdot n - rank A = lo g_{2} \frac{∣ F _{2}^{mn} ∣}{∣ im A ∣}

completely determines both how many patterns are solvable ( $2^{rank A} = 2^{mn - d i m k e r A}$ ) and how many solutions each solvable pattern has (exactly $2^{d i m k e r A}$ ).

27.1 Interactive: 3 × 3 and 5 × 5 solvers

The 3 × 3 board's A is full rank — every pattern is solvable in at most 9 presses. The 5 × 5 board has $rank A = 23, dim ker A = 2$ : exactly $2^{23} = 8388608$ patterns are solvable (a quarter of all $2^{25}$ ), each in $2^{2} = 4$ distinct ways. Both boards below run Gaussian elimination and then pick the minimum-Hamming-weight coset representative. Diameter = 15 on 5 × 5.

3 × 3

full rank · every pattern solvable · diameter 9

lit

0 / 9

solvable

yes

min moves

# solutions

quiet patterns

5 × 5

rank 23 · 2 quiet patterns · 4 solutions per solvable · diameter 15

lit

0 / 25

solvable

yes

min moves

# solutions

quiet patterns

27.2 Quiet patterns

The 5 × 5 kernel has basis $Q_{1}, Q_{2} \in ker A$ . Geometric meaning: pressing exactly the marked buttons restores the all-off board. Adding any quiet pattern to a solution yields another valid solution — that is where the "4 solutions" come from. They also give the solvability test:

p solvable ⟺ p \cdot Q_{1} \equiv 0 (mod 2) and p \cdot Q_{2} \equiv 0 (mod 2) .

(Proof: A is symmetric, hence $im A = (ker A)^{⊥}$ — the standard finite-dimensional fact, which still holds over $F_{2}$ .) Toggle cells and watch the two dot products update. A pattern is solvable iff it is orthogonal to both $Q_{1}$ and $Q_{2}$ .

orthogonality test

your pattern p

Q₁ · p·Q₁ = 0

Q₂ · p·Q₂ = 0

verdict

solvable — orthogonal to both quiet patterns

Observation 27.1 — geometry of quiet

Q_{1}

is the four-corner-block pattern,

Q_{2}

is the four-quadrant-block pattern. Both have D₄ symmetry (the 8-element dihedral group) — no coincidence. The 5 × 5 grid itself is D₄-symmetric, so A decomposes under the D₄ representation, and ker A must sit in some isotypic component. Only two non-trivial D₄-invariant solutions to

A x = 0

exist on 5 × 5, namely

Q_{1}, Q_{2}

. This is "representation-theoretic subspace decomposition" giving a hard constraint.

27.3 Gaussian elimination — stepping through 3 × 3

The abstract sentence "A is full rank ⇒ solvable" does not tell you how to solve. Real solvers run row reduction over $F_{2}$ : starting from $[A ∣ b]$ , swap rows and add rows (XOR over $F_{2}$ ) until reaching $[I ∣ x]$ . Each step: in column c, find a non-zero entry at or below row r and swap it up as pivot; then XOR-clear every other row's c-column. After 9 pivots, b has been transformed into the solution x.

3 × 3 Gaussian elimination, step by step

augmented matrix [A | b] — 9 cols of A + 1 col of b · pivot row and eliminating rows highlighted

step 0 / 9pivot r0, c0 · clearing 2 rows

110100000|0

111010000|1

011001000|1

100110100|1

010111010|1

001011001|0

000100110|1

000010111|1

000001011|0

The whole process costs $O ((mn)^{3})$ bit operations — on 25 × 25 that is about $\sim 2 5^{3} = 15625$ XORs, microseconds on a modern CPU. This contrasts sharply with the cube: the cube group is non-Abelian and optimal solving is NP-hard (§16); Lights Out, being Abelian, sits comfortably in P.

27.4 The light-chasing heuristic

Every Lights Out player learns to chase the lights: hold the top row, then scan downward — if (r−1, c) is still lit, press (r, c) to kill it. This is one-pass forward elimination; it always clears every row above. But the bottom row's residual need not be zero — it depends on the top-row "kick". The top row has 32 possible kicks; on 5 × 5, exactly 4 of them (because dim ker = 2 and the bottom-row residual must land in the projection of ker onto the bottom row) let the chase finish. Two passes — "chase + correct top row + chase again" — solves any solvable pattern in ≤ 15 moves.

light-chasing animator (5 × 5)

click "start chase" to run forward elimination; non-zero bottom row means you must restart with a different top-row kick (4 valid choices)

pressed: 0

still lit: 12

Top row stays. Sweep downward: if cell (r−1, c) is lit, press (r, c). That always clears row r.

Chase-the-lights is essentially block upper-triangulation: write A using the first m − 1 rows as $(U 0 * S)$ where S is the Schur complement. The space of admissible top-row kicks is exactly $ker S$ . On a 5 × n board, S is 5 × 5 and its kernel dimension equals dim ker A (so dim = 2 when n = 5). That is the algebraic reason "4 of the 32 top rows work".

27.5 The 1 × n line, and the n-cycle

Reduce Lights Out to a 1 × n line. Now A is the n × n reflexive tridiagonal-symmetric matrix $A = I + T_{n}$ . Its characteristic polynomial obeys a Chebyshev-style recurrence — Sutner's key observation:

c_{n} (x) = x c_{n - 1} (x) - c_{n - 2} (x), c_{0} = 1, c_{1} = x .

Over $F_{2}$ , $c_{n} (x)$ reduces to the Fibonacci polynomial mod 2. Consequence: $dim ker A_{1 \times n} = 1$ if $n \equiv 2 (mod 3)$ , else 0. Concretely:

n = 2: quiet pattern (1, 1) — pressing both buttons restores all-off. Half of patterns unsolvable.
n = 5: quiet pattern (1, 1, 0, 1, 1). Half unsolvable.
n = 8: quiet pattern (1, 1, 0, 1, 1, 0, 1, 1). Period-3 rhythm visible.
n = 3, 4, 6, 7, 9, …: every pattern solvable.

slide n · highlight quiet pattern

n = 7

kernel dim ker A = 0 · n ≢ 2 (mod 3): every pattern solvable

Now close the line into a ring (index mod n addition) — the σ⁺ game on the cycle $C_{n}$ . The matrix A becomes cyclic-symmetric (an n × n circulant). Diagonalising over its discrete Fourier basis, one proves over $F_{2}$ :

dim ker A_{C_{n}} = {20 n \equiv 0 (mod 3) otherwise .

Contrast: the line needs n ≡ 2 (mod 3) for a non-trivial kernel; the cycle needs n ≡ 0 (mod 3) and gives dimension 2 (not 1). Same local rule, different topology, completely different kernel. The cleanest small example of "boundary conditions change the global solution space".

27.6 Sutner's recurrence + gcd kernel formula

For a general m × n board, the kernel dimension has a strikingly elegant algebraic formula — due to Sutner (1989) and crystallised by Anderson & Feil (1998). With $c_{n} (x)$ from §27.5:

Theorem 27.2 (Sutner 1989)

For the m × n Lights Out grid,

dim ker A_{m \times n} = de g g cd (c_{m} (x), c_{n} (- x - 1))

over

F_{2}

, where

c_{k}

satisfies

c_{k} (x) = x c_{k - 1} (x) - c_{k - 2} (x)

with

c_{0} = 1, c_{1} = x

Key observation: A is the Kronecker sum $I_{m} \otimes (I_{n} + T_{n}) + T_{m} \otimes I_{n}$ . For each eigenvalue λ of $T_{n}$ over $F_{2}$ , A restricts on that eigenblock to $(I_{m} + T_{m}) + λ I_{m} = λ I_{m} + B_{m}$ , which is $B_{m}$ evaluated at x = λ + 1 (≡ −λ − 1 over $F_{2}$ ). So A is singular iff some λ satisfies $c_{n} (λ) = 0$ and $c_{m} (- λ - 1) = 0$ — i.e. the two polynomials share a root — i.e. their gcd has positive degree.

Compute dim ker for m, n = 1..8 (the table below runs gf2Reduce live in your browser) — a "gold-band" pattern appears: roughly one-third of sizes carry a non-trivial kernel.

dim ker A_{m×n} table — computed live in your browser

dim ker A_m×n — the dimension of the "quiet pattern" subspace. Gold = non-trivial kernel ⇒ that board has unreachable patterns. 5×5 is gold (dim = 2), exactly the smallest non-trivial size — which is why Tiger chose it.

	1	2	3	4	5	6	7	8
1	0	1	0	0	1	0	0	1
2	1	0	2	0	1	0	2	0
3	0	2	0	0	3	0	0	2
4	0	0	0	4	0	0	0	0
5	1	1	3	0	2	0	4	1
6	0	0	0	0	0	0	0	6
7	0	2	0	0	4	0	0	2
8	1	0	2	0	1	6	2	0

Hover any cell for details.

5 × 5 has dim = 2 (Tiger's commercial choice was not coincidental — too small means no kernel, no "unreachable patterns", no flavour; too large and fingers can't keep up. 5 × 5 hits the sweet spot.). The 4 × 4 board is full rank over

F_{2}

(dim = 0) — mini-Lights Out has no quiet patterns. 6 × 6 is full rank too. 7 × 7 has dim = 0, but 9 × 9 has dim = 8 — a striking jump.

27.7 σ-game — graph-theoretic generalisation

Sutner's 1989 paper introduced the σ-game on an arbitrary simple graph G = (V, E). Vertices are lights. Pressing vertex v:

σ-game: toggles the neighbours of v (excluding v itself). Operator = A(G), the adjacency matrix.
σ⁺-game: toggles v and all neighbours (reflexive). Operator = A(G) + I — the "closed neighbourhood" matrix. This is Lights Out.

Sutner's signature theorem — an "every graph can be all-lit" miracle:

Theorem 27.3 (Sutner 1989 — universal σ⁺ solvability)

For every finite simple graph G, the σ⁺-game's "all-lit" target

1 = (1, 1, \dots, 1)

is solvable — there exists

x \in F_{2}^{∣ V ∣}

with

(A (G) + I) x = 1

Proof sketch: A + I is symmetric over $F_{2}$ , so $im (A + I) = (ker (A + I))^{⊥}$ . Key lemma: every kernel vector v ∈ ker(A + I) has even Hamming weight — its support is an "odd closed-neighbourhood subset" of G, and the handshake lemma forces it to be even. Therefore $v \cdot 1 = ∣ v ∣_{1} \equiv 0 (mod 2)$ , so $1 ⊥ ker (A + I)$ , so $1 \in im (A + I)$ . QED. A delicious example of a combinatorial lemma getting algebraised.

Here are 5 small graphs. P₅ is a path, C₅ a 5-cycle, K₄ and K₅ complete, Petersen the famous 10-vertex 3-regular graph. Click "show all-ones solution" to see the press set Sutner's theorem guarantees (green ring).

σ⁺ game · 5 preset small graphs

click vertex = press button · live lit-state · or auto-show the Sutner solution

lit0 / 5

pressed0

dim ker A1

all-ones reachableyes

Note Petersen has dim ker = 0 in σ⁺ (full rank), so its all-ones solution is unique. K₅'s A + I is the all-ones 5 × 5 matrix, rank 1 over $F_{2}$ with nullity 4 — the all-ones target has $2^{4} = 16$ different solutions (pressing any 1, 3, or 5 of the vertices works).

27.8 Variants — different topologies, different alphabets

Tiger and others have re-issued Lights Out many times; each variant is "swap (G, k)" — change graph G or coefficient ring $F_{k}$ . The well-studied ones:

variant	graph G	ring	state space	dim ker
Lights Out (1995)	5 × 5 grid	$F_{2}$	2²³ = 8.4 M	2
Mini Lights Out	4 × 4 torus	$F_{2}$	2¹⁶ = 65 K	0
Lights Out 2000	5 × 5 grid	$F_{3}$	3²² ≈ 31 G	3
Lights Out Cube	3 × 3 × 3 surface (54 lights)	$F_{2}$	2⁴⁸ ≈ 281 T	6
Lights Out Deluxe	6 × 6 grid + diag neighbours	$F_{2}$	2³⁶ ≈ 69 G	0
XL-25 (1983, Vulcan)	5 × 5 grid (earliest commercial)	$F_{2}$	2²³	2
hex Lights Out	hexagonal honeycomb	$F_{2}$	size-dependent	varies

The Cube variant's dim ker = 6 stems from the 3 × 3 × 3 surface graph's symmetry: the 24 outer cube rotations give 6 independent "face-symmetric" quiet patterns. The 24-rotation group is the same as the cube symmetries from §14 — but acting on a different algebraic object (adjacency vs permutation), the outcome is completely different.

Lights Out 2000 moves to mod 3: lights cycle through grey / green / red on each press. The same matrix $A_{5 \times 5}$ now lives over $F_{3}$ . Its kernel dimension jumps to 3 — the extra "mod 3 quiet patterns" are invisible from the $F_{2}$ viewpoint. General fact: $dim_{F_{p}} ker A$ depends on p; the integer determinant $det A$ tells you exactly which primes make A singular. On 5 × 5, $det A = 0$ over $Z$ , and the Smith normal form shows the elementary divisors contribute singular behaviour at both mod 2 and mod 3.

27.9 Bridge to coding theory

Lights Out is literally a linear coding problem over $F_{2}$ . Think of "button configuration" as plaintext $x \in F_{2}^{25}$ and "lit pattern" as codeword $y = A x \in F_{2}^{25}$ , then:

Encoding matrix = A · code length 25 · message length 23 ( = rank A) · 2 parity bits ( = dim ker A).
"Solvable iff p ⊥ ker A" is classic syndrome decoding: use a basis of ker A as a parity-check matrix H, test $H p = 0$ .
"Minimum-length solve" = minimum-Hamming-weight coset representative = "nearest codeword" — NP-hard in general (Berlekamp–McEliece–Tilborg 1978), but the 25 × 25 instance is small enough to enumerate the 4 cosets of ker A.

This links the toy puzzle to LDPC / coding theory. Conversely, any solvable $F_{2}$ -linear system can be re-cast as some Lights Out instance.

27.10 Complexity — why Lights Out ≪ Rubik's cube

Three facts make Lights Out "easy":

Abelian: press order is irrelevant ( $A_{i} + A_{j} = A_{j} + A_{i}$ ). The state space is the group $F_{2}^{mn}$ , and solving = "find a representative" — linear algebra suffices.
Linear: the operator $x \mapsto A x$ is linear, so superposition works — decompose any target into a basis.
Involutive: each button squares to identity, so $x \in F_{2}^{mn}$ instead of $Z^{mn}$ . Restricting to "press at most once" is free.

Consequence: on an N = mn-cell Lights Out board, is it solvable? and what is a shortest solve? are both in $O (N^{3})$ time, or $O (N^{ω})$ with $ω \approx 2.37$ (fastest known matrix multiplication). Contrast: optimal-solving the n × n × n Rubik's cube is NP-complete (Demaine et al. 2018). Drop any of the three properties above (press order matters → non-Abelian; or 4-state lights with non-linear rule), and Lights Out lands in NP-hard immediately.

"Abelian toys yield to linear algebra; non-Abelian toys yield NP-hardness proofs. Lights Out and Rubik's cube sit on opposite sides of this watershed."

27.11 Historical note

The earliest commercial release was XL-25 (Vulcan Electronics 1983), invented by Hungarian László Mérő — 5 × 5 with both standard and knight's-move rules. Merlin (1978) had used a 3 × 3 with a different rule. Tiger Electronics released Lights Out in 1995 and made it a household toy; Lights Out 2000 (1997) / Cube / Deluxe followed. On the math side: Sutner (1989) introduced the σ-game framework with the recurrence and gcd formula — the foundational paper; Anderson & Feil (1998), "Turning Lights Out with Linear Algebra" in Mathematics Magazine, made it an undergraduate-textbook standard; Goldwasser, Klostermeyer, Trapp (1995–1997) gave the domino/monomino tiling characterisation. A specimen of "one toy puzzle, half a century of academic work".

Side by side with the cube: both emerged into popular culture around 1980 from Hungary / the US, both are symmetric, reversible, group-theoretic discrete systems. The single difference is Abelian vs non-Abelian — and that single bit determines whether linear algebra suffices, planting the two puzzles in different complexity classes (P vs NP-hard). Because Lights Out is in P, it lectures cleanly in elementary olympiad and undergrad linear algebra; the cube cannot, because the algorithms it needs are too special-purpose.

∎

cuberoot.me · Rubik's Cube as a Group · 2026

	1	2	3	4	5	6	7	8
1	0	1	0	0	1	0	0	1
2	1	0	2	0	1	0	2	0
3	0	2	0	0	3	0	0	2
4	0	0	0	4	0	0	0	0
5	1	1	3	0	2	0	4	1
6	0	0	0	0	0	0	0	6
7	0	2	0	0	4	0	0	2
8	1	0	2	0	1	6	2	0

	1	2	3	4	5	6	7	8
1	0	1	0	0	1	0	0	1
2	1	0	2	0	1	0	2	0
3	0	2	0	0	3	0	0	2
4	0	0	0	4	0	0	0	0
5	1	1	3	0	2	0	4	1
6	0	0	0	0	0	0	0	6
7	0	2	0	0	4	0	0	2
8	1	0	2	0	1	6	2	0

	1	2	3	4	5	6	7	8
1	0	1	0	0	1	0	0	1
2	1	0	2	0	1	0	2	0
3	0	2	0	0	3	0	0	2
4	0	0	0	4	0	0	0	0
5	1	1	3	0	2	0	4	1
6	0	0	0	0	0	0	0	6
7	0	2	0	0	4	0	0	2
8	1	0	2	0	1	6	2	0