# Transforming linear equation over $GF(2)$ to system of the equations

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).

-

$$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$.