Fill the board with zeroes, inverting the intersections of rows and columns

Question

Given $n \times n$ board randomly filled with $x \in \{0, 1\}$. When you invert value in cell $x_{i,j}$, all corresponding values in $row_i$ and $col_j$ are inverted too. The goal is to fill the board only with zeroes.

I solved this task a long time ago for $n = 4$ in an old game. The question is how to find a rigorous proof that a solution exists $\forall n \in \mathbb{N}$?

I started to think in the following way. We can find all solutions for $n = 2$ and all of them would require less than $3$ steps to solve. So, because of $a \oplus1 = \overline a$ (this operation actually describes each step) and the parity of the number of columns/rows, we can say that solutions exist $\forall n = 2 ^ k$, because we will be able to solve each square $2 \times 2$ independently. But it doesn't help for $n = 3$, which actually has solutions for some cases.

I created a quick example to test here.

Answer 1

I think the puzzle cannot always be solved when $n>1$ is odd. Consider the entries in the top and bottom rows. Each step flips an even number of entries (either 2 or $n+1$) in these rows. So if you start with an odd number of zeros in these rows, you cannot finish with all zeros.

If $n$ is even, I believe you can always solve the puzzle, as you can produce a sequence of steps with the net result of flipping just one entry. (A sketch as follows. First construction: Flip four times in a rectangle shape. The net result is just flipping the corners of the rectangle. Second construction: Flip two times, not using the same row or column. The result is a set of flips in the shape of a hash (#) with two intersections missing. Because $n$ is even, the non-intersection points can be partitioned into sets of 4, each 4 points making up a rectangle. Use the first construction to remove the flips in all these 4 element sets. The net result is two just flips, in different rows and columns. Third construction: One step produces flips in the shape of a plus (+). The flips not at the intersection can be partitioned into pairs, each in a different row and column. Use the second construction to remove these. The result is a single flip.)

Answer 2

This is an extended comment short of a solution.

Define an $n^2\times n^2$ matrix $A_n$ with rows and columns indexed by the positions $(i,j)$. Row $(i,j)$ of the matrix is 0 except for 1 in the columns $(i,\ast)$ and $(\ast,j)$. I.e., row $(i,j)$ says what happens when you invert position $(i,j)$. Each row thus has $2n-1$ ones in it.

Now the boards that you can solve are exactly the vectors in the row space of $A_n$ over the field of 2 elements.

To show that all boards can solved, what you need is for $A_n$ to be non-singular, again over the field of 2 elements. One way would be to show that every elementary board can be solved, where an elementary board has exactly one 1. By symmetry, it will suffice to solve the board with 1 in the (1,1) position and zeros elsewhere. If that board is solvable, all boards are solvable.

Incidentally, this is a game but it isn't game theory.