# how to solve system of linear equations of XOR operation?

how can i solve this set of equations ? to get values of $x,y,z,w$ ?
\begin{aligned} 1=x \oplus y \oplus z \end{aligned} \begin{aligned}1=x \oplus y \oplus w \end{aligned} \begin{aligned}0=x \oplus w \oplus z \end{aligned} \begin{aligned}1=w \oplus y \oplus z \end{aligned}

this is not a real example, the variables don't have to make sense, i just want to know the method.

-
As for every linear system. Recall that XOR is just addition modulo 2. – martini Jul 12 '12 at 13:04

As I wrote in my comment, you can just use any method you now for solving linear systems, I will use Gauss:

$$\begin{array}{cccc|c||l} \hline x & y & z & w &\ & \\ \hline\hline 1 & 1 & 1 & 0 & 1 & \\ 1 & 1 & 0 & 1 & 1 & \text{+ I}\\ 1 & 0 & 1 & 1 & 0 & \text{+ I}\\ 0 & 1 & 1 & 1 & 1 & \\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \text{III}\\ 0 & 1 & 0 & 1 & 1 & \text{II}\\ 0 & 1 & 1 & 1 & 1 & \text{+ III}\\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 1 & 0 & 1 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \\ 0 & 0 & 1 & 0 & 0 & \text{+ III}\\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 1 & 0 & 1 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \\ 0 & 0 & 0 & 1 & 0 & \\\hline \end{array}$$ Now we can conclude $w = 0$ from line 4, which gives $z = 0$ from 3 and $y = 1$ from 2, and finally $x = 0$. So $(x,y,z,w) = (0,1,0,0)$ is the only solution.

-
can you explain please martini ? :) – Salma Nafady Jul 12 '12 at 13:25
@SalmaNafady Do you know Gauss' elemination method (see for example here)? – martini Jul 12 '12 at 13:27
Thanks for the answer martini :) one more thing, what if the variables are matrices? ex: [1,0,0,1]=x⊕y⊕z [0,1,0,1]=x⊕y⊕w etc ? – Salma Nafady Jul 12 '12 at 16:30
Just consider each component seperately ... – martini Jul 12 '12 at 20:13
im having a hard time understanding how gaussian works when using binary, especially with multiplication and division.. can you explain to me using your own words? :) – Salma Nafady Jul 14 '12 at 15:59

I'll try it the 'artisanal way'.

These four rules should be enough : \begin{align} &x\oplus 0=x\\ &x\oplus 1=\overline{x}\\ &x\oplus x=0\\ &x\oplus \overline{x}=1\\ \end{align}

$\tag{1}1=x\oplus y\oplus z$
$\tag{2}1=x\oplus y\oplus w$
$\tag{3}0=x\oplus w\oplus z$
$\tag{4}1=w\oplus y\oplus z$

Applying $x\oplus$ on the three first equations and $w\oplus$ on the last gives :

$\tag{5}\overline{x}=y\oplus z$
$\tag{6}\overline{x}=y\oplus w$
$\tag{7}x= w\oplus z$
$\tag{8}\overline{w}=y\oplus z$

$(6)\oplus(7)\$ gives $\ \tag{6'}1=y\oplus z$ so that from $(8)$ $w=0$
from $(7)$ and $(6)$ $\ x=z$ and $\ \overline{x}=y$
from $(5)$ $\ \overline{x}=1$ and the final conclusion :
$$(w,x,y,z)=(0,0,1,0)$$ as found (earlier) by martini...

-

As others have noted, all the usual methods of solving systems of linear equations (such as Gaussian elimination) in the field of real numbers work just as well in the finite field of integers modulo 2, also known as $GF(2)$.

In this field, addition corresponds to the XOR operation, while multiplication corresponds to AND (as it does in the reals, if the operands are restricted to $0$ and $1$). As both $0$ and $1$ are their own additive inverses in $GF(2)$ (since $0 \oplus 0 = 1 \oplus 1 = 0$), subtraction is also equivalent to XOR, while division is trivial (dividing by $1$ does nothing, dividing by $0$ is undefined).

So, let's try solving your example equations. Since martini already did Gaussian elimination, let me do Gauss–Jordan:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 1x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 1x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$$

The first coefficient of the first equation is already $1$, so we just subtract (XOR) that equation from the second and the third:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$$

Now the second coefficient of the second equation is $0$, so we need to choose some later row that has a $1$ for that coefficient and swap those rows:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$$

... and then subtract that row from all the others with a non-zero second coefficient:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 0w & = & 0 \\ \end{array}$$

Then we subtract the third row from those with a non-zero third coefficient:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 0z & \oplus & 0w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 0y & \oplus & 0z & \oplus & 1w & = & 0 \\ \end{array}$$

... and finally the fourth row from those with a non-zero fourth coefficient:

$$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 0z & \oplus & 0w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 0w & = & 0 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 0y & \oplus & 0z & \oplus & 1w & = & 0 \\ \end{array}$$

And now we can read out the result: $x = 0$, $y = 0$, $z = 1$, $w = 0$.

-

The other answers are fine, but you can use even more elementary (if somewhat ad hoc) methods, just as you might with an ordinary system of linear equations over $\Bbb R$. You have this system:

\left\{\begin{align*} 1&=x\oplus y\oplus z\\ 1&=x\oplus y\oplus w\\ 0&=x\oplus w\oplus z\\ 1&=w\oplus y\oplus z \end{align*}\right.

\begin{align*} (x\oplus y\oplus z)\oplus(x\oplus y\oplus w)&=(z\oplus w)\oplus\Big((x\oplus y)\oplus(x\oplus y)\Big)\\ &=z\oplus w\oplus 0\\ &=z\oplus w\;, \end{align*}

and $1\oplus 1=0$, so you get $z+w=0$. Substitue this into the last two equations to get $0=x\oplus 0=x$ and $1=y\oplus 0=y$. Now you know that $x=0$ and $y=1$ so $x\oplus y=1$. Substituting this into the first two equations, we find that $1=1\oplus z$ and $1=1\oplus w$. Add $1$ to both sides to get $0=z$ and $0=w$. The solution is therefore $x=0,y=1,z=0,w=0$.

-

Fast Walsh–Hadamard Transform used to solve system of boolean linear equations with distorted right-hand sides. See implementation on https://fwht.codeplex.com/

-

as stated:

$(x \oplus y) \oplus z = 1 = (x \oplus y) \oplus w \Longrightarrow z = w$

as stated:

$x \oplus ( y \oplus w ) = 1 = ( w \oplus y ) \oplus z \Longrightarrow x = z$ (AS $a \oplus b = b \oplus a$ ) SO $x = z = w$

substitute our 2nd conclusion:

$0 = x \oplus w \oplus z = x \oplus x \oplus z = 0 \oplus z = z \Longrightarrow x = z = w = 0$ (AS $a \oplus a = 0$)

substitute our 3rd conclusion:

$1 = x \oplus y \oplus w = 0 \oplus y \oplus 0 = 0 \oplus y = y \Longrightarrow y = 1$

-