Results 1 to 6 of 6

Math Help - F2 binary field

  1. #1
    Suy
    Suy is offline
    Newbie
    Joined
    Sep 2010
    Posts
    12

    F2 binary field

    A system of m equations over F2 in n unknowns has exactly 2^(n−m) solutions. • A. True • B. False?

    answer is false
    I don't understand why
    please also explain the relationship between power of 2 and F2 binary field
    thx!
    Last edited by Suy; September 26th 2010 at 08:43 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    The question doesn't assume that the equations are independent, which might add redundancy when solving them, and it doesn't assume that the equations are linear, in which case you are not guaranteed a solution at all.

    Anyway, the equations are probably assumed implicitly to be linear, and you need to think in terms of free variables. If you are solving your system of linear equations, and you end up with, say, 7 free variables, then for each combination of choices of values for these free variables, the set of linear equations has a solution. But since each variable can take values in F_2 (giving 2 choices for each variable), this makes a total of 2^7 choices.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Suy
    Suy is offline
    Newbie
    Joined
    Sep 2010
    Posts
    12
    I see, thank you so much...
    I asked so many forum, but no one answered...
    Can you also explain

    __________________________________
    "general rule
    2^(# of variable - # of equation)
    --------
    x+y =0
    y+z=0
    (0,0,1)
    (1,1,0)
    2 solution
    2^1=2
    ---------
    "
    ________________________________

    It was in my note, but it's not very clear..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Suy View Post
    I see, thank you so much...
    I asked so many forum, but no one answered...
    Can you also explain

    __________________________________
    "general rule
    2^(# of variable - # of equation)
    --------
    x+y =0
    y+z=0
    (0,0,1)
    (1,1,0)
    2 solution

    None of the two above are solutions to that system: neither (0,0,1) nor (1,1,0) are asolution to y+z=0...

    Solutions are ,for example, (0,0,0),\,(1,1,1)...can you find more?

    Tonio



    2^1=2
    ---------
    "
    ________________________________

    It was in my note, but it's not very clear..
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    Quote Originally Posted by Suy View Post
    I see, thank you so much...
    I asked so many forum, but no one answered...
    Can you also explain

    __________________________________
    "general rule
    2^(# of variable - # of equation)
    --------
    x+y =0
    y+z=0
    (0,0,1)
    (1,1,0)
    2 solution
    2^1=2
    ---------
    "
    ________________________________

    It was in my note, but it's not very clear..
    Sure. But I'm not certain what the deal is with the triples (0,0,1) and (1,1,0). Maybe they are supposed to be the two solutions of the system, but they are not. Instead, the two solutions are (0,0,0) and (1,1,1).

    To see this, just treat the system like any old system of linear equations. If you like, you may plug it into a matrix and start row reducing it. Usually, one has the last variable (here z) as the free variable, so add the equation y+z = 0 to the equation x+y = 0 to obtain x+2y+z = 0. Since we are in F_2, we have 2=0, whereas this last equation is x+z=0. So you have now the two equations x+z=0 and y+z=0, where z is the free variable. The equations are equivalent to x = -z and y = -z. But remember that in F_2, we have -z=z (signs don't matter in F_2), so we have x = z and y = z.
    So both x and y are completely determined by z. In other words, whenever you choose a value for z, this will automatically force some value on both x and y. There are two possible choices for z (either 0 or 1).

    Letting z = 0 gives x=0 and y=0, and the solution (0,0,0).
    Letting z = 1 gives x=1 and y=1, and the solution (1,1,1).

    So a total number of 2 solutions.

    Notice that this is consistent with the "general rule". You have 3 variables and 2 equations, so # of variables - # of equations = 1, and 2^1 = 2, which was exactly the number of solutions.

    In general, if you have m linear _independent_ equation in n variables, then the number of free variables will be n-m. Assigning a value to each of these free variables completely determines a solutions - and each of the free variables can be chosen in 2 ways.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Suy
    Suy is offline
    Newbie
    Joined
    Sep 2010
    Posts
    12
    sorry , I typed wrong
    it should be
    x+y =0
    y+z=1
    (0,0,1)
    (1,1,0)
    2 solution


    your explanation is very clear,ty!!
    Last edited by Suy; September 26th 2010 at 11:05 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ring, field, Galois-Field, Vector Space
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 15th 2012, 04:25 PM
  2. Splitting Field of a Polynomial over a Finite Field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2011, 04:45 PM
  3. Binary
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 20th 2009, 09:30 PM
  4. Field of char p>0 & splitting field
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 22nd 2009, 01:20 AM
  5. Binary
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 1st 2008, 01:28 PM

Search Tags


/mathhelpforum @mathhelpforum