## Formulating Lights Out as a system of equations

Consider the following configuration coming from a $$3\times 3$$ version of Lights Out.

We saw how we could play the game mathematically by first representing the configuration as a $$9$$-tuple, namely $$\begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}$$, and the action of pressing the squares as $$9$$-tuples as shown in the following table $\begin{array}{|c|cccccccccc|} \hline \text{Square} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline \text{Tuple} & \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} & \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} & \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} & \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} & \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} & \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} & \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} & \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \end{bmatrix} \\\hline \end{array}$ and then find a set of $$9$$-tuples from the table whose sum is identical to the $$9$$-tuple representing the configuration. We can formulate this question as a tuple equation: $x_1\begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} + x_2\begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} + x_3\begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + x_4\begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} + x_5\begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} + x_6\begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} + x_7\begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix} + x_8\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} + x_9\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix}$ where each $$x_i$$ is $$0$$ or $$1$$ with $$1$$ meaning that the corresponding square is chosen to be pressed.

Performing all the scalar multiplications and tuple additions gives $\begin{bmatrix} x_1 + x_2 + x_4 \\ x_1 + x_2 + x_3 + x_5 \\ x_2 + x_3 + x_6 \\ x_1 + x_4 + x_5 + x_7 \\ x_2 + x_4 + x_5 + x_6 + x_8 \\ x_3 + x_5 + x_6 + x_9 \\ x_4 + x_7 + x_8 \\ x_5 + x_7 + x_8 + x_9 \\ x_6 + x_8 + x_9 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix},$ or equivalently, the system of equations \begin{eqnarray} x_1 + x_2 + x_4 = 0, \\ x_1 + x_2 + x_3 + x_5 = 0, \\ x_2 + x_3 + x_6 = 1, \\ x_1 + x_4 + x_5 + x_7 = 1, \\ x_2 + x_4 + x_5 + x_6 + x_8 = 0, \\ x_3 + x_5 + x_6 + x_9 = 1, \\ x_4 + x_7 + x_8 = 0, \\ x_5 + x_7 + x_8 + x_9 = 1, \\ x_6 + x_8 + x_9 = 0. \end{eqnarray}

All we need to do is to find appropriate values for $$x_1,\ldots,x_9$$ to satisfy all these equations. Note that the only permissible values are $$0$$ and $$1$$ and under the rule “$$1+1=0$$”. However, the task does not seem easy, even though it is for a $$3\times 3$$ board. Imagine what it will be like for the original $$5 \times 5$$ board. Hence, we will have to study methods for solving such a system. Until then, can you find a solution?