In a game of Lights Off, how many light configurations are valid given a starting position?

Question

Suppose you have a 5x5 grid, and the starting configuration

⚫⚫
⚫⚫⚫⚫
⚫
⚫⚫⚫⚫
⚫⚫⚫

or something, after any amount of taps (where a "tap" on a light inverts that light's state and all surrounding ones' state as well) how many are the possible configurations? Or are all $2^{25}$ reachable?

Alternate problem, same question: array of eight lights, starting with ⚫⚫⚫⚫⚫⚫⚫⚫. Before a tap, every light's state is inverted (not sure that matters) and then a tap works the same way: it inverts the chosen light and the ones just before and after. Additional constraint here is that you can't tap the ones at the borders: with every tap, exactly three consecutive lights must be switched.

And yet another question: in a Lights Off game with three states ⚫, and ("toggling" means to cycle to the next state) do the same reasonings still apply?

Answer 1

What Lorenzo suggested in the comments is to look at matrices over $\operatorname{GF}(2)$ (aka $\mathbb{Z}_2$). Specifically, for each move corresponding to $(i, j)$ we look at the $01$-matrix which has $1$'s at positions adjacent to and including $(i, j)$ and $0$'s everywhere else.

For instance the matrix corresponding to $(1,2)$ is

\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}

Let's call these matrices $A(i,j)$. If our initial state is represented by a $01$-matrix $A_0$ then adding $A_0 + A(i,j)$ modulo $2$ gives the updated matrix after we perform the move "$(1,2)$."

Any state we can reach can be described as $$ A_0 + \sum_{i = 1}^5 \sum_{j = 1}^5 c_{i,j} A(i,j) \pmod 2$$ and since $1 + 1 \equiv 0 \pmod 2$ we may assume that $c_{i,j}$ is either $0$ or $1$.

So we might think then that the answer is $2^{25}$ since there are $25$ coefficients $c_{i,j}$ but not so fast because there might be some linear dependencies among the matrices $A(i,j)$. What we want is the dimension of the linear space $\operatorname{span}\{A(i,j) : 1 \le i, j \le 5\}$.

I used Mathematica to compute this since each matrix has $25$ entries and there are $25$ matrices so to compute this we would form a $25 \times 25$ matrix and row reduce (operations done mod $2$) to find its rank.

Adjacent[i_, j_] := 
 Boole[
  Table[
   Abs[x - i] == 1 && y == j || x == i && Abs[y - j] == 1 || x == i && y == j,
{x, 5}, {y, 5}]]

MatrixRank[Flatten[Table[Flatten[Adjacent[x, y]], {x, 5}, {y, 5}], 1], Modulus -> 2]
(*output: 23*)

I'm flattening $A(i,j)$ first to turn it into a vector. So the matrix $A(1,2)$ would become the vector $(1,1,1,0,0,0,1,0,0,0,\dots,0)$ (just write the rows in order).

Thus $\dim \operatorname{span}\{A(i,j) : 1 \le i, j \le 5\} = 23$ which means that there are $2^{23}$ distinct linear combinations of $A(i,j)$ over $\operatorname{GF}(2)$.

Doing the same thing with the modulus set to $3$ gives a dimension of $22$ and so there would be $3^{22}$ if we played the same game over $\operatorname{GF}(3)$.

If you are confused as to why it is modulus^dimension imagine taking a basis. So for $\operatorname{GF}(2)$ the dimension is $23$ so there is a basis $E_1,\dots,E_{23}$ (which we could calculate from the RREF). Then

$$ \left\{ \sum_{i = 1}^5 \sum_{j = 1}^5 c_{i,j} A(i,j) : c_{i,j} = 0 \text{ or } 1\right\} = \left\{ \sum_{k = 1}^{23} d_{k} E_k : d_k = 0 \text{ or } 1\right\} $$

(again, mod $2$). But unlike the first set where we could write the same matrix using different choices of $c_{i,j}$, for the second set, there is a unique matrix for each different choice of $(d_1,d_2,\dots,d_{23})$. And now finally there are $2$ choices for each $d_k$: either $0$ or $1$.

---

And if you want the diagonal cells as well in $A(i,j)$ then in the code, we can use instead

Adjacent[i_, j_] := 
  Boole[Table[Abs[x - i] <= 1 && Abs[y - j] <= 1, {x, 5}, {y, 5}]]

With the diagonal cells, the dimensions are both $16$ (mod $2$ or mod $3$).

Thus here there are only $2^{16}$ or $3^{16}$ states we can reach respectively.