Results 1 to 11 of 11

Math Help - Linear Transformation help

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    6

    Linear Transformation help

    let GF(2^n) be the extension of the binary field.Let " F " be a linear function, which means F(X+Y)=F(X)+F(Y) and F(0)=0.
    Assume that X,Y are any two elements in the GF(2^n) -the finite field- . The question is can we define a linear function "F" such that F(X)=F(Y), for any X,Y belong to GF(2^n)?? in another word "what kind of function that will look like this?? will do this F(X)=F(Y)???
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    \forall x,y \in GF(2^{n}),\ F(x)=F(y) means F is a constant function. Since F(0)=0, F must be the zero function. But then is it linear?

    \forall x,y\in GF(2^{n}),\ F(x+y)=0=0+0=F(x)+F(y)

    But of course, it's not a field homomorphism.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    6

    Note this.....

    First of all, Thank you so much for helping.. I really appreciate that.

    Well, remember that a finite field or Galois field is a field of order p elements under modulo-p addition and multiplication is denoted by GF(p).
    GF(p) = {0,1,2,... ,p-1} modulo p.

    For p=2, we obtain the binary field GF(2) which has only two elements. In binary arithmetic we use modulo 2 addition and multiplication. This arithmetic is actually equivalent to ordinary arithmetic , except that we consider 2 to be equal 0 which means (1+1=2=0). Note that since (1+1=0) ,then (1=-1).
    GF(2)= {0,1}.

    The extension of the binary field is GF(2^n), where 2^{2^n-1}=1. Therefore ,the set GF(2^n)= {0,1, alpha, alpha^2, alpha^3,..., alpha^{2^n-2}} is a finite field of 2^n elements. Note that the addition and multiplication definied on GF(2^n) imply modulo-2 addition and multiplication . Hence, the binary field GF(2) forms a subfield of GF(2^n)$.
    For exmaple , let n=4 .The polynomial p(X)=1+X+X^4 is the primitive polynomial over GF(2).Set the p(alpha)=1+ alpha + alpha^4 = 0 Then, alpha^4 = 1 + alpha .We can construct GF(2^4) using this relation. The identity (alpha^4=1+alpha) is used repeatedly to form the polynomial representations for the elements of GF(2^4) , and every element could be constructed from the basis (1, alpha,alpha^2,alpha^3).
    ____________
    The only thing I know is that "F" is a linear function, saying that F(0)=0 that's one of the properties of being linear. "F" is defined as:
    F: GF(2^n)->C2*C2*...C2 'n- times'.
    Linear properties are:
    1) F(X+Y) = F(X)+F(Y).
    2) F(aX) = a F(X),where 'a' is a constant.
    this implies that -> F(0)=0

    The question is : What kind of linear function "F" that will satisfy F(X)=F(Y) for any X,Y in the GF(2^n). How to define that linear function??
    Last edited by butterfly4ever; November 18th 2008 at 05:08 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Mhhh... I know finite fields even if I use \mathbb{F}_{p^{n}} instead of GF(p^{n}).

    Ok, what I understood was that F:GF(p^{n})\rightarrow GF(p^{n}).

    But don't you agree that \forall x,y \in GL(p^{n}),\ F(x)=F(y) means that F is a constant function?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2008
    Posts
    6

    clarification

    I am not sure, simply because -> The range of "F" is not a Finite field , it is not GF(2^n).
    F is defined like this :
    F: GF(2^n)-> C2 x C2 x C2... n times

    The range looks like this in case of n=3 {000,010,100,001,110,101,011,111}, note that this is a cyclic group and it is not a finite field.
    Now the problem if I define sets like this:

    Sa={X in GF(2^n) | F(X)= a), where a is a group element belongs to the (C2 x C2 x C2... n times). so for example we may have S101={alpha, alpha^3} in case n=3. SO, there exist a function "F" that can group the two elements from GF(2^n) . MY question is : I want to define a function "F" of course a linear function that will take any X,Y to the same set "S"..the whole idea is I need to know what kind of function that will look like this F(X)=F(Y).

    You said a constant, in may range which is C2 xC2 xC2 how that will look like.

    Thank you so much for your help, I know you are smart
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2008
    Posts
    6

    Please Help

    Let me make the problem clear:
    Assume that given any two elements X,Y from GF(2^n), I know in advance that I have these two elements. I want to find a linear function "F" such that F(X)=F(Y). SO, it is not for all X,Y in GF(2^n). the actual term is the two elements from the GF(2^n), how can I define a linear function such that F(X)=F(Y) knowing that:

    F: GF(2^n) -> C2 x C2 xC2... n times.

    I think the F function should be based and depends on both X, and Y.

    So for example:
    n=3 , which means I know a finite field GF(2^3)= {0, alpha, alpha^1, ..,alpha^6}. If given (X=alpha^4) and my (Y= alpha^2) the problem is how to define a linear function F based on (alpha^4, alpha^2) such that F(alpha^4)=F(alpha^2) ???
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Ahhh ok, x and y given Indeed this is no more the definition of a constant map.
    What do you call C2?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2008
    Posts
    6
    C2 is cyclic group {0,1} , C2 x C2 is {01,10,00,11}, C2 x C2 x C2 ={000,111,101,010,001,110,101,011}.. and so on which means each position will take a value of either "0" or "1".
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    What can GL(2^{n}) and (C_{2})^{n} be considered as? As GL(2^{n}) vector spaces.

    Let F be a linear map and x,y be two different vectors such that F(x)=F(y).
    The line \{0, x-y\} belongs to its kernel.

    Let x and y be two non zero vectors in GL(2^{n}), can they be linearly independent? x and y are dependent iff x=y, so x and y are independent. \{x,y\} can be completed in a basis of GL(2^{n}), to determine F, you have to determine the range of a basis.
    That let you n-1 choices, dim(Range(F))\leq n-1.
    If x=0 and y\neq 0, you build a base \{y,b_{2},...,b_{n}\}, and you also have n-1 choices (what is demanded is F(y)=0)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2008
    Posts
    6
    remember that "F" range is a group. could be C2 only or, C2 xC2 or, C2 xC2 XC2 maximum 'n' times. so it is a group and not a field.. any you know they are different.
    I didn't really get what the "F" function will looks like??
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Yeah but a vector space is first a group. Well, I'm trying to see what the problem really is! But maybe I'm missing some things because of my not-so-good english, so... But if you get a solution, please tell me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 1st 2011, 11:00 PM
  2. Example of a linear transformation T:R^4 --> R^3?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 5th 2011, 08:04 PM
  3. linear transformation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 28th 2009, 07:40 AM
  4. Linear Algebra.Linear Transformation.Help
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 5th 2009, 02:14 PM
  5. Linear Transformation
    Posted in the Pre-Calculus Forum
    Replies: 10
    Last Post: May 25th 2008, 01:14 AM

Search Tags


/mathhelpforum @mathhelpforum