# Thread: Gaussian elimination

1. ## Gaussian elimination

I have a little problem with this exercise:

Consider system of 4 equations in 4 variables over GF(2).
$\displaystyle p_1: x_1x_2+x_2x_3+x_2x_4+x_3x_4+x_1+x_3+1=0$
$\displaystyle p_2: x_1x_2+x_1x_3+x_1x_4+x_3x_4+x_2+x_3+1=0$
$\displaystyle p_3: x_1x_2+x_1x_3+x_2x_3+x_3x_4+x_1+x_4+1=0$
$\displaystyle p_4: x_1x_3+x_1x_4+x_2x_3+x_2x_4+1=0$

Using Gaussian elimination we get:
$\displaystyle p'_1: x_1x_2+x_2x_3+x_2x_4+x_3x_4+x_1+x_3+1=0$
$\displaystyle p'_2: x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_1+x_2=0$
$\displaystyle p'_3: x_1x_4+x_2x_3+x_1+x_2+x_3+x_4=0$
$\displaystyle p'_4: x_1+x_2+1=0$

How can I show this?

2. Use bases:
$\displaystyle {x_1x_2, x_1x_3, x_1x_4, x_2x_3, x_2x_4, x_3x_4, x_1, x_2, x_3, x_4, 1}$.
Then write equations in matrix form:

|1 0 0 1 1 1 1 0 1 0 1|
|1 1 1 0 0 1 0 1 1 0 1|
|1 1 0 1 0 1 1 0 0 1 1| = A (sorry for that form - latex command doesn't work)
|0 1 1 1 1 0 0 0 0 0 1|

And now bring A into the row echelon form using Gaussian elimination.
You get then
$\displaystyle p'_1, p'_2, p'_3$
But $\displaystyle p'_4$ is not the same like Yours.

3. Thanks. I check this.

4. You should very carefully examine papers about Mutants.