2
$\begingroup$

I have a equation with 256 variables * 256-dimensional vectors in $\mathbb{Z}_2 $:

$ x_1 \cdot \left(\begin{array}{c} 1\\ 1\\ 1\\ \vdots\\ 0 \end{array}\right) + x_2 \cdot \left(\begin{array}{c} 0\\ 1\\ 1\\ \vdots\\ 0 \end{array}\right) + \cdots + x_{256} \cdot \left(\begin{array}{c} 0\\ 0\\ 0\\ \vdots\\ 1 \end{array}\right) \equiv \left(\begin{array}{c} 1\\ 0\\ 1\\ \vdots\\ 1 \end{array}\right) \mod 2 $

Each variable is either 0 or 1. As I have 256 variables, bruteforcing isn't an option.

How can I solve such an equation?

  • 0
    @Jack: Yes, I k$n$ow how to use Gaussian elimination with real variables. Or with 0,1 and mod 2. But I don't know how to convert such a system. Could you explain it please? (Whats GAP? If you mean the [software](http://en.wikipedia.org/wiki/GAP_computer_algebra_system "GAP software") - that doesn't help me. I have to use python, as this is only a part of my problem.)2011-06-14

1 Answers 1

4

Gaussian elimination works over any field, not just the real numbers; all you have to remember is to do the operations in that field.

Over $\mathbb{Z}_2$ Gaussian elimination is even simpler, because the elementary operation "multiply a row by a nonzero constant" is a trivial operation (the only nonzero constant being $1$).

So all you have to do is perform Gaussian elimination, adding modulo $2$.

For a small example, suppose you had $x_1\left(\begin{array}{c}1\\1\\0\\0\\1\end{array}\right) + x_2\left(\begin{array}{c}0\\1\\1\\1\\0\end{array}\right) + x_3\left(\begin{array}{c}1\\0\\1\\0\\1\end{array}\right) + x_4\left(\begin{array}{c}0\\1\\1\\0\\1\end{array}\right) + x_5\left(\begin{array}{c}1\\1\\1\\1\\1\end{array}\right) \equiv \left(\begin{array}{c}1\\0\\0\\1\\0\end{array}\right)\pmod{2}.$ (I made it up on the fly). Set up the problem for Gaussian elimination the way you would normally: $\left(\begin{array}{ccccc|c} 1 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 \end{array}\right).$ Choose a pivot: the (1,1) entry. Subtract suitable multiples of the first row from the other rows to make the first column below the first entry all zeros; subtracting modulo $2$ is the same as adding modulo $2$, so we add the first row to the second and fifth row; addition is modulo $2$, so $1+1=0$. We get: $\left(\begin{array}{ccccc|c} 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 0 & 1 \end{array}\right).$ Next pivot is the (2,2) entry, and we add the second row to the third and fourth row: $\left(\begin{array}{ccccc|c} 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1 \end{array}\right).$ Shuffle the last three rows (via exchanges) so that the current fourth row is the new row 3, the current fifth row is row 4, current third row is the last row: $\left(\begin{array}{ccccc|c} 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 \end{array}\right).$ This is already in row-echelon form, so you can back-substitute: last line says $x_5=1$; fourth line says $x_4 = 1$; third line says $x_3+x_4+x_5=0$, which means $x_3+1+1=0$; since $1+1\equiv 0 \pmod{2}$, this means $x_3=0$. Then the second line gives $1 = x_2 + x_3 + x_4 = x_2 + 0 + 1 = x_2+1$ so $x_2=0$. And finally, the first line says $1 = x_1 + x_3 + x_5 = x_1 + 0 + 1$ so $x_1=0$. Thus, the (unique) solution is $x_1=x_2=x_3=0$, $x_4=x_5 = 1$, which you can easily verify by plugging in.