1
$\begingroup$

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]

and

{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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Jan 27, 2013 at 22:10
  • $\begingroup$ in your example it seems to follow trivially from the observation there are no rational non zero elements of the kernel. $\endgroup$
    – roy smith
    Commented Jan 27, 2013 at 22:15
  • $\begingroup$ 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. $\endgroup$
    – Alphan Sahin
    Commented Jan 27, 2013 at 23:03
  • $\begingroup$ 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 $\endgroup$
    – Will Sawin
    Commented Jan 28, 2013 at 23:27
  • $\begingroup$ Do you think that it is helpful for this question if i constraint my alphabet as the roots of polynomials with the integer coefficients? $\endgroup$
    – Alphan Sahin
    Commented Jan 29, 2013 at 16:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .