Maximising the number of lit lightbulbs through row-column toggling

Question

You have an $n\times n$ grid, with each cell containing a lightbulb. On a move, you may select a lightbulb, and toggle the state of that lightbulb, and all other lightbulbs sharing a row or column. For example, toggling the red $0$ results in $$\begin{bmatrix} 1 & \color{#c20}{0}& 1 \\\ 0 & 0 & 0 \\\ 1 & 1 & 0 \end{bmatrix}\longrightarrow \begin{bmatrix} 0 & 1& 0 \\\ 0 & 1 & 0 \\\ 1 & 0 & 0 \end{bmatrix} $$ where $1$ and $0$ represent lightbulb states (either lit or unlit).

Find the largest positive integer $k$, in terms of $n$, for which you can always arrive at a configuration with at least $k$ lit lightbulbs regardless of the starting configuration.

Answer 1

The answer is

$k = n^2$ if $n$ is even, and $k = n^2-n+1$ if $n$ is odd.

Reasoning for even $n$:

We can switch on a bulb by performing a move on every cell which is in the same row or the same column as this bulb. This way the bulb itself is switched $2n-1$ times, the other bulbs in the same column or row are switched $n$ times (which is even), and all the other bulbs are switched 2 times.
By performing this sequence of moves with every bulb which is switched off, we can get to a situation with all bulbs switched on

Reasoning for odd $n$:

Note that Paul Panzer has already shown how to turn on at least $n^2-n+1$ bulbs, so it is left to show that there are configurations where this cannot be improved.
Observe that if $n$ is odd, then a move always toggles an odd number of bulbs in every row and column. So in particular, after an even number of moves, the parity of the number of bulbs which is switched off in a particular row or column is the same as the parity of the number of bulbs which was switched on initially, and after an odd number of moves all parities are switched.
Now consider the following starting position:
$$\begin{bmatrix} 0 & \cdots & 0 & 1 \\ 1 & \cdots & 1 & 1 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \cdots & 1 & 1 \end{bmatrix}$$ After an even number of moves, by the previous observation, the first $n-1$ columns will always will have an odd number of bulbs (so at least 1) switched off, so there are at most $n^2-n+1$ bulbs lit. After an odd number of moves, every row contains an odd number of bulbs (at least 1) switched off, so there can be at most $n^2-n$ lit bulbs. This shows that we indeed can never reach a configuration with more than $n^2-n+1$ lit bulbs.

Answer 2

Lower bound:

k(n) >= n(n-1) + 1

Reasoning:

First observe that using the last row and last column as buffer we can freely switch all the other bulbs, for example, to toggle bulb at row a, col b without side effects toggle it and then toggle row a col n and row n col b. So we can get (n-1)(n-1) from that plus the best we can get out of the last row and the last column together as we can toggle at row n col n we get at least another n.