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.

I have a large matrix with unique, non repeating numbers from 0 to $2^{14}$ (14-bit) in each cell. I need to decompose this matrix into the same size matrix but only using 7 bits in each cell. The rest of the 7-bits for unique representation need to be obtained by taking 1, 2, or 3 bits from adjacent cells so that summing (or using some other operator) on these extra bits from adjacent cells in addition to the 7-bits in the current cell gives back the original matrix from 0 to $2^{14}$.

Is this possible? How do I go about resolving this? I have been looking at square matrices and similar matrices that could have similar properties, but I have been unable yet to find this.

share|improve this question
Is your data restricted to a smaller set in some way? It's generally not possible to store 14 bits of information in less than 14 bits, and even the information that they're unique doesn't improve this by more than about 1.5 bits... –  Alfonso Fernandez Jan 15 '13 at 18:01
Unfortunately no. I need those numbers to be unique so that I have a unique mapping. There is almost no limitation on how the numbers can be organized in either matrix, but I thought as you said that this might not be possible since I'm trying to use a relationship to provide the extra bits of information (which it likely can't). –  user58386 Jan 15 '13 at 18:22
You're trying to represent a permutation of $2^{14}$ numbers (doesn't matter in what form it's ordered), which requires about $205,733.21$ bits ($\log_2(2^{14}!)$) with $2^{14}\cdot7 = 114,688$ bits. The information that comes from the position of number is determined by its place in the permutation, so relationship between cells can't hold any more information. –  Alfonso Fernandez Jan 15 '13 at 21:01

Your Answer


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

Browse other questions tagged or ask your own question.