Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero one at a time what will be minimum number of operations (i.e multiplications) I will need. For example, for the matrix
$\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$
the answer is two. For this example
$\begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$
the answer is two not three.
Any help to go for head start is appreciated.