This is a special case ($3\times 3$ and $4\times 4$) of USAMO 1998 problem #4.
A $98\times 98$ chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and switching their colors. What is the smallest number of moves required to make all the squares black?
I am trying to obtain optimal moves for $3\times 3$ and $4\times 4$ cases. (I couldn't understand the answers of linked post) I read somewhere that the optimal moves for first one is 2 and for second case is 4. But I tried almost all ways without reaching these numbers. For example for $3\times 3$ one possible solution is as follows:
$$\begin{bmatrix}
\color{red}{1} & 0&1\\
\color{red}{0}&1&0\\
\color{red}{1} & 0&1
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&\color{red}{1}\\
1&1&\color{red}{0}\\
0 & 0&\color{red}{1}
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&0\\
\color{red}{1}&\color{red}{1}&\color{red}{1}\\
0 & 0&0
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&0\\
0&0&0\\
0 & 0&0
\end{bmatrix}$$
which is 3 moves and not 2. What is the best way with 2 moves? and the $4\times 4$ case one possible solution is as follows which is 5 moves:
$$\begin{bmatrix}
\color{red}{1} & 0&1&0\\
\color{red}{0}&1&0&1\\
\color{red}{1} & 0&1&0\\
\color{red}{0}&1&0&1
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&\color{red}{1}&0\\
1&1&\color{red}{0}&1\\
0 & 0&\color{red}{1}&0\\
1&1&\color{red}{0}&1
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&0&\color{red}{1}\\
1&1&1&\color{red}{0}\\
0 & 0&0&\color{red}{1}\\
1&1&1&\color{red}{0}
\end{bmatrix}\implies \begin{bmatrix}
0 & 0&0&0\\
\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}\\
0 & 0&0&0\\
\color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{1}
\end{bmatrix}\stackrel{2 rows=2times}{\implies}\begin{bmatrix}
0 & 0&0&0\\
0&0&0&0\\
0 & 0&0&0\\
0 & 0&0&0
\end{bmatrix}$$
Best Answer
For the $3\times3$ case you could change two middle rows and get all $1$'s (check that). For the $4\times4$ case the possible sequence of moves is "$3$rd row", "$3$rd column", "$1$st row", "$1$st column".