CODEWITHSUNDEEP
mathmatrixbinary-data
Salma Nafady
Salma Nafady

Reputation: 341

how to solve an xor'd system of linear equations?


I have this system of equations

a⊕0⊕c⊕0⊕0⊕0=2
0⊕b⊕0⊕d⊕0⊕0=3

a⊕0⊕0⊕0⊕x⊕0=4
0⊕b⊕0⊕0⊕0⊕y=8

0⊕0⊕c⊕0⊕x⊕0=6
0⊕0⊕0⊕d⊕0⊕y=11

⊕ is XOR
when i solve this equations using Gaussian, following Denley Bihari's method here it gives me this:

1 0 1 0 0 0 = 2
0 1 0 1 0 0 = 3
0 0 1 0 1 0 = 6
0 0 0 1 0 1 = 11
0 0 0 0 0 0 = 0
0 0 0 0 0 0 = 0

that's DNE,although the answer is
a=5
b=10
c=7
d=9
x=1
y=2
(I had the constants values first then i formed the equations ofcourse)

so what's the proper way to do this? I've searched the web high and low!
your help is much appreciated

Upvotes: 0

Views: 2730

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183978

Your equations are dependent (as is also shown by the Gaussian elimination leading to all 0 rows), thus you have in fact fewer constraints than variables, therefore multiple solutions.

In this particular case, you have two groups of equations, one involving a, c, x, the other involving b, d, y. Removing the 0s, we obtain

a ⊕ c     =  2
a     ⊕ x =  4
    c ⊕ x =  6

b ⊕ d     =  3
b     ⊕ y =  8
    d ⊕ y = 11

and obviously the last of these three is obtained by XORing the first two in both groups (or, any of the three is obtained by XORing the other two in the group).

So you can pick x and y as parameters, assign arbitrary values to them and find

a =  4 ⊕ x
c =  6 ⊕ x
b =  8 ⊕ y
d = 11 ⊕ y

You can use Gaussian elimination, that either yields a reduced form giving a unique solution (if the number of independent equations equals the number of involved variables), a reduced form with all-0 rows which allows to parametrize the space of all solutions, or a reduced form with a(t least) one row with all coefficients 0 but nonzero right hand side, in which case there are no solutions.

All other methods of solving will yield the same result.

Upvotes: 3

Charles
Charles

Reputation: 11499

What are you solving for? It looks like you have six constants and six constant equations.

Solving equations involving only xor is very easy, in general.

Upvotes: 0

Related Questions