# Gaussian elimination

• Feb 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).
\$\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?
• Feb 8th 2010, 09:42 AM
Arczi1984
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.
• Feb 8th 2010, 10:15 AM
Migotek84
Thanks. I check this.
• Feb 8th 2010, 11:53 AM
Arczi1984
You should very carefully examine papers about Mutants.