MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let y=Ax. A is a matrix n by m and m>n. Also, x gets its values from a finite alphabet. Elements of A and x can be complex numbers. How can i show if the mapping from x to y is injective for given A and alphabet (beside a search method)?

For example, let A and the alphabet be

[1 0 1/sqrt2 1/sqrt2] [0 1 1/sqrt2 -1/sqrt2]


{1, -1}

respectively. For this alphabet, x can be [1 1 -1 -1]'. Actually, there are 2^m=16 possible options for x, considering all permutations. Using this permutation set and A matrix, the operation will be one-to-one even if we map larger space to smaller space! Indeed, it is possible to test the injectivity with this scale. However, when we have larger matrices, search algorithm (i.e., testing all mappings) would take very long. If i can, i would like to verify it without a search algorithm.

share|cite|improve this question
This is almost certainly a NP-complete problem (or, the way you phrased it, co_NP). Indeed, if $A$ is a single row and the alphabet is ${0,1}$, then this is a slight variation on the subset sum problem. I don't immediately see a reduction but it seems hard to believe it's any easier. – Will Sawin Jan 27 '13 at 22:10
in your example it seems to follow trivially from the observation there are no rational non zero elements of the kernel. – roy smith Jan 27 '13 at 22:15
I think, we can say that this question is also related with cryptology. How can we sure that a crypto algorithm results in one-to-one transformation? We cannot test all inputs. – Alphan Sahin Jan 27 '13 at 23:03
One uses a very special algorithm with nice mathematical properties, like taking powers of a number mod another number. For a general transformation, there is no known method – Will Sawin Jan 28 '13 at 23:27
Do you think that it is helpful for this question if i constraint my alphabet as the roots of polynomials with the integer coefficients? – Alphan Sahin Jan 29 '13 at 16:37

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.