Balthazar Charles

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

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, which allows for the effective computation of both the character table of M other 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 especially Markov chains used to randomly generate combinatorial objects first uncovered in the seminal article of Brown [? ]. This has lead to an exploration of the combinatorial properties of monoid representations, for instance in [? ], [? ] or [? ].

In this last article [? ], Thiéry gives a formula for the Cartan matrix of a finite monoid of M in terms of the number of fixed points and the character table of M . More precisely, the formula involves computing the cardinality of the set {s ∈ M | hsk = s} for any h, k ∈ 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 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 1, n to 1, n is n n , making the naive computation of |{s ∈ 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 [? ]) gives an explicit description of the simple kM -modules. This 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 computationally inefficient as it necessitates iterating over explicitly constructed irreducible group representations and dealing with high dimensional tensor products and quotients. In contrast, the method we propose allows for a "bundling" of the group representations using the easier to compute L-class modules. Moreover, although themselves high dimensional, these modules are combinatorial and the action of the monoid can be efficiently computed. We also note that although some results on character tables are known in the case of interesting families of monoids (full transformation monoids, inverse 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 fixedpoints 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, . . . , n}, equipped with the multiplication given by map composition: ∀f, g ∈ T n , f g = f • g (with the argument on the right : f • g(x) = f (g(x))). 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.

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 ∈ M being a left (or right) multiple of y ∈ 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. It can be proven (see for instance [? , Theorem 1.9]) that in finite monoids, the relation J is the smallest equivalence relation containing R and L. This is not true in general, and this smallest relation is usually denoted by D in the literature. Since we are only interested in finite monoids, we shall only use the terms Jrelation, J -class, etc. From the definition, it is clear that the relation L and R are finer than J and that H is finer that both L and R. Because of this, "the L-class of some H-class H" or "the J -class of some R-class R", etc... are well-defined and we shall denote them by L(H), J (R), etc.

Example 3 (Green relations in T n ). Let a, b be two elements of M .

• We have aLb if and only if they have the same kernel ker a = {a -1 {i} | i ∈ 1, n }.

• We have aRb if and only if they have the same image,

Im a = {a(i) | i ∈ 1, n }.
• Since T n is finite, J is generated by L and R so aJ b if and only if Im (a) and Im (b) (or equivalently ker(a) and ker(b)) have the same cardinality.

• Since H is the intersection of L and R, aHb 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 S n ⊂ T n and that we can rearrange both image and kernel as we please.

The following notation 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× S the application from S to hS defined by s → hs,

• × S k the application from S to Sk defined by s → sk,

• M Stab(S) = {m ∈ M | mS = S}, • Stab M (S) = {m ∈ M | Sm = S}, • Fix S (h, k) = {s ∈ 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. An important consequence of Green's Lemma is that J -classes can be neatly organized as eggbox pictures1 : the J -class can be represented as a rectangular array with the L-classes as columns, the R-classes as rows and the H-classes, the eggs, in the cases. This level organization is actually what allows for efficient computer representation of monoids and most of their algorithmic exploration.

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.

M Stab(H) = {[1 2 3], [3 2 1], [1 3 3], [3 1 1], [1 1 3], [3 3 1]} and subsequently, Γ(H) = {[1 2 3]× H , [3 3 1]× H }. Notice that, as elements of Γ(H), [3 3 1]× H = [3 2 1]× H
and that the only important thing is the permutations induced by the elements of M Stab(H) on Im H. Thus, in the case of transformation monoids, the left Schützenberger group of a H-class H can be represented as a subgroup of S(Im H). In the same way, the right Schützenberger groups can be represented as subgroups of 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 a H-class. The natural actions of Γ(H) and Γ ′ (H) on H are free and transitive.

We reproduce below a proof for Proposition 8 from [? ] 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 ′ ∈ H are in the same L-class so there is some u ∈ M such that uh = h ′ . By Green's Lemma, this means that u ∈ M Stab(H), so Γ(H) acts transitively on H. Suppose that uh = h for some u ∈ M . Since h, h ′ are also in the same R class, there is some v such that h ′ = hv, so uh ′ = uhv = hv = h ′ : an element of Γ(H) either fixes all points in H or fixes none. The only element of Γ(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 Γ ′ (H).

A special case that is interesting to note, and that will be important later, is the case where H is the H-class of an idempotent : Definition 9. An element e ∈ M is idempotent if e 2 = e. Given an idempotent e, the set G e = {x ∈ M | ∃y ∈ 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 = H(e).

In that case, Γ(H) and Γ ′ (H) can be defined as before, and are canonically isomorphic to G e , simply because G e ⊂ M Stab(H) naturally induce a map making it a subgroup of Γ(H) and that since G e acts freely and transitively on H, this map must be injective and surjective (and similarly for Γ ′ (H)).

Example 10. Consider, in Example 3, e = [1 2 2] and H = 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 :

Γ(H) = S({1, 2}), Γ ′ (H) = S({{1}, {2, 3}}).
Note that the canonical isomorphism between Γ(H) and H(e) is simply given by g ∈ Γ(H) → g • e ∈ H.

Counting fixed points

Consider the problem of counting the number of elements of the set Fix G (h, k) where G is a finite group and h, k ∈ G. If Fix G (h, k) is non-empty, it contains an element γ such that hγk = γ, or equivalently h = γk -1 γ -1 . So for any g ∈ Fix G (h, k) we have:

hgk = g ⇔ γk -1 γ -1 gk = g ⇔ γ -1 gk = kγ -1 g. This means that g ∈ γ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 | 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× H and × H k are in the same conjugacy class", and how to factorize our previous remark over all the H-classes of the same J -class.

As the bijections between L (and R) classes will play a major role in the remainder of this section, we introduce the following notation.

Notation 11. Given R, R ′ two R-classes in the same J -class, we say that (λ, λ ′ ) is a left Green pair with respect to (R, R ′ ) if:

• λR = R ′ and λ ′ R ′ = R. • (λλ ′ )× R = Id R and (λ ′ λ)× R ′ = Id R ′ Similarly, given two L-classes L, L ′ in the same J -classes, (ρ, ρ ′ ) is a right Green pair with respect to (L, L ′ ) if: • Lρ = L ′ and L ′ ρ ′ = L. • × L (ρρ ′ ) = Id L and × L ′ (ρ ′ ρ) = Id L ′
Using Green pairs, one can transport the problem of counting fixed points in an arbitrary H-class to a reference H-class.

Proposition 12. Let H 1 , H 2 ⊂ J be two H-classes contained in the same J -class. Then there exists λ, λ ′ , ρ, ρ ′ such that:

• (λ, λ ′ ) is a left Green pair with respect to (R(H 1 ), R(H 2 )),
• (ρ, ρ ′ ) is a right Green pair with respect to (L(H 1 ), L(H 2 )).

and the maps x → λ ′ xρ ′ and x → λxρ are reciprocal bijections between H 2 and

H 1 . Moreover, let (h, k) ∈ M Stab(R(H 2 ))×Stab M (L(H 2 )) and define (h ′ , k ′ ) = (λ ′ hλ, ρkρ ′ ).
Then the maps restrict to bijection between the sets

Fix H 2 (h, k) = {a ∈ H 2 | hak = a} and Fix H 1 (h ′ , k ′ ) = {a ∈ H 1 | h ′ ak ′ = a}.
Proof. The first part is exactly [? ,Proposition 2.3 (a)]. The second part is immediately deduced from [? , Proposition 2.3 (c)]. Still, for completeness, we provide a proof in our very simple (and less general) setup. Let a 1 be an element of H 1 and denote by a 2 = λa 1 ρ. Then:

ha 2 k = a 2 ⇔ λ ′ ha 2 kρ ′ = λ ′ a 2 ρ ′ ⇔ (λ ′ hλ)a 1 (ρkρ ′ ) = a 1 ⇔ h ′ a 1 k ′ = a 1 so these bijections restrict to Fix H 1 (h ′ , k ′ ) and 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 H-class, avoiding the repetition of multiple similar computations for each H-class.

The question is now to determine the fixed points in a single 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 H-class H, a ∈ H and g ∈ Γ(H), we define τ a (g) as the unique element of Γ ′ (H) such that g • a = a • τ a (g). Then τ a : Γ(H) -→ Γ ′ (H) is an anti-isomorphism2 . Moreover τ a gives rise to a bijection between the conjugacy classes of Γ(H) and Γ ′ (H) that is independent of the choice of a.

Proof. The first part is known since [? ]. We want to check that for a ∈ H, g ∈ Γ(H), the conjugacy class of τ a (g) is defined independently of a. Take any a, b ∈ H. By definition of Γ(H), there exist some

h ∈ Γ(H) such that b = h • a. So : b • τ a (g) = (h • a) • τ a (g) = h • (g • a) = hgh -1 • (h • a) = b • τ b (hgh -1 ).
Since Γ ′ (H) acts freely, this means that τ a (g) = τ b (h)τ b (g)τ b (h) -1 and thus τ a (g) is conjugated with τ b (g), which proves that the conjugacy class of τ a (g) is indeed defined independently of a. Finally, as τ a is a group morphism, the image are of two conjugated elements are conjugated, meaning that τ 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 H-class, a ∈ H and (h, k) ∈ M Stab(R(H)) × Stab M (L(H)). Then | Fix H (h, k)| = |C Γ ′ (H) (× H k)| if τ a (h× H ) -1 ∈ × H k 0 otherwise
where

× H k is the conjugacy class of × H k in Γ ′ (H) and C Γ ′ (H) (× H k) is the cen- tralizer in Γ ′ (H) of × H k.
Proof. For simplicity, we commit an abuse of notation by denoting h× H as h and × H k as k. Let a be any element of H.

Fix H (h, k) = {b ∈ H | hbk = b} = {a • g | g ∈ Γ ′ (H) and ha • gk = a • g} = {a • g | g ∈ Γ ′ (H) and a • τ a (h)gk = a • g} = {a • g | g ∈ Γ ′ (H) and τ a (h)gk = g}.
The last equality comes from the fact that Γ ′ (H) acts freely so we can simplify the a. Suppose that Fix H (h, k) is non-empty and let γ ∈ Γ ′ (H) such that τ a (h)γk = γ. Then, for any g ∈ Γ ′ (H) :

τ a (h)gk = g ⇔ g -1 τ a (h)gk = e ⇔ g -1 γk -1 γ -1 gk = e ⇔ [γ -1 g, k] = e
where [•, •] is the commutation bracket. This means that

Fix H (h, k) = {a • g | g ∈ γC Γ ′ (H) (k)}.
Note that because, again, Γ ′ (H) acts freely, Fix H (h, k) has the same cardinality as C Γ ′ (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] ∈ T 4 and H = H(a). We have 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] / ∈ 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 Γ(H) = S(Im a) and Γ ′ (H) = 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 Γ(H), h corresponds to Id Im a and k corresponds to

({2, 3} {1}) in Γ ′ (H). Since we have τ a (h) = Id ker a , it follows that | Fix H (h, k)| = 0.
If we now take h to be [1 3 2 4], the corresponding element in Γ(H) is (2 3) and τ a (h) = ({2, 3} {4}). Since ({2, 3} {4}) and ({2, 3} {1}) are conjugated in 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 Fix J (h, k).

Corollary 16. Let J be a J -class, a any element of J and denote by H 0 = H(a), R 0 = R(a), L 0 = L(a). Let h, k be any elements of M . We denote by:

• (λ R , λ ′ R ) a left Green pair with respect to (R 0 , R) for each R-class R ⊂ J,
• (ρ L , ρ ′ L ) a right Green pair with respect to (L 0 , L) for each L-class L ⊂ J,

• S R (h) = {R ⊂ J | R is a R-class and hR = R}, • S L (k) = {L ⊂ J | R is a L-class and Lk = L}
Denoting the set of conjugacy classes of Γ ′ (H 0 ) as C, we further define two vectors:

• r J (h) = (|C Γ ′ (H) (g)| • |{R ∈ S R (h) | τ a (λ ′ R hλ R ) ∈ ḡ}|) ḡ∈C , • l J (k) = (|{L ∈ S L (k) | ρ ′ L kρ L ∈ ḡ}|) ḡ∈C .
Then Fix J (h, k) has cardinality the dot product of r J (h) with l J (k).

II. Modules: character table and Cartan matrix

We will discuss the representation theory of a monoid M over k using the language of modules, for which we assume a level a familiarity from the reader. In the remainder of this paper, k is a perfect field of null characteristic and M is still a finite monoid. Furthermore, we suppose that 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 kM .

As previously mentioned, we will refer to representations in terms of modules, let us recall the language that we use. A representation of M over k will be a k-vector space V equipped with a linear action of the algebra kM . As is usage, whenever the action is on the left we will say that V is a kM -mod and a mod -kM if the action is on the right. If M , M ′ are two finite, possibly different monoids, a kM -mod -kM ′ is simply simultaneously a kM -mod and a mod -kM ′ . For a monoid M , we denote by M op the opposite monoid, with multiplication defined by m • M op m ′ = m ′ m. We will use liberally the fact that a kM -mod -kM ′ is naturally a kM ⊗ kM ′op -mod and a k(M × M ′op ) -mod, and reciprocally. In the totality of this paper, we assume that the modules are finite dimensional as vector spaces over 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 kMmodule and S is a simple kM -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 Clifford-Munn-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 a L-class containing an idempotent e quotiented by its radical as a product of simple kG e -modules and simple kM -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 [? ].

On modules

Note that if we choose an element a ∈ M and denote by L its L-class and H its H-class, we can equip kL with a kM -mod -kΓ ′ (H) structure. kL is already a mod -kΓ ′ (H) by definition of Γ ′ (H). We can also make it into a kM -mod by setting, for every m ∈ M and l ∈ L:

m • l = ml if ml ∈ L 0 otherwise .
This is well-defined, as ml / ∈ L implies that l > L ml and so for every m ′ ∈ M , l > L m ′ ml / ∈ 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 ∈ M be an idempotent, L(e) its L-class, G e the associated maximal subgroup. We define the two following maps :

Ind M Ge : kG e -mod -→ kM -mod V -→ kL(e) ⊗ kGe V N e : kM -mod -→ kM -mod V -→ {v ∈ V | eM v = 0} .
The idempotents and their maximal subgroups play a central role in the theory. One can show (see for instance [? , Proposition 1.14]) that if e, f are two idempotents in the same J -class, there are some x, x ′ ∈ M such that xx ′ = e and x ′ x = f and that G e ∼ = G f . A J -class containing an idempotent is called a regular 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 kM -module. A proof of the Clifford-Munn-Ponizovskii Theorem can be found in [? , Section 5.2].

Definition 18. Let V be a kM -mod, we denote its annihilator in M by Ann M (V ) = {m ∈ M | mV = {0}}. This is clearly a two-sided ideal of M and as such is a union of J -classes. A regular J -class J is said to be the apex of

V if Ann M (V ) = I J where I J = {J ̸ ≤ L J (s) | s ∈ M }. If e ∈ 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 ∈ M an idempotent and k be a field.

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 -→ V # = Ind M Ge (V )/ rad(Ind M Ge (V )).
The reciprocal bijection is given by S -→ eS. 2. rad(Ind M Ge (V )) = N e (rad(Ind M Ge (V ))) 3. Every simple M -module has an apex. 4. Every composition factor of Ind M Ge (V ) with the exception of V # has an apex strictly J -greater than e. Moreover, V # has apex e and is a factor of multiplicity one. This allows us the following description of the L-class of an idempotent e.

Proposition 20. Let e ∈ M be an idempotent and G e be the maximal subgroup at e. Let Irr e be a set of representatives of the isomorphism classes of simple kG emodules. Then:

kL(e) =

V ∈Irre

Ind M Ge (V ) ⊗ k V *
where V * is the dual of V .

Proof. By definition, Ind M Ge (V ) = L(e)⊗ kGe V . Now, since direct sum and tensor product over a ring with identity commute :

V ∈Irre Ind M Ge (V )⊗V * = V ∈Irre kL(e)⊗ Ge V ⊗V * = kL(e)⊗ Ge V ∈Irre V ⊗ V *
Because k is of null characteristic, kG e is semisimple. By the Wedderburn-Artin theorem, kG e = V ∈Irre V ⊗ V * so :

V ∈Irre Ind M Ge (V ) ⊗ V * = kL(e) ⊗ kGe kG e = L(e)
since kG e is a ring with identity.

Note that this puts in relation three kinds of modules : the simple kG e -modules, which are well understood, kL(e) which is understood as well because it is a combinatorial module3 , and finally the modules Ind M Ge (V ) which contain, in a sense, the simple kM -modules that we are after. According to the Clifford-Munn-Ponizovskii Theorem, we still need to remove the radical of each Ind M Ge (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 k. Then:

rad(A ⊗ B) = rad(A) ⊗ B + A ⊗ 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 Plamondon4 .

Proof. Because k is perfect, Wedderburn's Principal Theorem applies, and we get the decompositions A = A ′ ⊕rad(A), B = B ′ ⊕rad(B), with A ′ and B ′ semisimple algebras. To prove the result, we show that rad(A)

⊗ B + A ⊗ rad(B) is a nil radical and that A ⊗ B ⧸ rad(A) ⊗ B + A ⊗ rad(B)
is semisimple. Let us first show that the quotient is semisimple. We have:

A ⊗ B = (A ′ ⊕ rad(A)) ⊗ (B ′ ⊕ rad(B)) = A ′ ⊗ B ′ ⊕ A ′ ⊗ rad(B) ⊕ rad(A) ⊗ B ′ ⊕ rad(A) ⊗ rad(B).
On the other hand, the same decompositions give us

A ⊗ rad(B) ⊕ rad(A) ⊗ B = A ′ ⊗ rad(B) ⊕ rad(A) ⊗ B ′ ⊕ rad(A) ⊗ rad(B). Finally, A ⊗ B ⧸ A ⊗ rad(B) ⊕ rad(A) ⊗ B = A ′ ⊗ B ′ which, since A ′ , B ′ are semisimple, is also semisimple. A⊗rad(B)⊕rad(A)⊗B is also nil, because rad(B) and rad(A) are, so, indeed, rad(A ⊗ B) = A ⊗ rad(B) ⊕ rad(A) ⊗ B.
From Lemma 21, we get the following Corollary by recalling that if V is an

A-module, rad A (V ) = rad(A) • V .
Corollary 22. Let A, B be two finite dimensional unitary algebras over a perfect field.

If V A ⊗ V B is an A -mod -B (or equivalently an A ⊗ B op -mod), then rad A⊗B op (V A ⊗ V B ) = rad A (V A ) ⊗ B + A ⊗ rad B (V B ).
This allows us to identify the radical of kL(e).

Proposition 23. Let M be a finite monoid, e ∈ S an idempotent G e be the maximal subgroup at e and k be a perfect field. Then:

rad kM ⊗kG op e (kL(e)) = N e (kL(e)).
Proof. Using Lemma 21, for V a simple G e -module, we have that :

rad kM ⊗kG op e (Ind S Ge (V ) ⊗ k V * ) = rad kM Ind M Ge (V ) ⊗ V * + Ind M Ge (V ) ⊗ rad kG op e (V * ) (1) = rad kM Ind M Ge (V ) ⊗ V * (2) = N e (Ind M Ge (V )) ⊗ V *
where equality (1) comes from the simplicity of V * as a kG op e -module and (2) is the second point of Theorem 19.

Since radical and direct sums commute, denoting by Irr e a set of representatives of the isomorphism classes of simple kG e -modules, we know that:

rad kM ⊗kG op e (L(e)) = V ∈Irre N e (Ind M Ge (V )) ⊗ V * .
It remains to be seen why

V ∈Irre N e (Ind M Ge (V )) ⊗ V * = N e (kL(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 ′ are kM -modules, N e (V ⊕ V ′ ) = N e (V ) ⊕ N e (V ′ ). Given the proposition 20, it is enough to show that N e (Ind M Ge (V )) ⊗ V * = N e (Ind M Ge (V ) ⊗ V * ). Let x ∈ Ind M Ge (V ) ⊗ V * be such that for every m ∈ M, emx = 0.
x can be written as i ( j x i,j b j ) ⊗ b ′ i where {b j } j is a basis of Ind M Ge (V ) and {b ′ i } i is a basis of V * . For every m ∈ M , we have :

em • x = em • i ( j x i,j b j ) ⊗ b ′ i = i (em • j x i,j b j ) ⊗ b ′ i = 0 that is, for every b ′ i we get em • j x i,j b j = 0 so j x i,j b j ∈ N e (Ind M Ge (V )) which means x ∈ N e (Ind M Ge (V )) ⊗ V * .
Proposition 24. Let e ∈ M be an idempotent and G e be the maximal subgroup at e. Let Irr e be a set of representatives of the isomorphism classes of simple kG emodules. Then:

kL(e)/ rad kM ⊗kG op e (kL(e)) ∼ = V ∈Irre V # ⊗ V * .
Proof. From Proposition 23, we have a decomposition of rad kM ⊗kG op e (L(e)) as a direct sum adapted to the decomposition of kL(e) as V ∈Irre Ind S Ge (V ) ⊗ k V * . So:

kL(e)/ rad kM ⊗kG op e (kL(e)) ∼ = V ∈Irre (Ind S Ge (V )⊗ k V * )/(N e (Ind S Ge (V ))⊗V * ).
From Theorem 19, we know that

0 -→ N e (Ind S Ge (V )) -→ Ind S Ge (V ) -→ V # -→ 0
is a short exact sequence. Since N e (Ind S Ge (V )) ⊗ V * a submodule of Ind S Ge (V ) ⊗ V * and because tensor product over a field is exact we have a short exact sequence:

0 -→ N e (Ind S Ge (V )) ⊗ V * -→ Ind S Ge (V ) ⊗ V * -→ V # ⊗ V * -→ 0
which proves the result.

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 kM -module, its character is the map from M to k defined by χ

V kM : m -→ Tr(v → m • v).
We recall the following well-known facts about characters. Proofs for fact 2 and 3 are respectively (ii) and (iii) of [? , Proposition 7.12]5 .

Proposition 26.

1. Let V be a kM -module. We have χ V kM = χ V * kM op . 2. Consider the short exact sequence of kM -modules:

0 -→ A -→ B -→ B/A -→ 0. Then χ B/A kM = χ B kM -χ A kM . 3. Consider M, M ′ two finite monoids, V a kM -module and W a kM ′op -module. Then χ V ⊗W kM ⊗kM ′ = χ V kM χ W kM ′ .
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 [? , Theorem 7.7] for reference):

Proposition 27. The irreducible characters {χ S kM | S is a simple kM -mod} are linearly independent as 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 kM -module V , has S as a composition factor with multiplicity [V : S] for any simple kM -module S. Then:

χ V kM = S [V : S]χ S kM .
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 [? ].

Definition 28. We say that two elements m, m ′ in M are in the same generalized conjugacy class or character equivalency class if for every kM -module V , We can now recall the definition of the character table of a monoid.

χ V M (m) = χ V M (m ′ ).
Definition 30. Let Irr M be the set of isomorphism classes of simple kM -modules and C M as in definition 28. The character table of M over k is the (square) matrix defined by :

X(M ) = (χ V kM (m)) V ∈Irr M ,m∈C M . Moreover, if e ∈ 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 k given the character tables of the groups G e over k.

Proposition 31. Let e ∈ M be an idempotent, G e be the maximal subgroup at e. We have the formula for X e (M ) : Then, from Proposition 24, we know that:

X e (M ) = t X(G e ) -1 • χ kL(e)
χ kL(e)/Ne(kL(e)) kM ⊗kG op e (m, g) = χ V ∈Irre V # ⊗V * kM ⊗kG op e = V ∈Irre χ V # ⊗V * kM ⊗kG op e = V ∈Irre χ V # kM (m)χ V kGe (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 χ

L(e)/ rad(L(e)) M -Ge is equal to the coefficient in position (g, m) of t X(G e ) • X e (M ), which, together with Proposition 26(ii), proves the equality.

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 semisimple" the algebra of the monoid is. We use a non standard definition of the Cartan matrix, first given in [? , Definition 2.6]. A formal proof that this is equivalent to the usual definition can be found in [? , Corolary 7.28].

Definition 32. Let {S 1 , . . . , S n } be a set of representatives of the isomorphism classes of simple kM -modules. The simple kM ⊗ kM op modules are the S i ⊗ S * j for all i, j ∈ 1, n . Denote by [kM : S i ⊗ S * j ] the multiplicity of S i ⊗ S * j as a composition factor of kM .

The Cartan matrix of kM is defined by:

C(kM ) = ([kM : S i ⊗ S * j ]) i,j .
In other words, the Cartan matrix is a recording of the multiplicities of the composition factors of kM as a kM ⊗ kM op module. But so is its character! The difference being that the character of kM as it is computed is expressed in the basis of the character equivalency classes of M × 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(kM ) = t X -1 M BX -1 M where B = (|{s ∈ M | msm ′ }|) m,m ′ ∈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: kJ for a J -class J, kM as kM -mod -kM and kL(e) for a L-class containing an idempotent e as a kM -mod -kG 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 kL(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.

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 [? ] in which East, Egri-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 [? ] 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 [? ], 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 [? ] that we do use).

• Assumption III : Green's pairs.

• Assumption IV : Given h ∈ M Stab(H) compute the corresponding element in Γ(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 [? ]. As such, we refer to the top of Section 5.2 of [? ] on how to realize these computations in the case of transformation monoids.

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

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

• Checking membership of an element in a Green's class: [? , Algorithms 7 & 8].

• Finding idempotents: [? , Algorithm 10]. This algorithm also allows for finding the regular J -classes.

• Decomposing the monoid in R, L and J -classes : [? , 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's class: this is given by the data structure representing the Green's classes described at the top of [? , Section 5.4].

Finally, we require the following points that, although they are not described in [? ], 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. compute a set E of idempotent representatives of the regular J -classes, 2. compute Γ(H(e)) for each e ∈ E, 3. compute a set C e of representatives of the conjugacy classes of Γ(H(e))

for each e ∈ E, using for instance the procedure described in [? ], 4. for each e ∈ E and c ∈ C e compute the corresponding element of H(e) as in Example 10.

• Computing τ a as in Proposition 13 : given g ∈ Γ(H), τ a (g) is simply, seen as an element of S(ker a) :

a -1 {i} → (g • a) -1 {g • a(i)},
which can be computed in O(n). Note that this is a special case of the application described in [? , Proposition 3.11 (a)]

• Testing that two elements g, g ′ in Γ ′ (H(a)) are conjugated : Γ ′ (H) is represented as a subgroup of S(ker a) and known procedures, such as the one described in [? ], 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 [? ].

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 ′ be two finite monoids and (V, B) a finite dimensional kMmod -kM ′ space equipped with a basis B. If the actions of M, M ′ on (V, B) are combinatorial, meaning for any

(m, b, m ′ ) ∈ M × B × M ′ , mbm ′ ∈ (B ∪ {0}), then: χ V kM ⊗kM ′op = |{b ∈ B | mbm ′ = b}|.
Proof. In the basis B, the matrix of the linear map x → mxm ′ is a {0, 1}-matrix, with for every b ∈ B exactly one 1 in the b-th column, that 1 being on the b-th row if mbm ′ = b. Thus, the trace counts the number of fixed points.

Note that we have already defined a structure of combinatorial kM -mod -kG e on (kL(e), L(e)) for any idempotent e. In the same way, kJ for a J -class J, can be equipped with a structure of kM -mod -kM by setting for every (m, j) ∈ M × J:

m • j = mj if mj ∈ J 0 otherwise and j • m = jm if jm ∈ J 0 otherwise .
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 ≤ L m ′ or m ≤ R m ′ imply m ≤ J m ′ 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 (kJ, 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 J -class). Keeping the assumptions and notations of the previous Paragraph 1, we get from Corollary 16 an algorithm to compute the bicharacter of kJ as a kM -mod -kM :

• Input : A J -class J, a set of representatives of the character equivalency classes C M .

• Output : A matrix (|{m

∈ J | hmk = m}|) (h,k)∈C 2 M 1. Preparations: (a) Choose a ∈ J and define H = H(a). (b) Compute Green's pairs (λ R , λ ′ R ) (respectively (ρ L , ρ ′ L )) for (R(a), R) (resp. (L(a), L)) for all R-class R ⊂ J (resp. L-class L ⊂ J). (c) Compute the set C of conjugacy classes of Γ ′ (H).
2. For each character equivalency representative h ∈ C M , initialize r J (h) and l J (h) to both be (0) ḡ∈C .

(a) For each R-class R ⊂ J, test if hλ R a ∈ R. If so, denoting by

ḡ the conjugacy class of τ a ((λ ′ R hλ R )× H ) in Γ ′ (H), increment r J (h) by |C Γ ′ (H) (g)| at position ḡ. (b) For each L-class L ⊂ J, test if aρ R h ∈ L. If so, denoting by ḡ the conjugacy class of × H (ρ ′ L hρ L ) in Γ ′ (H), increment r J (h) by 1 at po- sition ḡ. 3. Compute the matrix χ = (r J (h) • l J (k)) (h,k)∈C 2 M
using the previously computed vectors and return χ.

Example 36. An aperiodic monoid is a monoid where all H-classes are singletons. Let us apply the algorithm we just described in the case of a J -class J with trivial 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 R (h)|) h∈C M and r J = (|S L (h)|) h∈C M with S L (h) and S R (h) defined as in Corollary 16. The bicharacter is simply the matrix product of r T j with l J . The particular case of this algorithm for aperiodic monoid is described in [? , Section .1] Algorithm 37 (Computing the bicharacter of kM ). If we consider (kM, M ) as a combinatorial kM -mod -kM , we immediately have that:

χ kM kM ⊗kM ′op = J∈J χ kJ kM ⊗kM ′op
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 J -classes and sum the results.

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

Algorithm 38 (Computing the bicharacter of a L-class). Let e be an idempotent en let L = L(e). In this example kL 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 Ge 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. Initialize χ to (0) (h,k)∈C M ×C 2. For each h ∈ C M , for each H-class H, test if hλ H a ∈ H. If so, denoting by k the conjugacy class of λ ′ H hλ H in G e , increment χ by |C Ge (h)| at position (h, k). 3. Return χ 3. Computing N e (kL)
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 kL(e) as a kM ⊗ kG op e -module for some idempotent e ∈ M . It remains to compute the bicharacter of N e (kL(e)) as a kM ⊗ kG op e -module, which we discuss now. Let L = L(e). Recall that, by definition, N e (kL) = {x ∈ kL | eM x = 0}. Taking L as a basis for kL, we can form a matrix with rows indexed by M × L and columns indexed by L, with the coefficient at ((m, l), l ′ ) = 1 if eml = l ′ and 0 otherwise. Computing the kernel of this matrix yields a basis for N e (kL) but is extremely inefficient as the number of rows is many times the cardinality of the monoïd.

Notice first that for any m ∈ M , em ≤ R e so we can consider only the elements of M that are R-smaller than e. Conversely, recall that the structure of kM -module on M is defined by m • l = ml if ml ∈ L and 0 otherwise and that this latter case happens if ml ≤ L l. Since if m ≤ L l implies ml ≤ 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 L-below e. Together with the previous point, this means that the similarly defined matrix but whose rows are only indexed by R(e)×L has the same kernel. This is good news, as we may now exploit the structure of the 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 [? ,Theorem 1.11].

Lemma 39 (Location Theorem). Let r, l be two elements in the same J -class. We have: Lemma 40. Let e ∈ M be an idempotent, R = R(e) its R-class and R ′ another R-class of J (e). Let (λ, λ ′ ) be a left Green's pair for (L, L ′ ). Then (λe, eλ ′ ) is a left Green's pair for (R, R ′ ).

rl = γ ∈ R(r) ∩ L(l) if L(r) ∩ R(l) contains an idempotent, γ < J l, r otherwise. l rl e r = × R(r) R(l) L(l) L(r)
Similarly, if L = L(e), L ′ is a L-class of J (e) and (ρ, ρ ′ ) is a right Green's pair for (L, L ′ ), then (eρ, ρ ′ e) is a right Green's pair for (L, L ′ ) Proof. Let g be any element of H(e) and g ′ = λg. Since e is idempotent, H(e) is a group with identity e so we have eλ ′ λeg = eλ ′ λg = eg = g and λeeλ ′ g ′ = λeg = λg = g ′ which, from Green's Lemma, make (λe, eλ ′ ) a left Green's pair for (L, L ′ ). A similar argument applies for the second part of the proposition.

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

Proposition 41. Let e ∈ M be an idempotent and H = H(e), L = L(e), R = R(e) and J = J (e). For each R-class R ′ ⊂ J, we choose a left Green's pair (l, l ′ ) ∈ J 2 . We denote by L the set of all l for the chosen left Green's pairs. We define R similarly. Then N e is the set of solutions of :

∀r ∈ R, ∀g ∈ H, l∈L 1 H (rl)x l(rl) -1 g = 0
Proof. Consider an element a ∈ R. a can be written in a unique way as gr, with g ∈ H and r ∈ R corresponding to L(a). Similarly, an element b in L as a unique decomposition as lγ, l ∈ L, γ ∈ H. For an element x ∈ kL we note:

x = l∈L,γ∈H
x lγ lγ its decomposition over the basis L.

We want to find the equations that describe ker(gr× L ) (where gr× L is the linear map on kL obtained by extending the monoid's multiplication by linearity). From the Location Theorem, we get that Im (gr× L ) ⊂ kH. For k ∈ H, denote by f k,gr the k-th coordinate function of gr× L . Because gr× L acts combinatorially on kL, we have :

f k,gr (x) = l∈L,γ∈H 1 {k} (grlγ)x lγ
Note that x lγ appears in the sum if and only if grlγ = k. From the Location Theorem, and because we chose l ∈ L, r ∈ R, we have grlγ = k if and only if rl ∈ H and γ = (rl) -1 g -1 k and thus the equation becomes:

f k,gr (x) = l∈L 1 H (rl)x l(rl) -1 g -1 k .
For x to be in ker(gr× L ), x must cancel simultaneously f k,gr for all k ∈ H. We now have a set of equations for ker(gr× L ), and we can deduce that the set of equations

∀r ∈ R, ∀g, k ∈ H, f k,gr (x) = l∈L,γ∈H 1 H (rl)x l(rl) -1 g -1 k = 0
describes N e (kL). However, the equation system is redundant as the equation f k,gr (x) = 0 is the same for all pairs (g, gk ′ ) with k ′ ∈ H. Removing the duplicates equations 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 J -class with trivial H-classes. In this case, we have L = L, R = R and H = {1 H }, so the equations become:

∀r ∈ R, l∈L 1 H (rl)x l .
Again from the Location Theorem, we have that 1 H (rl) = 1 if and only if there is an idempotent in L(r) ∩ R(l). So if we form a matrix A with rows indexed by L and columns indexed by R, and with coefficients 1 at (L(r), R(l)) if L(r) ∩ R(l) contains an idempotent and 0 otherwise, the above equations becomes :

(x l ) T l∈L A = 0, that is, in the case of a H-trivial J -class, N e (kL) 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 χ Ne(kL(e)) kM ⊗kG op e from the formula in Proposition 31 using classical linear algebra algorithms to find a basis of N e (kL(e)) and then computing the value of the character at any (m, g) ∈ C M ×C Ge by iterating over the basis vectors, applying (m, g) as a linear map and computing the relevant coefficient in the image vector.

IV. Performance, computational complexity and benchmarks

To begin with, in this section, we discuss the challenges and choices we have been led to make to measure the performance of our algorithms. In a second part, we present the experimental results as well as, when possible, their complexity analysis. We discuss performance for the computation of the number of fixed points, the character table and finally the Cartan matrix. At the end of this section, in Figures 3,4 and 5, we give experimental measures of the complexity of our algorithms as a function of cardinality.

Challenges, experimental choices and methodology

Monoids being as diverse as they are, a meaningful analysis of the time and space complexities of the above algorithms is difficult, as many relevant metrics (such as the number of Green classes of a given type) cannot be straightforwardly computed. Moreover, in some sense these metrics vary a lot: two transformation monoid acting on the same number of points with the same number of generators can have vastly different Green structures. Although we can provide some time complexities in terms of number of L, R-classes and cardinality of H-classes (as we do below), the real test of viability is to see if the algorithm effectively terminates in practice. Thus, we provide timings and memory usage measures for the computation of the three main objects of our discussion: the bicharacter, the character table and the Cartan matrix.

The performance measures 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. Our specific implementation, as well as the test cases used and the raw data, are publicly available on our git repository6 . As the following section will show, these algorithms are, on our test machine, memory limited. We have made some test computations on a machine equipped with 128 GB of RAM. Even then, due to the rapid explosion of memory requirements, we cannot compute the character table of T 8 using these methods, and it seems that monoids containing S 12 generally fail to reach the end of the bicharacter computation. Since in the cases where this more powerful machine enables more computation by bypassing memory limitations, computation time can reach the hour range, we choose to focus on the smaller scale tests allowed by our smaller machine.

We consider three families of monoids implemented by the package GAP Semigroups [? ]: transformation monoids, which we have introduced before, partition monoids, and partial permutation monoids. Definition 43. A partition P of a set S is a collection of subsets of S such that P = S and for all p, p ′ ∈ P, p ∩ p ′ = ∅. The elements of P are called its blocks. Given s ∈ S, P (s) is the unique block of P containing s.

Let P , Q be two set partitions of the set S = -n, -1 ∪ 1, n . The partition product of P by Q is the partition P Q where i, j ∈ S are in the same block if:

• i, j > 0 and are in the same P -block.

• i, j < 0 and are in the same Q-block.

• i > 0 and j < 0 and there exists k ∈ -n, -1 such that k ∈ P (i) and k ∈ Q(j).

• i and j are related in the transitive closure of the relation given by the previous point.

This defines the partition monoid P n (with identity {{i, -i} | i ∈ 1, n }). A partition monoid (of rank n) is a submonoid of P n .

Definition 44. A partial permutation of 1, n is an injective partial function from 1, n to itself. Equipped with the identity function and the partial map composition, this defines the inverse symmetric monoid I n . A partial permutation monoid (of rank n) is a submonoid of I n .

We test our functions on the families T n , P n and I n , with numeric values provided for our canonical example T n in Tables 2, 3 and 4. However, many computer algebra systems, including GAP, are smart enough to detect that the Schützenberger groups are actually symmetric groups and thus use some nongeneral algorithms that could not be used on a typical finite monoid. This has the potential to falsify our measures (and indeed probably does, given Figures 3-(a), 4-(a) and5-(a)). To mitigate this issue, we provide timings for randomly chosen finite monoids. The question of picking a "generic" monoid is entirely outside the scope of this paper. We simply choose a monoid R(m, n) of rank m with n generators by picking uniformly n element of T m , P m or I m . The set of (rank, number of generators) pairs used is given in Table 1. For reasons discussed hereafter, we have chosen to have "enough" generators to have non-trivial Jstructure. Experimentally, we note that the resources in time and memory used by two transformation monoids acting of the same rank with the same number of generators can differ by up to an order of magnitude. Thus, for each pair (m, n), we measure performance on 10 randomly chosen test cases. To experimentally evaluate the complexity as a function of cardinality, we do a linear regression of the logarithm of the (time and memory) measures against the logarithm of the cardinality. In the case of transformation monoids and partition monoid, the data follows a relatively tight distribution (see Figures 3 and4). To mitigate threshold effects, we weight the sample values linearly (and not logarithmically) so that the higher values have more importance. By contrast, the randomly generated partial permutation monoids give more dispersed samples. Given this dispersion, considering only (or with a heavy weight) the highest values makes for an overestimation of necessary resources in most cases. Thus, in that case, we do the linear regression with equal weights on all samples. This does not dramatically change the measured complexity (we refer to the actual code as the final arbiter), but we advise caution when using these figures. For ease of discussion, we will call structured monoids the non-random ones present in our tests.

Performances and experimental results.

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

Proposition 45. Consider a J -class J containing n L L-classes, n R R-classes, containing a H-class H with n C conjugacy classes in Γ ′ (H), and let C M be a set of representatives of the character equivalence classes, as before. Then, the Algorithm 35 does: Proof. This simply results from an inspection of Algorithm 35, with the caveat that we precompute the cardinalities of the conjugacy classes of Γ ′ (H).

• n C computations of
In the case of Algorithm 37 applied to an arbitrary monoid, such an analysis is mostly meaningless because we would need to express the number of Green classes and understand their breakdown. However, because of the vast variety of possible monoids, there is no meaningful way to do it from simple parameters such as the rank or the number of generators.

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. 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 2, with a sublinear (with respect to cardinality) measured complexity (Figure 3). As shown in Table 3, the computation of the character table takes much longer. This is because, to compute the radical of kL(e) for an idempotent e, we must solve M character values in O(d 2 ) operations each. Experiments indicate that the computation time of the character tables of the maximal subgroups is small in comparison to all radical related computations. As can be seen in Figures 3-(b, c), 4-(b, c) and5-(b, c) the limiting factor is memory (the test on random monoids fails for the random transformation monoids of the form R(9, 8) by exceeding the 16 GB memory capacity of our testing machine). Although computation requirements are close to linear in the cardinality, the cardinality tends to be more than exponential in the rank, limiting these methods to small ranks. 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 L-classes. In Table 4, we show some timings for that computation, and a comparison with Sage's 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. In the case T 5 , Sage's algorithm was interrupted before the end of the computation.

Monoid

Again, memory fails before time for T 8 and onward. For the transformation 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 2. Generally, our algorithms achieve (at worst) near linear measured complexity. The fixed point counting is most efficient in the structured monoids, where there are few, big J -class with big Schützenberger groups. In the contrary, on "sparse" monoid with many small J -class, the efficiency of the algorithm drops. This most apparent in Figure 5, where the blue clusters are (roughly) semigroups of the same rank with the same number of generators. The partial permutation semigroups generated that way tends to have either (at our scale) low tens or multiple thousands J -classes (without intermediate values). The latter kind tends to be much more expensive to deal with, despite implementing "lazy" fixed point counting on small J -classes and J -classes with trivial Schützenberger groups to avoid costly computations. The situation balances out (or even inverses itself, see Figure 4) when it comes to computing the character table and the Cartan matrix. This seems to come from the fact that bigger J -classes mean higher dimensional radical and bigger Schützenberger groups mean less sparse basis vectors in the radical. Still, the measured complexity remains near linear in our experiments.

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 the hypotheses of Section III are verified. We also invite the reader to consult and test our implementation, available on our GitHub repository7 . 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 allow 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 L-classes. It 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 seems unlikely to us that a general method for computing the radical of an entirely combinatorial nature exists. However, 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 L-classes L 1 , L 2 of a submonoid M of T n are contained in the same L-class L of T n . Thus, in step 2-b of Algorithm 35 (for instance), instead of visiting each L of M , we could visit each L of T n that contains a 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 arises, again, when computing the radical of a 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.

Annex: Given P, Q two set partitions on {±1, ±2, . . . , ±n}, one can create a new partition P, Q on the same set in the following way:

  Green's relations). Let M be a finite monoid and a, b two of its elements. The Green relations are:• The L preorder is defined by a ≤ L b ⇔ b = ua for some u ∈ M . The associated equivalence relation is :a ∈ L(b) ⇔ a ≤ L b and b ≤ L a ⇔ M a = M b. • The R preorder is defined by a ≤ R b ⇔ b = av for some v ∈ M . The associated equivalence relation is : a ∈ R(b) ⇔ a ≤ R b and b ≤ R a ⇔ aM = bM . • The J preorder is defined by a ≤ J b ⇔ b = uav for some u, v ∈ M . The associated equivalence relation is: a ∈ J (b) ⇔ a ≤ J b and b ≤ J a ⇔ M aM = M bM .• The H equivalence relation is defined by a ∈ H(b) ⇔ a ∈ L(b) and a ∈ R(b).

Lemma 5 (

 5 Green's Lemma). Let a, a ′ be two elements in the same L-class and let λ, λ ′ such that λa = a ′ and λ ′ a ′ = a. Then λ× R(a) and λ ′ × R(a ′ ) are reciprocal bijections. Moreover, for any L-class L λ× R(a)∩L and λ ′ × R(a ′ )∩L are reciprocal bijections. Similarly, if a, b are two elements in the same R-class and ρ, ρ ′ are such that ρa = b and ρ ′ b = a, then × L(a) ρ and × L(b) ρ ′ are reciprocal bijections. Moreover, for any R-class R × L(a)∩R ρ and × L(b)∩R ρ ′ are reciprocal bijections.

  For a full introduction (and more!) to the representation theory of finite monoids in module theoretic terms, we refer to Representation theory of finite monoids from Benjamin Steinberg [? ]. For a comprehensive guide to the wider theory of algebra representations we refer to the very comprehensive Representation theory of finite groups and associative algebras [? ] from Charles W. Curtis and Irving Reiner, or, for a gentle introduction to the subject to Introduction to representation theory from Pavel Etingof et al. [? ].

  We note C M the set of generalized conjugacy classes.Proposition 29. ([? , Proposition 2.5]) Let E = {e 1 , . . . , e n } be idempotent representatives of the regular J -classes of M and for each e i let C i = {c i,1 , . . . , c i,m i } be representatives of the conjugacy classes of G e i . Then the set C M = e i ∈E C i is a set of representatives of character equivalency classes of M .

g∈C

  Ge ,m∈C M where the dot is the matrix product. Proof. First, we have, because of Proposition 26-2, we have: χ kL(e)/Ne(kL(e)) kM ⊗kG op e

Figure 1 :

 1 Figure 1: Location Theorem Since there is an idempotent e in L(r) ∩ R(l), rl stays in the same J -class, in L(l) ∩ R(r).

  a linear system of size |R(e)| × |L(e)|, which necessitates O(|R(e)| 2 |L(e)|) arithmetic operations. In the case of the full transformation semigroup T n , if e has k elements in its image, |L(e)| = k! × n k , while |R(e)| = k! × S(n, k) where S(n, k) is a Stirling number of the second kind, which gives |R(e)| ∼ k n . The size of that linear system becomes rapidly intractable. Moreover, once we have a basis of N e (kL) of cardinality d, we still have to compute the C 2

Figure 2 :

 2 Figure 2: Cartan Matrix of T 7 For legibility, the entries are represented as gray values. The entries are integers from 0 (in white) to 4 (the single black pixel).

Figure 3 :

 3 Figure 3: Time and memory usage: transformation monoids

Figure 4 :

 4 Figure 4: Time and memory usage: partition monoids

Figure 5 :

 5 Figure 5: Time and memory usage: partial permutation monoids

Table 1 :

 1 conjugacy classes of Γ ′ (H) cardinality (if we precompute Rank and number of generators for random monoids those cardinalities 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 Γ ′ (H) membership tests, • O(|C M |n R ) computations of τ a , • O(|C M |n L ) conjugacy class of Γ ′ (H) cardinality lookups,• n C |C M | 2 integer multiplications.

	Type	Bicharacter	Character table and Car-tan matrix
	Transformation	(4,3), (5,3), (5,4), (6,5), (7,6), (8,8), (9,8)	(4,3), (5,3), (5,4), (6,5), (7,6)
		(4,3), (4,6), (5,10), (5,15),	(4,3), (4,6), (5,10), (5,15),
	Partition	(6,18), (7,20), (8,20),	(6,18), (7,20), (8,20),
		(9,25), (10,30), (12,40)	(9,25), (10,30), (12,40)
	Partial Permutation	(3,6), (3,9), (4,8), (4,12), (5,15), (6,20), (7,21), (7,25), (7,30), (8,25), (8,30)	(3,6), (3,9), (4,8), (4,12), (5,15), (6,20), (7,21), (7,25), (7,30)

Table 2 :

 2 Computation time of the regular representation bicharacter.

		Cardinality Coefficients	Naive	Ours
	T 3	27	6 2	29 ms	8 ms
	T 4	256	11 2	92 ms	32 ms
	T 5	3125	18 2	1.44 s	84 ms
	T 6	46656	29 2	53.0 s	0.30 s
	T 7	823543	44 2	>30 min 1.54 s
	T 8	16777216	66 2	• • •	8.65 s
	T 9	387420489	96 2	• • •	58.2 s

Table 3 :

 3 Computation time of the character table.

Table 4 :

 4 Computation time of the Cartan matrix.

Terminology introduced in [? ]

Note that some authors equip the right Schützenberger group with reversed composition, and thus obtain an isomorphism instead of anti-isomorphism.

That is, the multiplication of an element of the basis of the module by an element of M is either another element of the basis or 0.

Pr. Pierre-Guy Plamondon, Laboratoire de Mathématiques de Versailles, Université Paris-Saclay, website.

Note that for Fact 3, our reference deals only with the case M = M ′ , but the proof is the same.

github.com/ZoltanCoccyx/monoid-character-table

github.com/ZoltanCoccyx/monoid-character-table

Figure 7: Cartan Matrix of the P 5 . For readability, zeroes are replaced with dots.

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. 1 . . . . . . . . . . . . . . . . . . 2 1 1 3 . 1 . . . . . . . . . . . . . . . . . 2 2 1 1 . . 1 . . . . . . . . . . . . . . . . 3 1 1 2 . . . 1 . . . . . . . . . . . . . . . 3 1 2 1 . . . . 1 . . . . . . . . . . . . . . 4 1 1 1 . . . . . 2 . . . . 1 . . . . . . . . 5 1 . . . . . . 1 . . . . . . . . . . . . 1 4 . . . . . . . 1 . . . . . . . . . . . 2 1 1 2 . . . . . . . . 1 . . . . . . . . . . 2 2 . . . . . . . . . 1 . . . . . . . . . 3 1 1 1 . . . . . 1 . . . . 2 . . 1 . . . . . 4 1 . . . . . . . . . . . 1 . . . . . . . 1 3 . . . . . . . . . . . . 1 . . . . . . 2 1 1 1 . . . . . . . . . . 1 . . 2 . 1 . . . 3 1 . . . . . . . . . . . . . 1 . . . . 1 2 . . . . . . . . . . . . . 1 . 2 . . 1 2 1 . . . . . . . . . . . . . . . . 1 . . 1 1 . . . . . . . . . . . . . . . . . 1 . 1 1 . . . . . . . . . . . . . . . 1 . . 1

151 47 19 13 5 5 1 37 13 5 4 1 10 4 1 3 1 1 .

Figure 6: Character table of P 5 . For readability, zeroes are replaced with dots.