Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Injective Mapping

  1. Jan 27, 2013 #1
    Let y=Ax. A is a matrix n by m and m>n. Also, x gets its values from a finite alphabet. 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.
     
  2. jcsd
  3. Jan 27, 2013 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    well A not injective on your set, means some difference of vectors in your set is in the kernel of the matrix. in the present example no searching is needed, since all such differences have rational, indeed integer, entries, and there are no non zero rational elements of the kernel of A. you see this just by looking at the entries of A.
     
  4. Jan 27, 2013 #3
    " in the present example no searching is needed, since all such differences have rational, indeed integer, entries, and there are no non zero rational elements of the kernel of A. you see this just by looking at the entries of A."

    It is true for this example. However, in general case, elements of A matrix and the alphabets are complex numbers.

    For example, i could choose my alphabet as

    {-1 -sqrt(2)/2 sqrt(2)/2 1}.

    Then, when A is

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

    x_0 = [-1 -1 sqrt(2)/2 -sqrt(2)/2 ].'
    x_1 = [-1 1 -sqrt(2)/2 sqrt(2)/2 ].'

    both Ax_0 and Ax_1 gives the same result as [-1 0]. I think, as you said

    "A not injective on your set, means some difference of vectors in your set is in the kernel of the matrix."

    is the key sentence for this issue. However, i still don't know how to check this for a set. It is easy to check it for a vector space by calculating the intersection between null space and input space. However, difference of possible x vectors is derived from a set. In other words, it is not a linear combination of possible inputs.

    What am i missing here?
     
  5. Jan 27, 2013 #4
    "However, difference of possible x vectors is derived from a set. In other words, it is not a linear combination of possible inputs."

    I meant i am not interested in all linear combinations of x vectors generated with permutation. I only need to consider subspace of the difference of all x vectors generated with permutation.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook