Flip the bulbs in minimum number of moves We are given a $n \times m$ rectangular matrix in which every cell there is a light bulb, together with the information whether the bulb is ON or OFF.
Now i am required to switch OFF all the bulbs but i can perform only one operation that is as follows:


*

*I can simultaneously flip all the bulbs from ON to OFF and vice versa in any submatrix.


I need to switch OFF all the bulbs in a minimum number of moves and tell the number of moves needed as well as the moves themselves. Is there an efficient algorithm for this?
EXAMPLE: Let us assume  $n=2$ and $m=3$ .The initial grid is as follow if $0$ stands for OFF and $1$ for ON:
$$\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix}$$
Now we can switch OFF all bulbs in 2 moves which are as follow : 
Move 1: Flip bulbs in subarray from $(1,1)$ to $(1,1)$
Move 2: Flip bulbs in subarray from $(1,2)$ to $(2,3)$
 A: I don't know of an efficient algorithm that produces the minimal number of moves, but there's an algorithm that gives pretty good results.
The algorithm is based on the following observation: From the original $m \times n$ matrix construct a derived matrix of size $m+1 \times n+1$ by considering all $2\times2$ submatrices of the original matrix (imagine a border of zeros around it) and marking $0$ if the $2 \times 2$ submatrix has an even number of $1$s and $1$ if it has an odd number of $1$s. Now in the derived matrix a move on the original matrix corresponds to a move that switches just the four corners of a rectangle.
This all is best explained by an example. For your original matrix
$$\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1\end{matrix}$$
the derived matrix would be
$$\begin{matrix}1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1\end{matrix}$$
After the first move it becomes
$$\begin{matrix}1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0\end{matrix}$$
and after the second one it is cleared.
The algorithm then looks for rectangles in the derived matrix with as many corners $1$ as possible and removes them in a greedy fashion. This is not optimal, but leads to quite good results.
Note in particular, that it follows that we must make at least $u/4$ moves, where $u$ is the number of $1$s in the derived matrix.
A: There are $n={N+1\choose 2}{M+1\choose2}$ ways to pick a submatrix, each corresponding to a vector $v_i\in\mathbb F_2^{NM}$, $1\le i\le n$. You are looking for a  solution of $\sum c_iv_i=A$ that minimizes the weight $w(c)$ (i.e. the number of $i$ with $c_i=1$)
Proposition: Among all minimum-weight solutions there exists one where no tow of the chosen submatrices share a corner.
Proof:
Among all minimum weight solutions let $c$ minimize $\sum_{c_i=1}w(v_i)$. 
Assume two submatrices $v_iv_j$ with $c_i=c_j=1$ share a corner.
Wlog. it is their top left corner, say say $v_i$ covers $(a,b)$ to $(c,d)$ and $v_j$ covers $(a,b)$ to $(e,f)$ with $a\le c$, $b\le d$, $a\le e$, $b\le f$.


*

*If $c< e$ and $d< f$, we could flip $(a,d+1)$ to $(c,f)$ and $(c+1,b)$ to $(e,f)$ instead

*If $c<e$ and $d=f$, we could flip $(c+1,b)$ to $(e,f)$ instead

*If $c<e$ and $d>f$, we could flip $(a,f+1)$ to $(c,d)$ and $(c+1,b)$ to $(e,f)$ instead

*All remaining cases can be treated similarly (use symmetry)


Since this replaces overlapping rectangles with disjoint rectangles the sum of rectangle weights decreases, contradicting its minimality. $_\square$
EDIT: This proposition may be helpful to devise an algorithm to find the answer by dynamic programmming, though I am not sure yet how to do so without requiring lots of memory. Thanks to Christoph Pregel that my original corallary of the proposition was trivial. Indeed we already find a  better simple general estimate as follows: A row (or column) of $N$ light bulbs with $n$ separate intervals of on-bulbs (so $N\ge 2n-1$) can easily be cleared with $n$ moves. Thus for even $N$ we need at most $\frac12NM$ moves to clear the whole matrix; the same holds for even $M$; and if both $N$ and $M$ ore odd, it takes at most $\frac{N+1}{2}$ moves to reduce to the case of even $M$, i.e. we need at most $\lceil\frac{NM}2\rceil $ moves in general. 
In fact one can verify by exhaustive search that any $4\times 4$ matrix can be cleared in at most $5$ moves; this shows that $\le 5\cdot \lceil \frac N4\rceil\cdot \lceil \frac M4\rceil\approx \frac{5}{16}NM$ moves suffice. Again, this does not solve the problem itself, but it may give a helpful heuristic estimate for "distance" in a suitable algorithm.
