# Computing character tables and Cartan matrices of finite monoids with fixed
point counting.

Balthazar Charles111LISN, Université Paris-Saclay, 6 Rue Noetzlin, Gif-sur-
Yvette, 91190, France

###### Abstract

In this paper we present an algorithm for efficiently counting fixed points in
a finite monoid $M$ under a conjugacy-like action. We then prove a formula for
the character table of $M$ in terms of fixed points and radical, which allows
for the effective computation of the character table of $M$ over a field of
null characteristic, as well as its Cartan matrix, using a formula from
[Thiéry ’12], again in terms of fixed points. We discuss the implementation
details of the resulting algorithms and provide benchmarks of their
performances.

## Introduction

The last two decades have seen the development of a new dynamic around the
study of monoid representation theory. This is due to applications to certain
types of discrete Markov chains and specially Markov chains used to randomly
generate combinatorial objects first uncovered in the seminal article of Brown
[1]. This has lead to an exploration of the combinatorial properties of monoid
representations, for instance in [2], [3] or [4].

In this last article [4], Thiéry gives a formula for the Cartan matrix of a
finite monoid of $M$ in terms of number of fixed points and the character
table of $M$. More precisely, the formula involves computing the cardinality
of the set $\\{s\in M\,|\,hsk=s\\}$ for any $h,k\in M$. In this paper, we set
out to use this formula to effectively compute the Cartan matrix of the
algebra of $M$ over a perfect field $\mathbf{k}$ of null characteristic.

Two difficulties have to be overcome in the pursuit of this goal. Firstly, the
cardinality of many interesting families of monoids tends the increase very
quickly. For instance, the cardinality of the _full transformation monoid_
$T_{n}$ of all functions from $\llbracket{1,n}\rrbracket$ to
$\llbracket{1,n}\rrbracket$ is $n^{n}$, making the naive computation of
$|\\{s\in M\,|\,hsk=s\\}|$ impractical even for small $n$. To remedy this we
provide an algorithm to efficiently compute this statistic. Secondly, to use
the formula one has to compute the character table of the monoid. The
Clifford-Munn-Ponizovskii Theorem (such as presented in [5]) gives an explicit
description of the simple $\mathbf{k}M$-modules and technically makes the
computation of the character table possible, provided that we know how to
compute the simple modules associated to certain groups. However, this
approach is rather convoluted and inefficient. We also note that although some
results on character tables are known in the case of many interesting families
of monoids, no algorithms are available to compute the character table of an
arbitrary finite monoid. Thus, for the general case, we prove a formula for
the character table that allows for computation exploiting the Green structure
of the monoid for increased efficiency.

In the first section of this paper, we present the results necessary for our
fixed-points counting algorithm, with a particular emphasis on the notions of
Green classes and Schützenberger groups. In the second section, we prove a
formula for the character table of a finite monoid, after recalling the
necessary module and character theoretic results. In the third section, we
give and discuss the algorithms and equation systems used for computing the
Cartan matrix with two focuses: the algorithms for fixed point counting and
the equation system to compute the character table. Finally, in the last
section, we discuss the performance of these algorithms in terms of execution
time and size of tractable problems.

##  I Combinatorics of fixed point counting.

In this section we first recall essential and elementary results on the Green
structure of finite monoids and on Schützenberger groups. The informed reader
may skip this first paragraph, with the exception of the notations (4) that
are used throughout this paper. We then use these results to devise a fixed
point counting method.

In the totality of this paper, we assume that all monoids are finite. We will
often use the following special case of finite monoid to illustrate the
various results presented hereafter.

######  Definition 1 (The full transformation monoid).

Consider the set $T_{n}$ of all transformations of the set $\\{1,\dots,n\\}$,
equipped with the multiplication given by map composition: $\forall f,g\in
T_{n},fg=f\circ g$. This is a monoid, aptly named the _full transformation
monoid_. A submonoid of $T_{n}$ is called a transformation monoid and $n$ is
called its _rank_.

###  1 Green structure and Schützenberger groups

Although finite monoids have been considered to be much wilder objects than
groups, it turns out that, with the right optics, they are actually highly
structured by their internal multiplication. Consider the divisibility
relation: $x$ divides $y$ if $x=yz$ for some $z$. If $x,y,z$ are taken in a
group $G$, the relation is trivial. If however, we take them in a general
monoid $M$, left or right translation by an arbitrary element need not be
surjective, making the question of $x\in M$ being a left (or right) multiple
of $y\in M$ non-trivial. These questions of "divisibility" in a general monoid
are studied under the name of Green structure, of which we give a brief
overview necessary for our purpose in the subsection below. In the following
subsection, we also present the related notion of Schützenberger groups.

####  1.1 Green Structure

######  Definition 2 (Green’s relations).

Let $M$ be a finite monoid and $a,b$ two of its elements. The _Green
relations_ are:

  * •

The $\mathcal{L}$ preorder is defined by $a\leq_{\mathcal{L}}b\Leftrightarrow
b=ua$ for some $u\in M$. The associated equivalence relation is :
$a\in\mathcal{L}(b)\Leftrightarrow a\leq_{\mathcal{L}}b\textrm{ and
}b\leq_{\mathcal{L}}a\Leftrightarrow Ma=Mb$.

  * •

The $\mathcal{R}$ preorder is defined by $a\leq_{\mathcal{R}}b\Leftrightarrow
b=av$ for some $v\in M$. The associated equivalence relation is :
$a\in\mathcal{R}(b)\Leftrightarrow a\leq_{\mathcal{R}}b\textrm{ and
}b\leq_{\mathcal{R}}a\Leftrightarrow aM=bM$.

  * •

The $\mathcal{J}$ preorder is defined by $a\leq_{\mathcal{J}}b\Leftrightarrow
b=uav$ for some $u,v\in M$. The associated equivalence relation is:
$a\in\mathcal{J}(b)\Leftrightarrow a\leq_{\mathcal{J}}b\textrm{ and
}b\leq_{\mathcal{J}}a\Leftrightarrow MaM=MbM$.

  * •

The $\mathcal{H}$ equivalence relation is defined by
$a\in\mathcal{H}(b)\Leftrightarrow a\in\mathcal{L}(b)\textrm{ and
}a\in\mathcal{R}(b)$.

It can be proven (see for instance [6, Theorem 1.9]) that in finite monoids,
the relation $\mathcal{J}$ is the smallest equivalence relation containing
$\mathcal{R}$ and $\mathcal{L}$. This is not true in general, and this
smallest relation is usually denoted by $\mathcal{D}$ in the literature. Since
we are only interested in finite monoids, we shall only use the terms
$\mathcal{J}$-relation, $\mathcal{J}$-class, etc. From the definition, it is
clear that the relation $\mathcal{L}$ and $\mathcal{R}$ are finer than
$\mathcal{J}$ and that $\mathcal{H}$ is finer that both $\mathcal{L}$ and
$\mathcal{R}$. Because of this, "the $\mathcal{L}$-class of some
$\mathcal{H}$-class $H$" or "the $\mathcal{J}$-class of some
$\mathcal{R}$-class $R$", etc… are well-defined and we shall denote them by
$\mathcal{L}(H),\mathcal{J}(R),$ etc.

######  Example 3 (Green relations in $T_{n}$).

Let $a,b$ be two elements of $M$. • If $a\mathcal{L}b$, if and only if they
have the same _kernel_ $\ker
a=\\{a^{-1}\\{i\\}\,|\,i\in\llbracket{1,n}\rrbracket\\}$. We also say that $a$
and $b$ have the same nuclear equivalence. • If $a\mathcal{R}b$, if and only
if they have the same image, $\mathrm{Im}\,(a)=\mathrm{Im}\,(b)$. • Since
$T_{n}$ is finite, $\mathcal{J}$ is generated by $\mathcal{L}$ and
$\mathcal{R}$ so $a\mathcal{J}b$ if and only if $\mathrm{Im}\,(a)$ and
$\mathrm{Im}\,(b)$ (or equivalently $\ker(a)$ and $\ker(b)$) have the same
cardinality. • Since $\mathcal{H}$ is the intersection of $\mathcal{L}$ and
$\mathcal{R}$, $a\mathcal{H}b$ if and only $a$ and $b$ have the same image and
the same kernel. These conditions are necessary conditions in any
transformation monoid. To get that they are sufficient, we use the fact that
$\mathfrak{S}_{n}\subset T_{n}$ and that we can rearrange both image and
kernel as we please. These relations are illustrated in the case of the monoid
$T_{3}$ in Figure 1.

$\mathcal{J}$(1 2 3)1 2 32 3 13 1 22 1 31 3 23 2 1$\mathcal{J}$(1 2 2)1 2 22 1
11 2 12 1 21 1 22 2 11 3 33 1 11 3 13 1 31 1 33 3 12 3 33 2 23 2 32 3 22 2 33
3 2$\mathcal{J}$(1 1 1)1 1 12 2 23 3 3 Figure 1: Green relations in $T_{3}$.
Each block is a $\mathcal{J}$-class, each line is a $\mathcal{R}$-class, each
column a $\mathcal{L}$-class and each case an $\mathcal{H}$-class. The red,
green and black arrows represent the $\mathcal{L}$, $\mathcal{R}$ and
$\mathcal{J}$-order respectively.

The following notations will prove useful, as the study of Green relations is,
in part, the study of the maps given by left and right translations in the
monoid.

######  Notation 4.

Let $h,k$ be elements of $M$ and $S$ be a subset of $M$. We denote by:

  * •

$h\times_{S}$ the application from $S$ to $hS$ defined by $s\mapsto hs$,

  * •

$\times_{S}k$ the application from $S$ to $Sk$ defined by $s\mapsto sk$,

  * •

${}_{M}\operatorname{Stab}(S)=\\{m\in M\,|\,mS=S\\}$,

  * •

$\operatorname{Stab}_{M}(S)=\\{m\in M\,|\,Sm=S\\}$,

  * •

$\operatorname{Fix}_{S}(h,k)=\\{s\in S\,|\,hsk=s\\}$.

Using these notations, let us recall Green’s Lemma, which is one of the
central elements of the theory of Green relations, as it shows that the
structure of the relations is actually heavily constrained, making their study
practical.

######  Lemma 5 (Green’s Lemma).

Let $a,a^{\prime}$ be two elements in the same $\mathcal{L}$-class and let
$\lambda,\lambda^{\prime}$ such that $\lambda a=a^{\prime}$ and
$\lambda^{\prime}a^{\prime}=a$. Then $\lambda\times_{\mathcal{R}(a)}$ and
$\lambda^{\prime}\times_{\mathcal{R}(a^{\prime})}$ are reciprocal bijections.
Moreover, for any $\mathcal{L}$-class $L$ $\lambda\times_{\mathcal{R}(a)\cap
L}$ and $\lambda^{\prime}\times_{\mathcal{R}(a^{\prime})\cap L}$ are
reciprocal bijections.

Similarly, if $a,b$ are two elements in the same $\mathcal{R}$-class and
$\rho,\rho^{\prime}$ are such that $\rho a=b$ and $\rho^{\prime}b=a$, then
$\times_{\mathcal{L}(a)}\rho$ and $\times_{\mathcal{L}(b)}\rho^{\prime}$ are
reciprocal bijections. Moreover, for any $\mathcal{R}$-class $R$
$\times_{\mathcal{L}(a)\cap R}\rho$ and $\times_{\mathcal{L}(b)\cap
R}\rho^{\prime}$ are reciprocal bijections.

$a^{\prime}$$a$$b^{\prime}$$b$$\lambda\times_{\mathcal{R}(a)}$$\lambda^{\prime}\times_{\mathcal{R}(a^{\prime})}$$\times_{\mathcal{L}(a)}\rho$$\times_{\mathcal{L}(b)}\rho^{\prime}$$\mathcal{R}(a)$$\mathcal{R}(a^{\prime})$$\mathcal{L}(a)$$\mathcal{L}(b)$
Figure 2: Green’s Lemma

An important consequence of Green’s Lemma is that $\mathcal{J}$-classes can be
neatly organized as _eggbox pictures_ 222Terminology introduced in [7]: the
$\mathcal{J}$-class can be represented as a rectangular array with the
$\mathcal{L}$-classes as columns, the $\mathcal{R}$-classes as rows and the
$\mathcal{H}$-classes, the eggs, in the cases, as can be seen in Figure 1.
This level organization is actually what allows for efficient computer
representation of monoids and most of their algorithmic exploration.

####  1.2 Schützenberger groups

The Green structure offers a second way of facilitating computer exploration
of monoids through groups that arise as stabilizers of some Green classes.
These are called the _Schützenberger groups_ and – this a running theme of
monoid theory – allow for a number of monoid theoretic questions to be
formulated in terms of groups for which we dispose of an array of efficient
algorithms.

######  Definition 6 (Schützenberger groups).

Let $H$ be an $\mathcal{H}$-class. The set
$\\{h\times_{H}\,|\,h\in{}_{M}\operatorname{Stab}(H)\\}$ equipped with map
composition is a subgroup of $\mathfrak{S}(H)$ called the _left Schützenberger
group_ and denoted by $\Gamma(H)$.

Similarly, $(\\{\times_{H}k\,|\,k\in\operatorname{Stab}_{M}(H)\\},\circ)$ is a
subgroup of $\mathfrak{S}(H)$ called the _right Schützenberger group_ and
denoted by $\Gamma^{\prime}(H)$.

######  Example 7.

Consider $H=\mathcal{H}([1\ 3\ 1])$ (the elements of $T_{n}$ are given in
function notation in all examples). We have :
${}_{M}\operatorname{Stab}(H)=\\{[1\ 2\ 3],[3\ 2\ 1],[1\ 3\ 3],[3\ 1\ 1],[1\
1\ 3],[3\ 3\ 1]\\}$ and subsequently, $\Gamma(H)=\\{[1\ 2\ 3]\times_{H},[3\ 3\
1]\times_{H}\\}$. Notice that, as elements of $\Gamma(H)$, $[3\ 3\
1]\times_{H}=[3\ 2\ 1]\times_{H}$ and that the only important thing is the
permutations induced by the elements of ${}_{M}\operatorname{Stab}(H)$ on
$\mathrm{Im}\,H$. Thus, in the case of transformation monoids, the left
Schützenberger group of an $\mathcal{H}$-class $H$ can be represented as a
subgroup of $\mathfrak{S}(\mathrm{Im}\,H)$. In the same way, the right
Schützenberger groups can be represented as subgroups of $\mathfrak{S}(\ker
H)$. This fact is used to represent the Schützenberger groups in Section III.

Our precedent remark on exploiting Schützenberger groups to get efficient
algorithms for computational monoid theoretic questions is seconded by the
fact that Schützenberger groups do not contain any "superfluous information"
in the following sense.

######  Proposition 8.

Let $H$ be an $\mathcal{H}$-class. The natural actions of $\Gamma(H)$ and
$\Gamma^{\prime}(H)$ on $H$ are free and transitive.

We reproduce below a proof for Proposition 8 from [8] for the purpose of
showcasing the main argument. The argument itself is widely known and we will
use it multiple times in the remainder of this paper.

###### Proof.

Two elements $h,h^{\prime}\in H$ are in the same $\mathcal{L}$-class so there
is some $u\in M$ such that $uh=h^{\prime}$. By Green’s Lemma, this means that
$u\in{}_{M}\operatorname{Stab}(H)$, so $\Gamma(H)$ acts transitively on $H$.
Suppose that $uh=h$ for some $u\in M$. Since $h,h^{\prime}$ are also in the
same $\mathcal{R}$ class, there is some $v$ such that $h^{\prime}=hv$, so
$uh^{\prime}=uhv=hv=h^{\prime}$ : an element of $\Gamma(H)$ either fixes all
points in $H$ or fixes none. The only element of $\Gamma(H)$ that fixes all
points (and, consequently, the only one that fixes any point) is the identity
and thus the action is free. The same arguments apply for
$\Gamma^{\prime}(H)$. ∎

A special case that is interesting to note, and that will be important later,
it the case where $H$ is the $\mathcal{H}$-class of an idempotent :

######  Definition 9.

An element $e\in M$ is _idempotent_ if $e^{2}=e$. Given an idempotent $e$, the
set $G_{e}=\\{x\in M\,|\,\exists y\in M,xy=yx=e\\}$ is called the _maximal
subgroup at $e$_. One can check that $G_{e}$ is indeed a group and that
$G_{e}=\mathcal{H}(e)$.

In that case, $\Gamma(H)$ and $\Gamma^{\prime}(H)$ can be defined as before,
and are canonically isomorphic to $G_{e}$, simply because
$G_{e}\subset{}_{M}\operatorname{Stab}(H)$ naturally induce a map making it a
subgroup of $\Gamma(H)$ and that since $G_{e}$ acts freely and transitively on
$H$, this map must be injective and surjective (and similarly for
$\Gamma^{\prime}(H)$).

######  Example 10.

Consider, in Example 3, $e=[1\ 2\ 2]$ and $H=\mathcal{H}(e)$. $e$ is an
idempotent, and, indeed, $H=G_{e}$ is group : setting $t=[2\ 1\ 1]$, we have
$e^{2}=e,t^{2}=e$ and $et=te=t$. As noted in Example 7 :
$\Gamma(H)=\mathfrak{S}(\\{1,2\\}),\qquad\Gamma^{\prime}(H)=\mathfrak{S}(\\{\\{1\\},\\{2,3\\}\\}).$
Note that the canonical isomorphism between $\Gamma(H)$ and $\mathcal{H}(e)$
is simply given by $g\in\Gamma(H)\mapsto g\cdot e\in H$.

###  2 Counting fixed points

Consider the problem of counting the number of elements of the set
$\operatorname{Fix}_{G}(h,k)$ where $G$ is a finite group and $h,k\in G$. If
$\operatorname{Fix}_{G}(h,k)$ is non-empty, it contains an element $\gamma$
such that $h\gamma k=\gamma$, or equivalently $h=\gamma k^{-1}\gamma^{-1}$. So
for any $g\in\operatorname{Fix}_{G}(h,k)$ we have:

$hgk=g\Leftrightarrow\gamma
k^{-1}\gamma^{-1}gk=g\Leftrightarrow\gamma^{-1}gk=k\gamma^{-1}g.$

This means that $g\in\gamma C_{G}(k)$ where $C_{G}(k)$ is the centralizer of
$k$ in $G$. Because the other inclusion is obvious, we get a description of
$|\operatorname{Fix}_{G}(h,k)|$: either $h$ and $k^{-1}$ are conjugated in
which case there are $|C_{G}(k)|$ fixed points, or they are not, and there are
no fixed points. In the case of a monoid, this reasoning mostly breaks: we
crucially used the invertibility property, which monoids lack. The
Schützenberger groups seem to be ideal candidates to get back some of this
invertibility. In this section we clarify the role of the Schützenberger
groups for counting fixed points, how to give meaning to "$h\times_{H}$ and
$\times_{H}k$ are in the same conjugacy class", and how to factorize our
previous remark over all the $\mathcal{H}$-classes of the same
$\mathcal{J}$-class.

As the bijections between $\mathcal{L}$ (and $\mathcal{R}$) classes will play
an major role in the remainder of this section, we introduce the following
notations.

######  Notation 11.

Given $R,R^{\prime}$ two $\mathcal{R}$-classes in the same
$\mathcal{J}$-class, we say that $(\lambda,\lambda^{\prime})$ is a _left Green
pair_ with respect to $(R,R^{\prime})$ if:

  * •

$\lambda R=R^{\prime}$ and $\lambda^{\prime}R^{\prime}=R$.

  * •

$(\lambda\lambda^{\prime})\times_{R}=\mathrm{Id}_{R}$ and
$(\lambda^{\prime}\lambda)\times_{R^{\prime}}=\mathrm{Id}_{R^{\prime}}$

Similarly, given two $\mathcal{L}$-classes $L,L^{\prime}$ in the same
$\mathcal{J}$-classes, $(\rho,\rho^{\prime})$ is a _right Green pair_ with
respect to $(L,L^{\prime})$ if:

  * •

$L\rho=L^{\prime}$ and $L^{\prime}\rho^{\prime}=L$.

  * •

$\times_{L}(\rho\rho^{\prime})=\mathrm{Id}_{L}$ and
$\times_{L^{\prime}}(\rho^{\prime}\rho)=\mathrm{Id}_{L^{\prime}}$

Using Green pairs, one can transport the problem of counting fixed points in
an arbitrary $\mathcal{H}$-class to a reference $\mathcal{H}$-class.

######  Proposition 12.

Let $H_{1},H_{2}\subset J$ be two $\mathcal{H}$-classes contained in the same
$\mathcal{J}$-class. Let $\lambda,\lambda^{\prime},\rho,\rho^{\prime}$ such
that:

  * •

$(\lambda,\lambda^{\prime})$ is a left Green pair with respect to
$(\mathcal{R}(H_{1}),\mathcal{R}(H_{2}))$,

  * •

$(\rho,\rho^{\prime})$ is a right Green pair with respect to
$(\mathcal{L}(H_{1}),\mathcal{L}(H_{2}))$.

Finally, let
$(h,k)\in{}_{M}\operatorname{Stab}(\mathcal{R}(H_{2}))\times\operatorname{Stab}_{M}(\mathcal{L}(H_{2}))$
and define $(h^{\prime},k^{\prime})=(\lambda^{\prime}h\lambda,\rho
k\rho^{\prime})$. Then the maps $x\mapsto\lambda^{\prime}x\rho^{\prime}$ and
$x\mapsto\lambda x\rho$ are reciprocal bijections between the sets
$\operatorname{Fix}_{H_{2}}(h,k)=\\{a\in H_{2}\,|\,hak=a\\}$ and
$\operatorname{Fix}_{H_{1}}(h^{\prime},k^{\prime})=\\{a\in
H_{1}\,|\,h^{\prime}ak^{\prime}=a\\}$.

###### Proof.

First notice that Green’s Lemma give us the existence of
$\lambda,\lambda^{\prime},\rho,\rho^{\prime}$ respecting the hypothesis we
demand, and also gives that $x\mapsto\lambda^{\prime}x\rho^{\prime}$ and
$x\mapsto\lambda x\rho$ are reciprocal bijections between $H_{1}$ and $H_{2}$.
Let $a_{1}$ be an element of $H_{1}$ and denote by $a_{2}=\lambda a_{1}\rho$.
Then:

$ha_{2}k=a_{2}\Leftrightarrow\lambda^{\prime}ha_{2}k\rho^{\prime}=\lambda^{\prime}a_{2}\rho^{\prime}\Leftrightarrow(\lambda^{\prime}h\lambda)a_{1}(\rho
k\rho^{\prime})=a_{1}\Leftrightarrow h^{\prime}a_{1}k^{\prime}=a_{1}$

so these bijections restrict to
$\operatorname{Fix}_{H_{1}}(h^{\prime},k^{\prime})$ and
$\operatorname{Fix}_{H_{2}}(h,k)$. ∎

Keeping in mind our computational goals, transporting the problem of counting
fixed points from $H_{2}$ to $H_{1}$ is helpful, as for the price of 4 monoid
multiplications, we can use a lot of precomputations specific to a particular
$\mathcal{H}$-class, avoiding the repetition of multiple similar computations
for each $\mathcal{H}$-class.

The question is now to determine the fixed points in a single
$\mathcal{H}$-class, using our previous remark on conjugacy. Let us first
clarify the idea of elements of the left and right Schützenberger groups being
in the same conjugacy class.

######  Proposition 13.

Given and $\mathcal{H}$-class $H$, $a\in H$ and $g\in\Gamma(H)$, we define
$\tau_{a}(g)$ as the unique element of $\Gamma^{\prime}(H)$ such that $g\cdot
a=a\cdot\tau_{a}(g)$. Then
$\tau_{a}:\Gamma(H)\longrightarrow\Gamma^{\prime}(H)$ is an anti-
isomorphism333Note that some authors equip the right Schützenberger group with
reversed composition, and thus obtain an isomorphism instead of anti-
isomorphism.. Moreover $\tau_{a}$ gives rise to a bijection between the
conjugacy classes of $\Gamma(H)$ and $\Gamma^{\prime}(H)$ that is independent
of the choice of $a$.

###### Proof.

The first part is known since [8]. We want to check that for $a\in
H,g\in\Gamma(H)$, the conjugacy class of $\tau_{a}(g)$ is defined
independently of $a$. Take any $a,b\in H$. By definition of $\Gamma(H)$, there
exist some $h\in\Gamma(H)$ such that $b=h\cdot a$. So :

$b\cdot\tau_{a}(g)=(h\cdot a)\cdot\tau_{a}(g)=h\cdot(g\cdot
a)=hgh^{-1}\cdot(h\cdot a)=b\cdot\tau_{b}(hgh^{-1}).$

Since $\Gamma^{\prime}(H)$ acts freely, this means that
$\tau_{a}(g)=\tau_{b}(h)\tau_{b}(g)\tau_{b}(h)^{-1}$ and thus $\tau_{a}(g)$ is
conjugated with $\tau_{b}(g)$, which proves that the conjugacy class of
$\tau_{a}(g)$ is indeed defined independently of $a$. Finally, as $\tau_{a}$
is a group morphism, the image are of two conjugated elements are conjugated,
meaning that $\tau_{a}$ does indeed induces bijection between the conjugacy
classes of the left and right Schützenberger groups, independently of the
choice of $a$. ∎

In the next proposition, we formalize the idea of searching the fixed points
as some centralizer, but in the context of a monoid.

######  Proposition 14.

Let $H$ be a $\mathcal{H}$-class, $a\in H$ and
$(h,k)\in{}_{M}\operatorname{Stab}(\mathcal{R}(H))\times\operatorname{Stab}_{M}(\mathcal{L}(H))$.
Then

$|\operatorname{Fix}_{H}(h,k)|=\left\\{\begin{aligned}
&|C_{\Gamma^{\prime}(H)}(\times_{H}k)|&&\textrm{ if
}\tau_{a}(h\times_{H})^{-1}\in\overline{\times_{H}k}\\\ &0&&\textrm{
otherwise}\end{aligned}\right.$

where $\overline{\times_{H}k}$ is the conjugacy class of $\times_{H}k$ in
$\Gamma^{\prime}(H)$ and $C_{\Gamma^{\prime}(H)}(\times_{H}k)$ is the
centralizer in $\Gamma^{\prime}(H)$ of $\times_{H}k$.

###### Proof.

For simplicity, we commit an abuse of notation by denoting $h\times_{H}$ as
$h$ and $\times_{H}k$ as $k$. Let $a$ be any element of $H$.

$\displaystyle\operatorname{Fix}_{H}(h,k)$ $\displaystyle=\\{b\in
H\,|\,hbk=b\\}$ $\displaystyle=\\{a\cdot g\,|\,g\in\Gamma^{\prime}(H)\textrm{
and }ha\cdot gk=a\cdot g\\}$ $\displaystyle=\\{a\cdot
g\,|\,g\in\Gamma^{\prime}(H)\textrm{ and }a\cdot\tau_{a}(h)gk=a\cdot g\\}$
$\displaystyle=\\{a\cdot g\,|\,g\in\Gamma^{\prime}(H)\textrm{ and
}\tau_{a}(h)gk=g\\}.$

The last equality comes from the fact that $\Gamma^{\prime}(H)$ acts freely so
we can simplify the $a$. Suppose that $\operatorname{Fix}_{H}(h,k)$ is non-
empty and let $\gamma\in\Gamma^{\prime}(H)$ such that $\tau_{a}(h)\gamma
k=\gamma$. Then, for any $g\in\Gamma^{\prime}(H)$ :

$\tau_{a}(h)gk=g\Leftrightarrow g^{-1}\tau_{a}(h)gk=e\Leftrightarrow
g^{-1}\gamma k^{-1}\gamma^{-1}gk\ =e\Leftrightarrow[\gamma^{-1}g,k]=e$

where $[\cdot,\cdot]$ is the commutation bracket. This means that

$\operatorname{Fix}_{H}(h,k)=\\{a\cdot g\,|\,g\in\gamma
C_{\Gamma^{\prime}(H)}(k)\\}.$

Note that because, again, $\Gamma^{\prime}(H)$ acts freely,
$\operatorname{Fix}_{H}(h,k)$ has the same cardinality as
$C_{\Gamma^{\prime}(H)}(k)$ and that, from Proposition 13 this is independent
from the choice of $a$ which proves the result. ∎

######  Example 15.

Consider $a=[1\ 2\ 2\ 3]\in T_{4}$ and $H=\mathcal{H}(a)$. We have
$\mathrm{Im}\,a=\\{1,2,3\\}$ and $\ker a=\\{\\{1\\},\\{2,3\\},\\{4\\}\\}$.
Notice that $H$ is not a group since $a^{2}=[1\ 2\ 2\ 2]\notin H$. Considering
the Schützenberger groups as symmetric groups on the image and kernel common
to all elements of $H$ as in Example 7, we have
$\Gamma(H)=\mathfrak{S}(\mathrm{Im}\,a)$ and
$\Gamma^{\prime}(H)=\mathfrak{S}(\ker a)$. Let us first check for fixed points
under the action of $h=[1\ 2\ 3\ 4]$ on the left and $k=[2\ 1\ 1\ 4]$ on the
right. Seen as an element of $\Gamma(H)$, $h$ corresponds to
$\mathrm{Id}_{\mathrm{Im}\,a}$ and $k$ corresponds to $(\\{2,3\\}\ \\{1\\})$
in $\Gamma^{\prime}(H)$. Since we have $\tau_{a}(h)=\mathrm{Id}_{\ker a}$, it
follows that $|\operatorname{Fix}_{H}(h,k)|=0$. If we now take $h$ to be $[1\
3\ 2\ 4]$, the corresponding element in $\Gamma(H)$ is $(2\ 3)$ and
$\tau_{a}(h)=(\\{2,3\\}\ \\{4\\})$. Since $(\\{2,3\\}\ \\{4\\})$ and
$(\\{2,3\\}\ \\{1\\})$ are conjugated in $\mathfrak{S}(\ker a)$, the set of
fixed points is non-empty. Their centralizers have cardinal 2 and one can
indeed check that $[2\ 3\ 3\ 1]$ and $[3\ 2\ 2\ 1]$ are the only fixed points
in $H$.

Putting together the previous results, we get the following Corollary on the
cardinality of $\operatorname{Fix}_{J}(h,k)$.

######  Corollary 16.

Let $J$ be a $\mathcal{J}$-class, $a$ any element of $J$ and denote by
$H_{0}=\mathcal{H}(a),R_{0}=\mathcal{R}(a),L_{0}=\mathcal{L}(a)$. Let $h,k$ be
any elements of $M$. We denote by:

  * •

$(\lambda_{R},\lambda^{\prime}_{R})$ a left Green pair with respect to
$(R_{0},R)$ for each $\mathcal{R}$-class $R\subset J$,

  * •

$(\rho_{L},\rho^{\prime}_{L})$ a right Green pair with respect to $(L_{0},L)$
for each $\mathcal{L}$-class $L\subset J$,

  * •

$S_{\mathcal{R}}(h)=\\{R\subset J\,|\,R\textrm{ is a
}\mathcal{R}\textrm{-class and }hR=R\\}$,

  * •

$S_{\mathcal{L}}(k)=\\{L\subset J\,|\,R\textrm{ is a
}\mathcal{L}\textrm{-class and }Lk=L\\}$

Denoting the set of conjugacy classes of $\Gamma^{\prime}(H_{0})$ as $C$, we
further define two vectors:

  * •

$r_{J}(h)=(|C_{\Gamma^{\prime}(H)}(g)|\cdot|\\{R\in
S_{\mathcal{R}}(h)\,|\,\tau_{a}(\lambda_{R}^{\prime}h\lambda_{R})\in\bar{g}\\}|)_{\bar{g}\in
C}$,

  * •

$l_{J}(k)=(|\\{L\in
S_{\mathcal{L}}(k)\,|\,\rho_{L}^{\prime}k\rho_{L}\in\bar{g}\\}|)_{\bar{g}\in
C}$.

Then $\operatorname{Fix}_{J}(h,k)$ has cardinality the dot product of
$r_{J}(h)$ with $l_{J}(k)$.

##  II Modules: character table and Cartan matrix

In the remainder of this paper, $\mathbf{k}$ is a perfect field of null
characteristic and $M$ is still a finite monoid. Furthermore, we suppose that
$\mathbf{k}$ is "big enough", meaning that if not algebraically closed, at
least a splitting field for the characteristic polynomials of the elements of
$M$ seen as linear maps on $\mathbf{k}M$.

We will discuss the representation theory of a monoid $M$ over $\mathbf{k}$
using the language of modules. That is, a representation of $M$ over
$\mathbf{k}$ will be a $\mathbf{k}$-vector space $V$ equipped with a linear
action of the algebra $\mathbf{k}M$. As is usage, whenever the action is on
the left we will say that $V$ is a $\mathbf{k}M-\operatorname{mod}$ and a
$\operatorname{mod}-\mathbf{k}M$ if the action is on the right. If $M$,
$M^{\prime}$ are two finite, possibly different monoids, a
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M^{\prime}$ is simply simultaneously
a $\mathbf{k}M-\operatorname{mod}$ and a
$\operatorname{mod}-\mathbf{k}M^{\prime}$. For a monoid $M$, we denote by
$M^{op}$ the _opposite_ monoid, with multiplication defined by
$m\cdot_{M^{op}}m^{\prime}=m^{\prime}m$. We will use liberally the fact that a
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M^{\prime}$ is naturally a
$\mathbf{k}M\otimes\mathbf{k}M^{\prime op}-\operatorname{mod}$ and a
$\mathbf{k}(M\times M^{\prime op})-\operatorname{mod}$, and reciprocally. In
the totality of this paper, we assume that the modules are finite dimensional
as vector spaces over $\mathbf{k}$. Because of this, the Jordan-Hölder Theorem
applies and the set of composition factors counted with multiplicities of a
module is independent of the choice of a composition series. If $S$ is a
$\mathbf{k}M$-module and $S$ is a simple $\mathbf{k}M$-module, we denote by
$[V:S]$ the multiplicity of $S$ as a composition factor of $V$.

In this section, we deal with monoid representation theory, with the goal in
mind to compute the character table of $M$. Using the Munn-Clifford-
Ponizovskii, this can largely be reduced to group representation theory.
Stated differently, the representation theory of a monoid $M$ is an extension
of the representation theory of certain groups embedded in $M$. The groups in
question are precisely the groups of Definition 9. In the first part of this
section, we use this fact to find a description of an $\mathcal{L}$-class
containing an idempotent $e$ quotiented by its radical as a product of simple
$\mathbf{k}G_{e}$-modules and simple $\mathbf{k}M$-modules. In the second
part, we translate this decomposition in terms of characters, which gives us
the formula we seek. Finally, we recall and discuss the formula for the Cartan
matrix from Thiéry [4].

###  1 On modules

Note that if we choose an element $a\in M$ and denote by $L$ its
$\mathcal{L}$-class and $H$ its $\mathcal{H}$-class, we can equip
$\mathbf{k}L$ with a
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}\Gamma^{\prime}(H)$ structure.
$\mathbf{k}L$ is already a $\operatorname{mod}-\mathbf{k}\Gamma^{\prime}(H)$
by definition of $\Gamma^{\prime}(H)$. We can also make it into a
$\mathbf{k}M-\operatorname{mod}$ by setting, for every $m\in M$ and $l\in L$:

$m\cdot l=\left\\{\begin{aligned} &ml\textrm{ if }ml\in L\\\ &0\textrm{
otherwise}\end{aligned}\right..$

This is well defined, as $ml\notin L$ implies that $l>_{\mathcal{L}}ml$ and so
for every $m^{\prime}\in M$, $l>_{\mathcal{L}}m^{\prime}ml\notin L$ : once
fallen out of $L$, we cannot climb back in.

We have previously stated that the representation theory of monoids is an
extension of the representation theory of some subgroups. This mainly
expressed using the two following functors.

######  Definition 17.

Let $e\in M$ be an idempotent, $\mathcal{L}(e)$ its $\mathcal{L}$-class,
$G_{e}$ the associated maximal subgroup. We define the two following maps :

$\displaystyle\operatorname{Ind}_{G_{e}}^{M}:$
$\displaystyle\left\\{\begin{aligned}
\mathbf{k}G_{e}\mathrm{-mod}&\longrightarrow\mathbf{k}M\mathrm{-mod}\\\
V&\longmapsto\mathbf{k}\mathcal{L}(e)\otimes_{\mathbf{k}G_{e}}V\end{aligned}\right.$
$\displaystyle N_{e}:$ $\displaystyle\left\\{\begin{aligned}
\mathbf{k}M\mathrm{-mod}&\longrightarrow\mathbf{k}M\mathrm{-mod}\\\
V&\longmapsto\\{v\in V\,|\,eMv=0\\}\end{aligned}\right..$

The idempotents and their maximal subgroups play a central role in the theory.
One can show (see for instance [6, Proposition 1.14]) that if $e,f$ are two
idempotents in the same $\mathcal{J}$-class, there are some $x,x^{\prime}\in
M$ such that $xx^{\prime}=e$ and $x^{\prime}x=f$ and that $G_{e}\cong G_{f}$.
A $\mathcal{J}$-class containing an idempotent is called a _regular_
$\mathcal{J}$-class.

We are almost ready to state the Clifford-Munn-Ponizovskii theorem, which is
the central piece connecting group and monoid representation theory. We will
need the notion of _apex_ of a $\mathbf{k}M$-module. A proof of the Clifford-
Munn-Ponizovskii Theorem can be found in [9, Section 5.2].

######  Definition 18.

Let $V$ be a $\mathbf{k}M-\operatorname{mod}$, we denote its annihilator in
$M$ by $\operatorname{Ann}_{M}(V)=\\{m\in M\,|\,mV=\\{0\\}\\}$. This is
clearly an two-sided ideal of $M$ and as such is an union of
$\mathcal{J}$-classes. A regular $\mathcal{J}$-class $J$ is said to be the
_apex_ of $V$ if $\operatorname{Ann}_{M}(V)=I_{J}$ where
$I_{J}=\\{J\not\leq_{\mathcal{L}}\mathcal{J}(s)\,|\,s\in M\\}$. If $e\in J$ is
an idempotent, we also say that $V$ has apex $e$.

######  Théorème 19 (Clifford-Munn-Ponizovskii).

Let $M$ be a finite monoid, $e\in M$ an idempotent and $\mathbf{k}$ be a
field.

  1. 1.

There is a bijection between isomorphism classes of simple $M$-modules with
apex $e$ and isomorphism classes of simple $G_{e}$-modules given by :

$V\longmapsto
V^{\\#}=\operatorname{Ind}_{G_{e}}^{M}(V)/\operatorname{rad}(\operatorname{Ind}_{G_{e}}^{M}(V)).$

The reciprocal bijection is given by $S\longmapsto eS$.

  2. 2.

$\operatorname{rad}(\operatorname{Ind}_{G_{e}}^{M}(V))=N_{e}(\operatorname{rad}(\operatorname{Ind}_{G_{e}}^{M}(V)))$

  3. 3.

Every simple $M$-module has an apex.

  4. 4.

Every composition factor of $\operatorname{Ind}_{G_{e}}^{M}(V)$ with the
exception of $V^{\\#}$ has an apex strictly $\mathcal{J}$-greater than $e$.
Moreover, $V^{\\#}$ has apex $e$ and is a factor of multiplicity one.

This allows us the following description of the $\mathcal{L}$-class of an
idempotent $e$.

######  Proposition 20.

Let $e\in M$ be an idempotent and $G_{e}$ be the maximal subgroup at $e$. Let
$\operatorname{Irr}_{e}$ be a set of representatives of the isomorphism
classes of simple $\mathbf{k}G_{e}$-modules. Then:

$\mathbf{k}\mathcal{L}(e)=\bigoplus_{V\in\operatorname{Irr}_{e}}\operatorname{Ind}^{M}_{G_{e}}(V)\otimes_{\mathbf{k}}V^{*}$

where $V^{*}$ is the dual of $V$.

###### Proof.

By definition,
$\operatorname{Ind}^{M}_{G_{e}}(V)=\mathcal{L}(e)\otimes_{\mathbf{k}G_{e}}V$.
Now, since direct sum and tensor product over a ring with identity commute :

$\bigoplus_{V\in\operatorname{Irr}_{e}}\operatorname{Ind}^{M}_{G_{e}}(V)\otimes
V^{*}=\bigoplus_{V\in\operatorname{Irr}_{e}}\mathbf{k}\mathcal{L}(e)\otimes_{G_{e}}V\otimes
V^{*}=\mathbf{k}\mathcal{L}(e)\otimes_{G_{e}}\left(\bigoplus_{V\in\operatorname{Irr}_{e}}V\otimes
V^{*}\right)$

Because $\mathbf{k}$ is of null characteristic, $\mathbf{k}G_{e}$ is semi-
simple. By the Wedderburn-Artin theorem,
$\mathbf{k}G_{e}=\bigoplus_{V\in\operatorname{Irr}_{e}}V\otimes V^{*}$ so :

$\bigoplus_{V\in\operatorname{Irr}_{e}}\operatorname{Ind}^{M}_{G_{e}}(V)\otimes
V^{*}=\mathbf{k}\mathcal{L}(e)\otimes_{\mathbf{k}G_{e}}\mathbf{k}G_{e}=\mathcal{L}(e)$

since $\mathbf{k}G_{e}$ is a ring with identity. ∎

Note that this puts in relation three kinds of modules : the simple
$\mathbf{k}G_{e}$-modules, which are well understood,
$\mathbf{k}\mathcal{L}(e)$ which is understood as well because it is a
combinatorial module444That is, the multiplication of an element of the basis
of the module by an element of $M$ is either an other element of the basis or
0., and finally the modules $\operatorname{Ind}^{M}_{G_{e}}(V)$ which contain,
in a sense, the simple $\mathbf{k}M$-modules that we are after. According to
the Clifford-Munn-Ponizovskii Theorem, we still need to remove the radical of
each $\operatorname{Ind}^{M}_{G_{e}}(V)$ factor. Proposition 23 puts the
radical in a form similar to Theorem 19 while Proposition 24 does exactly
this. Lemma 21 and its Corollary are technical results on radicals used in the
proof of Proposition 23.

######  Lemma 21.

Let $A,B$ be two finite dimensional algebras over a perfect field
$\mathbf{k}$. Then:

$\operatorname{rad}(A\otimes B)=\operatorname{rad}(A)\otimes
B+A\otimes\operatorname{rad}(B).$

While we haven’t be able to find a source for that claim it seems to be
folklore in the algebra representation community. For the sake of
completeness, we reproduce a proof communicated to us by Pr. Pierre-Guy
Plamondon555Pr. Pierre-Guy Plamondon, Laboratoire de Mathématiques de
Versailles, Université Paris-Saclay, website..

###### Proof.

Because $\mathbf{k}$ is perfect, Wedderburn’s Principal Theorem applies and we
get the decompositions
$A=A^{\prime}\oplus\operatorname{rad}(A),B=B^{\prime}\oplus\operatorname{rad}(B)$,
with $A^{\prime}$ and $B^{\prime}$ semi-simple algebras. To prove the result,
we show that $\operatorname{rad}(A)\otimes B+A\otimes\operatorname{rad}(B)$ is
a nil radical and that

${\mathchoice{\raisebox{3.41666pt}{$\displaystyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\displaystyle{\operatorname{rad}(A)\otimes
B+A\otimes\operatorname{rad}(B)}$}}{\raisebox{3.41666pt}{$\textstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\textstyle{\operatorname{rad}(A)\otimes
B+A\otimes\operatorname{rad}(B)}$}}{\raisebox{2.39166pt}{$\scriptstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.625pt}{$\scriptstyle{\operatorname{rad}(A)\otimes
B+A\otimes\operatorname{rad}(B)}$}}{\raisebox{1.70833pt}{$\scriptscriptstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-1.875pt}{$\scriptscriptstyle{\operatorname{rad}(A)\otimes
B+A\otimes\operatorname{rad}(B)}$}}}$

is semi-simple. Let us first show that the quotient is semi-simple. We have:

$\displaystyle A\otimes B$
$\displaystyle=(A^{\prime}\oplus\operatorname{rad}(A))\otimes(B^{\prime}\oplus\operatorname{rad}(B))$
$\displaystyle=A^{\prime}\otimes B^{\prime}\oplus
A^{\prime}\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B^{\prime}\oplus\operatorname{rad}(A)\otimes\operatorname{rad}(B).$

On the other hand, the same decompositions give us

$A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B=A^{\prime}\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B^{\prime}\oplus\operatorname{rad}(A)\otimes\operatorname{rad}(B).$

Finally,

${\mathchoice{\raisebox{3.41666pt}{$\displaystyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\displaystyle{A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B}$}}{\raisebox{3.41666pt}{$\textstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.75pt}{$\textstyle{A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B}$}}{\raisebox{2.39166pt}{$\scriptstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.625pt}{$\scriptstyle{A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B}$}}{\raisebox{1.70833pt}{$\scriptscriptstyle{A\otimes
B}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-1.875pt}{$\scriptscriptstyle{A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes
B}$}}}=A^{\prime}\otimes B^{\prime}$

which, since $A^{\prime},B^{\prime}$ are semi-simple, is also semi-simple.
$A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes B$ is also
nil, because $\operatorname{rad}(B)$ and $\operatorname{rad}(A)$ are, so,
indeed, $\operatorname{rad}(A\otimes
B)=A\otimes\operatorname{rad}(B)\oplus\operatorname{rad}(A)\otimes B$. ∎

From Lemma 21, we get the following Corollary by recalling that if $V$ is a
$A$-module, $\operatorname{rad}_{A}(V)=\operatorname{rad}(A)\cdot V$.

######  Corollary 22.

Let $A,B$ be two finite dimensional unitary algebras over a perfect field. If
$V_{A}\otimes V_{B}$ is a $A-\operatorname{mod}-B$ (or equivalently a
$A\otimes B^{op}-\operatorname{mod}$), then

$\operatorname{rad}_{A\otimes B^{op}}(V_{A}\otimes
V_{B})=\operatorname{rad}_{A}(V_{A})\otimes
B+A\otimes\operatorname{rad}_{B}(V_{B}).$

This allows us to identify the radical of $\mathbf{k}\mathcal{L}(e)$.

######  Proposition 23.

Let $M$ be a finite monoid, $e\in S$ an idempotent $G_{e}$ be the maximal
subgroup at $e$ and $\mathbf{k}$ be a perfect field. Then:

$\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}(\mathbf{k}\mathcal{L}(e))=N_{e}(\mathbf{k}\mathcal{L}(e)).$

###### Proof.

Using Lemma 21, for $V$ a simple $G_{e}$-module, we have that :

$\displaystyle\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}$
$\displaystyle(\operatorname{Ind}^{S}_{G_{e}}(V)\otimes_{\mathbf{k}}V^{*})$
$\displaystyle=$
$\displaystyle\operatorname{rad}_{\mathbf{k}M}\operatorname{Ind}_{G_{e}}^{M}(V)\otimes
V^{*}+\operatorname{Ind}_{G_{e}}^{M}(V)\otimes\operatorname{rad}_{\mathbf{k}G_{e}^{op}}(V^{*})$
$\displaystyle\overset{(1)}{=}$
$\displaystyle\operatorname{rad}_{\mathbf{k}M}\operatorname{Ind}_{G_{e}}^{M}(V)\otimes
V^{*}$ $\displaystyle\overset{(2)}{=}$ $\displaystyle
N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))\otimes V^{*}$

where equality (1) comes from the simplicity of $V^{*}$ as a
$\mathbf{k}G_{e}^{op}$-module and (2) is the second point of Theorem 19.

Since radical and direct sums commute, denoting by $\operatorname{Irr}_{e}$ a
set of representatives of the isomorphism classes of simple
$\mathbf{k}G_{e}$-modules, we know that:

$\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}(\mathcal{L}(e))=\bigoplus_{V\in\operatorname{Irr}_{e}}N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))\otimes
V^{*}.$

It remains to be seen why

$\bigoplus_{V\in\operatorname{Irr}_{e}}N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))\otimes
V^{*}=N_{e}(\mathbf{k}\mathcal{L}(e)).$

It is clear the direct sum on the left is a subset of the set on the right.
For the other inclusion, we see that if $V,V^{\prime}$ are
$\mathbf{k}M$-modules, $N_{e}(V\oplus V^{\prime})=N_{e}(V)\oplus
N_{e}(V^{\prime})$. Given the proposition 20, it is enough to show that
$N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))\otimes
V^{*}=N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V)\otimes V^{*})$. Let
$x\in\operatorname{Ind}_{G_{e}}^{M}(V)\otimes V^{*}$ be such that for every
$m\in M,emx=0$. $x$ can be writen as $\sum_{i}(\sum_{j}x_{i,j}b_{j})\otimes
b^{\prime}_{i}$ where $\\{b_{j}\\}_{j}$ is a basis of
$\operatorname{Ind}_{G_{e}}^{M}(V)$ and $\\{b^{\prime}_{i}\\}_{i}$ is a basis
of $V^{*}$. For every $m\in M$, we have :

$em\cdot x=em\cdot\sum_{i}(\sum_{j}x_{i,j}b_{j})\otimes
b^{\prime}_{i}=\sum_{i}(em\cdot\sum_{j}x_{i,j}b_{j})\otimes b^{\prime}_{i}=0$

that is, for every $b^{\prime}_{i}$ we get $em\cdot\sum_{j}x_{i,j}b_{j}=0$ so
$\sum_{j}x_{i,j}b_{j}\in N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))$ which means
$x\in N_{e}(\operatorname{Ind}_{G_{e}}^{M}(V))\otimes V^{*}$. ∎

######  Proposition 24.

Let $e\in M$ be an idempotent and $G_{e}$ be the maximal subgroup at $e$. Let
$\operatorname{Irr}_{e}$ be a set of representatives of the isomorphism
classes of simple $\mathbf{k}G_{e}$-modules. Then:

$\mathbf{k}\mathcal{L}(e)/\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}(\mathbf{k}\mathcal{L}(e))\cong\bigoplus_{V\in\operatorname{Irr}_{e}}V^{\\#}\otimes
V^{*}.$

###### Proof.

From Proposition 23, we have a decomposition of
$\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}(\mathcal{L}(e))$
as a direct sum adapted to the decomposition of $\mathbf{k}\mathcal{L}(e)$ as
$\bigoplus_{V\in\operatorname{Irr}_{e}}\operatorname{Ind}^{S}_{G_{e}}(V)\otimes_{\mathbf{k}}V^{*}$.
So:

$\mathbf{k}\mathcal{L}(e)/\operatorname{rad}_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}(\mathbf{k}\mathcal{L}(e))\cong\bigoplus_{V\in\operatorname{Irr}_{e}}(\operatorname{Ind}^{S}_{G_{e}}(V)\otimes_{\mathbf{k}}V^{*})/(N_{e}(\operatorname{Ind}^{S}_{G_{e}}(V))\otimes
V^{*}).$

From Theorem 19, we know that

$0\longrightarrow
N_{e}(\operatorname{Ind}^{S}_{G_{e}}(V))\longrightarrow\operatorname{Ind}^{S}_{G_{e}}(V)\longrightarrow
V^{\\#}\longrightarrow 0$

is a short exact sequence. Since
$N_{e}(\operatorname{Ind}^{S}_{G_{e}}(V))\otimes V^{*}$ a submodule of
$\operatorname{Ind}^{S}_{G_{e}}(V)\otimes V^{*}$ and because tensor product is
right exact we have a short exact sequence :

$0\longrightarrow N_{e}(\operatorname{Ind}^{S}_{G_{e}}(V))\otimes
V^{*}\longrightarrow\operatorname{Ind}^{S}_{G_{e}}(V)\otimes
V^{*}\longrightarrow V^{\\#}\otimes V^{*}\longrightarrow 0$

which proves the result. ∎

###  2 On characters

One of the major features of the finite group representation theory is the
fact that all the information on a representation can be summarized in its
_character_. This (partially) carries over to monoid representation theory, as
we shall see in this section where we reformulate the results of the previous
section in terms of characters.

######  Definition 25.

If $V$ is a finite dimension $\mathbf{k}M$-module, its _character_ is the map
from $M$ to $\mathbf{k}$ defined by
$\chi_{\mathbf{k}M}^{V}:m\longmapsto\operatorname{Tr}(v\mapsto m\cdot v)$.

We recall the following well know facts about characters. Proofs for fact 2
and 3 are respectively (ii) and (iii) of [9, Proposition 7.12]666Note that for
Fact 3, our reference deals only with the case $M=M^{\prime}$, but the proof
is the same..

######  Proposition 26.

  1. 1.

Let $V$ be a $\mathbf{k}M$-module. We have
$\chi_{\mathbf{k}M}^{V}=\chi_{\mathbf{k}M^{op}}^{V^{*}}$.

  2. 2.

Consider the short exact sequence of $\mathbf{k}M$-modules :

$0\longrightarrow A\longrightarrow B\longrightarrow B/A\longrightarrow 0.$

Then $\chi_{\mathbf{k}M}^{B/A}=\chi_{\mathbf{k}M}^{B}-\chi_{\mathbf{k}M}^{A}$.

  3. 3.

Consider $M,M^{\prime}$ two finite monoids, $V$ a $\mathbf{k}M$-module and $W$
a $\mathbf{k}M^{\prime op}$-module. Then
$\chi_{\mathbf{k}M\otimes\mathbf{k}M^{\prime}}^{V\otimes
W}=\chi_{\mathbf{k}M}^{V}\chi_{\mathbf{k}M^{\prime}}^{W}$.

The previous properties are simply extensions of similar properties on groups,
and their proof is similar. From groups, we also keep in the case of monoids
the linear independence of irreducible characters (see [9, Theorem 7.7] for
reference):

######  Proposition 27.

The irreducible characters $\\{\chi_{\mathbf{k}M}^{S}\,|\,S\textrm{ is a
simple }\mathbf{k}M-\operatorname{mod}\\}$ are linearly independent as
$\mathbf{k}$ valued functions.

This, together with the second point in the Proposition 26, has a nice
consequence. As we are interested in finite dimensional module over finite
monoids, those modules have a composition series. Say that a
$\mathbf{k}M$-module $V$, has $S$ as a composition factor with multiplicity
$[V:S]$ for any simple $\mathbf{k}M$-module $S$. Then:

$\chi_{\mathbf{k}M}^{V}=\sum_{S}[V:S]\chi_{\mathbf{k}M}^{S}.$

In that way, since characters of the simple modules are linearly independent,
the character of a module can be seen as a record of its composition factors.

The question of where to compute characters is worth asking: in the case of
groups, one needs only to compute the character for a transversal of conjugacy
classes to get its value everywhere. The case of monoids was described for the
first time by McAlister in [10].

######  Definition 28.

We say that two elements $m,m^{\prime}$ in $M$ are in the same _generalized
conjugacy class_ or _character equivalency class_ if for every
$\mathbf{k}M$-module $V$, $\chi_{M}^{V}(m)=\chi_{M}^{V}(m^{\prime})$. We note
$C_{M}$ the set of generalized conjugacy classes.

######  Proposition 29.

([10, Proposition 2.5]) Let $\mathcal{E}=\\{e_{1},\dots,e_{n}\\}$ be
idempotent representatives of the regular $\mathcal{J}$-classes of $M$ and for
each $e_{i}$ let $\mathcal{C}_{i}=\\{c_{i,1},\dots,c_{i,m_{i}}\\}$ be
representatives of the conjugacy classes of $G_{e_{i}}$. Then the set
$\mathcal{C}_{M}=\bigcup_{e_{i}\in\mathcal{E}}\mathcal{C}_{i}$ is a set of
representatives of character equivalency classes of $M$.

We can now recall the definition of the character table of a monoid.

######  Definition 30.

Let $\operatorname{Irr}_{M}$ be the set of isomorphism classes of simple
$\mathbf{k}M$-modules and $C_{M}$ as in definition 28. The _character table_
of $M$ over $\mathbf{k}$ is the (square) matrix defined by :

$X(M)=(\chi_{\mathbf{k}M}^{V}(m))_{V\in\operatorname{Irr}_{M},m\in C_{M}}.$

Moreover, if $e\in M$ is an idempotent, we define $X_{e}(M)$ as the matrix
obtained by extracting from $X(M)$ only the lines corresponding to simple
modules with apex $e$.

Finally, we can apply the language of characters to Proposition 24, which
yield a formula for computing the character table of $M$ over $\mathbf{k}$
given the character tables of the groups $G_{e}$ over $k$.

######  Proposition 31.

Let $e\in M$ be an idempotent, $G_{e}$ be the maximal subgroup at $e$. We have
the formula for $X_{e}(M)$ :

$X_{e}(M)={}^{t}X(G_{e})^{-1}\cdot\left(\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{\mathbf{k}\mathcal{L}(e)}(m,g)-\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{N_{e}(\mathbf{k}\mathcal{L}(e))}(m,g)\right)_{g\in
C_{G_{e}},m\in C_{M}}$

where the dot is the matrix product.

###### Proof.

First, we have, because of Proposition 26-2, we have:

$\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{\mathbf{k}\mathcal{L}(e)/N_{e}(\mathbf{k}\mathcal{L}(e))}=\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{\mathbf{k}\mathcal{L}(e)}(m,g)-\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{N_{e}(\mathbf{k}\mathcal{L}(e))}(m,g)$

Then, from Proposition 24, we know that:

$\displaystyle\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{\mathbf{k}\mathcal{L}(e)/N_{e}(\mathbf{k}\mathcal{L}(e))}(m,g)$
$\displaystyle=\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{\bigoplus_{V\in\operatorname{Irr}_{e}}V^{\\#}\otimes
V^{*}}$
$\displaystyle=\sum_{V\in\operatorname{Irr}_{e}}\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{V^{\\#}\otimes
V^{*}}$
$\displaystyle=\sum_{V\in\operatorname{Irr}_{e}}\chi_{\mathbf{k}M}^{V^{\\#}}(m)\chi_{\mathbf{k}G_{e}}^{V}(g)$

This last sum is clearly the dot product between the column of $X(G_{e})$
indexed by $g$ and the column of $X_{e}(M)$ indexed by $m$. That is, the
coefficient in position $(g,m)$ of
$\chi_{M-G_{e}}^{\mathcal{L}(e)/\operatorname{rad}(\mathcal{L}(e))}$ is equal
to the coefficient in position $(g,m)$ of ${}^{t}X(G_{e})\cdot X_{e}(M)$,
which, together with Proposition 26(ii), proves the equality. ∎

###  3 One step beyond: The Cartan matrix

We are, at last, in measure to state the formula from Thiéry for the Cartan
Matrix. Without getting into the specific details, the Cartan matrix can be
seen as measure of how "not semi-simple" the algebra of the monoid is. We use
a non standard definition of the Cartan matrix, first given in [4, Definition
2.6]. A formal proof that this is equivalent to the usual definition can be
found in [9, Corolary 7.28].

######  Definition 32.

Let $\\{S_{1},\dots,S_{n}\\}$ be a set of representatives of the isomorphism
classes of simple $\mathbf{k}M$-modules. The simple
$\mathbf{k}M\otimes\mathbf{k}M^{op}$ modules are the $S_{i}\otimes S_{j}^{*}$
for all $i,j\in\llbracket{1,n}\rrbracket$. Denote by
$[\mathbf{k}M:S_{i}\otimes S_{j}^{*}]$ the multiplicity of $S_{i}\otimes
S_{j}^{*}$ as a composition factor of $\mathbf{k}M$.

The Cartan matrix of $\mathbf{k}M$ is defined by:

$C(\mathbf{k}M)=([\mathbf{k}M:S_{i}\otimes S_{j}^{*}])_{i,j}$

In other words, the Cartan matrix is a recording of the multiplicities of the
composition factors of $\mathbf{k}M$ as a $\mathbf{k}M\otimes\mathbf{k}M^{op}$
module. But so is its character! The difference being that the character of
$\mathbf{k}M$ as it is computed is expressed in the basis of the character
equivalency classes of $M\times M^{op}$ while the Cartan matrix is expressed
directly in the basis of the simple modules. Since the basis change between
the two is precisely given by the character table and hence, we have the
Thiéry’s Formula for the Cartan matrix.

######  Proposition 33.

The Cartan matrix is given by the formula:

$C(\mathbf{k}M)={}^{t}X_{M}^{-1}BX_{M}^{-1}$

where $B=(|\\{s\in M\,|\,msm^{\prime}\\}|)_{m,m^{\prime}\in C_{M}}$

##  III Some explicit computations

In this section, $M$ is a fixed submonoid of $T_{n}$. We explain how to
combinatorially compute the characters of three interesting modules:
$\mathbf{k}J$ for a $\mathcal{J}$-class $J$, $\mathbf{k}M$ as
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M$ and $\mathbf{k}\mathcal{L}(e)$
for an $\mathcal{L}$-class containing an idempotent $e$ as a
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}G_{e}$. For clarity, we will
designate these characters as _bicharacters_.

We begin by discussing the computational hypotheses we make before presenting
the algorithms themselves. In a third subsection, we detail how to compute the
radical of $\mathbf{k}\mathcal{L}(e)$ to apply our formula from Proposition 31
to compute the character table of a monoid. This latter case is not as tidy as
the former ones, as we don’t have a purely combinatorial way of computing the
radical.

###  1 Computational hypotheses

In this section we discuss the computational hypotheses necessary for the
algorithms in the next section. This section is based on the work [11] in
which East, Egry-Nagy, Mitchell and Péresse provide efficient algorithms for
all basic computational questions on finite semigroups (which include
monoids). Although we limit our scope to the case of transformation monoids,
methods described [11] allow the algorithms described below to be applied to
other interesting classes of monoids. Moreover, they can theoretically be
applied to any finite monoid using a Cayley embedding in a full transformation
monoid. In general however, this is very inefficient and not feasible in
practice.

Following the authors of [11], we make the following fundamental assumptions
that we can compute:

  * •

Assumption I : a product of two elements of the monoid.

  * •

Assumption II : the image and kernel of a transformation (note that we do not
explicitly use this assumption, but that it is necessary for the algorithms of
[11] that we do use).

  * •

Assumption III : Green pairs.

  * •

Assumption IV : Given $h\in{}_{M}\operatorname{Stab}(H)$ compute the
corresponding element in $\Gamma(H)$ (understood as a permutation group of the
image common to all elements of $H$ as seen in Example 7), and similarly on
the right.

Not only do we directly need to be able to do these computations for our own
algorithm, but they are also prerequisite for the algorithms from [11]. As
such, we refer to the top of Section 5.2 of [11] on how to realize these
computations in the case of transformation monoids.

We, again, refer to [11] for the specific algorithms meeting our computational
prerequisites.

  * •

Computing the Schützenberger groups: [11, Algorithm 4]

  * •

Checking membership of an element in a Green class: [11, Algorithms 7 & 8].

  * •

Finding idempotents: [11, Algorithm 10]. This algorithm also allows for
finding the regular $\mathcal{J}$-classes.

  * •

Decomposing the monoid in $\mathcal{R},\mathcal{L}$ and $\mathcal{J}$-classes
: [11, Algorithm 11] and its discussion. Note that by storing this
decomposition, we can, given an element of the monoid, find the classes that
contain it.

  * •

Obtaining a representative of a Green class: this is given by the data
structure representing the Green classes described at the top of [11, Section
5.4].

Finally, we require the following points that, although they are not described
in [11], are easily obtained from it.

  * •

Computing a set $C_{M}$ of character equivalency representatives: given
Proposition 29, this can be done in four steps:

    1. 1.

compute a set $\mathcal{E}$ of idempotent representatives of the regular
$\mathcal{J}$-classes,

    2. 2.

compute $\Gamma(\mathcal{H}(e))$ for each $e\in\mathcal{E}$,

    3. 3.

compute a set $C_{e}$ of representatives of the conjugacy classes of
$\Gamma(\mathcal{H}(e))$ for each $e\in\mathcal{E}$, using for instance the
procedure described in [12],

    4. 4.

for each $e\in\mathcal{E}$ and $c\in C_{e}$ compute the corresponding element
of $\mathcal{H}(e)$ as in Example 10.

  * •

Computing $\tau_{a}$ as in Proposition 13 : given $g\in\Gamma(H)$,
$\tau_{a}(g)$ is simply, seen as an element of $\mathfrak{S}(\ker a)$ :

$a^{-1}\\{i\\}\mapsto(g\cdot a)^{-1}\\{g\cdot a(i)\\},$

which can be computed in $O(n)$. Note that this is a special case of the
application described in [11, Proposition 3.11 (a)]

  * •

Testing that two elements $g,g^{\prime}$ in $\Gamma^{\prime}(\mathcal{H}(a))$
are conjugated : $\Gamma^{\prime}(H)$ is represented as a subgroup of
$\mathfrak{S}(\ker a)$ and known procedures, such as the one described in
[13], can be used.

  * •

Computing the cardinality of a conjugacy class of a Schützenberger group: for
instance, the computer algebra system GAP uses the method described in [12].

###  2 Combinatorial bicharacter computing: 3 applications.

We are now ready to present the algorithm for fixed-point counting, keeping in
mind that we want first to use the formula from Section II.2 to compute the
character table of the monoid and further to compute the Cartan matrix of the
monoid. In the cases we are interested in, we use the formalism of character
computing, since, as stated in the Lemma below, computing the characters of so
called _combinatorial modules_ is actually counting fixed points.

######  Lemma 34.

Let $M,M^{\prime}$ be two finite monoids and $(V,B)$ a finite dimensional
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M^{\prime}$ space equipped with a
basis $B$. If the actions of $M,M^{\prime}$ on $(V,B)$ are _combinatorial_ ,
meaning for any $(m,b,m^{\prime})\in M\times B\times
M^{\prime},mbm^{\prime}\in(B\cup\\{0\\})$, then:

$\chi_{\mathbf{k}M\otimes\mathbf{k}M^{\prime op}}^{V}=|\\{b\in
B\,|\,mbm^{\prime}=b\\}|.$

###### Proof.

In the basis $B$, the matrix of the linear map $x\mapsto mxm^{\prime}$ is a
$\\{0,1\\}$-matrix, with for every $b\in B$ exactly one 1 in the $b$-th
column, that 1 being on the $b$-th row if $mbm^{\prime}=b$. Thus, the trace
counts the number of fixed points. ∎

Note that we have already defined a structure of combinatorial
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}G_{e}$ on
$(\mathbf{k}\mathcal{L}(e),\mathcal{L}(e))$ for any idempotent $e$. In the
same way, $\mathbf{k}J$ for a $\mathcal{J}$-class $J$, can be equipped with a
structure of $\mathbf{k}M-\operatorname{mod}-\mathbf{k}M$ by setting for every
$(m,j)\in M\times J$:

$m\cdot j=\left\\{\begin{aligned} &mj\textrm{ if }mj\in J\\\ &0\textrm{
otherwise}\end{aligned}\right.\textrm{ and }j\cdot m=\left\\{\begin{aligned}
&jm\textrm{ if }jm\in J\\\ &0\textrm{ otherwise}\end{aligned}\right..$

As before, this is well defined: firstly because the actions on the left and
on the right commute (because the monoid’s law is associative by assumption)
and secondly because either $m\leq_{\mathcal{L}}m^{\prime}$ or
$m\leq_{\mathcal{R}}m^{\prime}$ imply $m\leq_{\mathcal{J}}m^{\prime}$ so, as
in Section II.1, if $ml$ or $lm$ has "fallen to 0", it can’t "climb back up"
to $J$.

This structure makes $(\mathbf{k}J,J)$ into a combinatorial module and we may
apply our fixed points counting methods to compute its character.

######  Algorithm 35 (Computing the bicharacter of a $\mathcal{J}$-class).

Keeping the assumptions and notations of the previous Paragraph 1, we get from
Corollary 16 an algorithm to compute the bicharacter of $\mathbf{k}J$ as a
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M$:

  * •

Input : A $\mathcal{J}$-class $J$, a set of representatives of the character
equivalency classes $C_{M}$.

  * •

Output : A matrix $(|\\{m\in J\,|\,hmk=m\\}|)_{(h,k)\in C_{M}^{2}}$

  1. 1.

Preparations:

    1. (a)

Choose $a\in J$ and define $H=\mathcal{H}(a)$.

    2. (b)

Compute Green pairs $(\lambda_{R},\lambda_{R}^{\prime})$ (respectively
$(\rho_{L},\rho_{L}^{\prime})$) for $(\mathcal{R}(a),R)$ (resp.
$(\mathcal{L}(a),L)$) for all $\mathcal{R}$-class $R\subset J$ (resp.
$\mathcal{L}$-class $L\subset J$).

    3. (c)

Compute the set $C$ of conjugacy classes of $\Gamma^{\prime}(H)$.

  2. 2.

For each character equivalency representative $h\in C_{M}$, initialize
$r_{J}(h)$ and $l_{J}(h)$ to both be $(0)_{\bar{g}\in C}$.

    1. (a)

For each $\mathcal{R}$-class $R\subset J$, test if $h\lambda_{R}a\in R$. If
so, denoting by $\bar{g}$ the conjugacy class of
$\tau_{a}((\lambda_{R}^{\prime}h\lambda_{R})\times_{H})$ in
$\Gamma^{\prime}(H)$, increment $r_{J}(h)$ by $|C_{\Gamma^{\prime}(H)}(g)|$ at
position $\bar{g}$.

    2. (b)

For each $\mathcal{L}$-class $L\subset J$, test if $a\rho_{R}h\in L$. If so,
denoting by $\bar{g}$ the conjugacy class of
$\times_{H}(\rho_{L}^{\prime}h\rho_{L})$ in $\Gamma^{\prime}(H)$, increment
$r_{J}(h)$ by $1$ at position $\bar{g}$.

  3. 3.

Compute the matrix $\chi=(r_{J}(h)\cdot l_{J}(k))_{(h,k)\in C_{M}^{2}}$ using
the previously computed vectors and return $\chi$.

######  Example 36.

An _aperiodic_ monoid is a monoid where all $\mathcal{H}$-classes are
singletons. Let us apply the algorithm we just described in the case of a
$\mathcal{J}$-class $J$ with trivial $\mathcal{H}$-classes. Several
simplifications occur : first, we don’t need to check for the conjugacy class,
as there is only one. Secondly, the conjugacy class has cardinality one.
Consider the vectors $r_{J}=(|S_{\mathcal{R}}(h)|)_{h\in C_{M}}$ and
$r_{J}=(|S_{\mathcal{L}}(h)|)_{h\in C_{M}}$ with $S_{\mathcal{L}}(h)$ and
$S_{\mathcal{R}}(h)$ defined as in Corollary 16. The bicharacter is simply the
matrix product of $r_{j}^{T}$ with $l_{J}$. The particular case of this
algorithm for aperiodic monoid is described in [4, Section .1]

######  Algorithm 37 (Computing the bicharacter of $\mathbf{k}M$).

If we consider $(\mathbf{k}M,M)$ as a combinatorial
$\mathbf{k}M-\operatorname{mod}-\mathbf{k}M$, we immediately have that:

$\chi_{\mathbf{k}M\otimes\mathbf{k}M^{\prime
op}}^{\mathbf{k}M}=\sum_{J\in\mathcal{J}}\chi_{\mathbf{k}M\otimes\mathbf{k}M^{\prime
op}}^{\mathbf{k}J}$

and we can therefore compute the bicharacter of the whole monoid $M$: we first
compute a set $C_{M}$ of representatives of the character equivalency classes
and we the iterate Algorithm 35 over all $\mathcal{J}$-classes and sum the
results.

The final useful example is the case of counting fixed points in a single
regular $\mathcal{L}$-class, for the purpose of computing the character table
of the monoid.

######  Algorithm 38 (Computing the bicharacter of an $\mathcal{L}$-class).

Let $e$ be an idempotent en let $L=\mathcal{L}(e)$. In this example
$\mathbf{k}L$ is still a combinatorial module, but it has the particularity,
compared with the other two examples, that the monoids on the left and right
are not the same. However, as the maximal subgroup at $e$, $G_{e}$, is a
subsemigroup of $M$, the same results apply at no extra costs.

We can simply adapt the algorithm of Algorithm 35. Since an element of
$C_{G_{e}}$ acts "as itself" on the right, we don’t need to keep track of the
action of the right with a vector $r_{L}$ as we did previously.

  1. 1.

Initialize $\chi$ to $(0)_{(h,k)\in C_{M}\times C}$

  2. 2.

For each $h\in C_{M}$, for each $\mathcal{H}$-class $H$, test if
$h\lambda_{H}a\in H$. If so, denoting by $k$ the conjugacy class of
$\lambda_{H}^{\prime}h\lambda_{H}$ in $G_{e}$, increment $\chi$ by
$|C_{G_{e}}(h)|$ at position $(h,k)$.

  3. 3.

Return $\chi$

###  3 Computing $N_{e}(\mathbf{k}L)$

We are now almost in position to use the formula of Proposition 31: the
character tables of the groups are supposed to be given, as we dispose of
efficient group algorithms in the literature to compute them, from Algorithm
38 we now know how the efficiently compute the bicharacter of
$\mathbf{k}\mathcal{L}(e)$ as a
$\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}$-module for some idempotent $e\in M$.
It remains to compute the bicharacter of $N_{e}(\mathbf{k}\mathcal{L}(e))$ as
a $\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}$-module, which we discuss now.

Let $L=\mathcal{L}(e)$. Recall that, by definition,
$N_{e}(\mathbf{k}L)=\\{x\in\mathbf{k}L\,|\,eMx=0\\}$. Taking $L$ as a basis
for $\mathbf{k}L$, we can form a matrix with rows indexed by $M\times L$ and
columns indexed by $L$, with the coefficient at $((m,l),l^{\prime})=1$ if
$eml=l^{\prime}$ and 0 otherwise. Computing the kernel of this matrix yields a
basis for $N_{e}(\mathbf{k}L)$ but is extremely inefficient as the number of
rows is many times the cardinality of the monoïd.

Notice first that for any $m\in M$, $em\leq_{\mathcal{R}}e$ so we can consider
only the elements of $M$ that are $\mathcal{R}$-smaller than $e$. Conversely,
recall that the structure of $\mathbf{k}M$-module on $M$ is defined by $m\cdot
l=ml$ if $ml\in L$ and $0$ otherwise and that this latter case happens if
$ml\leq_{\mathcal{L}}l$. Since if $m\leq_{\mathcal{L}}l$ implies
$ml\leq_{\mathcal{L}}l$ we have that the $(m,l)$-th row of the matrix is null
and that we may omit it. This shows that we need only to consider the element
of $M$ that are not $\mathcal{L}$-below $e$. Together with the previous point,
this means that the similarly defined matrix but whose rows are only indexed
by $\mathcal{R}(e)\times L$ has the same kernel. This is good news, as we may
now exploit the structure of the $\mathcal{J}$-class given by Green’s Lemma to
further reduce the dimension of this matrix. Indeed, another consequence of
Green’s Lemma is the so called "Location Theorem" from Clifford and Miller. A
proof can be found in [14, Theorem 1.11]

######  Lemma 39 (Location Theorem).

Let $r,l$ be two elements in the same $\mathcal{J}$-class. We have:

$rl=\left\\{\begin{aligned} &\gamma\in\mathcal{R}(r)\cap\mathcal{L}(l)\textrm{
if }\mathcal{L}(r)\cap\mathcal{R}(l)\textrm{ contains an idempotent},\\\
&\gamma<_{\mathcal{J}}l,r\textrm{ otherwise}.\end{aligned}\right.$

$l$$rl$$e$$r$$=$$\times$$\mathcal{R}(r)$$\mathcal{R}(l)$$\mathcal{L}(l)$$\mathcal{L}(r)$
Figure 3: Location Theorem
Since there is an idempotent $e$ in $\mathcal{L}(r)\cap\mathcal{R}(l)$, $rl$
stays in the same $\mathcal{J}$-class, in $\mathcal{L}(l)\cap\mathcal{R}(r)$.

######  Lemma 40.

Let $e\in M$ be an idempotent, $R=\mathcal{R}(e)$ its $\mathcal{R}$-class and
$R^{\prime}$ another $\mathcal{R}$-class of $\mathcal{J}(e)$. Let
$(\lambda,\lambda^{\prime})$ be a left Green pair for $(L,L^{\prime})$. Then
$(\lambda e,e\lambda^{\prime})$ is a left Green pair for $(R,R^{\prime})$.

Similarly, if $L=\mathcal{L}(e)$, $L^{\prime}$ is a $\mathcal{L}$-class of
$\mathcal{J}(e)$ and $(\rho,\rho^{\prime})$ is a right Green pair for
$(L,L^{\prime})$, then $(e\rho,\rho^{\prime}e)$ is a right Green pair for
$(L,L^{\prime})$

###### Proof.

Let $g$ be any element of $\mathcal{H}(e)$ and $g^{\prime}=\lambda g$. Since
$e$ is idempotent, $\mathcal{H}(e)$ is a group with identity $e$ so we have
$e\lambda^{\prime}\lambda eg=e\lambda^{\prime}\lambda g=eg=g$ and $\lambda
ee\lambda^{\prime}g^{\prime}=\lambda eg=\lambda g=g^{\prime}$ which, from
Green’s Lemma, make $(\lambda e,e\lambda^{\prime})$ a left Green pair for
$(L,L^{\prime})$. A similar argument applies for the second part of the
proposition. ∎

######  Remark.

This lemma means that for a regular $\mathcal{J}$-class $J$ and for any two
$\mathcal{L}$-class (or $\mathcal{R}$-class) it contains, we may choose a
corresponding Green pair among the elements of those two classes.

######  Proposition 41.

Let $e\in M$ be an idempotent and
$H=\mathcal{H}(e),L=\mathcal{L}(e),R=\mathcal{R}(e)$ and $J=\mathcal{J}(e)$.
For each $\mathcal{R}$-class $R^{\prime}\subset J$, we choose a left Green
pair $(l,l^{\prime})\in J^{2}$. We denote by $\mathfrak{L}$ the set of all $l$
for the chosen left Green pairs. We define $\mathfrak{R}$ similarly. Then
$N_{e}$ is the set of solutions of :

$\forall r\in\mathfrak{R},\forall g\in
H,\quad\sum_{l\in\mathfrak{L}}\mathds{1}_{H}(rl)x_{l(rl)^{-1}g}=0$

###### Proof.

Consider an element $a\in R$. $a$ can be written in a unique way as $gr$, with
$g\in G$ and $r\in\mathfrak{R}$ corresponding to $\mathcal{L}(a)$. Similarly,
an element $b$ in $L$ as a unique decomposition as
$l\gamma,l\in\mathfrak{L},\gamma\in H$. For an element $x\in\mathbf{k}L$ we
note:

$x=\sum_{l\in\mathfrak{L},\gamma\in H}x_{l\gamma}l\gamma$

its decomposition over the basis $L$.

We want to find the equations that describe $\ker(gr\times_{L})$ (where
$gr\times_{L}$ is the linear map on $\mathbf{k}L$ obtained by extending the
monoid’s multiplication by linearity). From the Location Theorem, we get that
$\mathrm{Im}\,(gr\times_{L})\subset\mathbf{k}H$. For $k\in H$, denote by
$f_{k,gr}$ the $k$-th coordinate function of $gr\times_{L}$. Because
$gr\times_{L}$ acts combinatorially on $\mathbf{k}L$, we have :

$f_{k,gr}(x)=\sum_{l\in\mathfrak{L},\gamma\in
H}\mathds{1}_{\\{k\\}}(grl\gamma)x_{l\gamma}$

Note that $x_{l\gamma}$ appears in the sum if and only if $grl\gamma=k$. From
the Location Theorem, and because we choose $l\in L,r\in R$, we have
$grl\gamma=k\textrm{ if and only if }rl\in H\textrm{ and
}\gamma=(rl)^{-1}g^{-1}k$ and thus the equation becomes:

$f_{k,gr}(x)=\sum_{l\in\mathfrak{L}}\mathds{1}_{H}(rl)x_{l(rl)^{-1}g^{-1}k}.$

For $x$ to be in $\ker(gr\times_{L})$, $x$ must cancel simultaneously
$f_{k,gr}$ for all $k\in H$. We now have a set of equations for
$ker(gr\times_{L})$, and we can deduce that the set of equations

$\forall r\in\mathfrak{R},\forall g,k\in H,\quad
f_{k,gr}(x)=\sum_{l\in\mathfrak{L},\gamma\in
H}\mathds{1}_{H}(rl)x_{l(rl)^{-1}g^{-1}k}=0$

describes $N_{e}(\mathbf{k}L)$. However, the equation system is redundant as
the equation $f_{k,gr}(x)=0$ is the same for all pairs $(g,gk^{\prime})$ with
$k^{\prime}\in H$. Removing the duplicates equation gives the system announced
in the proposition. ∎

######  Example 42 ($N_{e}$ in the case of an aperiodic monoid).

As in Example 36, let us consider the case of a $\mathcal{J}$-class with
trivial $\mathcal{H}$-classes. In this case, we have
$L=\mathfrak{L},R=\mathfrak{R}$ and $H=\\{1_{H}\\}$, so the equations become:
$\forall r\in R,\quad\sum_{l\in M}\mathds{1}_{H}(rl)x_{l}.$ Again from the
Location Theorem, we have that $\mathds{1}_{H}(rl)=1$ if and only if there is
an idempotent in $\mathcal{L}(r)\cap\mathcal{R}(l)$. So if we form a matrix
$A$ with rows indexed by $L$ and columns indexed by $R$, and with coefficients
1 at $(\mathcal{L}(r),\mathcal{R}(l))$ if $\mathcal{L}(r)\cap\mathcal{R}(l)$
contains an idempotent and 0 otherwise, the above equations becomes :
$(x_{l})_{l\in L}^{T}A=0,$ that is, in the case of an $\mathcal{H}$-trivial
$\mathcal{J}$-class, $N_{e}(\mathbf{k}L)$ is the left kernel of the eggbox
picture seen as a $\\{0,1\\}$-matrix.

Note that given this set of equations, we can compute the character
$\chi_{\mathbf{k}M\otimes\mathbf{k}G_{e}^{op}}^{N_{e}(\mathbf{k}\mathcal{L}(e))}$
from the formula in Proposition 31 using classical linear algebra algorithms
to find a basis of $N_{e}(\mathbf{k}\mathcal{L}(e))$ and then computing the
value of the character at any $(m,g)\in C_{M}\times C_{G_{e}}$ by iterating
over the basis vectors, applying $(m,g)$ as a linear map and computing the
relevant coefficient in the image vector.

##  IV Performances, computational complexity and benchmarks

In this section, we discuss performances in terms of complexity whenever we
can, and in terms of benchmarks for timings and memory usage. In the next
paragraph, we discuss the challenges in measuring performances and the
subsequent choices made. Given these considerations, in the three paragraphs
following, we discuss the computationnal performances of our three main
objects of interest: the combinatorial bicharacter (_i.e._ fixed-point
counting), the character table and finally the Cartan matrix.

###  1 Discussion and Challenges

Despite concentrating on transformation monoids, monoids being as diverse as
they are, a meaningful analysis of the complexities of the above algorithms is
difficult to do in terms of elementary parameters such as the rank (_i.e._ the
cardinality of the set acted upon), the number of generators or even the
cardinality. Using only these parameters, we would have to make so many
simplifying assumptions as to lose all meaning in our analysis.

Indeed, for our algorithms, the relevant metrics tends to be related to the
Green-class structure and are the number of $\mathcal{L}$ and
$\mathcal{R}$-classes in a $\mathcal{J}$-class, the cardinality of the
$\mathcal{H}$-classes of a $\mathcal{J}$-class as well as the number of
conjugacy classes in its Schützenberger groups, the number of generalized
conjugacy classes, etc. In some sense, these metrics vary a lot: two
transformation monoids acting on the same number of points with the same
number of generators can have vastly different Green structures. Given this
hurdle, it seems that the most meaningful level of analysis in terms of
complexity is at the level of the $\mathcal{J}$-class, where these parameters
are a constant, rather than on the level of the whole monoid where we do not
have any good monoid-wide estimate of how these useful metrics average out on
all (regular) $\mathcal{J}$-classes. Thus, in the following subsections, we
will comment in any depth on the time complexity only for Algorithm 35 and for
the solving of the equation system from Proposition 41.

Although a theoretical complexity of our algorithms is hard to precisely
provide on the monoid-wide level, the real test of viability is to see if the
algorithm effectively terminates in practice on typical examples. Thus, we
provide benchmarks (for time and memory usage) for the computation of the
three main objects of our discussion: the bicharacter, the character table and
the Cartan Matrix. We would like to know what is the typical performance on a
"randomly chosen finite monoid". However, the question of taking a "generic"
transformation monoid acting on a set number of points is a subject in itself,
and outside the scope of this paper. Thus we chose to use two families of test
cases: firstly the full transformation monoids and secondly random monoids
generated by $m$ elements picked uniformly at random in $T_{n}$ and denoted by
$R(m,n)$. The full transformation monoids constitute a interesting test case
in the sense that they are as big as possible. However, they are also highly
structured and many computer algebra systems, including GAP, are smart enough
to detect that the Schützenberger groups are actually symmetric groups and
thus use some non general algorithms that could not be used on typical finite
monoids. This may introduce bias in our measurements on the full
transformations monoids (and indeed probably does given Figure 4), hence why
we separate the measure made on them from those made on the $R(m,n)$ monoids.

The measurements provided for these new algorithms (as well as the computation
results presented hereafter) all come from an implementation using the
computer algebra system GAP. All performance measures are realized on a laptop
equipped with an Intel Core i7-10850H @ 2.7GHz (on one core) and 16 GB memory.
The measures on random monoids presented in this section are realized on
monoids of the form $R(m,n)$, with
$(m,n)\in\\{(4,3),(5,3),(5,4),(6,5),(7,6),(9,8)\\}$ (with $(9,8)$ excluded in
the character table and Cartan matrices benchmarks) with 10 randomly chosen
test cases for each $(m,n)$ in this set. Every appearance of $R(m,n)$ for a
specific pair $(m,n)$ refers to the same monoid. Our specific implementation,
as well as the test cases used and the raw data, are publicly available on our
git repository777github.com/ZoltanCoccyx/monoid-character-table.

###  2 Fixed point counting

In the case of Algorithm 35, we can give some analysis of the time complexity
in terms of the Green structure of the particular $\mathcal{J}$-class
Algorithm 35 is applied to.

######  Proposition 43.

Consider a $\mathcal{J}$-class $J$ containing $n_{L}$ $\mathcal{L}$-classes,
$n_{R}$ $\mathcal{R}$-classes, containing an $\mathcal{H}$-class $H$ with
$n_{C}$ conjugacy classes in $\Gamma^{\prime}(H)$, and let $C_{M}$ be a set
representatives of the character equivalence classes, as before. Then, the
Algorithm 35 does:

  * •

$n_{C}$ cardinality computations of conjugacy classes of $\Gamma^{\prime}(H)$
(assuming memoization to be able to do a lookup in step 2-a of Algorithm 35,
instead of computing it on the fly),

  * •

$O(|C_{M}|(n_{L}+n_{R}))$ monoid multiplications, Green class membership tests
and conjugacy class of $\Gamma^{\prime}(H)$ membership tests,

  * •

$O(|C_{M}|n_{R})$ computations of $\tau_{a}$,

  * •

$O(|C_{M}|n_{L})$ conjugacy class of $\Gamma^{\prime}(H)$ cardinality lookups,

  * •

$n_{C}|C_{M}|^{2}$ integer multiplications.

###### Proof.

This simply results from an inspection of Algorithm 35. ∎

As explained before, we cannot meaningfully extend this analysis to Algorithm
35. We can get a similar result by inspection of Algorithm 38: it is
essentially the same algorithm, except that it is applied on only one
$\mathcal{L}$-class and that we don’t need the final integer multiplications
ate the end.

Figure 4: Computation time and memory usage of Algorithm 37.
The blue points correspond to the random monoids, the yellow ones to $T_{n}$
for $n\in\llbracket{3,9}\rrbracket$. The yellow points are excluded of the
linear regression as the algorithm is "anormaly" efficient on them: we mesure
a complexity on the full transformation monoids of approximately
$O(\sqrt{|T_{n}|})$ while the measured complexity on random monoids is about
$O(n^{0.76})$ in time and memory.

Note that we do not provide a cumulative formula for the complexity of
Algorithm 35 as for instance the complexity of a conjugacy class membership
test heavily depends on the algorithm used by the computer algebra system,
that can itself vary depending on the characteristics of the Schützenberger
groups. This makes the task of providing a meaningful evaluation of the global
complexity of the algorithm quite difficult, mainly because expressing the
complexity of those "elementary" operations of monoid multiplications,
membership testing, etc… in terms of the same parameters is not
straightforward and in some cases even unknown as noted in [13]. However, we
can at least compare this to the naive algorithm of testing if every element
of $J$ is a fixed point which demands $O(n_{L}n_{R}|H|^{2}|C_{M}|^{2})$ monoid
multiplications: as long as the complexity of the more complex operations of
Green class or conjugacy class membership testing remains limited in terms of
monoid multiplications, our complexity is better. For instance, in the case of
the monoid $T_{n}$, all the required operations can be done on $O(n)$, making
Algorithm 35 (and, in turn, Algorithm 37) more efficient than the naive
algorithm, as can be seen in Table 1, with a sub linear (with respect to
cardinality) measured complexity (Figure 4).

Monoid | Cardinality | Coefficients | Naive | Ours
---|---|---|---|---
$T_{3}$ | 27 | $6^{2}$ | 29 ms | 18 ms
$T_{4}$ | 256 | $11^{2}$ | 92 ms | 63 ms
$T_{5}$ | 3125 | $18^{2}$ | 1.44 s | 113 ms
$T_{6}$ | 46656 | $29^{2}$ | 53.0 s | 0.34 s
$T_{7}$ | 823543 | $44^{2}$ | >30 min | 1.59 s
$T_{8}$ | 16777216 | $66^{2}$ | $\cdots$ | 8.86 s
$T_{9}$ | 387420489 | $96^{2}$ | $\cdots$ | 56.7 s
Table 1: Computation time of the regular representation bicharacter.

###  3 Character table

As shown in Table 2, the computation of the character table takes much longer.
This is due to the fact that, to compute the radical of
$\mathbf{k}\mathcal{L}(e)$ for an idempotent $e$, we must solve a linear
system of size $|\mathcal{R}(e)|\times|\mathcal{L}(e)|$ which necessitates
$O(|\mathcal{R}(e)|^{2}|\mathcal{L}(e)|)$ arithmetic operations. In the case
of the full transformation semigroup $T_{n}$, if $e$ as $k$ elements in its
image, $|\mathcal{L}(e)|=k!\times\binom{n}{k}$, while
$|\mathcal{R}(e)|=k!\times S(n,k)$ where $S(n,k)$ is a Stirling number of the
second kind, which gives $|\mathcal{R}(e)|\sim k^{n}$. The size of that linear
system becomes rapidly untractable. Moreover, once we have a basis of
$N_{e}(\mathbf{k}L)$ of cardinality $d$, we still have to compute the
$C_{M}^{2}$ character values in $O(d^{2})$ operations each. Experiments show
that the computation time of the character tables of the maximal subgroups is
small in comparison of all radical related computations. As can be seen on
Figure 5, time and memory usage are in lockstep (at least for big enough
monoids) and the limiting factor is memory (the test on random monoids fail
for the random monoids of the form $R(9,8)$ by exceeding the 16GB memory
capacity of our testing machine).

Monoid Cardinality Coefficients Ours $T_{3}$ 27 $6^{2}$ 27 ms $T_{4}$ 256
$11^{2}$ 151 ms $T_{5}$ 3125 $18^{2}$ 1.74 s $T_{6}$ 46656 $29^{2}$ 29.8 s
$T_{7}$ 823543 $44^{2}$ 11.0 min

Table 2: Computation time of the character table.

Figure 5: Computation time and memory usage for computing the character table
using Propositions 31 and 41.
The blue points correspond to the random monoids, the yellow ones to $T_{n}$
for $n\in\llbracket{3,7}\rrbracket$. As before, the yellow points are excluded
of the linear regression although in this case, $T_{n}$ behave more or less
like the randomly chosen monoids. The measured complexity on random monoids is
slighly more than linear in time and memory.

###  4 Cartan matrix

Finally, for the computation of the Cartan Matrix, the previous timings show
that the vast majority of the computation time is spent computing the
character table of the monoid. As the computation of the combinatorial
bicharacter is more than a hundred times faster than the computation of the
character table, this is a clear invitation to improve in particular the
computation of the character of the radical of the $\mathcal{L}$-classes. In
Table 3, we show some timings for that computation, and a comparison with Sage
generalist algorithm (based on the Peirce decomposition of the monoid algebra)
for the computation of the Cartan Matrix: despite its limitations our
specialized algorithm allows for the handling of larger objects. Indeed, our
algorithm has near linear performance with respect to cardinality, while
sage’s has roughly cubic complexity.

Monoid Coefficients Sage’s Ours $T_{3}$ $6^{2}$ 575 ms 56 ms $T_{4}$ $11^{2}$
5.23 min 173 ms $T_{5}$ $18^{2}$ >2h 1.82 s $T_{6}$ $29^{2}$ $\cdots$ 34.6 s
$T_{7}$ $44^{2}$ $\cdots$ 11.5 min

Table 3: Computation time of the Cartan matrix.
In the case $T_{5}$, Sage’s algorithm was interrupted before the end of the
computation.

Figure 6: Computation time and memory usage for computing the Cartan Matrix
using Proposition 33.
The blue points correspond to the random monoids, the yellow ones to $T_{n}$
for $n\in\llbracket{3,7}\rrbracket$. As before, the yellow points are excluded
of the linear regression although in this case, $T_{n}$ behave more or less
like the randomly chosen monoids. The measured complexity on random monoids is
slighly more than linear in time and memory.

Again, time and memory usage are in lockstep, and although memory fails before
time for $T_{8}$ and onward and for the monoids of the form $R(9,8)$, using
the regression we can predict a computation time of around 6 hours on our
testing machine if it was not memory limited.

An example of a Cartan matrix obtained using our Algorithms and Thiéry’s
formula is pictured in Figure 7.

Figure 7: Cartan Matrix of $T_{7}$
For legibility, the entries are represented as grey values. The entries are
integers from 0 (in white) to 4 (the single black pixel).

## Conclusion and perspectives

The methods presented in this paper provide a new tool for the computational
exploration of finite monoids representation theory. We give a method to
compute the character table of a finite monoid in the general case as well as
a method for the computation of the Cartan matrix. In the latter case,
although general algorithms for any finite dimensional algebra already exist,
by specializing to monoid algebras, we achieve vastly shorter computation
times, thus making the question tractable for bigger monoids. Although we have
presented the methods in details only for transformation monoids, the
underlying formulas are true in general for finite monoids, and it remains
computationally applicable whenever wherever the hypotheses of Section III are
verified. We also invite the reader the consult and test our impementation,
available on our github repository888github.com/ZoltanCoccyx/monoid-character-
table. As this paper is inspired by the combinatorial research on monoid
representation theory which have seen renewed activity in recent years we hope
that providing this effective tool will allows for the observation of new
phenomena.

This work has two natural continuations: improving and expanding. For the
improvement part, we have noted that by far the most inefficient part of our
algorithm is the computation of the radical of the $\mathcal{L}$-classes,
which happens to be the only point where linear algebra is necessary and
combinatorics are seemingly not enough. We can ask whether this step could be
replaced by a combinatorial computation. Some experiments show that, even in
relatively small and very regular cases ($T_{5}$ for instance) the basis we
find for the radical by solving the equation system described in Proposition
41 does not have easily understandable structure, once the common denominator
of the coefficients is eliminated. It therefore seem unlikely to us that a
general method for computing the radical of an entirely combinatorial nature
exists, although we remain optimistic that in very regular cases (again,
$T_{n}$), the issue lies with us not finding the method rather than it not
existing. More modestly, in a general context, we could try to exploit further
the structure of the equations that define the radical to reduce the size of
the system, which is a major bottleneck.

Another improvement, although perhaps less impactful, could be made by
exploiting redundancy: it can happen that two $\mathcal{L}$-classes
$L_{1},L_{2}$ of a submonoid $M$ of $T_{n}$ are contained in the same
$\mathcal{L}$-class $L$ of $T_{n}$. Thus, in step $2-b$ of Algorithm 35 (for
instance), instead of visiting each $\mathcal{L}$ of $M$, we could visit each
$\mathcal{L}$ of $T_{n}$ that contain an $\mathcal{L}$-class of $M$ and count
them with some multiplicity. Although this probably would not lead to great
improvements in efficiency, this has the advantage of making, in some sense,
$T_{n}$ the worst case scenario, allowing for a finer complexity analysis.

As for extending this work, the natural path seem to adapt these methods for
fields of finite characteristic. At this point it appears to us that this
question is tractable as the theory remains essentially the same, although it
is somewhat difficult to implement in practice. The main hurdle arise, again,
when computing the radical of an $\mathcal{L}$-class: an equivalent of
Proposition 23 would have to take into account the role of the radical of the
maximal subgroup algebra, which can be non-trivial in positive characteristic.
This would translate in needing to effectively compute this radical. Although
algorithms are available (for instance in GAP), this is a theoretically
difficult and computationally expensive problem, considerably reducing the
maximum size of a tractable problem. While modular representation theory is
known to be a difficult subject in groups it seems that, again, the situation
is not much more complicated for monoids than it is for groups as it is
standard practice to reduce monoid theoretic questions to group theoretic
ones. Treating modular group representation theory as a black box coming with
already existing algorithms (much as we did here for null characteristic group
representation theory as a matter of fact), we hope to be able to provide a
modular version of our algorithms along with an implementation in the near
future.

## Acknowledgements

The research work devoted to this project was funded by a PhD grant from the
French _Ministère de la recherche et de l’enseignement supérieur_ , in the
form of a _Contrat Doctoral Spécifique Normalien_ attributed for a PhD in the
STIC (_Sciences et Technologies de l’Information et de la Communication_)
doctoral school of Paris-Saclay University, in the LISN (_Laboratoire
Interdisciplinaire des Sciences du Numérique_) under the supervision of Pr.
Nicolas Thiéry.

## References

  * [1] Kenneth S. Brown  “Semigroups, rings, and Markov chains”  In _J. Theoret. Probab._ 13.3, 2000, pp. 871–938  DOI: 10.1023/A:1007822931408
  * [2] Arvind Ayyer, Anne Schilling, Benjamin Steinberg and Nicolas M. Thiéry  “Markov chains, R-trivial monoids and representation theory” arXiv:1401.4250  In _International Journal of Algebra and Computation_ 25, 2014, pp. 169–231  DOI: 10.1142/S0218196715400081
  * [3] Arvind Ayyer, Anne Schilling and Nicolas M. Thiéry  “Spectral gap for random-to-random shuffling on linear extensions” arXiv:1412.7488  In _Experimental Mathematics_ , 2016, pp. 1–9  DOI: http://dx.doi.org/10.1080/10586458.2015.1107868
  * [4] Nicolas M. Thiéry  “Cartan invariant matrices for finite monoids: description and computation using characters” FPSAC’12 Nagoya, 12 pages [math.RT]  In _DMTCS Proceedings_ , 2012, pp. 887–898  URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAR0178
  * [5] Olexandr Ganyushkin, Volodymyr Mazorchuk and Benjamin Steinberg  “On the irreducible representations of a finite semigroup”  In _Proceedings of the American Mathematical Society_ 137.11, 2009, pp. 3585–3592
  * [6] Jean-Éric Pin  “Mathematical Foundations of Automata Theory”  In _Cours du MPRI_ , 2020
  * [7] Alfred H Clifford and Gordon B Preston  “The algebraic theory of semigroups, vol. 1”  In _AMS surveys_ 7, 1961, pp. 1967
  * [8] Marcel-Paul Schutzenberger  “$\bar{D}$-représentation des demi-groupes”  In _Comptes-Rendus de l’Académie des Sciences_ 224, 1957, pp. 1994–1996
  * [9] Benjamin Steinberg  “Representation theory of finite monoids”  Springer, 2016
  * [10] Donald B McAlister  “Characters of finite semigroups”  In _Journal of Algebra_ 22.1 Elsevier, 1972, pp. 183–200
  * [11] James East, Attila Egri-Nagy, James D Mitchell and Yann Péresse  “Computing finite semigroups”  In _Journal of Symbolic Computation_ 92 Elsevier, 2019, pp. 110–155
  * [12] Alexander Hulpke  “Conjugacy classes in finite permutation groups via homomorphic images”  In _Mathematics of computation_ 69.232, 2000, pp. 1633–1651
  * [13] Greg Butler  “An inductive schema for computing conjugacy classes in permutation groups”  In _mathematics of computation_ 62.205, 1994, pp. 363–383
  * [14] Jean-Éric Pin  “Mathematical Foundations of Automata Theory”  URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf