Octave: matrix multiplication over a group

Question

I'd like to simply compute multiplication of two matrices.

But instead of real numbers I'd like to use elements of a finite group in the matrix. Namely I want to use elements of F4={0,1,x,1+x} (so i only have 4 possible elements). In this group, addition and multiplication are well-defined, and the relations x^2=1+x, 1+1=0 and x+x=0 hold.

Since I'm a beginner at programming in Octave, I have no idea how to compute operations with something different than real numbers.

My idea was, that if it's possible to define some operations on a certain set of elements (here F4), then it's maybe possible to use these operations when multiplicating matrices.

You won't be able to re-use the existing * operator, but you could create a class for this group, and overload the mtimes method. Either way, you'll have to write out the multiplication explicitly. — Cris Luengo
Also: enumerators are not yet supported in Octave, so you'll need to represent your group as integers: {0,1,2,3}. This shouldn't affect generality, and you could even write a special print function to output 2 as "x" and 3 as "x+1". But it'll make coding a bit more challenging because it'll be easier to mix up the values for the group with regular numbers. — Cris Luengo

Cris Luengo Cris Luengo · Accepted Answer · 2018-03-05T06:15:53

I think the most efficient way to do arithmetic with a finite group of possible values and non-standard addition and multiplication is by table lookup.

Table lookup requires matrices to be encoded such that the elements are indices into the list of group elements. And since indexing starts at 1, you'll need to represent {0,1,x,x+1} as {1,2,3,4}.

But aside the awkward mapping of 1=0, 2=1, things are quite straightforward with table lookup. This is some example code I cooked up, it seems to work but I might have made some mistake (and I might have misunderstood the exact arithmetic rules):

function out = group_mtimes(lhs,rhs)
[I,K] = size(lhs);
[K2,J] = size(rhs);
if K~=K2, error('Inner dimensions must agree'), end

out = zeros(I,J);
for j=1:J
   for i=1:I
      v = 1;
      for k=1:K
         v = group_scalar_add(v, group_scalar_times(lhs(i,k),rhs(k,j)));
      end
      out(i,j) = v;
   end
end

disp('lhs = ')
group_print(lhs)
disp('rhs = ')
group_print(rhs)
disp('lhs * rhs = ')
group_print(out)

end

function group_print(in)
names = {'0','1','x','1+x'};
disp(names(in)) % Quick-and-dirty, can be done much better!
end

function out = group_scalar_add(lhs,rhs)
table = [
   1,2,3,4
   2,1,4,3
   3,4,1,2
   4,3,2,1
   ];
out = table(lhs,rhs);
end

function out = group_scalar_times(lhs,rhs)
table = [
   1,1,1,1
   1,2,3,4
   1,3,4,2
   1,4,2,3
   ];
out = table(lhs,rhs);
end

For example:

>> lhs=[1,2,3,4;2,3,1,4]';
>> rhs=[2,3;4,1];
>> group_mtimes(lhs,rhs);
lhs = 
    '0'      '1'  
    '1'      'x'  
    'x'      '0'  
    '1+x'    '1+x'

rhs = 
    '1'      'x'
    '1+x'    '0'

lhs * rhs = 
    '1+x'    '0'
    '0'      'x'
    'x'      '0'
    'x'      '1'

There is no input checking in this code, if the input contains a 5, you'll get and index out of range error.

As I mentioned in a comment, you could make a class that encapsulates arrays of this type. You could then overload plus, times and mtimes (for operators +, .* and *, respectively), as well as disp to write out the values properly. You would define the constructor so that objects of this class always have valid values, this would prevent lookup table indexing errors. Such a class would make working with these functions a lot simpler.

Octave: matrix multiplication over a group

2 Answers