<p>Your problem can be solved in polynomial time, by reduction to bipartite matching.  In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property.</p>

<p>Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN).  Add an edge $(i,j)$ whenever $M_{i,j} \ne z_j$.  Now each subset of rows with your property corresponds to a matching in this bipartite graph: take $S$ to be the set of left-vertices covered by the matching.  In particular, the maximum matching in this graph corresponds to the largest subset of rows that satisfies your property.  You can compute the maximum matching in polynomial time.</p>

CC BY-SA 3.0
2016-08-17T22:35:56.517Z
2016-08-17T22:35:56.517Z
D.W.
<p>I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M such that the following holds: for every $i\in [n]$, there is $at$ $most$ one row in $v\in S$ such that $v_i\neq z_i$.</p>

<p>I was wondering if this combinatorial notion has been used to characterize some complexity in literature? Any reference/ pointer is welcome. I am not interested in an algorithm to find the largest subset, but rather if such a combinatorial notion has been used to character some "other complexity measure"</p>

CC BY-SA 3.0
2016-08-17T22:36:21.923Z
What do you want to know about it? Are you looking for an algorithm to solve this problem? Are you trying to prove bounds on the size of the largest subset? Something else? Can you edit your post to ask a more specific question?  What's the context where you ran across this?  Is it an exercise?  Is there some application?
D.W.
<reference-request><co.combinatorics><matrices><extremal-combinatorics><boolean-matrix>
reference request- property of subset of rows in a matrix
researcher
# reference request- property of subset of rows in a matrix

(Asked by: username_0 on 2016-08-17)

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}\_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M such that the following holds: for every $i\in [n]$, there is $at$ $most$ one row in $v\in S$ such that $v\_i\neq z\_i$.

I was wondering if this combinatorial notion has been used to characterize some complexity in literature? Any reference/ pointer is welcome. I am not interested in an algorithm to find the largest subset, but rather if such a combinatorial notion has been used to character some "other complexity measure"

**Tags:** reference-request, co.combinatorics, matrices, extremal-combinatorics, boolean-matrix
> **Comments:**
> **username_1**: What do you want to know about it? Are you looking for an algorithm to solve this problem? Are you trying to prove bounds on the size of the largest subset? Something else? Can you edit your post to ask a more specific question?  What's the context where you ran across this?  Is it an exercise?  Is there some application?  

---

## 1 answers

### Answer by username_1 on 2016-08-17. Score: 1

Your problem can be solved in polynomial time, by reduction to bipartite matching. In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property.

Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN). Add an edge $(i,j)$ whenever $M\_{i,j} \ne z\_j$. Now each subset of rows with your property corresponds to a matching in this bipartite graph: take $S$ to be the set of left-vertices covered by the matching. In particular, the maximum matching in this graph corresponds to the largest subset of rows that satisfies your property. You can compute the maximum matching in polynomial time.


---

