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

• acco40
In summary, the conversation discusses the issue of determining whether a mapping from x to y is injective for a given matrix A and alphabet. It is possible to test the injectivity using a permutation set and A matrix, but for larger matrices, a search algorithm would be necessary. However, in some cases, such as the given example, no searching is needed as all differences of vectors have rational or integer entries and there are no non-zero rational elements in the kernel of A. In more general cases with complex numbers, it is still possible to determine injectivity by looking at the entries of A, but the issue of checking for a set instead of a vector space remains.
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.

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.

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

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

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.

## 1. What is the concept of injectivity in a mapping?

Injectivity in a mapping refers to the property of a function where each input has a unique output. In other words, no two different inputs can produce the same output. In the context of the mapping y=Ax for finite alphabet without a search algorithm, this means that each symbol in the input alphabet has a unique corresponding symbol in the output alphabet.

## 2. How is the concept of injectivity relevant in this mapping?

The concept of injectivity is important in this mapping because it ensures that the mapping is one-to-one, meaning that there is a unique mapping for each input symbol. This is necessary in order to accurately represent and preserve the information in the input alphabet.

## 3. How can we prove that the mapping y=Ax is injective for a finite alphabet without a search algorithm?

To prove the injectivity of the mapping y=Ax, we can use a proof by contradiction. Assume that there are two different input symbols that produce the same output symbol. Then, using the properties of matrix multiplication, we can show that this would lead to a contradiction, thus proving that the mapping is injective.

## 4. What are the limitations of using a search algorithm to show injectivity?

Using a search algorithm to show injectivity can be time-consuming and impractical, especially for large alphabets. It also relies on the assumption that all possible input-output pairs have been accounted for in the search, which may not always be the case.

## 5. How is the concept of finite alphabet important in this mapping?

The finite alphabet is important in this mapping because it guarantees that there is a finite number of input-output pairs to consider. This makes it possible to prove the injectivity of the mapping without using a search algorithm, as all possible combinations can be exhaustively checked.

Replies
7
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
1K
Replies
14
Views
2K
Replies
10
Views
3K
Replies
1
Views
2K
Replies
31
Views
2K
Replies
13
Views
2K