# Gaussian elimination

• February 1st 2010, 10:25 AM
Migotek84
Gaussian elimination
I have a little problem with this exercise:

Consider system of 4 equations in 4 variables over GF(2).
$
p_1: x_1x_2+x_2x_3+x_2x_4+x_3x_4+x_1+x_3+1=0
$

$
p_2: x_1x_2+x_1x_3+x_1x_4+x_3x_4+x_2+x_3+1=0
$

$
p_3: x_1x_2+x_1x_3+x_2x_3+x_3x_4+x_1+x_4+1=0
$

$
p_4: x_1x_3+x_1x_4+x_2x_3+x_2x_4+1=0
$

Using Gaussian elimination we get:
$
p'_1: x_1x_2+x_2x_3+x_2x_4+x_3x_4+x_1+x_3+1=0
$

$
p'_2: x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_1+x_2=0
$

$
p'_3: x_1x_4+x_2x_3+x_1+x_2+x_3+x_4=0
$

$
p'_4: x_1+x_2+1=0
$

How can I show this?
• February 8th 2010, 09:42 AM
Arczi1984
Use bases:
${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
$p'_1, p'_2, p'_3$
But $p'_4$ is not the same like Yours.
• February 8th 2010, 10:15 AM
Migotek84
Thanks. I check this.
• February 8th 2010, 11:53 AM
Arczi1984
You should very carefully examine papers about Mutants.