Suppose we have a grid of $5 \times 5$ light bulbs with a switch to each bulb. If we press a switch it toggles all the lights in its row and column. Given any initial configuration, is it possible to make all the lights on or all the lights off by a particular sequence of switches?
I do not remember whether I have read about this problem somewhere or it just came up in my mind by some similar problems. Any hints/suggestions/links are highly appreciated.
The answer is no, not for all initial configurations it is possible to switch all lights off. As for many similar light-switching puzzles, the trick is to interpret the setting in a vector space over the finite field $\mathbb{F}_2$.
Identify the state of the lights with $5\times 5$ matrices over $\mathbb{F}_2$. (An entry $1$ means light on, an entry $0$ means light off.) Given such a matrix $A$, the effect of pressing the switch in the $i$th row and the $j$th column is the same as doing the transition $A \rightarrow A+S_{ij}$, where $S_{ij}$ is the $5\times 5$ matrix having entries $1$ in the $i$th row and in the $j$th column and having entries $0$ otherwise.
Now we compute $$B := S_{12} + S_{13} + S_{14} + S_{15} + S_{21} + S_{31} + S_{41} + S_{51}.$$ All $8$ involved $S$-matrices have an entry $1$ at the position $(1,1)$, so $B_{11} = 0$. Moreover, for all $j\in\{2,3,4,5\}$ there are exactly $4$ involved $S$-matrices (namely $S_{12}, S_{13}, S_{14}$ and $S_{15}$) with an entry $1$ at the position $(1,j)$. The same is true for position $(j,1)$, so $B_{1j} = B_{j1} = 0$ for all $j\in\{2,3,4,5\}$. Finally, for $i,j\in\{2,3,4,5\}$, there are exactly two involved $S$-matrices having an entry $1$ at the position $(i,j)$ (namely $S_{i1}$ and $S_{1j}$), so $B_{ij} = 0$ for all $i,j\in\{2,3,4,5\}$. Together, we get $B = 0$.
Therefore, the set of the $25$ matrices $S_{ij}$ is linearly dependent, implying that their linear hull does not equal the vector space of all $5\times 5$ matrices over $\mathbb{F}_2$ (which has dimension $25$).
Hence, there are initial light configurations which can never be switched off.
Remark We look at the natural generalization to $n\times n$ grids.
If $n \geq 3$ and $n$ is odd, you get the answer "no" analogously to the above argument.
If $n$ is even, the answer is "yes", so all initial light configurations can be switched off. For a proof, one verifies that $$ S_{ab} + \sum_{i\in\{1,\ldots,n\}\setminus\{b\}} S_{ai} + \sum_{j\in\{1,\ldots,n\}\setminus\{a\}} S_{jb} = E_{ab} $$ is the matrix whose only non-zero entry is at the position $(a,b)$ and equals $1$. Therefore, the span of the matrices $S_{ij}$ contains all standard basis matrices, so it equals the set of all $n\times n$ matrices over $\mathbb{F}_2$.