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 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 an invariant and rigorously proof that solution exists $ \forall n \in \mathbb{N}$ ?

I started to think in a such way. We can find all solutions for $ n = 2$ and all of them would require $ steps <= 3$ to solve. So, because of $ a \oplus1 = \overline a$ (this op is actually describe each our 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.