# Cartan invariant matrices for finite monoids: Expression and computation using characters

Nicolas M. Thiéry

Univ Paris-Sud, Laboratoire de Mathématiques d'Orsay, Orsay, F-91405; CNRS, Orsay, F-91405, France

**Abstract.** Let $M$ be a finite monoid. In this paper we describe how the Cartan invariant matrix of the monoid algebra of $M$ over a field $K$ of characteristic zero can be expressed using characters and some simple combinatorial statistic. In particular, it can be computed efficiently from the composition factors of the left and right class modules of $M$. When $M$ is aperiodic, this approach works in any characteristic, and generalizes to $K$ a principal ideal domain like $Z$. When $M$ is $R$-trivial, we retrieve the formerly known purely combinatorial description of the Cartan matrix.

**Résumé.** Soit $M$ un monoïde fini. Dans cet article, nous exprimons la matrice des invariants de Cartan de l'algèbre de $M$ sur un corps $K$ de caractéristique zéro à l'aide de caractères et d'une statistique combinatoire simple. En particulier, elle peut être calculée efficacement à partir des facteurs de compositions des modules de classes à gauche et à droite de $M$. Lorsque $M$ est apériodique, cette approche se généralise à toute caractéristique et aux anneaux principaux comme $Z$. Lorsque $M$ est $R$-trivial, nous retrouvons la description combinatoire de la matrice de Cartan précédemment connue.

**Keywords:** representation theory of finite monoids, Cartan invariant matrix, characters, computation

## 1 Introduction

The recent years have witnessed a convergence of algebraic combinatorics and monoid/semigroup theory, with a flurry of papers on the representation theory of finite monoids (see e.g. [HT06, Sal07, Sal08, Ste08, HT09, AMSV09, HST10a, HST10b, DHST11, Den11, BBBS10, MS11a, MS11b] often involving intense computer exploration. The general plan is to reduce their representation theory to that of groups. This plan had been successfully applied a long time ago to the construction of their simple modules (see [GMS09]) and their characters [McA72]. An important current focus is on quivers and Cartan (invariant) matrices.

A typical approach is to use decompositions of the identity into primitive orthogonal idempotents. However, constructing such decompositions can be a non trivial task, even for highly structured monoids like the 0-Hecke monoid [Den10, Den11] or $R$-trivial monoids [BBBS10]. In this paper, we report on our investigation of the alternative use of characters to express the Cartan matrix and compute it efficiently. The spirit is similar to that of [MS11b], which gives a description of the quiver for monoids with basic algebra (all simple modules are of dimension 1) and rectangular monoids, and of the Cartan matrix for $R$-trivial monoids.

The key ingredient is a definition of the Cartan invariant matrix as generalized bimodule character of the regular representation (Definition 2.6). Here, we focus mostly on characteristic zero, though the extension to characteristic $p$ is in progress.
In Section 3 we setup the stage for character tables and their use to compute generalized characters of modules and bimodules, and in particular Cartan matrices. In Section 4 we reformulate in this setting the construction of [McA72] of the character table, showing further that it is block triangular, with the diagonal blocks being the character tables of the subgroups (Theorem 4.1). We then derive a simple expression for the Cartan matrix, in term of the character table and of a simple combinatorial statistic on the monoid (Theorem 4.4). In the case of groups, this statistic boils down to the size of the centralizers. Then, we remark that the computations can be broken down into much smaller chunks using $\mathcal{J}$-classes and the Schützenberger representation.

In Section 5 we explore special cases. For $\mathcal{J}$-trivial monoids, we retrieve our previous results [DHST11], without the need for orthogonal idempotents. For aperiodic monoids, the Cartan matrix takes a particularly simple form (Theorem 5.2) which involves only left and right class modules, and works in any characteristic, or even over a principal ideal domain like $\mathbb{Z}$.

The point of this paper is that, once put together, most of the results are essentially straightforward. Furthermore, they translate naturally into algorithms, an implementation of which is publicly available in Sage-Combinat. A detailed analysis remains to be carried out; however, roughly speaking, the algorithmic complexity for calculating the Cartan matrix drops from $|M|^6$ for usual algorithms for finite dimensional algebras down to $|M|^3$. In practice we could calculate in one hour the representation theory of the biHecke monoid of type $A_4$, a monoid of cardinality 31103 with 120 simple representations, whereas this calculation was out of reach previously.

Detailed proofs and examples will be given in an upcoming long version.

## Acknowledgments

We would like to thank Florent Hivert, Stuart Margolis, Franco Saliola, and Anne Schilling for the continuing enlightening discussions that made this paper possible. This research was driven by computer exploration, using the open-source mathematical software Sage [S+09] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc08], together with the Semigroupe package by Jean-Éric Pin [Pin10b].

# 2 Preliminaries

## 2.1 Monoids: basic combinatorics and representation theory

### 2.1.1 Monoids

A monoid is a set $M$ together with a binary operation $\cdot : M \times M \rightarrow M$ such that we have closure $(x \cdot y \in M$ for all $x, y \in M$), associativity ($(x \cdot y) \cdot z = x \cdot (y \cdot z)$ for all $x, y, z \in M$), and the existence of an identity element $1 \in M$ (which satisfies $1 \cdot x = x \cdot 1 = x$ for all $x \in M$). In this paper, unless explicitly mentioned, all monoids are finite. We use the convention that $A \subseteq B$ denotes $A$ a subset of $B$, and $A \subset B$ denotes $A$ a proper subset of $B$.

Monoids come with a far richer diversity of features than groups, but collections of monoids can often be described as varieties satisfying a collection of algebraic identities and closed under subquotients and finite products (see e.g. [Pin86, Pin10a] or [Pin10a, Chapter VII]). Groups are an example of a variety of monoids, as are all of the classes of monoids described in this paper. In this section, we recall the basic tools for monoids, and describe in more detail some of the varieties of monoids that are relevant to this paper.
### 2.1.2 Green relations

In 1951 Green introduced several preorders on monoids which are essential for the study of their structures (see for example [Pin10a, Chapter V]). Let $M$ be a monoid and define $\le_R$, $\le_L$, $\le_J$, $\le_H$ for $x, y \in M$ as follows:

$$x \le_R y \quad \text{if and only if } x = yu \text{ for some } u \in M$$

$$x \le_L y \quad \text{if and only if } x = uy \text{ for some } u \in M$$

$$x \le_J y \quad \text{if and only if } x = u y v \text{ for some } u, v \in M$$

$$x \le_H y \quad \text{if and only if } x \le_R y \text{ and } x \le_L y.$$

Beware that 1 is the largest element of these (pre)-orders. This is the usual convention in the semi-group community, but is the converse convention from the closely related notions of left/right/Bruhat order in Coxeter groups. These preorders give rise to equivalence relations, and for $K \in \{\mathcal{R}, \mathcal{L}, \mathcal{J}, \mathcal{H}\}$, we denote by $K(x)$ the $K$-equivalence class of $x$.

**Definition 2.1** A monoid $M$ is called $K$-trivial if all $K$-classes are of cardinality one, where $K \in \{\mathcal{R}, \mathcal{L}, \mathcal{J}, \mathcal{H}\}$.

The variety of $H$-trivial monoids coincides with that of *aperiodic* monoids (see for example [Pin10a, Proposition 4.9]): a monoid is called *aperiodic* if for any $x \in M$, there exists some positive integer $N$ such that $x^N = x^{N+1}$. The element $x^\omega := x^N = x^{N+1} = x^{N+2} = \dots$ is then an idempotent (the idempotent $x^\omega$ can in fact be defined for any element of any monoid [Pin10a, Chapter VI.2.3], even infinite monoids; however, the period $k$ such that $x^N = x^{N+k}$ need no longer be 1). We write $E(M) := \{x^\omega \mid x \in M\}$ for the set of idempotents of $M$. Our favorite example of a monoid which is aperiodic but not $R$-trivial is the biHecke monoid [HST10a, HST10b].

A monoid is *regular* if all its *$\mathcal{J}$-classes* are *regular*, that is contain at least one idempotent.

### 2.1.3 The Schützenberger representation

Let $\mathcal{R}(x)$ be a right class. Then, the right class module $\mathcal{KR}(x)$ is defined by considering the natural quotient structure given by $\mathcal{KR}(x) \approx \mathcal{K}xM / \sum_{y<x} \mathcal{K}yM$. The action of $M$ on $\mathcal{R}(x)$ is simply given by:

$$x.m = \begin{cases}xm & \text{if } x m \in \mathcal{R}(x), \\0 & \text{otherwise.}\end{cases}$$

Symmetrically, any $\mathcal{L}$-class gives rise to a *left class module*.

Furthermore, by the same construction, any $\mathcal{J}$-class $\mathcal{J}(x)$ gives rise to a $M$-mod-$M$ bimodule $\mathcal{K}\mathcal{J}(x)$. We will see that elucidating the structure of those bimodules from the structure of left and right class modules is the key to the efficient computation of the Cartan invariants matrix.

**Proposition 2.2** When $M$ is aperiodic, the bimodule $\mathcal{K}\mathcal{J}(x)$ admits a very simple description in terms of the left and right class modules of $x$:

$$\mathcal{K}\mathcal{J}(x) \equiv_{M-\mathrm{mod}-M} \mathcal{K}\mathcal{L}(x) \otimes \mathcal{K}\mathcal{R}(x).$$

This is a straightforward application of the so-called eggbox picture [Pin10a].

For a general monoid, the description is slightly more complicated (see [CP61]). There is a group $H(x)$ naturally associated to the $\mathcal{J}$-class of $x$. If the $\mathcal{J}$-class is regular, then $H(x)$ is simply given by $\mathcal{H}(e)$ for
any $e$ idempotent in $\mathcal{J}(x)$. Otherwise, it is defined from the action of higher classes in $\mathcal{J}$-order. Then, the right class $\mathcal{R}(x)$ is endowed with a natural $H(x)$-mod-$M$ module structure, called the *Schützenberger representation*; $\mathcal{KR}(x)$ is further free as left $H(x)$-module:

$$ \mathcal{KR}(x) = \bigoplus_{y} \mathcal{KH}(x)y, $$

where $H(x)y$ ranges through the $\mathcal{H}$-classes in $\mathcal{R}(x)$ (think diagonal action of a subgroup $H$ of a group $G$ on the $H$-cosets in $G$). Similarly, the left class module $\mathcal{KL}(x)$ is endowed with a natural $M$-mod-$H(x)$ module structure; which is free as right $H(x)$-module.

**Proposition 2.3** *The $\mathcal{J}$-class module of an element $x$ of a monoid $M$ can be described as:*

$$ \mathcal{K}\mathcal{J}(x) \equiv_{M-\mathrm{mod}-M} \mathcal{KL}(x) \otimes_{\mathcal{KH}(x)} \mathcal{KR}(x). $$

For an aperiodic monoid, $H(x)$ is trivial, and we recover Proposition 2.2 as a special case.

### 2.1.4 Simple modules

We recall here the construction of the simple modules of a finite monoid $M$. A nice survey exposition is given in [GMS09], including detailed references to the literature since the pioneering work of Clifford, Munn and Ponizovskii.

For each regular $\mathcal{J}$-class $J_i$, write $H_i$ for any of the $\mathcal{H}$-classes containing an idempotent. Observe that $H_i$ is a group. Choose an indexing set $I_i$ for the simple modules $S_{i,j}^{H_i}$ of $H_i$, and write $I = \bigcup_i I_i$. Each module $S_{i,j}^{H_i}$ can be canonically induced to a simple module $S_{i,j}$ of $M$, and each simple module of $M$ is obtained exactly once by this construction.

More explicitly, the induction proceeds as follows: one takes a left class module $L_i$ of $J_i$, and compute its top by moding out the radical, which is simply the annihilator of $J_i$ acting on $L_i$. Then one uses the right action of $H_i$ on $L_i$ to extract the appropriate simple module out of this top. This may equivalently be achieved from a right class module.

For an aperiodic monoid, the group $H_i$ is trivial, and thus has a single simple module, and we can drop the $j$ in our notations. Then, the simple left module $S_i$ is the top of the left class module $L_i$; equivalently, the dual simple right module $S_i^*$ is the top of the right class module $R_i$. For a $\mathcal{J}$-trivial monoid, the simple module $S_i$ is given directly by the $\mathcal{J}$-class $J_i$.

## 2.2 Representation theory of finite dimensional algebras

We refer to [CR06] and [Ben91] for an introduction to representation theory.

### 2.2.1 Generalized characters and Grothendieck group

Let $A$ be a finite-dimensional algebra. Given an $A$-module $X$, any strictly increasing sequence $(X_i)_{i \le k}$ of submodules

$$ \{0\} = X_0 \subset X_1 \subset X_2 \subset \cdots \subset X_k = X $$

is called a *filtration of* $X$. A filtration $(Y_j)_{i \le \ell}$ such that, for any $i$, $Y_i = X_j$ for some $j$ is called a *refinement of* $(X_i)_{i \le k}$. A filtration $(X_i)_{i \le k}$ with no non-trivial refinement is called a *composition series*. For a composition series, each quotient module $X_j/X_{j-1}$ is simple is called a *composition factor*. The multiplicity of a simple module $S$ in the composition series is the number of indices $j$ such that $X_j/X_{j-1}$
is isomorphic to $S$. The Jordan-Hölder theorem states that this multiplicity does not depend on the choice of the composition series. Hence, we may define the generalized character (or character for short) of a module $X$ as the formal sum

$$[X] := \sum_{i \in I} c_i[S_i],$$

where $I$ indexes the simple modules of $A$ and $c_i$ is the multiplicity of the simple module $S_i$ in any composition series for $X$.

The additive group of formal sums $\sum_{i \in I} m_i[S_i]$, with $m_i \in \mathbb{Z}$, is called the Grothendieck group of the category of $A$-modules, and is denoted by $\mathcal{G}_0(A)$. By definition, for any exact sequence $0 \to X \to Y \to Z \to 0$, the following equality holds in the Grothendieck group:

$$[X] = [Y] + [Z].$$

See [Ser77] for more information about Grothendieck groups.

**Example 2.4** The prototypical example, due to Frobenius, is given by the symmetric group in characteristic zero: $A = \mathbb{K}\mathbb{S}_n$. Here, $I$ is the set of integer partitions of $n$, and the Grothendieck group is identified with the homogeneous component of degree $n$ of the $\mathbb{Z}$-algebra of symmetric functions. The map $V \mapsto [V]$ is called the Frobenius map; it sends the simple module $S_\lambda$ to the Schur function $s_\lambda = [S_\lambda]$.

By analogy, we denote by $(s_i := [S_i])_{i \in I}$ the $\mathbb{Z}$-basis of the Grothendieck group $\mathcal{G}_0(A)$. It is often convenient to enlarge the ground ring by considering instead: $\mathbb{K} \otimes_{\mathbb{Z}} \mathcal{G}_0(A) = \mathbb{K}(s_i)_{i \in I}$.

### 2.2.2 Bimodules

We consider now $A$-mod-$B$ bimodules. Recall that they can be considered equivalently as left $A \otimes B^{\text{op}}$ modules, where $B^{\text{op}}$ is the opposite algebra of $B$ (a right module for $B$ being a left module for $B^{\text{op}}$). Hence all of the above applies right away. Furthermore, the simple modules can be derived from the following general theorem:

**Theorem 2.5** (See [CR81], Th. 10.38, p. 252) Let $A$ and $B$ be two finite dimensional algebras over a field $\mathbb{K}$ which we assume to be large enough (e.g. algebraically closed). Then, the simple $A \otimes B$ modules are given by the tensor products of the $A$ simple modules by the $B$ simple modules. In particular the simple $A$-mod-$A$ modules are given by the $S_i \otimes S_j^*$, where $(S_i)_{i \in I}$ are the simple left modules of $A$, and $(S_i^*)_{i \in I}$ their dual simple right modules.

### 2.2.3 Cartan invariant matrix

The Cartan invariant matrix of a finite dimensional algebra is usually defined using the dimensions of sandwiches by orthogonal idempotents, or of Homsets between projective modules. We propose here an alternative definition as bimodule character of the regular representation. This definition is natural and must be well known, though we have not yet found a reference in the literature.

**Definition 2.6** Let $A$ be a finite dimensional algebra over a large enough field. Then, the Cartan invariant matrix $(C_{i,j})_{i,j \in I}$ of $A$ is its $A$-mod-$A$ character $\chi_A$, expressed in $\mathbb{Z}(s_i)_i \otimes \mathbb{Z}(s_i)_i$. In other words, $C_{i,j}$ counts the number of composition factors of type $S_i \otimes S_j^*$ in $A$.
Here is a quick argument for why this definition is equivalent to the usual one. Let $(q_i)_{i \in I}$ be a transversal of a decomposition of the identity into primitive orthogonal idempotents. Fix two idempotents $q_i$ and $q_j$. Then, the dimension of the sandwich of a simple $A$-mod-$A$ module $S_{i'} \otimes S_{j'}$ is given by:

$$ \dim q_i S_{i'} \otimes S_{j'} q_j = \delta_{i,i'} \delta_{j,j'}. $$

Since computing the dimension of a sandwich is compatible with composition series, we obtain that $C_{i,j} = \dim q_i A q_j$ counts the number of composition factors of type $S_i \otimes S_j^*$ in $A$, as desired.

# 3 Characters and Cartan invariant matrix for finite dimensional algebras

## 3.1 Concrete characters

Let $G$ be a group, and assume for simplicity that the field is large enough and of characteristic zero. It is well known that one can give a concrete realization of the Grothendieck group by defining, for $g \in G$ and $V$ a module, $\chi_V(g)$ as the trace of the action of $g$ on $V$. Indexing the conjugacy classes by $i \in I$, and choosing an element $g_i$ in each conjugacy class, we define the map $V \mapsto \chi_V := \sum \chi_V(g_i)p_i$, where the $p_i$'s are formal indeterminates. This map is independent of the choice of the $g_i$'s since $\chi_V(g)$ is constant on conjugacy classes. Furthermore the map $V \mapsto \chi_V$ depends only on $[V]$ and extends to a one-to-one $\mathbb{Z}$-linear map $G_0(M) \mapsto K(p_i)_{i \in I}$. Then, a convenient point of view is to consider $(p_i)_i$ as an alternative basis for the (enlarged) Grothendieck group $K(s_i)_{i \in I}$ of $A$, with the character table being the matrix of the change of basis from $(s_i)_i$ to $(p_i)_i$.

**Example 3.1** Let $G = \mathfrak{S}_n$ be the symmetric group. If the $p_\lambda$ are chosen as the powersum symmetric functions, then the character $\chi_V$ correspond to the element $[V]$ of the Grothendieck group with the identification done as in Example 2.4. This motivates the notation $p_\lambda$.

**Definition 3.2** Given some field $K$ and set $\mathbb{L}$, an $\mathbb{L}$-valued trace function is a function $\chi$ assigning to each $K$-vector space $V$ and endomorphism $g \in \mathrm{End}_K(V)$ some number $\chi_V(g) \in \mathbb{L}$, and satisfying the usual axioms of the usual ($K$-valued) trace function (compatibility with duality, tensor products, quotients, conjugation). We further request that the trace function is computable.

Most of the time we take the usual trace function. However, we occasionally take some alternative, in the spirit of *Brauer characters* for modular representations of groups.

**Definition 3.3** A concrete character for a finite dimensional algebra $A$ is given by a trace function $\chi$ and two families $(g_i)_{i \in I}$ and $(g_i^*)_{i \in I}$ of elements of $A$, called support of the concrete character, such that:

(i) for a module $V$ the action of $g_i$ on $V$ is adjoint to that of $g_i^*$ acting on the dual module $V^*$;

(ii) the following $\mathbb{Z}$-linear map is one-to-one:

$$ \left\{ \begin{array}{rcl} \mathcal{G}_0(G) & \to & \mathbb{L}(p_i)_{i \in I} \\ [V] & \mapsto & \sum_{i \in I} \chi_V(g_i)p_i \end{array} \right. . $$

**Example 3.4** Let $G$ be a group, and $\mathbb{K}G$ its group algebra for some field $\mathbb{K}$ of characteristic zero and containing the appropriate roots of unity. A concrete character is obtained by taking some transversal $(g_i)_{i \in I}$ of the conjugacy classes of $G$, together with $(g_i^* := g_i^{-1})_{i \in I}$ and the usual trace function.
More generally, the results of McAlister [McA72] can be reformulated as the construction, for a finite monoid and a large enough field of characteristic zero, of a suitable choice of $(g_i)_{i \in I}$ and $(g_i^*)_{i \in I}$ to get a concrete character with the usual trace function (see Section 4.1).

The following example shows that concrete characters exist as soon as the field is large enough; the interesting point is to find some that are easy to compute.

**Example 3.5** Let A be a finite dimensional algebra over a large enough field of characteristic zero. Consider a decomposition of the identity into primitive orthogonal idempotents, and pick one such idempotent $q_i$ per simple representation of A. Then, setting $g_i = g_i^* = q_i$, together with the usual trace function gives a concrete character for A.

### 3.1.1 Character table

Let now A be any finite dimensional algebra endowed with a concrete character. Then, by definition, the irreducible representations $S_i$ of A can be indexed by $i \in I$, and the concrete character may be summarized by a matrix called the character table of A:

$$T := (\chi_{S_i}(g_j))_{i \in I, j \in I}.$$

For a group, and taking the usual trace function, this is the usual character table of the group. For a finite dimensional algebra, if one takes the concrete character given by primitive orthogonal idempotents as in example 3.5, the character table is just the identity; it thus contains no useful information.

By definition, the character table also summarizes the character for right modules and is invertible. However, unlike for groups, it is not necessarily an orthogonal matrix. It also depends a priori on the choice of the $g_i$'s; for example, the definition does not prohibit replacing each $g_i$ by $g_i/2$; we will see that, for a finite monoid, enforcing that the $g_i$'s are in the monoid makes the character table canonical up to relabeling of the rows and columns.

### 3.1.2 Composition factors of modules from characters

**Remark 3.6** Let A be a finite dimensional algebra endowed with a concrete character. Then, the character [V] of a left or right module V, that is its composition factors $S_i$ with multiplicities, can be computed by calculating $\chi_V$ in $K(p_i)_i$, and converting it back to $\mathbb{Z}(s_i)_i$.

If a filtration $\{0\} \subset V_0 \subset \cdots \subset V_k = V$ is known, the character calculation reduces to the sum of the characters of the composition factors $V_{i+1}/V_i$.

## 3.2 Characters for tensor products and bi-modules

**Proposition 3.7** Let A and B be two finite dimensional algebras endowed each with a concrete character using the same trace function $\chi$. Then, $A \otimes B$ can be endowed with the concrete character given by the families:

$$(g_i^A \otimes g_j^B)_{i \in I^A, j \in I^B} \quad \text{and} \quad (g_i^{A^*} \otimes g_j^{B^*})_{i \in I^A, j \in I^B},$$

where $(g_i^A)_{i \in I^A}$ and $(g_i^{A^*})_{i \in I^A}$ is the support of the concrete character of A, and similarly for B.

As a special case of Proposition 3.7, we can compute the composition factors of bimodules.

**Corollary 3.8** Let A be a finite dimensional algebra endowed with a concrete character, and V be an A-mod-A bimodule V. Then, its character [V], that is its composition factors $S_i \otimes S_j$ with multiplicities,
can be computed by calculating the A-mod-A character $\chi_V$ in $K(p_i)_i \otimes K(p_i^*)_i$ and converting it back to $\mathbb{Z}(s_i)_i \otimes \mathbb{Z}(s_i^*)_i$.

If a filtration $\{0\} \subset A_0 \subset \dots \subset A_k = A$ is known, the character calculation reduces to the sum of the characters of the composition factors $A_{i+1}/A_i$.

### 3.3 The Cartan invariant matrix

**Theorem 3.9** Let A be a finite dimensional algebra over a large enough field of characteristic zero endowed with a concrete character. Then, its Cartan invariant matrix can be obtained by computing the character of A as a A-mod-A module, in $K(p_i)_i \otimes K(p_i)_i$, and converting back to $\mathbb{Z}(s_i)_i \otimes \mathbb{Z}(s_i)_i$.

## 4 Characters and Cartan invariant matrices for finite monoids

### 4.1 Concrete characters

**Theorem 4.1** Let $M$ be a finite monoid, and $K$ a large enough field of characteristic zero. For each regular $J$-class $J_i$ of $M$, choose one element $g_{i,j}$ in each conjugacy class of $H_i$, and set $g_{i,j}^* := g_{i,j}^{-1}$, where the inverse is taken in $H_i$. Then:

(i) The families $(g_{i,j})_{(i,j) \in I}$ and $(g_{i,j}^*)_{(i,j) \in I}$ together with the usual trace function is a concrete character of $KM$.

(ii) The obtained character does not depend on the choice of $g_{i,j}$.

(iii) The character table is block-triangular, with the diagonal blocks given by the character tables of the groups $H_i$. In particular, those blocks are invertible.

This is mostly a reformulation of the main result of McAlister in [McA72]. As far as we know, the block triangularity (iii) is new. Besides, it allows for a short proof.

**Remark 4.2** In practice, the character table can be computed by letting the $g_{i,j}$'s act on the simple modules $S_{i',j'}$ as constructed in Section 2.1.4, for $i' \le j$ i.

### 4.2 The Cartan invariant matrix

Let $M$ be a finite monoid and $KM$ its algebra. Let $(g_i)_{i \in I}$ be as in Theorem 4.1. Define the matrix $\bar{C} = (\bar{c}_{i,j})_{i,j \in I}$ by

$$ \bar{c}_{i,j} := |\{s \in M, g_i s g_j^* = s\}|. $$

**Lemma 4.3** The character of $KM$ as a $KM$-mod-$KM$ module is given by

$$ \chi_{KM} = \sum_{i,j \in I} \bar{c}_{i,j} p_i \otimes p_j^*. $$

Let furthermore $T$ be the character table of $M$.

**Theorem 4.4** The Cartan matrix of $KM$ is given by:

$$ C = {}^t T^{-1} \overline{C} T^{-1}. $$
It follows from the above theorem that, beside the character table, the Cartan matrix $C$ depends only on the combinatorial data given by the matrix $\bar{C}$.

**Example 4.5** Let $G$ be a finite group, and $\mathbb{K}$ a field of characteristic zero. Then,

$$ \bar{c}_{i,j} = \delta_{i,j} |C_G(g_i)|, $$

where $C_G(g_i)$ is the centralizer of $g_i$. Hence,

$$ \chi_{\mathbb{K}G} = \sum_i |C_G(g_i)| p_i \otimes p_i^*. $$

Since $\mathbb{K}G$ is semi-simple, it is isomorphic to $\sum S_i \otimes S_i^*$ as a $\mathbb{K}G$-bimodule (in particular, its left regular representation is the direct sum of $\dim S_i$ copies of each simple module $S_i$). We therefore expect that:

$$ \chi_{\mathbb{K}G} = \sum_i s_i \otimes s_i^*. $$

We start from the right hand side, and use the fact that the columns of the character table are orthogonal, with the norm of the column indexed by $g_i$ being $|C_G(g_i)|$.

$$ \begin{aligned} \sum_{i \in I} s_i \otimes s_i^* &= \sum_{i \in I} \left( \sum_{j \in I} c_{i,j} p_j \right) \otimes \left( \sum_{j' \in I} \overline{c_{i,j'}} p_{j'}^* \right) \\ &= \sum_{j,j' \in I} \left( \sum_{i \in I} c_{i,j} \overline{c_{i,j'}} \right) p_j \otimes p_j^* = \sum_{j \in I} |C_G(g_j)| p_j \otimes p_j^*. \end{aligned} $$

We conclude this example with a remark when $G$ is the symmetric group $S_n$. Recall that the conjugacy classes of $S_n$ are indexed by partitions of $n$, and that the size of the centralizer of the permutation $g_\lambda$ having cycle type $\lambda$ is usually denoted by $z_\lambda$. Then,

$$ \sum_{\lambda \in I} z_{\lambda} p_{\lambda} \otimes p_{\lambda} = \sum_{\lambda \in I} s_{\lambda} \otimes s_{\lambda} $$

is nothing but the homogeneous component of degree $n$ of the Cauchy kernel expanded respectively in the powersum and Schur bases.

## 4.3 Exploiting $\mathcal{J}$-classes

The $\mathcal{J}$-classes of $M$ provide a natural $\mathbb{K}M$-mod-$\mathbb{K}M$ filtration for $\mathbb{K}M$, which can be used to reduce the calculation of the Cartan matrix of $\mathbb{K}M$.

**Remark 4.6** The Cartan matrix of $\mathbb{K}M$ is the sum of the $\mathbb{K}M$-mod-$\mathbb{K}M$ character of each $\mathcal{J}$-class module.

**Remark 4.7** The Schützenberger representation can be used to compute efficiently the character of a $\mathcal{J}$-class module $\mathbb{K}\mathcal{J}(x)$ from those of the corresponding left and right class modules. To this end, one first computes the $\mathbb{K}M$-mod-$\mathbb{H}(x)$ character of $\mathbb{K}\mathcal{L}(x)$ and the $\mathbb{H}(x)$-mod-$\mathbb{K}M$ of $\mathbb{K}\mathcal{R}(x)$, and use Proposition 2.3 to recombine them.
# 5 Special cases

## 5.1 Aperiodic monoids

**Proposition 5.1** Let $M$ be an aperiodic monoid, and $\mathbb{K}$ be any field. One may take a concrete character such that the character table is integer valued and uni-triangular. In particular, the $(p_i)_i$ form a $\mathbb{Z}$ basis of the Grothendieck group $G_0(\mathbb{K}M)$.

Let $\bar{I}$ be the indexing set of all $\mathcal{J}$-classes, regular or not. Let

$$T_L := (\chi_{L_i}(g_j))_{i \in \bar{I}, j \in I} \quad \text{and} \quad T_R := (\chi_{R_i}(g_j))_{i \in \bar{I}, j \in I}$$

be the (rectangular) matrices of the characters of the left class modules $\mathbb{K}L_i$ and right class modules $\mathbb{K}R_i$ respectively. Note that $M$ act on those modules by transformation on the basis, so $T_L$ and $T_R$ are combinatorial and do not depend on the characteristic. Note that the matrix $D_L := T_L T^{-1}$ is the decomposition matrix of the left class modules in term of the simple modules, and similarly for $D_R$. As an essentially straightforward corollary of Theorem 4.4, one gets:

**Theorem 5.2** The Cartan matrix of $M$ is given by:

$$C = {}^t D_L D_R = {}^t T^{-1} {}^t T_L T_R T^{-1}.$$

**Remark 5.3** Restricting $T_L$ to the regular $\mathcal{J}$-classes, gives a unitriangular matrix. It follows that the character of the left classes provide yet another alternative basis for the Grothendieck group $G_0(\mathbb{K}M)$, and similarly for the right classes.

Hence, the theory is characteristic free for aperiodic monoids, and could be generalized straightforwardly to, say, principal ideal domains like $\mathbb{Z}$. Altogether, all the ingredients are combinatorial, except for the construction of the simple modules as top of the left class modules (the radical is obtained by solving a linear system), and computation of the character of the $g_i$ thereupon; because of that, the character table still depends on the characteristic.

## 5.2 $\mathcal{J}$-trivial monoids

We recover directly the description of the Cartan matrix of a $\mathcal{J}$-trivial monoid $M$ of [DHST11], without the need for orthogonal idempotents. The simple modules are in one-to-one correspondence with the idempotents of $M$, so we use $I = E(M)$ as indexing set. For $x \in M$, define

$$\mathrm{rfix}(x) := \min\{e \in E(M) \mid xe = x\} \quad \text{and} \quad \mathrm{lfix}(x) := \min\{e \in E(M) \mid ex = x\},$$

where the min's are taken in $\mathcal{J}$-order (see [DHST11] for the details).

**Theorem 5.4** Let $\mathbb{K}$ be any field and $M$ be a $\mathcal{J}$-trivial monoid. Then, the Cartan matrix of $\mathbb{K}M$ is given by:

$$\chi_{\mathbb{K}M} = \sum_{x \in M} s_{\mathrm{lfix}(x)} \otimes s_{\mathrm{rfix}(x)}^*.$$

**Proof:** By Theorem 5.2, one is reduced to the calculation of the $M$-mod-$M$ character of all $\mathcal{J}$-class modules. Each such module is of the form $\mathbb{K}x$ for $x$ in $M$; it is of dimension 1, simple, and isomorphic as a $M$-mod-$M$ bimodule to $S_{\mathrm{lfix}(x)} \otimes S_{\mathrm{rfix}(x)}^*$. $\square$
References

[AMSV09] Jorge Almeida, Stuart Margolis, Benjamin Steinberg, and Mikhail Volkov. Representation theory of finite semigroups, semigroup radicals and formal language theory. *Trans. Amer. Math. Soc.*, 361(3):1429–1461, 2009.

[BBBS10] Chris Berg, Nantel Bergeron, Sandeep Bhargava, and Franco Saliola. Primitive orthogonal idempotents for *R*-trivial monoids. 2010. preprint arXiv:1009.4943.

[Ben91] D. J. Benson. *Representations and cohomology. I*, volume 30 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1991. Basic representation theory of finite groups and associative algebras.

[CP61] A. H. Clifford and G. B. Preston. *The algebraic theory of semigroups*. Vol. I. Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I., 1961.

[CR81] Charles W. Curtis and Irving Reiner. *Methods of representation theory*. Vol. I. John Wiley & Sons Inc., New York, 1981. With applications to finite groups and orders, Pure and Applied Mathematics, A Wiley-Interscience Publication.

[CR06] Charles W. Curtis and Irving Reiner. *Representation theory of finite groups and associative algebras*. AMS Chelsea Publishing, Providence, RI, 2006. Reprint of the 1962 original.

[Den10] Tom Denton. A combinatorial formula for orthogonal idempotents in the 0-Hecke algebra of $S_N$. *DMTCS proc.*, AN(01):701–712, 2010.

[Den11] Tom Denton. A combinatorial formula for orthogonal idempotents in the 0-Hecke algebra of the symmetric group. *Electron. J. Combin.*, 18(1):Paper 28, 20, 2011. preprint arXiv:1008.2401v1 [math.RT].

[DHST11] Tom Denton, Florent Hivert, Anne Schilling, and Nicolas M. Thiéry. On the representation theory of finite *J*-trivial monoids. *Sém. Lothar. Combin.*, 64:Art. B64d, 44, 2010/11. 40 pages, arXiv:1010.3455 [math.RT].

[GMS09] Olexandr Ganyushkin, Volodymyr Mazorchuk, and Benjamin Steinberg. On the irreducible representations of a finite semigroup. *Proc. Amer. Math. Soc.*, 137(11):3585–3592, 2009.

[HST10a] Florent Hivert, Anne Schilling, and Nicolas M. Thiéry. The biHecke monoid of a finite Coxeter group. *DMTCS proc.*, AN(01):307–318, 2010. arXiv:0912.2212 [math.CO].

[HST10b] Florent Hivert, Anne Schilling, and Nicolas M. Thiéry. The biHecke monoid of a Coxeter group and its representation theory. Submitted, 57 pages, arXiv:1012.1361 [math.CO], December 2010.

[HT06] Florent Hivert and Nicolas M. Thiéry. Representation theories of some towers of algebras related to the symmetric groups and their Hecke algebras. In *Proceedings of FPSAC'06 San Diego*, 2006. arXiv:0607391v2 [math.RT].
[HT09] Florent Hivert and Nicolas M. Thiéry. The Hecke group algebra of a Coxeter group and its representation theory. *J. Algebra*, 321(8):2230–2258, 2009. arXiv:0711.1561 [math.RT].

[McA72] D. B. McAlister. Characters of finite semigroups. *J. Algebra*, 22:183–200, 1972.

[MS11a] Stuart Margolis and Benjamin Steinberg. The quiver of an algebra associated to the Mantaci-Reutenauer descent algebra and the homology of regular semigroups. *Algebr. Represent. Theory*, 14(1):131–159, 2011.

[MS11b] Stuart Margolis and Benjamin Steinberg. Quivers of monoids with basic algebras. *Compositio Mathematicae*, 2011.

[Pin86] J.-E. Pin. *Varieties of formal languages*. Foundations of Computer Science. Plenum Publishing Corp., New York, 1986. With a preface by M.-P. Schützenberger, Translated from the French by A. Howie.

[Pin10a] Jean-Éric Pin. *Mathematical Foundations of Automata Theory*. 2010.

[Pin10b] Jean-Éric Pin. Semigroupe: a software for computing finite semigroups, 2010. http://www.liafa.jussieu.fr/jep/semigroupes.html.

[S⁺09] W. A. Stein et al. *Sage Mathematics Software (Version 3.3)*. The Sage Development Team, 2009. http://www.sagemath.org.

[Sal07] Franco V. Saliola. The quiver of the semigroup algebra of a left regular band. *Internat. J. Algebra Comput.*, 17(8):1593–1610, 2007.

[Sal08] Franco V. Saliola. On the quiver of the descent algebra. *J. Algebra*, 320(11):3866–3894, 2008.

[SCc08] The Sage-Combinat community. *Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics*, 2008. http://combinat.sagemath.org.

[Ser77] Jean-Pierre Serre. *Linear representations of finite groups*. Springer-Verlag, New York, 1977. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.

[Ste08] B. Steinberg. Möbius functions and semigroup representation theory II: Character formulas and multiplicities. *Advances in Mathematics*, 217(4):1521–1557, 2008.