Maximum rows to partially distinguish all the columns

Question

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.

Answer 1

This is not an answer, only an extended comment on a possible transformation of the problem (hope it is correct :-).

Each row can be "mapped" to a $n \times (n-1) / 2$ "extended" row. Each element of the extended row represents a pair of elements in the original row and is set to 1 if the two elements are different, set to 0 if the two elements are the same.

For example:

row_i = 10011  
        ^1100   (*)
         ^011   
          ^11
           ^0

extended_row_i = 1100 011 11 0

(*) note that in building the extended row, when the current bit (marked with ^)
is 0, the remaining bits are just copied and when the current bit is 1 the
remaining bits are inverted

We can extend each row and obtain an "extended" matrix. For example the matrix:

10011
01101
00011

Becomes:

1100 011 11 0
1101 010 10 1
0011 011 11 0

And the original problem reduces to find a submatrix of the "extended" matrix with exactly one 1 in each column.