CODEWITHSUNDEEP
matlabbinarylinear-algebraxor
modou
modou

Reputation: 3

Solve the system AX=B for X over the finite field F2

Let A, B, and X be binary matrices (in F2 ) {0,1} positive values, where A and B are of size n×m with n>m (more equations than variables). X is an m×m matrix. Compute X such that AX=B.

Here, A is not a quadratic matrix.

I have A and B, and I am looking for X. What algorithm should I use to find X?

I have tried 

X=pinv(A)*B; 
X=mod(X,2);

but the results are real values and not binary (elements of finite field F2)

Upvotes: 0

Views: 2238

Answers (1)

user3717023
user3717023

Reputation:

Neither A\B nor pinv(A)*B help you any, because these commands treat matrix entries as real numbers, not as elements of finite field GF(2).

The command gflineq solves linear systems over the field GP(p) with x = gflineq(A,b,p); this command is a part of Communications System Toolbox. If you have the toolbox, then all you need to do is to put the matrix equation AX=B into the form Mx=B by stacking the columns of B, and then reshaping the solution back into matrix form. Like this: 

[n, m] = size(A);
b = B(:);                 % stacked B
M = kron(eye(m), A);      % duplicated A to match
sol = gflineq(M, b, 2);   % solved Mx=b over GF(2)
X = reshape(sol, m, m);   % reshaped into matrix form X

Now, if you don't have the Communications System Toolbox, you'll need to implement solution over GF(2) on your own. The method is standard: Gaussian elimination, and you can find lots of its implementation online. Specifically for binary matrices this algorithm is described in How can I find a solution of binary matrix equation AX = B?

Upvotes: 1

Related Questions