Solving Lights Out Using Linear Algebra

Lights Out is an electronic single-player puzzle released by Tiger Electronics in 1995. It presents a 5×5 grid of lights, each either on or off, sitting behind a button. Pressing a button flips that light and its up-to-four orthogonal neighbors - the lights directly above, below, left and right of it, together forming a plus shape. Starting from some scrambled pattern, the goal is to press buttons until every light is off. With \(2^{25}\) possible board states, trying combinations by hand is not an option. What follows is the linear-algebra shortcut that finds the shortest solution directly, or proves that none exists.

A related question is the "all-ones problem": can every square lattice be solved starting from all lights turned on? Sutner showed that the answer is always yes, regardless of the board size. Minevich's theorem for symmetric matrices over \(\mathbb{Z}_2\), proved below, explains why this is true not only for square lattices but for every finite undirected Lights Out graph in which pressing a vertex also toggles that vertex.

Modeling the Board as a Matrix over GF(2)

Pressing the same button twice returns every light it touches to its previous state, so only the parity of how often each button gets pressed matters - zero or one time, nothing else. That is exactly arithmetic modulo 2, so a board configuration is naturally a matrix \(\mathcal{C}\in\mathbb{Z}_2^{n\times m}\), with a \(1\) for a lit cell and a \(0\) for a dark one. For a smaller \(3\times 3\) lattice, a configuration might look like this:

\[\mathcal{C} = \left(\begin{array}{ccc} 1 & 0 & 1\\ 0 & 0 & 1\\ 1 & 1 & 0\\ \end{array} \right)\]

A board state like this is nothing more than a 9-bit vector in disguise; if you need a compact bit-vector type for states like this outside of a puzzle, BitSet.js implements one in JavaScript.

The Cross Pattern of a Single Button Press

Every button press can also be written as a matrix: a \(1\) at the pressed cell and at each orthogonal neighbor that exists, \(0\) everywhere else. Call this matrix \(\mathcal{A}_{i,j}\) for the button in row \(i\), column \(j\). Pressing it changes the board with addition in \(\mathbb{Z}_2\), so the new configuration is \(\mathcal{C}'=\mathcal{C}+\mathcal{A}_{i,j}\). Buttons on the edge or in a corner simply have fewer neighbors, so their cross has fewer arms. For the center button of the \(3\times 3\) board, the full plus shape appears:

\[\mathcal{A}_{22} = \left(\begin{array}{ccc} 0 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 0\\ \end{array} \right)\]

Every reachable configuration depends only on which buttons were pressed, never on the order - matrix addition is commutative. So if we start from an empty board, light up some cells at random, and then press exactly the same buttons again, the board returns to empty. That reversibility is the whole game compressed into one equation. A winning combination for a given \(\mathcal{C}\) satisfies:

\[\mathcal{C} + \sum\limits_{i, j}\beta_{i, j}\mathcal{A}_{i, j} = \mathbf{0}\]

where \(\mathbf{0}\) is a board with every light off, and each coefficient \(\beta_{i, j}\in\{0,1\}\) says whether button \((i, j)\) is part of the solution. Since we work modulo 2, \(-1\equiv 1\pmod 2\), so moving \(\mathcal{C}\) to the other side changes nothing about its sign:

\[\sum\limits_{i, j}\beta_{i, j}\mathcal{A}_{i, j} = \mathcal{C} \]

One Big Linear System

To turn this sum into ordinary matrix-vector notation, flatten every board-shaped matrix into a column vector - \(\mathcal{C}\) and \(\beta\) become vectors, and the collection of all \(n\times m\) possible cross patterns \(\mathcal{A}_{i,j}\) becomes a matrix \(\mathcal{A}\), one flattened cross pattern per column. Thus multiplying \(\mathcal{A}\) by \(\beta\) adds exactly the columns selected by the \(1\)s in \(\beta\):

\[\underbrace{\left(\begin{array}{cccccc}\operatorname{vec}(\mathcal{A}_{1,1}) & \operatorname{vec}(\mathcal{A}_{1,2}) & \cdots & \operatorname{vec}(\mathcal{A}_{1,m}) & \cdots & \operatorname{vec}(\mathcal{A}_{n,m})\end{array}\right)}_{\mathcal{A}} \cdot \underbrace{\left(\begin{array}{c}\beta_{1,1} \\ \beta_{1,2} \\ ... \\ \beta_{1,m} \\ ... \\ \beta_{n, m}\end{array}\right)}_{\beta} = \underbrace{\left(\begin{array}{c}\mathcal{C}_{1,1}\\ \mathcal{C}_{1,2}\\ ...\\ \mathcal{C}_{1,m}\\ ...\\ \mathcal{C}_{n, m}\end{array}\right)}_{\mathcal{C}}\]

\(\mathcal{A}\) is symmetric - pressing button \(k\) affects cell \(l\) exactly when pressing button \(l\) would affect cell \(k\), since "is an orthogonal neighbor of" is a mutual relationship - and has at most 5 ones in any row. For the \(3\times 3\) example, the resulting \(9\times 9\) matrix \(\mathcal{A}\) looks like this, where each column is one flattened cross pattern \(\mathcal{A}_{i,j}\). Symmetry makes the same statement true of its rows:

\[\mathcal{A}=\left(\begin{array}{ccccccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array}\right) \]

Why the All-Ones Board Is Always Solvable

A theorem due to Minevich states that the column space of every symmetric matrix over \(\mathbb{Z}_2\) contains its diagonal vector. Let \(A=(a_{ij})\) be symmetric and write

\[ \mathbf{d}:=(a_{11},a_{22},\ldots,a_{NN})^T. \]

For any \(\mathbf{x}\in\mathbb{Z}_2^N\), symmetry pairs every off-diagonal term in the quadratic form with an identical copy. The pair vanishes because \(2=0\) in \(\mathbb{Z}_2\), while \(x_i^2=x_i\). Therefore

\[ \begin{aligned} \mathbf{x}^T A\mathbf{x} &=\sum_i a_{ii}x_i^2 +\sum_{i<j}(a_{ij}+a_{ji})x_ix_j\\ &=\sum_i a_{ii}x_i =\mathbf{d}^T\mathbf{x}. \end{aligned} \]

If \(\mathbf{x}\in\operatorname{null}(A)\), then \(A\mathbf{x}=\mathbf{0}\), so the left side is zero and \(\mathbf{d}^T\mathbf{x}=0\). Thus \(\mathbf{d}\) is orthogonal to every vector in the null space. Using symmetry,

\[ \mathbf{d} \in\operatorname{null}(A)^\perp =\operatorname{col}(A^T) =\operatorname{col}(A). \]

This proves that some press pattern produces exactly the diagonal vector. In ordinary Lights Out every press toggles its own cell, so every diagonal entry is \(1\) and \(\mathbf{d}=\mathbf{1}\). The all-ones board is therefore reachable from the all-off board on every finite undirected graph, and pressing the same pattern again solves it. More generally, if only some vertices toggle themselves, the guaranteed reachable state has \(1\)s exactly at those vertices.

Solving the System

With the puzzle reduced to \(\mathcal{A}\beta = \mathcal{C}\), the fastest path to \(\beta\) is multiplying both sides by the inverse of \(\mathcal{A}\) - but only if \(\mathcal{A}\) has full rank. That happens to be true for some board sizes (\(2\times 2\), \(3\times 3\), \(6\times 6\), and \(7\times 7\), among others) and false for others, most notably the standard \(5\times 5\) board. Their corresponding matrices have dimensions \(4\times4\), \(9\times9\), \(36\times36\), and \(49\times49\), respectively, so a more general method is needed.

That method is Gauss-Jordan elimination, carried out entirely on the field \(\mathbb{Z}_2\) instead of the reals. Row-reducing \(\mathcal{A}\) to its reduced row echelon form \(\mathcal{E}=R\mathcal{A}\) - where \(R\) is the product of every row operation used - reveals the rank of \(\mathcal{A}\) directly from the number of pivot columns, which is exactly what decides whether the shortcut above works at all.

For the standard \(5\times5\) board, the \(25\times25\) matrix has rank 23, two short of full rank. Those missing two dimensions are not a defect to work around; they are the reason some boards cannot be solved and the reason a solvable board has more than one solution, both of which the next section makes precise.

In general, an \(N\times N\) Lights Out matrix of rank \(r\) has an image with \(2^r\) elements, so exactly \(2^r\) of the \(2^N\) board states are reachable. The rank-nullity theorem gives \(\dim\operatorname{null}(\mathcal{A})=N-r\), and every reachable state has exactly \(2^{N-r}\) press patterns: one particular solution plus every vector in the null space. For the standard board, \(N=25\) and \(r=23\). Consequently,

\[ \#\text{solvable boards}=2^{23}=\frac{1}{4}2^{25}, \qquad \#\text{solutions per solvable board}=2^{25-23}=4. \]

When Is a Configuration Solvable at All?

A configuration \(\mathcal{C}\) is winnable exactly when \(\mathcal{A}\beta=\mathcal{C}\) has some solution \(\beta\), which by definition means \(\mathcal{C}\) lies in the column space \(\text{col}(\mathcal{A})\) - the set of boards that some combination of button presses can actually reach. When \(\mathcal{A}\) has full rank, that space is everything and every board is winnable. When it does not, as for the \(5\times 5\) board, \(\text{col}(\mathcal{A})\) is a strict subspace, and most random boards fall outside of it.

Testing membership in a column space directly is awkward, but symmetry turns it into something easy to check. Because the columns of \(\mathcal{A}\) are the rows of \(\mathcal{A}^T\), the column space of any matrix always equals the row space of its transpose: \(\text{col}(\mathcal{A})=\text{row}(\mathcal{A}^T)\). Since \(\mathcal{A}=\mathcal{A}^T\) here, this collapses to \(\text{col}(\mathcal{A})=\text{row}(\mathcal{A})\) - no eigenvectors needed, just the definition of "symmetric".

The row space, in turn, is always the orthogonal complement of the null space: each row of \(\mathcal{A}\) defines a linear functional \(x\mapsto \text{row}_i\cdot x\), and the null space is precisely where every one of those functionals vanishes at once, which is the definition of being orthogonal to all of them. Row operations do not change what a matrix's null space is, so \(\text{null}(\mathcal{A})=\text{null}(\mathcal{E})\) as well. Chaining these three facts together:

\[\mathcal{C}\text{ is winnable} \iff \mathcal{C}\in\text{col}(\mathcal{A}) \iff \mathcal{C}\in\text{row}(\mathcal{A}) \iff \mathcal{C}\perp\text{null}(\mathcal{E})\]

So the whole winnability question reduces to finding a basis for \(\text{null}(\mathcal{E})\) and checking whether \(\mathcal{C}\) is orthogonal to every vector in it.

Quiet Patterns on the Standard 5×5 Board

A vector in \(\text{null}(\mathcal{A})\) is a set of button presses that changes nothing at all - a "quiet pattern". Solving \(\mathcal{E}x=\mathbf{0}\) for the \(25\times 25\) board leaves exactly two free variables, so the null space is spanned by two such quiet patterns, found by setting one free variable to \(1\) and the other to \(0\) in turn:

Press every lit button in \(\mathbf{v}_1\) or in \(\mathbf{v}_2\) on an already-off board, and the board stays off - every cell gets toggled an even number of times by construction. As flattened 25-entry vectors:

\[\mathbf{v}_1 = (0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0)^T\]

\[\mathbf{v}_2 = (1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1)^T\]

Their dot product, computed modulo 2, is \(\mathbf{v}_1\cdot\mathbf{v}_2=0\), confirming they really are orthogonal to each other and independent - a genuine 2-dimensional basis for \(\text{null}(\mathcal{E})\). Given an arbitrary \(5\times 5\) configuration \(\mathcal{C}\), the winnability test from the previous section becomes concrete: compute \(\mathcal{C}\cdot\mathbf{v}_1\) and \(\mathcal{C}\cdot\mathbf{v}_2\) modulo 2, and the board is solvable exactly when both dot products are zero. And whenever \(\mathcal{C}\) is winnable with some strategy \(\beta\), the three combinations \(\beta+\mathbf{v}_1\), \(\beta+\mathbf{v}_2\) and \(\beta+\mathbf{v}_1+\mathbf{v}_2\) are also valid strategies - pressing a quiet pattern on top changes which buttons get pressed, but not the final board.

Picking the Optimal Solution

A winnable \(5\times 5\) board therefore has exactly four solutions, not one. Finding one of them is straightforward: set the two free variables \(\beta_{24}\) and \(\beta_{25}\) to zero, and the reduced system gives the remaining pivot variables directly, \(\beta^{(0)}=R\mathcal{C}\). The other three follow by adding the quiet patterns:

\[ \begin{array}{rl} \beta^{(0)}&=R\mathcal{C}\\ \beta^{(1)}&=R\mathcal{C}+\mathbf{v}_1\\ \beta^{(2)}&=R\mathcal{C}+\mathbf{v}_2\\ \beta^{(3)}&=R\mathcal{C}+\mathbf{v}_1+\mathbf{v}_2 \end{array}\]

Since the number of button presses in a strategy is just how many \(1\)s it contains, the optimal - fewest-move - solution is whichever of the four has the smallest \(\ell_1\) norm, equal here to the Hamming distance to the zero vector:

\[\beta = \operatorname*{arg\,min}_{k\in\{0,1,2,3\}}\left\lVert\beta^{(k)}\right\rVert_1\]

Row Chasing as a Practical Solver

Gauss-Jordan elimination explains the entire solution space, but the local shape of a move also gives a compact implementation known as row chasing. Once the presses in the first row have been chosen, every later row is forced: after row \(j\) has been processed, a light still on in row \(j\) can only be cleared by pressing the cell directly below it in row \(j+1\). Repeating this step pushes all remaining information into the final row.

An \(n\times m\) board therefore needs only the \(2^m\) possible first-row press patterns to be tested. Chase each candidate downward, reject it if the last row remains lit, and compare the Hamming weights of the surviving press patterns. This produces a minimum-press solution without searching all \(2^{nm}\) strategies. Algebraically, the first-row choices parameterize a much smaller set of candidates; the chase merely performs the corresponding elimination in board order.

Worked Example: Solving a 3×3 Board

The \(3\times 3\) board is small enough to see the whole process land on a concrete answer. Its \(9\times 9\) matrix \(\mathcal{A}\) from earlier has full rank, so there is no quiet pattern to worry about and exactly one solution: solving \(\mathcal{A}\beta=\mathcal{C}\) for the configuration \(\mathcal{C}\) introduced at the top of this article gives \(\beta_1=\beta_3=\beta_7=1\) and every other \(\beta_{i,j}=0\) - press only the top-left, top-right and bottom-left corners:

Three presses total, matching \(\lVert\beta\rVert_1=3\) - and since this board's \(\mathcal{A}\) has full rank, there is no alternative solution to compare it against; it is optimal by default.

Try It Yourself

The interactive board at the top of this page generates a random solvable puzzle of any size from \(3\times 3\) to \(7\times 7\), running exactly the elimination described above in the background before the board is even shown, so every puzzle is guaranteed solvable. Click cells to press them, drag the slider to change the board size, and press space (or double-tap on mobile) to reveal one hint at a time if you get stuck.

References

• [AndersonFeil1998]M. Anderson and T. Feil, "Turning Lights Out with Linear Algebra," Mathematics Magazine, vol. 71, no. 4, pp. 300–303, 1998.
• [Minevich2012]I. Minevich, "Symmetric Matrices over \(F_2\) and the Lights Out Problem," arXiv:1206.2973, 2012.
• [Sutner1988]K. Sutner, "Additive Automata on Graphs," Complex Systems, vol. 2, no. 6, pp. 649–661, 1988.

Cite This Research

@misc{Eisele_2018_LightsOut,
  author={Eisele, Robert},
  title={Solving Lights Out Using Linear Algebra over GF(2)},
  year={2018},
  month={July},
  publisher={raw.org},
  url={https://raw.org/research/solving-lightsout-using-linear-algebra/},
  urldate={2026-08-09}
}