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!

Printable View

- September 26th 2010, 07:29 AMSuyF2 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! - September 26th 2010, 08:04 AMHappyJoe
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. - September 26th 2010, 08:59 AMSuy
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.. - September 26th 2010, 09:31 AMtonio
- September 26th 2010, 09:41 AMHappyJoe
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. - September 26th 2010, 09:45 AMSuy
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!!