How to solve a system of equations written using XOR?

Question

How to solve a bunch of linear equations written like:-

AXORBXORC=a

BXORCXORD=b

CXORDXORE=c

DXOREXORF=d

EXORFXORG=e

FXORGXORH=f

GXORHXORI=g

HXORIXORA=h

IXORAXORB=i

Where {a,b,c,d,e,f,g,h,i} are all known and {A,B,C,D,E,F,G,H,I} are unknown?

Answer 1

The answer to your question : according to the RHS values, this system has either 4 solutions or no solution. Let us prove it in two ways :

1) First way : Taking into account the specificity of this system.

One can see that, if $u=(u_1,u_2,\cdots u_9)$ designates the unknown vector, being given the values of the first unknowns $A$ and $B$ (alias $u(1)$ and $u(2)$), we have a deterministic way to find the other unknowns ; deterministic ? Yes but at the end this sequence has to fulfill a double condition, in order that the "data cycling" works well. This can be understood rather directly by following line by line the following Matlab program :

Z=rand(1,9)>0.5, %random RHS (i.e., known) vector
S=[];
for A=0:1
   for B=0:1
      u=zeros(1,9);
      u(1)=A;u(2)=B;
      for c=1:7
         u(c+2)=Z(c)-(u(c)+u(c+1));% or Z(c)+(u(c)+u(c+1)) because +1=-1 mod 2
      end;
      if mod(u(8)+u(9)+u(1),2)==Z(8) && mod(u(9)+u(1)+u(2),2)==Z(9);
         S=[S;mod(u,2)];% a sol. has been found and added to others
      end;
   end;
end;
S, % display of the set of solutions, either void or with 4 solutions (in rows).

Explanation : unrolling the way values of $u_3 \cdots u_9$ have been calculated, one gets :

$$\begin{array}[lcr] u_1&=&A\\ u_2&=&B\\ u_3&=&A+B-Z_1\\ u_4&=&A+2-(Z_1+Z_2)\\ u_5&=&2A+3B-(2Z_1+Z_2+Z_3)\\ \cdots&=&\cdots\\ u_8&=&8A+13B-(8Z_1+5Z_2+3Z_3+2Z_4+Z_5+Z_6)\\ u_9&=&13A+21B+13Z_1+8Z_2+5Z_3+3Z_4+2Z_5+Z_6+Z_7 \end{array} $$

(we have volontarily kept the integer values, leaving the reduction modulo 2 for the last step : it allows in particular to see that the coefficients are the beginning of a Fibonacci sequence). Then the conditions that can be found in the "if" condition of the program become :

$$22A+34B+21z_1+13z_2+8z_3+5z_4+3z_5+2z_6+z_7=z_8 \ \text{and} \ \ 14A+22B+13z_1+8z_2+5z_3+3z_4+2z_5+z_6+z_7=z_9.$$

Taking them modulo 2 yield conditions :

$$z_1+z_2+z_4+z_5+z_7=z_8 \ \text{and} \ \ z_1+z_3+z_4+z_6+z_7=z_9 \tag{1}$$

$A$ and $B$ have disappeared ! As an immediate consequence, either conditions (1) are fulfilled and for any of the 4 choices $(A,B)=(0,0), (0,1), (1,0), (1,1)$, there is a (different) solution. Or they aren't fulfilled : in this last case, no solution exists. We have proven the assertion given at the beginning of this answer.

An important remark is that the system of 9 equations above can be written as a unique vector equation under the form :

$$U=aK_1+bK_2+MY$$

for certain $7 \times 7$ matrix $M$ and certain vectors $K_1$ and $K_2$. This will be best understood after having seen the second part which begins now.

2) 2nd way : taking a reasoning that could be transferable to any other sort of linear system (with the specificity of boolean values).

Let us first write this system under the following form :

$$\underbrace{\begin{pmatrix} A\\B\\C\\D\\E\\F\\G\\H\\I \end{pmatrix}}_V=\underbrace{\begin{pmatrix} 1&1&1&0&0&0&0&0&0\\ 0&1&1&1&0&0&0&0&0\\ 0&0&1&1&1&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&1&1&1&0&0\\ 0&0&0&0&0&1&1&1&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&0&0&0&0&1&1\\ 1&1&0&0&0&0&0&0&1 \end{pmatrix}}_M \underbrace{\begin{pmatrix} a\\b\\c\\d\\e\\f\\g\\h\\i \end{pmatrix}}_v.$$

$M$ is not full-rank : its rank is 7, not 9.

As a consequence, it hasn't an inverse (it would be so simple to write $v=M^{-1}V$ !). Thus, $M$ has a dimension 2 kernel (that will prove useful later on), a basis of which is :

$$K_1=(-1,1,0,-1,1,0,-1,1,0) \ \ \text{and} \ \ K_2=(0,1,-1,0,1,-1,0,1,-1)$$

Till now, all what we have said was compatible with real numbers and ordinary addition ; it's time now to restrict ourselves to the set $\{0,1\}$ and xor addition $\oplus$ ; in particular $-1$ is the same as $1$ ; thus a basis for the kernel is :

$$K_1=(1,1,0,1,1,0,1,1,0) \ \ \text{and} \ \ K_2=(0,1,1,0,1,1,0,1,1) \tag{2}$$

What are the consequences ?

• Case a) either vector $v=(a,b,c...i)$ belongs to the so-called range space of matrix $M$ which is 7-dimensional ($7=9-2$) and there will be a solution vector $V=(A,B,C,\cdots I).$ (explanation : the range space is nothing else that the set of linear combinations of the columns of matrix $M$).

• Case b) or it is not in this range space : in this case, there is no solution vector $V$.

Let us give examples :

• for case a), taking $v=(a,b,c,d,e,f,g,h,i)=(1,1,1,1,1,1,1,1,1)$, we have a first (evident) solution $V_1=(A,B,C,D,E,F,G,H,I)=(1,1,1,1,1,1,1,1,1)$, but there are 3 other solutions :

$$V_2=(0,0,1,0,0,1,0,0,1), V_3=(1,0,0,1,0,0,1,0,0), V_4=(0,1,0,0,1,0,0,1,0).$$

Why that ? Because, once we know a particular solution $X_0$ to a linear system $AX=B$, the general solution is $X=X_0+K$ obtained by adding to this particular solution all the kernel (see (2)); let us check it :

$$ V_2=V_1+K_1, \ \ V_3=V_1+K_2, \ \ V_3=V_1+K_2, \ \ V_4=V_1+K_1+K_2 $$

• example for case b) : take $(a,b,c,d,e,f,g,h,i)=(1,0,0,0,0,0,0,0,0)$ : there is no solution (as can be verified by an exhaustive search).

Rows (8) and (9) in matrix $M$ can be expressed resp. under the form of the following rows combination :

$$(8)=(1)+(2)+(4)+(5)+(7) \ \ \text{and} \ \ (9)=(1)+(3)+(4)+(6)+(7) \tag{2}$$

Thus, in order to preserve the compatibility of these equations, the same relationships must exist on the RHSs, providing a double criteria for warranting solutions (i.e., being in case a) ; in view of (2), one must have :

$$h=a+b+d+e+g \ \ \text{and} \ \ i=a+c+d+f+g \tag{3}$$

said otherwise : only RHSs $(a,b,c,d,e,f,g,h,i)$ verifying conditions (3) will give the 4 solutions of case a). We have found back the conditions of the first part.

Here is a Matlab program that does the job for random entries $a,b,c,...$ :

clear all;hold on;
K1=[1,1,0,1,1,0,1,1,0];K2=[0,1,1,0,1,1,0,1,1];% kernel basis
M=[1 1 1 0 0 0 0 0 0
   0 1 1 1 0 0 0 0 0
   0 0 1 1 1 0 0 0 0
   0 0 0 1 1 1 0 0 0
   0 0 0 0 1 1 1 0 0
   0 0 0 0 0 1 1 1 0
   0 0 0 0 0 0 1 1 1
   1 0 0 0 0 0 0 1 1
   1 1 0 0 0 0 0 0 1];
A=M(1:7,1:7);B=M(1:7,8:9);
C=M(8:9,1:7);D=M(8:9,8:9);
Z=rand(1,9)>0.5;% random RHS (a,b,c,...i)
U=Z(1:7)';V=Z(8:9)';
% We have thus to solve the following system :
% AX+BY=U  (1)
% CX+DY=V  (2)
% U,V known ; X,Y unknown                                                   
% (2) corresponds to the 2 last equations ; they can be 
% dropped down if and only if certain compatibility equations
% are fulfilled (see the 'if' condition later on)
% thus, (1) becomes : X=A^(-1)*(U-B*V); (we are free to take Y = U).
if mod(sum(Z([1,2,4,5,7])),2)==Z(8) && mod(sum(Z([1,3,4,6,7])),2)==Z(9)
   X=inv(A)*(U-B*V);
   R=mod([X;V],2);
   disp('4 solutions :')
   mod([R';R'+K1;R'+K2;R'+K1+K2],2)
else
   disp('No solution')
end;

Remark : This question has some common points with a question I contributed to solve a few days ago : https://math.stackexchange.com/q/3029158 .