Lights Out Variant: Flipping the whole row and column.

Solution 1:

First, consider the $n\times n$ case.

I claim the following:

Claim:

If $n$ is even, there is always a solution given any starting configuration.

If $n$ is odd, there is a solution iff the 'on' lights parities for each row and column are the same.

i.e. if the lights were $1$ for on and $0$ for off, then modulo $2$, the sum of each individual row, and sum of each individual column must be the same.

Proof:

Case I: $n$ is even. You can toggle just a particular light by toggling all the lights in its row and column. So you can switch off all the lights by going after individual lights.

Case II: $n$ is odd.

Notice that if $n$ is odd, on any single operation, all the row and column parities change simultaneously.

Thus if they are not all the same, we can never achieve all lights off. This shows the necessity of the parities being the same.

To prove sufficiency, consider an arrangement of $(2k+1)\times(2k+1)$ which has all row and column parities the same.

Consider the $2k\times 2k$ subgrid which does not include the bottom row and the right column. Use the above even $n$ case algorithm to switch off all the lights in that $2k\times 2k$ grid. Since the row and column parities all flip together and were initially all the same, we must have that the remaining lights, in the bottom row and right column, are all the same (including the bottom right corner). Now we toggle the bottom right corner, if needed.

$\circ$

Now, the above can be generalized to the $m \times n$ case, when $m$ and $n$ have the same parity.

If $m$ and $n$ have different parities, there is more work to be done.

Solution 2:

Think of each light as a variable taking values in $0, 1$. Flipping a switch has the effect of adding $1$ to each corresponding light, modulo $2$. To the switch at position $i, j$ make correspond a variable $s_{i,j}$representing the number of times you flip that switch. Now the final value of each light is equal to its initial value plus each $s_{i,j}$ that shares a column or row with it - this is a linear equation in the variables $s_{i,j}$. For an $m\times n$ grid, we thus obtain $mn$ linear equations (one for each light) in $mn$ variables (one for each switch).

The integers modulo $2$ are a field, so all of the usual results of linear algebra should apply.

Example. Let's works out the $2\times2$ case. Which grids are solvable?

If we represent "on" as $1$ and "off" as $0$, then note that we need to add each light to itself. That is, if a light starts at value $0$, we need to flip the switches so as to add $0$ to that light (because we don't want it to change), but if it starts at value $1$, we need to flip the switches so as to add $1$ to that light. So the equation for each light is going to look like sum of associated switches = initial state.

Writing the initial state of the $i,j$ light as $l_{i,j}$, we therefore need to solve:

$$l_{1,1}=s_{1,1}+s_{1,2}+s_{2,1}$$ $$l_{1,2}=s_{1,2}+s_{1,1}+s_{2,2}$$ $$l_{2,1}=s_{2,1}+s_{1,1}+s_{2,2}$$ $$l_{2,2}=s_{2,2}+s_{1,2}+s_{2,1}$$

The matrix for this system looks like this (omitting zeros for readability):

\begin{array}{cccc} 1 & 1 & 1 & \\ 1 & 1 & & 1 \\ 1 & & 1 & 1 \\ & 1 & 1 & 1 \end{array}

Gaussian Elimination works easily on this matrix (tip: remember that mod $2$, $a + a = 0$ for any $a$) and we obtain an explicit solution for the general $2\times2$ grid:

$$s_{1,1}=l_{1,1}+l_{1,2}+l_{2,1}$$ $$s_{1,2}=l_{1,2}+l_{1,1}+l_{2,2}$$ $$s_{2,1}=l_{2,1}+l_{1,1}+l_{2,2}$$ $$s_{2,2}=l_{2,2}+l_{1,2}+l_{2,1}$$

So the answer is that all $2\times2$ grids are solvable, and there's the solution (concurring with Aryabhata's proposition).

As the number of equations is equal to the number of cells on the grid, this method quickly becomes too tedious and complicated to perform by hand. I would try to investigate the determinant of these matrices in the abstract case and see if you come up with anything. That would at least tell you which grid sizes have a guaranteed solution.