CantonMathGuy wrote:

The answer is
$N = \begin{cases*} n^2 & $n$ even\\ n^2 - n + 1 & $n$ odd. \end{cases*}$ We interpret the board state as an element of $\mathbb{F}_2^{n \times n}$ .
$\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}.$

Here's a different way to show that the above construction guarantees at least $n-1$ odd numbers. Denote by $S(i,j)$ the set of all cells in the $i$ th row and $j$ -th column, excluding $(i,j)$ . Note any move would toggle an even number of cells of $S(i,j) ~ \forall ~ i,j$ . Note that $S(i,k)$ is odd originally for all $1 \le i \le n$ and $2 \le k \le n$ . Now consider any position. If each of $k$ -th column ( $k \ge 2$ ) contains a odd number, we are fine. Otherwise, if some $k$ -th row doesn't contain an odd number, then consider $S(i,k) ~ \forall ~ 1 \le i \le n$ gives each row contains an odd number, done! $\blacksquare$