Solving the \(3 \times 3\) version of Lights Out amounts to solving the system \(Ax=b\) over \(GF(2)\) where \(A = \begin{bmatrix} 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{bmatrix}\) and \(b = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \\ b_8 \\ b_9 \end{bmatrix}\).
Recall that column \(i\) of \(A\) represents the action of pressing square \(i\); the entries in the column equal to 1 correspond to the squares that are toggled when square \(i\) is pressed.
The tuple \(b\) represents the configuration of lights. Hence, \(b_i = 1\) if and only if the light at square \(i\) is on.
The variable \(x_i\) corresponds to square \(i\) and is set to 0 or 1. It is set to 1 if and only if the corresponding square needs to be pressed in a solution of the game.
We now solve the system using row reduction. The following table shows the entire process. Separating lines have been added to the matrices to aid reading.
\begin{align*} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & b_2 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & b_3 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_4 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & b_5 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{R_2 \leftarrow R_2 + R_1} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & b_1+b_2 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & b_3 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_4 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & b_5 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{R_1 \leftarrow R_1 + R_4} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & b_1+b_4 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & b_1+b_2 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & b_3 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_4 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & b_5 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_3 \leftarrow R_3 + R_1 \\ R_5 \leftarrow R_5 + R_1 \end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & b_1+b_4 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & b_1+b_2 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & b_1+b_3+b_4 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_4 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & b_1+b_4+b_5 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_2 \leftarrow R_2 + R_3\\ R_6 \leftarrow R_6 + R_3 \end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & b_1+b_4 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & b_2+b_3+b_4 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & b_1+b_3+b_4 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & b_4 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & b_1+b_4+b_5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_2 \leftarrow R_2 + R_7 \\ R_4 \leftarrow R_4 + R_7 \\ R_5 \leftarrow R_5 + R_7\end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & b_1+b_4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & b_2+b_3+b_4+b_7 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & b_1+b_3+b_4 \\ \hline 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & b_4+b_7 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_1 \leftarrow R_1 + R_8 \\ R_3 \leftarrow R_3 + R_8 \\ R_4 \leftarrow R_4 + R_8\end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & b_2+b_3+b_4+b_7 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & b_1+b_3+b_4+b_8 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_4+b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c} R_2 \leftarrow R_2 + R_5 \\ R_3 \leftarrow R_3 + R_5 \\ R_9 \leftarrow R_9 + R_5\end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_1+b_2+b_3+b_5 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & b_3+b_5+b_7+b_8 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_4+b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_5+b_7+b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c} R_4 \leftarrow R_4 + R_6\\ R_7 \leftarrow R_7 + R_6\\ R_8 \leftarrow R_8 + R_6\end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_1+b_2+b_3+b_5 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & b_3+b_5+b_7+b_8 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_6++b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & b_1+b_3+b_4+b_6+b_7 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & b_1+b_3+b_4+b_6+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_5+b_7+b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_1 \leftarrow R_1 + R_9 \\ R_3 \leftarrow R_3 + R_9 \\ R_7 \leftarrow R_7 + R_9\end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_5+b_7+b_8+b_9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_1+b_2+b_3+b_5 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_4+b_8+b_9 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_6++b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_3+b_5+b_6+b_9 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & b_1+b_3+b_4+b_6+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & b_1+b_4+b_5+b_7+b_9 \end{array}\right] \\ \xrightarrow{ \scriptsize\begin{array}{c}R_8 \leftarrow R_8 + R_2 \\ R_9 \leftarrow R_9 + R_2 \end{array}} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_5+b_7+b_8+b_9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_1+b_2+b_3+b_5 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_4+b_8+b_9 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_6++b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_1+b_3+b_4+b_6 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_3+b_5+b_6+b_9 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & b_2+b_4+b_5+b_6+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & b_2+b_3+b_4+b_7+b_9 \end{array}\right] \\ \xrightarrow{R_6 \leftarrow R_6 + R_9} ~ & \left[\scriptsize\begin{array}{ccc|ccc|ccc|c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_5+b_7+b_8+b_9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_1+b_2+b_3+b_5 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_4+b_8+b_9 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_1+b_3+b_6+b_7+b_8 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & b_1+b_4+b_5+b_7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & b_1+b_2+b_6+b_7+b_9 \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & b_3+b_5+b_6+b_9 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & b_2+b_4+b_5+b_6+b_8 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & b_2+b_3+b_4+b_7+b_9 \end{array}\right] \end{align*}From the final augmented matrix, we see that \(\begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7\\ x_8\\ x_9 \end{bmatrix} = \begin{bmatrix} b_1+b_3+b_6+b_7+b_8 \\ b_5+b_7+b_8+b_9 \\ b_1+b_3+b_4+b_8+b_9 \\ b_3+b_5+b_6+b_9 \\ b_2+b_4+b_5+b_6+b_8 \\ b_1+b_4+b_5+b_7 \\ b_1+b_2+b_6+b_7+b_9 \\ b_1+b_2+b_3+b_5 \\ b_2+b_3+b_4+b_7+b_9 \end{bmatrix}.\)
Hence, if the top-left square is the only one with the light on, then the solution is to press squares 1, 3, 6, 7, and 8. (Why?)
Solve the \(4 \times 4\) version of Lights Out completely. Is there a solution for every possible configuration of lights? Explain your answer.