My Math Forum One-to-One Mapping

 Abstract Algebra Abstract Algebra Math Forum

 January 25th, 2013, 03:30 PM #1 Newbie   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.
 January 25th, 2013, 11: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).
 January 26th, 2013, 07:29 AM #3 Newbie   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.

 Tags mapping, onetoone

### how to determine matrices surjective or injectivd

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Taladhis Abstract Algebra 6 February 1st, 2013 05:56 PM alip Complex Analysis 0 March 15th, 2011 07:35 AM chenmq1990 Real Analysis 2 March 12th, 2011 02:40 PM tinynerdi Number Theory 4 August 11th, 2010 11:22 PM BigPete Complex Analysis 1 June 10th, 2010 02:22 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top