Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on the problem of solving systems of linear equations over $GF(2)$ using SAT-solver. There is a one step in the algorithm that I don't clearly understand. During this step I need to convert each linear equation in the system to the set of equation no longer than cutting number (which is $C = 4$ in this case). It is described as follows:

Let us have the following linear equation

$$x_1 + x_2 + \ldots + x_l = 0$$

and then it is clearly (not for me...) equivalent to $$ x_1 + x_2 + x_3 + y_1 = 0$$ $$ y_1 + x_6 + x_7 + y_2 = 0$$ $$ \vdots $$ $$ y_i + x_{4i+2} + x_{4i+3} + y_{i+1} = 0$$ $$ \vdots $$ $$ y_h + x_{l-2} + x_{l-1} + x_l = 0$$ So I don't understand where $x_4$ and $x_5$ are and what all $y_i, \space i=1\ldots h$ mean...

Thanks!

Here is the source (page 42).

share|improve this question

1 Answer 1

up vote 1 down vote accepted

It was revealed that it is a typo in the publication. So the correct transformation will be as follows:

Let us have the following linear equation

$$x_1 + x_2 + \ldots + x_l = 0$$

and then it is equivalent to $$ x_1 + x_2 + x_3 + y_1 = 0$$ $$ y_1 + x_4 + x_5 + y_2 = 0$$ $$ \vdots $$ $$ y_i + x_{2i+2} + x_{2i+3} + y_{i+1} = 0$$ $$ \vdots $$ $$ y_h + x_{l-2} + x_{l-1} + x_l = 0$$

It works because of $x_i \in \{0, 1\}, \forall i=1\ldots n$. Hence, we can write $y_1 = x_3 + x_4 + y_2$ and then, substituting this into the first equation, we will get $x_1 + x_2 + x_3 + x_4 + y_2 = 0$. Repeating this procedure for all other $y_i$, we will reclaim original equation $x_1 + x_2 + \ldots + x_l = 0$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.