# Introducing a finite monoid by giving its "multiplication" table

I am interested in working with some finite monoids. Looking at http://doc.sagemath.org/html/en/refer... I have not found anything about how to define a finite monoid by simply providing its (binary) "multiplication" table.

Is there some way to do so?

edit retag close merge delete

Sort by » oldest newest most voted

Hello,

Yes but not as direct as you may want. And the most important is: it really depends on what you want to do with these monoids.

If you put the following in a file like "finite_monoid.py"

from sage.structure.parent import Parent
from sage.categories.semigroups import Semigroups
from sage.structure.element_wrapper import ElementWrapper

class FiniteMonoidFromMultiplicationTable(Parent):
def __init__(self, table):
self._table = table
Parent.__init__(self, category=Semigroups().Finite())

def product(self, x, y):
return self(self._table[x.value][y.value])

def _repr_(self):
return "Finite monoid on {} elements given by its multiplication table".format(len(self._table))

def _element_constructor_(self, data):
data = int(data)
assert 0 <= data < len(self._table)
return self.element_class(self, data)

def __reduce__(self):
return (FiniteMonoidFromMultiplicationTable,
(self._table,))

def __eq__(self, other):
return type(self) is type(other) and \
self._table == other._table

def __ne__(self, other):
return not self == other

class Element(ElementWrapper):
wrapped_class = Integer

def __reduce__(self):
return self.parent(), (self.value,)


In the above code the most important are:

• the constructor __init__ and the choice of the category Semigroups().Finite()

• the method product that defines the product of elements from the multiplication table

• the subclass Element and the method _element_constructor_ that tells how to construct elements

Then you can do from the console

sage: from finite_monoid import FiniteMonoidFromMultiplicationTable
sage: F = FiniteMonoidFromMultiplicationTable([[0, 0, 0], [0, 1, 1], [0, 1, 2]])
sage: e0 = F(0); e1 = F(1); e2 = F(2)
sage: print (e0, e1, e2)
sage: e0 * e1 * e2 * e1
0
sage: e1 * e2 * e2
1
sage: TestSuite(F).run()   # check thaat everything is fine


If you want to know more, you should have a look at the thematic tutorial How to implement new algebraic structures in Sage?.

EDIT:

Then you can do cartesian products and create morphisms as follows

sage: from sage.categories.morphism import SetMorphism
sage: from finite_monoid import FiniteMonoidFromMultiplicationTable
sage: F1 = FiniteMonoidFromMultiplicationTable([[0, 0, 0], [0, 1, 1], [0, 1, 2]])
sage: F2 = FiniteMonoidFromMultiplicationTable([[0, 1, 2], [1, 1, 2], [2, 2, 2]])
sage: F = cartesian_product([F1,F2])
sage: F((0,1)) * F((1,1))
(0, 1)
sage: TestSuite(F).run()

sage: from sage.categories.morphism import SetMorphism
sage: H = HomF1F2 = Hom(F1, F2, Semigroups())
sage: f = SetMorphism(H, lambda x: F2(2-x.value))
sage: e1_0 = F1(0)
sage: e1_1 = F1(1)
sage: e1_2 = F1(2)
sage: f(e1_1) * f(e1_2) == f(e1_1 * e1_2)
True

more

Thanks a lot. I will check whether this method allows using the issues already implemented for monoids (direct products, quotients, homomomorphisms, etc) without having to code anything else. Indeed, this reason was the motivation behind my question. By the way, do you already know the answer?

1
1

I guess there is a problem with one line of the current code "assert 0 <= data < len(self._table):". The last symbol of such line must be deleted.