Dtyjlui

Given XOR values of 3 indices how can we find the numbers?
Like say if I have indices from 1 to 7, how can I find the numbers by given XOR values?

I have:

1. $X_{1} oplus X_{3} oplus X_{5}=V_1$




2. $X_{1} oplus X_{3} oplus X_{6}=V_2$



3. $X_{1} oplus X_{4} oplus X_{6}=V_3$


4. $X_{2} oplus X_{4} oplus X_{6}=V_4$


5. $X_{2} oplus X_{4} oplus X_{7}=V_5$


6. $X_{2} oplus X_{5} oplus X_{7}=V_6$


7. $X_{3} oplus X_{5} oplus X_{7}=V_7$

How can I find any $X_{i}$ from the above data? Is there any pattern?

Guide:

Let me solve for $X_7$.

First, I will compute $$X_1 oplus ldots oplus X_7 = V_1 oplus ldots oplus V_7$$

Then I can compute

$$X_1 oplus X_2 oplus X_3 oplus X_4 oplus X_5 oplus X_6 = V_1 oplus V_4$$

by considering the first and the fourth.

Now, we can compute $X_7$ by summing these two equations.

Build the matrix $A$ in which the entry $A_{i,j}$ is $1$ if in the $i$th equation there is $X_j$ appearing on the left hand side and $0$ otherwise.

The XOR system is equivalent to the following system of linear equations over the field $mathbb F_2$:
$$
left(
begin{array}{ccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 0 \
1 & 0 & 1 & 0 & 0 & 1 & 0 \
1 & 0 & 0 & 1 & 0 & 1 & 0 \
0 & 1 & 0 & 1 & 0 & 1 & 0 \
0 & 1 & 0 & 1 & 0 & 0 & 1 \
0 & 1 & 0 & 0 & 1 & 0 & 1 \
0 & 0 & 1 & 0 & 1 & 0 & 1 \
end{array}
right) cdot
begin{pmatrix} X_1\X_2\X_3\X_4\X_5\X_6\X_7 end{pmatrix}
=
begin{pmatrix} V_1\V_2\V_3\V_4\V_5\V_6\V_7 end{pmatrix}
$$

The matrix on the left is the matrix $A$ that I made you build at the beginning.

The system is certainly solvable if the matrix $A$ is invertible in $mathbb F_2$.

In our case, $det(A)=-3$, so it is possible to solve the system.

This is the inverse matrix:
$$
left(
begin{array}{ccccccc}
1 & 1 & 1 & 0 & 1 & 1 & 0 \
1 & 1 & 0 & 1 & 1 & 1 & 0 \
1 & 1 & 0 & 1 & 1 & 0 & 1 \
1 & 0 & 1 & 1 & 1 & 0 & 1 \
1 & 0 & 1 & 1 & 0 & 1 & 1 \
0 & 1 & 1 & 1 & 0 & 1 & 1 \
0 & 1 & 1 & 0 & 1 & 1 & 1 \
end{array}
right) .
$$
To compute $X_i$, read the $i$th row and look for the columns where $1$ is present. Those are the indices of your original equations that you have to XOR together. For instance, for $X_1$ you have to XOR together
$$
X_1 = V_1 oplus V_2 oplus V_3 oplus V_5 oplus V_6 .
$$

Take XOR of all equations. This tells you that

$$ X_{1} oplus X_{2} oplus dots X_{7}=V_1 oplus V_2 oplus dots V_7 .$$

Now, to find value of any particular $X_i$ take xor of two equations where all variables except $X_i$ appear and then xor with the xor of all seven.

For instance, (1)&(4) gives you $X_7$, (1)&(5) gives you $X_6$ and so on.

If we XOR lines 1 and 2, we get
$$
X_5oplus X_6 = V_1oplus V_2
$$
XORing lines 4 and 5 gives us
$$
X_6oplus X_7 = V_4oplus V_5
$$
XORing these two together, we get
$$
X_5oplus X_7 = V_1oplus V_2oplus V_4oplus V_5
$$
Finally, XORing this with either line 6 or 7 gives us $X_2$ and $X_3$ respectively.

From this you should be able to squeeze out the remaining unknowns. Just be clever about which lines you XOR, and keep track of what you already know so that you can hope to eliminate those at every turn.