Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have $N$ integers $a_1,a_2,\dots,a_N$, Given $M$ more integers $b_1,b_2,\dots,b_M$($b_i$ is calculated from $a_1\dots a_n$ by some ways)

Now remove any $M$ numbers from $a_1,a_2,\dots,a_N, b_1,b_2,\dots,b_M$, I want to recover $a_1,a_2,\dots,a_N$

My question is, Can I find a way to calculate such $b_1,b_2,\dots,b_m$?

For example, suppose $M=1$, we can calculate $b_1$ as $$ b_1=a_1\oplus a_2\oplus\dots\oplus a_N $$ so if $a_i$ is missing ,we just need to XOR $b_1$ and left $a_i$.

For any $M$, my idea is to make $b_i$ as a linear combinations of $a_i$, that is $b_i = \sum_{j=1}^{N}k_{ij}a_j, 1\le i\le M$

Define A as a $(M+N)\times N$ matrix $$ A = \left[ \begin{array}{cccc} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots& \vdots& & \vdots\\ 0 & 0 & \dots & 1\\ k_{11}& k_{12} &\dots & k_{1N}\\ \vdots& \vdots & & \vdots\\ k_{M1}& k_{M2} &\dots& k_{MN} \\ \end{array} \right] $$ The first $N$ rows form an identity matrix $I_N$

The problem is to find $k_{ij}$, such that remove any M rows of $A$, the left $N\times N$ matrix is still full rank.

I'm not sure whether we define $k_{ij}=i^{j-1}$ will work .

share|improve this question

3 Answers 3

Somewhere in between the two previous answers of joriki and Gerry Myerson, let me point out that there exists an entire theory devoted to this question, known as the theory of error-correcting codes or coding theory: how to encode information (a bunch of numbers) such that even with limited information (fewer numbers, or some numbers incorrect) we can recover the original information.

The scheme you propose in your question (and Gerry Myerson in his answer) is a particular specific error-correcting code, and the one in joriki's answer (pick an injection $\mathbb{Z}^n \to \mathbb{Z}$ and use it in your encoding — BTW, on such polynomial functions, rejecting exponential solutions like $2^{a_1}3^{a_2}\dots$, see the nice article "Bert and Ernie" by Zachary Abel) is also an error-correcting code. The theory in general includes analysis of the tradeoffs between size of the encoding, efficiency of encoding/decoding, the extent to which loss can happen while still leaving recovery possible, etc. Here is a good free book that touches on it.

For instance, here is an approach that answers your question in the sense of "Given $N$ numbers, generate $N+M$ numbers such that even if any $M$ numbers are removed, the original $N$ numbers can be recovered". Given the $N$ numbers $a_1, \dots, a_N$, construct a polynomial of degree $N-1$ e.g. $p(x) = a_1 + a_2x + \dots + a_Nx^{N-1}$ in some field, and let the $N+M$ values $b_i$ be the values $p(x_i)$ of this polynomial at some pre-chosen values $x_1, \dots, x_{N+M}$. Then given any $N$ of these values (and knowing which ones), we can reconstruct the polynomial and hence the $a_i$s, through polynomial interpolation. This is the idea behind Reed-Solomon codes, used in CDs and DVDs.

If you insist that the $N+M$ values must be the original $N$ values and $M$ others, then with this constraint too there are many error-correcting codes (and joriki points out below that the previous idea can also be made to work), for instance in the class known as cyclic redundancy checks. Your $M=1$ example of using a parity bit is precisely one such check (a variant is used in ISBN and UPC numbers; see check digit).

Those involve polynomials, in general. If you further insist that the $N+M$ values must be given by a linear transformation with a matrix of the form $A$ as you wrote in the question, then see Gerry Myerson's answer, I guess.

share|improve this answer
    
Thank you, ShreevatsaR –  Benson Oct 16 '12 at 6:26
1  
The interpolation approach can also be used with $N$ original values and $M$ additional values by letting $p$ be the unique polynomial interpolating between the $a_i$ considered as function values at $x_1,\dotsc,x_N$. –  joriki Oct 16 '12 at 6:27
    
@joriki: Oh indeed! That's a nice idea; thanks for the observation. –  ShreevatsaR Oct 16 '12 at 6:37

Since $\mathbb Z^n$ is countable and it's straightforward to construct an enumeration (e.g. in a similar spirit as the diagonal enumeration of $\mathbb Z^2$), you can encode all $N$ integers in a single value $b$. If you take all $b_i=b$, then either they all get removed and you still have all the $a_i$, or at least one of them remains and you can reconstruct all the $a_i$ from that one.

share|improve this answer
    
Thank you, joriki, though this answer seems a bit tricky –  Benson Oct 16 '12 at 5:47
    
@Benson: I don't think it's tricky in the sense of difficult (to implement). Perhaps you mean it seems like a trick? –  joriki Oct 16 '12 at 5:52
1  
Yes, I mean in actual use, we need a lot of space to store such $b_i$. If each $a_i$ takes 4Bytes to store, than each $b_i$ needs $4*N$ Bytes to store –  Benson Oct 16 '12 at 6:30

You are looking for a matrix whose square submatrices are all nonsingular. These have been studied in coding theory --- in a "Maximum Distance Separable" (or, MDS) code, the generator matrix has this property. For example, the problem is discussed in Lacan and Fimes, Systematic MDS Erasure Codes Based on Vandermonde Matrices, IEEE Communications Letters 8 (2004) 570-572.

In any event, I think your choice of $k_{ij}$ is fine; I think it leads to a Vandermonde matrix, and there are formulas for the determinant of Vandermonde matrices which show that every square submatrix of a Vandermonde matrix with positive entries is nonsingular.

See also the discussion of this question: http://cstheory.stackexchange.com/questions/11110/complexity-of-deciding-whether-a-matrix-is-totally-regular

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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