Compressing a system of linear equations

Question

Consider the system of linear equations $A\mathbf x=\mathbf b$ in which $A$ is an $m\times n$ matrix with $m < n$ and with the following property:

Property $\Gamma$: Given $M=\{ M_1,\cdots,M_r \}$ where $M_i \subset \{1,\cdots,n\}$ and $0 < |M_i| < m$ for all $i$, the submatrix shaped by selecting columns $M_i$ from $A$ has full rank.

Property $\Gamma$ states that if person $i$ has all the variables, but is missing $\{ x_j | j \in M_i \}$, he can find the value of the missing variables by removing the values that he has from the system and solving the remaining ones.

However, the system $A\mathbf x=\mathbf b$ has too many rows. It has $m$ rows but $k=\max_i |M_i|$ is enough for the system to have property $\Gamma$.

Question: Given $A$, $\mathbf b$, and $M$, is that possible to create a system $A'\mathbf x=\mathbf b'$ with $k$ rows and the same number of variables that preserves property $\Gamma$? How?

All the computation is done over a finite field GF$(p^q)$.

Answer 1

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

1. some entires of $\boldsymbol{x}$ are constants rather than variables, and
2. 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

1. $H'$ that corresponds to columns specified by $M_x$ is full rank and
2. $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.