matrix semigroups in SAGE

[mhs]

Hi,

I am looking for a way to define 1) finite (multiplicative) semigroups
generated by a set of square 0/1 matrices where the composition is the
reduced matrix multiplication (reduce the product of two 0/1 matrices
by putting a 1 whenever the result is positive and a 0 otherwise) or
more generally 2) finite multiplicative semigroups where I can
explicitely specify the group law.

Is there any support for such things already included in SAGE or do I
need to develop a new class for such semigroups - any ideas where such
class should be fit into the existing hierarchy of SAGE classes
(inheritance etc.)?

Thanks a lot for any comments.

Best
M.

[Vincent D]

Hi,

The best place to look at is in sage/categories/examples/
semigroups.py.

Following FreeSemiGroup in the file mentioned above, I was able to
implement 1) in 50 lines, which make me think that the category
mechanism is not so bad ;-)

I do have a question : do you know a small set of generators for that
semigroup ?

Cheers,
Vincent

[Florent Hivert]

Hi,

> I am looking for a way to define 1) finite (multiplicative) semigroups
> generated by a set of square 0/1 matrices where the composition is the
> reduced matrix multiplication (reduce the product of two 0/1 matrices
> by putting a 1 whenever the result is positive and a 0 otherwise) or
> more generally 2) finite multiplicative semigroups where I can
> explicitely specify the group law.

I've an implementation of this whic is unfortunately not already in Sage but
is in Sage-Combinat [1] patches [2]. With Nicolas Thiery we are currently
working of representation theory of monoid and we have some code to play with
finite semigroups including some generic algorithm for j-trivial r-trivial
semigroups. There is also a link to Jean-Eric Pin Semigroupe package [3]

> Is there any support for such things already included in SAGE or do I
> need to develop a new class for such semigroups - any ideas where such
> class should be fit into the existing hierarchy of SAGE classes
> (inheritance etc.)?

Yes with the category system. We have a lot more category for semigroup in the
Sage-combinat queue. I'n not sure what is the status of it for being ready to
enter Sage. we probably need to entange research code with stable stuff.

Florent

[1] http://wiki.sagemath.org/combinat/
[2] http://combinat.sagemath.org/patches/file/tip/finite_semigroup-nt.patch
[3] http://trac.sagemath.org/sage_trac/ticket/8360