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.

 

[blue_raver22]

To show injectivity of the mapping y=Ax for a finite alphabet without using a search algorithm, one approach would be to use the rank-nullity theorem. The rank-nullity theorem states that for a linear transformation T: V -> W, the dimension of the null space of T (i.e. the set of all vectors in V that are mapped to the zero vector in W) is equal to the dimension of the domain V minus the dimension of the range of T.

In this case, the linear transformation T is defined by the matrix A and the finite alphabet is the domain V. If we can show that the null space of T is empty, then we can conclude that the mapping y=Ax is injective for the given A and alphabet.

To show that the null space is empty, we can use the fact that the matrix A has more columns than rows (m>n). This means that the columns of A are linearly independent, and therefore, the null space of A is empty.

Furthermore, since x takes its values from a finite alphabet, the number of possible combinations of x is finite. This means that for each possible input x, there is a unique output y=Ax.

Therefore, we can conclude that the mapping y=Ax is injective for the given A and alphabet without using a search algorithm.