Results 1 to 11 of 11

Thread: 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
    $\displaystyle \forall x,y \in GF(2^{n}),\ F(x)=F(y)$ means $\displaystyle F$ is a constant function. Since $\displaystyle F(0)=0, F$ must be the zero function. But then is it linear?

    $\displaystyle \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; Nov 18th 2008 at 04: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 $\displaystyle \mathbb{F}_{p^{n}}$ instead of $\displaystyle GF(p^{n})$.

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

    But don't you agree that $\displaystyle \forall x,y \in GL(p^{n}),\ F(x)=F(y)$ means that $\displaystyle 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, $\displaystyle x$ and $\displaystyle 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 $\displaystyle GL(2^{n})$ and $\displaystyle (C_{2})^{n}$ be considered as? As $\displaystyle GL(2^{n})$ vector spaces.

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

    Let $\displaystyle x$ and $\displaystyle y$ be two non zero vectors in $\displaystyle GL(2^{n})$, can they be linearly independent? $\displaystyle x$ and $\displaystyle y$ are dependent iff $\displaystyle x=y$, so $\displaystyle x$ and $\displaystyle y$ are independent. $\displaystyle \{x,y\}$ can be completed in a basis of $\displaystyle GL(2^{n})$, to determine $\displaystyle F$, you have to determine the range of a basis.
    That let you $\displaystyle n-1$ choices, $\displaystyle dim(Range(F))\leq n-1$.
    If $\displaystyle x=0$ and $\displaystyle y\neq 0$, you build a base $\displaystyle \{y,b_{2},...,b_{n}\}$, and you also have $\displaystyle n-1$ choices (what is demanded is $\displaystyle 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: Aug 1st 2011, 10:00 PM
  2. Example of a linear transformation T:R^4 --> R^3?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Apr 5th 2011, 07:04 PM
  3. linear transformation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 28th 2009, 06:40 AM
  4. Linear Algebra.Linear Transformation.Help
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 5th 2009, 01:14 PM
  5. Linear Transformation
    Posted in the Pre-Calculus Forum
    Replies: 10
    Last Post: May 25th 2008, 12:14 AM

Search Tags


/mathhelpforum @mathhelpforum