reference request- property of subset of rows in a matrix

Question

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"

Answer 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.