How to solve this problem with Linear Algebra?

Question

I have a $N \times N$ grid, each cell initialized with an integer between $0$ and $5$. If I select one cell, each adjacent cell (8 cells if not on an edge or a corner) - but not the selected one- are incremented by $1$ then taken $\text{mod } 5$. I need to find the cells to select to get from the initial state to a given targeted state. I assume there is always a solution but I don't know if it is unique.

I have done this heuristically, but my implementation is very inefficient, and I wondered if linear algebra could be used here. In case it can be done with LA, any leads to help me formulate the problems would be very appreciated.

Thank you in advance for your help

Answer 1

Too long for a comment.

Let us consider the case $3\times 3$. Define $9$ matrices according to $$ \Delta_{1,1}=\begin{pmatrix}0& 1&0 \\ 1&1&0 \\ 0&0&0 \end{pmatrix}\\ \Delta_{1,2}=\begin{pmatrix}1& 0&1 \\ 1&1&1 \\ 0&0&0 \end{pmatrix}\\ \Delta_{1,3}=\begin{pmatrix}0& 1&0 \\ 0&1&1 \\ 0&0&0 \end{pmatrix}\\ \Delta_{2,1}=\begin{pmatrix}1& 1&0 \\ 0&1&0 \\ 1&1&0 \end{pmatrix}\\ \Delta_{2,2}=\begin{pmatrix}1& 1&1 \\ 1&0&1 \\ 1&1&1 \end{pmatrix}\\ \Delta_{2,3}=\begin{pmatrix}0& 1&1 \\ 0&1&0 \\ 0&1&1 \end{pmatrix}\\ \Delta_{3,1}=\begin{pmatrix}0& 0&0 \\ 1&1&0 \\ 0&1&0 \end{pmatrix}\\ \Delta_{3,2}=\begin{pmatrix}0& 0&0 \\ 1&1&1 \\ 1&0&1 \end{pmatrix}\\ \Delta_{3,3}=\begin{pmatrix}0& 0&0 \\ 0&1&1 \\ 0&1&0 \end{pmatrix} $$ Let us record the state into a $3\times 3$ matrix (with entries in $\mathbb Z/5\mathbb Z$), let the initial state be $I$. Then, any reachable state $F$ is of the form $$ F=I+\sum_{i,j=1}^3n_{i,j}\Delta_{i,j}. $$ Introduce the linear transformation $\mathscr L$ of $Mat(\mathbb Z/5\mathbb Z,3\times 3)$ onto itself by $$ N\mapsto \sum_{i,j=1}^3n_{i,j}\Delta_{i,j}. $$ Ordering the entries of $N$ as a $9$-dimensional vector $(n_{11},n_{12},n_{13},n_{21},n_{22},n_{23},n_{31},n_{32},n_{33})$, $\mathscr L$ is represented by the matrix $$ L=\left( \begin{array}{ccccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ \end{array} \right) $$ It can be checked that $\det L=0$, hence there are initial and final state which cannot be joined by this process.

For $1\times 1$ and $2\times 2$ the corresponding linear transformation $\mathscr L$ is instead invertible. Probably with some work (and/or some smart ideas) one can understand for which $n$ the relevant matrix $L$ is invertible.

EDIT: in fact, for the case $3\times 3$, the non-invertibility comes from the fact that the matrices $\Delta_{i,j}$ are not l.i.: $$ \Delta_{1,1}-\Delta_{1,3}-\Delta_{3,1}+\Delta_{3,3}=0_{3\times 3}. $$ A similar phenomenon occurs in the $4\times 4$ case: $$ \Delta_{1,1}+\Delta_{1,4} +\Delta_{2,1}-\Delta_{2,2}-\Delta_{2,3}+\Delta_{2,4} +\Delta_{3,1}-\Delta_{3,2}-\Delta_{3,3}+\Delta_{3,4} +\Delta_{1,4}+\Delta_{4,4}=0_{4\times 4} $$ and it is likely to occur for higher $n$ as well.

Answer 2

The way I would translate this into linear algebra is to consider the set $A_{i,j} \subset M_N(\mathbb{F}_5)$ where each matrix $A_{i,j}$ is filled whith $0$ in all entries except those surrounding the $i,j$ entry. Then the existence of a solution that gets you from the initial state to any given one is equivalent to $A_{i,j}$ being an spanning set of $M_N(\mathbb{F}_5)$, the uniqueness of a solution would be equivalent to it being a linearly independent set. As $dim(M_N(\mathbb{F}_5))=N^2$, the size of the set $A_{i,j}$, being a spannning set is equivalent to being linearly independet.

Answer 3

Thank you all for your inputs. Thanks to @Jaap I was directed to the wikipedia article on LightOut and there I found a link to a detailed article giving all the required steps. I share it as it might be useful to others. Also, the implementation in python was made easy thanks to the open source library galois.

I will accept the answer of @Giulio for the quality of his post !