This document is one of More SageMath Tutorials. You may edit it on github. \(\def\NN{\mathbb{N}}\) \(\def\ZZ{\mathbb{Z}}\) \(\def\QQ{\mathbb{Q}}\) \(\def\RR{\mathbb{R}}\) \(\def\CC{\mathbb{C}}\)

Demonstration: Computational representation theory for finite monoids (experimental)

Requirements

This demonstration requires experimental code that has not yet been migrated from the Sage-Combinat queue to the sage-semigroups package.

Running example

Let us consider an \(H\)-trivial monoid:

sage: O3 = HTrivialMonoids().Finite().example(action = "right"); O3
The finite H-trivial monoid of order preserving maps on {1, .., 3}
sage: O3.rename("O3")

Its generators:

sage: pi = O3.monoid_generators(); pi
Finite family {1: 113, 2: 122, -2: 133, -1: 223}

Its right Cayley graph:

sage: view(O3.cayley_graph(side="right"))

Its right classes:

sage: O3.r_classes()
[{123}, {233, 133, 122}, {113, 112, 223}, {111, 222, 333}]

Representation theory

The Cartan matrix of \(O_3\):

sage: O3.cartan_matrix()
[1 0 0]
[1 1 0]
[0 1 1]

A larger example:

sage: O = HTrivialMonoids().Finite().example(5); O
The finite H-trivial monoid of order preserving maps on {1, .., 5}
sage: O.cardinality()
126
sage: O.cartan_matrix()
[1 1 0 0 0]
[0 1 1 0 0]
[0 0 1 1 0]
[0 0 0 1 1]
[0 0 0 0 1]

sage: O = HTrivialMonoids().Finite().example(6)
sage: O.cardinality()
462
sage: O.cartan_matrix()
[1 1 0 0 0 0]
[0 1 1 0 0 0]
[0 0 1 1 0 0]
[0 0 0 1 1 0]
[0 0 0 0 1 1]
[0 0 0 0 0 1]

sage: O = HTrivialMonoids().Finite().example(7)
sage: O.cardinality()
1716
sage: O.cartan_matrix()
[1 1 0 0 0 0 0]
[0 1 1 0 0 0 0]
[0 0 1 1 0 0 0]
[0 0 0 1 1 0 0]
[0 0 0 0 1 1 0]
[0 0 0 0 0 1 1]
[0 0 0 0 0 0 1]

Constructing modules

Its regular right class modules:

sage: right_class_modules = [O3.lr_regular_class_module(i, side="right") for i in range(3)]; right_class_modules
[Free module generated by {123} endowed with an action of O3 over Rational Field,
 Free module generated by {113, 112, 223} endowed with an action of O3 over Rational Field,
 Free module generated by {111, 222, 333} endowed with an action of O3 over Rational Field]

Its simple modules:

sage: simple_modules = [O3.simple_module(i) for i in range(3)]; simple_modules
[A quotient of Free module generated by {123} endowed with an action of O3 over Rational Field,
 A quotient of Free module generated by {113, 112, 223} endowed with an action of O3 over Rational Field,
 A quotient of Free module generated by {111, 222, 333} endowed with an action of O3 over Rational Field]

sage: simple_modules[0].dimension()
1
sage: simple_modules[1].dimension()
2
sage: simple_modules[2].dimension()
1

Characters

As for groups, characters provide a convenient computational tool to recover the composition factors of a module \(V\) (although those composition factors are not sufficient to completely describe the structure of \(V\)). Let us take for example the right regular representation:

sage: V = O3.regular_representation(side="right", base_ring = QQ)
sage: V.character()
10*p[0] + 6*p[1] + 3*p[2]

It encodes the trace of appropriate idempotents of \(O_3\) when acting on \(V\). In particular, the identity is of trace \(10\) since \(V\) is of dimension \(10\).

Here are the characters of right class modules:

sage: right_class_modules[0].character()
p[0]
sage: right_class_modules[1].character()
3*p[0] + p[1]
sage: right_class_modules[2].character()
3*p[0] + 2*p[1] + p[2]

Here are the characters of the simple modules, a.k.a. the character table:

sage: simple_modules[0].character()
p[0]
sage: simple_modules[1].character()
2*p[0] + p[1]
sage: simple_modules[2].character()
p[0] + p[1] + p[2]

Note that it is unitriangular, and therefore invertible. Hence we may recover the composition factors of a module from its characters.

The characters ring

A convenient device is to use the character ring of \(V\); its elements model formal ZZ linear combinations of modules (aka virtual characters):

sage: G = O3.character_ring(QQ, side="right"); G
The right-character ring of O3 over Rational Field

and, like is done for the symmetric group, with symmetric functions, to play with changes of bases in this ring. For example, the character table is the change of bases from the S basis (analogue of Schur) to the C basis (analogue of powersum):

sage: S = G.S(); S
The right-character ring of O3 over Rational Field in the basis of characters of simple right modules
sage: p = G.C(); p
The right-character ring of O3 over Rational Field in the basis of characters of right-class functions modules

sage: p(S[0])
p[0]
sage: p(S[1])
2*p[0] + p[1]
sage: p(S[2])
p[0] + p[1] + p[2]

One can compute the composition factors of a module by using the inverse change of basis. Here are the composition factors of the right regular representation:

sage: V = O3.regular_representation()
sage: S(V.character())
3*S[0] + 3*S[1] + S[2]

and those of the right class modules:

sage: S(right_class_modules[0].character())
S[0]
sage: S(right_class_modules[1].character())
S[0] + S[1]
sage: S(right_class_modules[2].character())
S[1] + S[2]

sage: for cls in S.__class__.mro(): print cls ….:

Change of bases in the characters ring

This ring admits several bases:

sage: C = G.C(); C
The left-character ring of O3 over Rational Field in the basis of characters of left-class functions modules
sage: S = G.S(); S
The left-character ring of O3 over Rational Field in the basis of characters of simple left modules
sage: P = G.P(); P
The left-character ring of O3 over Rational Field in the basis of characters of projective indecomposable left modules
sage: T = G.T(); T
The left-character ring of O3 over Rational Field in the basis of characters of regular left-class modules

Here are the composition factors of projective modules and left class modules:

sage: for chi in P.basis():
....:     print "%s = %s"%(chi, S(chi))
P[0] = S[0] + S[1]
P[1] = S[1] + S[2]
P[2] = S[2]

sage: for chi in T.basis():
....:     print "%s = %s"%(chi, S(chi))
T[0] = S[0]
T[1] = S[0] + S[1]
T[2] = S[1] + S[2]

This shows that \(V\) could possibly have a composition series in term of right class modules (and here, it does!):

sage: T(V.character())
T[0] + 2*T[1] + T[2]

By changing bases one can calculate how a module could possibly decompose in term of various modules. For example, here are the composition factors of the regular representation:

sage: S(V.character())