solving binary linear equation in matlab

Question

Consider a binary linear equation of form x*A = b. I want to solve for x, the efficiency way is by avoiding using x = b*inv(A) and instead using x= b/A.But with this command results are not in binary form. I tried the command x = mod(b/A ,2)but still result was not in binary. How to fix this?

example `

x = 1     0     1     1     0     0     0     1     1     0`

and matrix A is

`0     1     0     1     0     0     1     1     1     1
 0     1     1     1     1     1     1     1     0     1
 0     0     1     0     1     1     0     1     1     1
 1     0     0     1     1     1     1     1     1     1
 1     1     0     0     1     1     0     0     0     0
 0     1     1     1     0     1     1     0     1     0
 0     0     1     1     0     0     0     1     0     0
 1     1     1     1     0     1     0     1     1     1
 1     0     1     0     1     1     1     0     1     1
 1     1     1     0     0     0     1     1     0     0`

which is full rank.

then

>> b = mod (x*A,2)

b =

 1     0     1     1     1     0     1     0     1     1

To find x, am getting

>> k = b / A

k =

Columns 1 through 6

1.3750   -0.5000   -0.7500   -0.7500    0.8750   -0.5000

Columns 7 through 10

1.8750   -0.5000    2.1250   -0.7500

or if am using modulus 2, the result is

>> k = mod (b / A,2)

k =

Columns 1 through 6

1.3750    1.5000    1.2500    1.2500    0.8750    1.5000

Columns 7 through 10

1.8750    1.5000    0.1250    1.2500

So ,how can I get x in the same binary form? and by the way matrices are all in class double not galois field

Sizes of A and b? Fields on which their values are defined? Ideally give an example of input data and desired result — Luis Mendo
– Luis Mendo, Commented Jul 14, 2015 at 15:21
What do you mean by "binary" ? I hope you're not entering values like 10110 and hoping that various functions automagically recognize that as a binary number! — Carl Witthoft
– Carl Witthoft, Commented Jul 14, 2015 at 15:27
The matrix A in your example is 10x10 with nonzero determinant. So there is only one solution to the system xA = b , and it's b/A. in general, there is no b made up of zeros and ones that will solve your system — Luis Mendo
– Luis Mendo, Commented Jul 14, 2015 at 16:04
@Luis Mendo I updated my question, in original problem the size of À is 602*602 and b's is 1*602 — Engtyma
– Engtyma, Commented Jul 14, 2015 at 16:05

bern · Accepted Answer · 2015-07-14 22:06:18Z

2

This example at Mathworks shows how to perform boolean matrix inversion with MATLAB and I believe answers your question.

I have not quite gotten it working perfectly, but I believe you need to use a combination of mod() and logical() for example:

A=logical(A);
b=(mod(x*A,2));
inverseA= ~A;
k=mod(b*inverseA,2)

this gives

k=[1 1 0 0 1 1 0 1 0 0]

which is not x, but i think if you play around with the logical function and logical operations in conjunction with mod() you should be able to get it to work

edited Jul 14, 2015 at 22:06

answered Jul 14, 2015 at 15:31

bern

3661 silver badge10 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Engtyma Over a year ago

even with command double() results are not in binary.` >> k = mod (double(x)/double(A),2) k = Columns 1 through 6 1.0000 0 0 1.5000 1.5000 0.5000 Columns 7 through 10 0 0.5000 1.5000 0.5000 `

bern Over a year ago

thanks for the feedback @Engtyma. I edited my answer per your feedback. By making either A, x, or b a logical array, you confine it to containing only 0's and 1's. Hopefully the updated answer can guide you in the right direction

Engtyma · Accepted Answer · 2015-07-14 21:16:56Z

To solvexin binary form, matrix A should be in galois field. consider the following example;

>> x = randi ([0 1],1,10)

x =

 1     1     0     1     1     1     0     1     1     1

>> A = gf (randi([0 1],10,10))

A = GF(2) array.

Array elements =

Columns 1 through 6

       1           1           1           0           0           1
       1           0           1           0           1           0
       1           0           1           1           0           1
       0           0           0           0           0           1
       1           1           1           0           1           1
       0           1           0           1           0           1
       0           0           0           1           1           1
       0           1           0           0           1           0
       0           0           1           0           1           0
       0           0           1           0           0           1

Columns 7 through 10

       1           1           0           0
       1           0           1           1
       1           1           0           0
       0           0           1           0
       1           1           1           1
       0           1           1           1
       1           0           1           0
       1           1           1           0
       1           0           0           0
       1           1           1           0

then,

>> b = x*A

b = GF(2) array.

Array elements =

Columns 1 through 6

       1           0           1           1           0           1

Columns 7 through 10

       0           1           0           1

>> x_solved = b*inv (A)

x_solved = GF(2) array.

Array elements =

Columns 1 through 6

       1           1           0           1           1           1

Columns 7 through 10

       0           1           1           1

As you can see x_solved is the same as the original x. Therefore you should convert matrix A to galois field by just running a codeA = gf(A).

Collectives™ on Stack Overflow

solving binary linear equation in matlab

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related