Product of matrices over finite fields

Hi all, can someone please help with the following?

Suppose we have two matrices A and B over the finite field F_2, such that:

A*B=the zero matrix

Suppose that both A and B are 2 by 2 matrices: A=(a&b\\c&d) and B=(e&f\\g&h).

How can I find all the possible combinations of a, b, c, d, e, f, g, and h over the finite field 2 that satisfy the above equation?

Answer 1

[John D'Errico]

Even in the simple case of F_2 matrices, I'm not sure it is easy to do better than brute force. But no, you don't need to write out each matrix product. This seems to work.

m = 3;
% all possible pairs of 2x2 matrices, as base m integers, doubles
[Adoub,Bdoub] = meshgrid(0:m^4-1); 

% convert those "matrices" into pages of 2x2 matrices,
% with each matrix as a plane in a 3-d matrix
Am = reshape(dec2base(Adoub,m)' - '0',[2 2 m^8]);
Bm = reshape(dec2base(Bdoub,m)' - '0',[2 2 m^8]);

% just take the product of all combinations of matrices, in F_m
AB = mod(pagemtimes(Am,Bm),m);

% and test for all zeros
zeroind = all(reshape(AB,[4,m^8]) == 0,1);

table(dec2base(Adoub(zeroind),m),dec2base(Bdoub(zeroind),m))

ans = 417x2 table
    Var1    Var2
    ____    ____

    0000    0000
    0000    0001
    0000    0002
    0000    0010
    0000    0011
    0000    0012
    0000    0020
    0000    0021
    0000    0022
    0000    0100
    0000    0101
    0000    0102
    0000    0110
    0000    0111
    0000    0112
    0000    0120

There are 58 sets of matrices identified for base 2, and 417 for base 3. If m is too large of course, expect things to get nasty in terms of computations, because you will have m^8 such combinations of matrices to deal with.

[Adrian]

Thank you. This really helps

Answer 2

[Torsten]

Just test the 16 x16 = 256 possible products for A and B.

[Adrian]

Thanks. But what if I change the finite field to like F_5 or increase the dimensions of the matrices. I have attempted writing a code (but it does not do what I want it to do) to produce all the different possibilities which I will share later.

[Torsten]

Use M to build A and B:

M = dec2bin(0:15)-'0';

A = 16×4

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

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

[Adrian]

Thanks. What I did, I multiplied A and B together and equated the results to the zero matrix. I then formed 4 equations:

ae+bg = 0

af+bh = 0

ce+dg = 0

cf+dh = 0

which I then solved using:

N = 8;

m= 2;

M = dec2base(0:m^N-1,m)-'0';

idex = mod(M(:,1).*M(:,5),m) == 0 ...

= .....

= .....

= .....

sol = M(idx,:); disp(sol)

Is there a quicker way so that I don't have to multiply the matrices first to define the equations?

[Torsten]

I simply use a loop:

M = dec2bin(0:15)-'0';
count = 0;
for i = 1:16
    A = [M(i,1) M(i,2);M(i,3) M(i,4)];
    for j = 1:16
        B = [M(j,1) M(j,2);M(j,3) M(j,4)];
        AB = mod(A*B,2);
        if all(abs(AB(:)) < 1e-4)
            count = count + 1;
        end
    end
end
count

count = 58

[Adrian]

Thank you. This helps

[John D'Errico]

@Torsten

When everything is integer, you can test for an exact zero. This would be valid unless m was on the order of 1e8, in which case the products would start to overflow flintmax. But for m that large, the process is meaningless, since you would need to generate something on the order of m^8 = 1e64 products of matrices.

[Adrian]

This makes sense. Thank you

[Torsten]

@John D'Errico

When everything is integer, you can test for an exact zero.

So if all variables in a computation are assigned values without decimal points, MATLAB treats them as integers up to the order of 1e8 although their class is double by default ? I'm not that familiar with MATLAB subtleties...

x = 1;
class(x)

ans = 'double'

[Walter Roberson]

@Torsten

IEEE 754 double precision has 52 bits of mantissa. Any integer number up to

2^26

ans = 67108864

is sure to have a minimum of 52-26 = 26 bits of trailing zeros in the representation.

Multiply two such values together and the maximum number of significant bits is 26+26 = 52 and so is exactly representable.

[Torsten]

So whether a number in MATLAB is "integer" is determined by the computational result of an arithmetic operation, not by the class of the numbers that lead to the result ? What exactly tells me if a result must be treated as a double or can be treated as an integer ?

[Adrian]

Hi all - thanks for all the comments. Out of curiosity, have you come accross the programming language MAGMA? I use it for my research in algebraic coding theory. Many problems are heavily computational and MAGMA deals with such problems better then MATLAB.

[Walter Roberson]

@Torsten

Integer:

isinteger(x) || all(x == floor(x),'all')

but even for integer data types, if abs(x) > sqrt(intmax(class(x))) then there is the potential for overflow if two such values get multiplied together. (Of course overflow in integer class only saturates, leaving the same datatype behind... but the point is the results would be inaccurate.)

[Torsten]

@Walter Roberson

Thank you.