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

<p>Each row can be "mapped" to a $n \times (n-1) / 2$ <em>"extended"</em> 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.</p>

<p>For example:</p>

<pre><code>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
</code></pre>

<p>We can extend each row and obtain an <em>"extended" matrix</em>. For example the matrix:</p>

<pre><code>10011
01101
00011
</code></pre>

<p>Becomes:</p>

<pre><code>1100 011 11 0
1101 010 10 1
0011 011 11 0
</code></pre>

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

CC BY-SA 3.0
2011-09-21T17:51:03.837Z
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.
Peng Zhang
CC BY-SA 3.0
2011-09-20T19:50:51.623Z
2011-09-20T19:56:38.700Z
2011-09-20T19:56:38.700Z
Marzio De Biasi
<p>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?</p>

<p><strong>Problem Description</strong>: 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</p>

<p>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.</p>

<p>Could someone give me <strong>any reference for it</strong>, if it has been studied before ? Thank you very much. </p>

<p>At first, I thought it was a special case of Minimum Test Set problem, however, it turns out not. </p>

CC BY-SA 3.0
2011-09-20T15:12:36.110Z
OK. It is not copied from some article, actually, I am asking for reference for this problem. It is copied from my draft.
Peng Zhang
<cc.complexity-theory><co.combinatorics>
Maximum rows to partially distinguish all the columns
Peng Zhang
# Maximum rows to partially distinguish all the columns

(Asked by: username_0 on 2011-09-20)

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.

**Tags:** cc.complexity-theory, co.combinatorics
> **Comments:**
> **username_0**: OK. It is not copied from some article, actually, I am asking for reference for this problem. It is copied from my draft.  

---

## 1 answers

### Answer by username_1 on 2011-09-20. Score: 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.

> **Comments:**
> **username_0**: 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.  

---

