# Maximum rows to partially distinguish all the columns

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$ $$\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) } } }.$$ $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.

• OK. It is not copied from some article, actually, I am asking for reference for this problem. It is copied from my draft. Commented Sep 20, 2011 at 15:12

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.

• Thank you very much for your kindness. I think the transformation is correct. Your transferred( extended ) matrix problem seems like NP-complete. So it does not justifies the original problem is NP-complete. If the extended matrix problem is in P, then the original problem got solved. Actually, I did a similar transformation before I ask, transferring a $n\times m$ input matrix to a $n \times (m-1)*m/2$ matrix, with each entry is a subset of indicies of rows. However, I cannot prove my transferred problem is NP-hard or polynomially solvable. Commented Sep 21, 2011 at 17:51