Checking if a matrix is zero deletable?

Question

Given a matrix $\in [0,1]$. Delete operation is defined as: If one of the elements of the matrix contains 1 or 2 it can be deleted and replaced by 0.

A matrix is zero deletable if there is a chain of delete operations that satisfies:-

1. Every row should have one or more elements that are greater than 0
2. All elements greater than 0 should be the same(in value) in each column

I tried to use a reduction from 3-SAT to prove NP-Completeness but couldn't think of any way to do it.

Answer 1

You are correct, testing for zero deletability is NP-complete. We can reduce a 3-SAT problem in conjunctive normal form to a problem of determining whether a matrix can be put in "zero deletable" form by deleting entries.

Consider a statement in conjunctive normal form, $\bigwedge_{i=1}^n (L_{i1}((x_{j_{i1}}) \lor L_{i2}(x_{j_{i2}}) \lor L_{i3}(x_{j_{i3}}))$, where each $j_{ik}$ is an index from 1 to $m$, each $x_j$ is a Boolean variable, and each $L_{ik}(x)$ is either $x$ or $\lnot x$. We can construct an $m \times n$ matrix $A \in \{0,1,2\}^{m \times n}$, defining $A_{ij}$ for each $i,j$ by $A_{ij}:=1$ if $L_{ik}(x_{j_{ik}})=x_j$ for any $k$, and setting $A_{ij}:=2$ if $L_{ik}(x_{j_{ij}})=\lnot x_j$ for any $k$, and $A_{ij}:=0$ otherwise. That is, the $j$th column corresponds to $x_j$: if $x_j$ is true, delete all the 2s and keep all the 1s in column $j$, while if $x_j$ is false, keep all the 2s and delete all the 1s. The $i$th row corresponds to the $i$th clause $(L_{i1}((x_{j_{i1}}) \lor L_{i2}(x_{j_{i2}}) \lor L_{i3}(x_{j_{i3}}))$. Initially, it contains 3 nonzero entries: a 1 in each column corresponding to one of its true literals, and a 2 in each column corresponding to one of its false literals. The $i$th clause is satisfied if at least one of the entries in the $i$th row isn't deleted.

Thus, for example, the 3-SAT instance $ (x_1 \lor x_2 \lor x_3) \land (x_1 \lor x_2 \lor \lnot x_3) \land (x_1 \lor \lnot x_2 \lor x_3) \land (x_1 \lor \lnot x_2 \lor \lnot x_3) \land{}$ $ (\lnot x_1 \lor x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor \lnot x_3) \land (\lnot x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3) $ corresponds to the matrix $\begin{pmatrix} 1&1&1\\1&1&2\\1&2&1\\1&2&2\\2&1&1\\2&1&2\\2&2&1\\2&2&2\end{pmatrix}$. The 3-SAT instance is false and the matrix is not zero deletable - e.g. if you fix $x_1=T$, then you keep the 1s and delete the 2s in the first row. Then there is no way to decide which number to keep in the other two rows so that the last four columns are all nonzero.

Reducing a zero deletability test to a SAT problem is easier: given a matrix $A \in \{0,1,2\}^{m \times n}$, just define variables $x_{ij}$ corresponding to each initially nonzero entry of $A$, zero if an entry is deleted and one otherwise, and convert the conditions for "zero deletable" form to statements about the $x_{ij}$.