# Compressing a system of linear equations

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)$.

• do you know the rank of $A$? – Dima Pasechnik Jun 19 '14 at 12:27
• It is at least $k$ and at most $m$. But given $A$, the exact rank can be computed. How does it help? – Helium Jun 19 '14 at 16:11
• I mean rank of $A$ is at least $k=\max_i |M_i|$. I made a mistake and used $k$ for two different purposes in my question, but it's know fixed. – Helium Jun 19 '14 at 16:29
• Is there some sort of assumption on $\boldsymbol{x}$? If I understand correctly, since $A$ is a fat matrix, you can't generally solve the linear equation. I'm guessing you're assuming that $\boldsymbol{x}$ is sparse (i.e., it has at most $s$ nonzero elements for some fixed small integer $s$). If this is the case, what you asked sounds the same as or closely related to MDS codes or the separating distance of $A$. – Yuichiro Fujiwara Jun 19 '14 at 16:47
• @YuichiroFujiwara: yes, $\mathbf x$ is sparse. And you are right, it's kind of similar to MDS codes, but not exactly. If $M$ contains all the subsets of $\{1,...,n\}$ of size $k$, then it would be like MDS. It has a looser assumption. – Helium Jun 19 '14 at 17:45

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:

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.

• I correct #2: $M_i$ specifies the unknown variables, not the known ones. – Helium Jun 19 '14 at 18:34
• @Mohsen Oh, I forgot to put "do not" before "correspond." This is what you meant, I think? – Yuichiro Fujiwara Jun 19 '14 at 18:37
• Yes, that's exactly what I mean. Thanks :) – Helium Jun 19 '14 at 18:41
• I like to add: $A'$ does not simply consist of $k$ rows of $A$. Each row of $A'$ can be a linear combination of all of rows of $A$. Since $A$ is $m\times n$ and $A'$ is $k\times n$, the question can be seen as finding a conversion matrix $T_{k\times m}$ such $A'=TA$. – Helium Jun 19 '14 at 18:45
• I think if $M$ contains only a few $M_i$, a random matrix $T$ solves the problem with high probability, but as $|M|$ grows, a random assignment to $T$ becomes less probable to solve the problem. – Helium Jun 19 '14 at 18:47