reference request- property of subset of rows in a matrix
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.