# Strategy to zerofy a matrix

I am considering an interesting question, given an $$\{0,1\}$$-matrix $$M \in \{0,1\}^{n\times p}$$, we define that an k-operation to the matrix is changing value of $$M$$ to be $$\tilde{M}$$ such that $$\tilde{M}_{ij}=\begin{cases} 0, & i \in\{1,\ldots,n\}\text{,and } j \in\{l\in\{1,\ldots,n\}|M_{kl}=1\} \\ M_{ij} ,& \text{otherwise.} \\ \end{cases}$$ We renew $$M$$ with $$\tilde{M}$$, operation finished.

A k-operation is essentially putting all columns that has the $$k$$th row element 1 to be $$\boldsymbol{0}$$.

The question is how to pick minimum number of the k s to do operations such that $$M$$ becomes the zero matrix (which is the matrix with all entries $$0$$)?

My idea is each step picking the $$k$$ which flips most number of $$1$$s to become $$0$$ in a greedy way. However, I could not prove this, could someone please help me with it?

• I don't think that's the same variant, but "$\forall i \in\{1,\ldots,n\},\, j \in\{l\in\{1,\ldots,n\}|M_{kl}=1\}$" is really the sort of thing best explained in words. Commented Mar 9, 2023 at 3:15
• Your operation is not well-defined. You said: $$\tilde{M}_{ij}=\begin{cases} 0, & \forall i \in\{1,\ldots,n\},\, j \in\{l\in\{1,\ldots,n\}|M_{kl}=1\} \\ M_{ij} ,& \text{otherwise.} \\ \end{cases}$$ In the first case on the right-hand side, $i$ is universally quantified. However, on the left-hand side, $i$ represents a (fixed) arbitrary index. Commented Mar 9, 2023 at 3:27
• Thank you @MishaLavrov, I made a line to explain the operation. Commented Mar 9, 2023 at 3:43
• Does this answer your question? Lights Out Variant: Flipping the whole row and column. Commented Mar 11, 2023 at 12:44
• @Sebastiano I initially had the same thought, but it’s not the same. Commented Mar 11, 2023 at 13:05