This is a problem I met in my work. I thought about it for about two weeks, no result. I don't know whether it has been studied before by others?
Problem Description: Given an $m\times n$ matrix $M$ with entries valued 0 or 1. Let $r_i$ denote the $i^{th}$ row, $c_i$ denote the $i^{th}$ column and $t_{ij}$ denote the entry in the $i^{th}$ row and $j^{th}$ column. Find a $k \times n$ submatrix $A$ of $M$, such that in $A$ \begin{equation} \forall_{r_i}{ \exists_{c_a,c_b}{ \forall_{r_j \ne r_i}{\left( t_{ia} \ne t_{ib} \land t_{ja} = t_{jb} \right) } } }. \end{equation} $k$ is the parameter
The selected rows satisfy the following condition: For each row $r_i$, there exist two columns $c_a, c_b$, such that entries of the two columns at row $i$ are different, and at the remaining rows are the same.
Could someone give me any reference for it, if it has been studied before ? Thank you very much.
At first, I thought it was a special case of Minimum Test Set problem, however, it turns out not.