January 25th, 2013, 02:30 PM  #1 
Newbie Joined: Jan 2013 Posts: 2 Thanks: 0  OnetoOne 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 onetoone or injective for given A and alphabet (beside a search method)? Could you suggest me reference on this problem? Best wishes. 
January 25th, 2013, 10:11 PM  #2 
Senior Member Joined: Mar 2012 Posts: 294 Thanks: 88  Re: OnetoOne 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 mspace, y lives in nspace. mspace 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). 
January 26th, 2013, 06:29 AM  #3 
Newbie Joined: Jan 2013 Posts: 2 Thanks: 0  Re: OnetoOne 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 onetoone 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 onetoone mapping? They also map a finite domain to another finite domain. But, input space is massive. You cannot test all possible inputs. 

Tags 
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 
oneone 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 