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

  • $\begingroup$ do you know the rank of $A$? $\endgroup$ – Dima Pasechnik Jun 19 '14 at 12:27
  • $\begingroup$ It is at least $k$ and at most $m$. But given $A$, the exact rank can be computed. How does it help? $\endgroup$ – Helium Jun 19 '14 at 16:11
  • $\begingroup$ 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. $\endgroup$ – Helium Jun 19 '14 at 16:29
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuichiro Fujiwara Jun 19 '14 at 16:47
  • $\begingroup$ @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. $\endgroup$ – 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:

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.

| cite | improve this answer | |
  • $\begingroup$ I correct #2: $M_i$ specifies the unknown variables, not the known ones. $\endgroup$ – Helium Jun 19 '14 at 18:34
  • $\begingroup$ @Mohsen Oh, I forgot to put "do not" before "correspond." This is what you meant, I think? $\endgroup$ – Yuichiro Fujiwara Jun 19 '14 at 18:37
  • $\begingroup$ Yes, that's exactly what I mean. Thanks :) $\endgroup$ – Helium Jun 19 '14 at 18:41
  • $\begingroup$ 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$. $\endgroup$ – Helium Jun 19 '14 at 18:45
  • $\begingroup$ 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. $\endgroup$ – Helium Jun 19 '14 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.