I think I got what you mean. Please correct me if I misunderstand your question.

So, I think "$0 < \vert M_i\vert < m$" in the description of property $\Gamma$ should read "$0 < \vert M_i\vert \leq k$." And what the paragraph under the description says is that

- some entires of $\boldsymbol{x}$ are constants rather than variables, and
- which entries are constants is determined by which $M_i$ is chosen from $M$, i.e., the values of the "variables" that do not correspond to the columns of chosen $M_i$ will be assumed to be known a priori.

So, what you want to do is, given a family $M$ of subsets $M_i \subset \{1,\dots,n\}$ with $\vert M_i\vert <k$, find a submatrix $A'$ that consists of $k$ rows of $A$ such that for any $M_i$ the $k \times \vert M_i\vert$ submatrix of $A'$ that consists of the columns specified by $M_i$ is full rank.

In general, it seems very unlikely that there exists a polynomial time algorithm that determines whether desirable $A'$ exists. This is because what you're asking is to determine if the linear code defined by $A$ as its parity-check matrix can detect all errors that correspond to $M_i$.

Take $M_x\in M$. Let $\boldsymbol{e}=(e_0,\dots,e_{n-1})$ be the $n$-dimensional vector such that $e_i=1$ if $i\in M_x$ and otherwise zero. Assuming $\vert M_x\vert < \frac{n}{2}$, a linear code defined by $H$ can correct error $\boldsymbol{e}$ if and only if

- $H'$ that corresponds to columns specified by $M_x$ is full rank and
- $H'$ with any other set of $\vert M_x\vert$ columns (which are not in $H'$) is also full rank.

So, if $M$ contains all subsets of size $t$, to have a desired submatrix you want, the linear code defined by $A$ should be of minimum distance at least $\frac{t-1}{2}$.

It is known that determining the minimum distance of a linear code is NP-complete. Moreover, it is proved that the minimum distance of a linear code is not approximable to within any constant factor in random polynomial time, unless NP equals random polynomial time:

I. Dumer, D. Micciancio, M. Sudan, Hardness of Approximating the minimum
distance of a linear code, *IEEE Trans. Inf. Theory,* **49** (2003), 22-37 (available for free here).

But you should know if $d\geq\frac{t-1}{2}$. Now you didn't specify how $M$ is chosen. But, for example, assume that you may end up with $M$ with all subsets of size $c\cdot n$ for some constant $c$. In other words, your algorithm should determine if $d\geq c'\cdot n$ for some constant $c'$. Because the minimum distance of a random linear code satisfies the Gilbert-Varshamov bound with high probability (which was proved in J. Pierce, Limit distribution of the minimum distance of random linear codes, IEEE Trans. Inf. Theory, **13** (1967), 595-599), basically your algorithm should determine if $d\geq c''\cdot d$ for some constant $c''$, which seems unlikely to be in polynomial time.