My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum

LinkBack Thread Tools Display Modes
January 25th, 2013, 02:30 PM   #1
Joined: Jan 2013

Posts: 2
Thanks: 0

One-to-One Mapping

I have a quick question:

Let y=Ax

A is a matrix n by m, m>n, and its rank is n.
x gets its values from a finite alphabet.

How can i show if the mapping from x to y is one-to-one or injective for given A and alphabet (beside a search method)? Could you suggest me reference on this problem?

Best wishes.
acco40 is offline  
January 25th, 2013, 10:11 PM   #2
Senior Member
Joined: Mar 2012

Posts: 294
Thanks: 88

Re: One-to-One Mapping

what is x supposed to be?

the fact that A has rank n and is nxm means it is of full rank. this means A is surjective, not injective (x lives in m-space, y lives in n-space. m-space is bigger, so in general A is NOT going to be injective). for example let A =

[1 0 0]
[0 1 0]

then A(1,0,1) = A(1,0,0) = (1,0).
Deveno is offline  
January 26th, 2013, 06:29 AM   #3
Joined: Jan 2013

Posts: 2
Thanks: 0

Re: One-to-One Mapping

In your example, yes, you are right. It is not injective since A(1,0,1) = A(1,0,0) = (1,0). This is a good example. But, we can find opposite examples.

Let's A (n x m matrix) and the alphabet be

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

and {1, -1}

respectively. For this alphabet, for example, 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 you map larger space to smaller space!

It is possible to test the injectivity with this scale. However, when you have larger matrices, search algorithm (testing all mappings) would take very long. If i can, i would like to verify it without a search algorithm.

I am not sure but this question might be related with crypto algorithms. How do you make sure that a crypto algorithm gives yields one-to-one mapping? They also map a finite domain to another finite domain. But, input space is massive. You cannot test all possible inputs.
acco40 is offline  

  My Math Forum > College Math Forum > Abstract Algebra

mapping, onetoone

Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
mapping Taladhis Abstract Algebra 6 February 1st, 2013 04:56 PM
mapping alip Complex Analysis 0 March 15th, 2011 06:35 AM
one-one mapping between R and R^2 chenmq1990 Real Analysis 2 March 12th, 2011 01:40 PM
mapping tinynerdi Number Theory 4 August 11th, 2010 10:22 PM
Mapping BigPete Complex Analysis 1 June 10th, 2010 01:22 PM

Copyright © 2018 My Math Forum. All rights reserved.