Show Injectivity of Mapping y=Ax for Finite Alphabet w/o Search Algorithm

[acco40]

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.

 

[mathwonk]

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.

 

[acco40]

" 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?

 

[acco40]

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