THE ALGEBRA OF ESSENTIAL RELATIONS ON A FINITE SET

SERGE BOUC AND JACQUES THÉVENAZ

Abstract. Let X be a finite set and let k be a commutative ring. We consider the k-algebra of the monoid of all relations on X, modulo the ideal generated by the relations factorizing through a set of cardinality strictly smaller than Card(X), called inessential relations. This quotient is called the essential algebra associated to X. We then define a suitable nilpotent ideal of the essential algebra and describe completely the structure of the corresponding quotient, a product of matrix algebras over suitable group algebras. In particular, we obtain a description of the Jacobson radical and of all the simple modules for the essential algebra.

1. Introduction

Let X and Y be finite sets. A correspondence between X and Y is a subset R of X × Y. In case X = Y, we say that R is a relation on X. Correspondences can be composed as follows. If R ⊆ X × Y and S ⊆ Y × Z, then RS is the correspondence between X and Z defined by

RS = {(x, z) ∈ X × Z | ∃ y ∈ Y such that (x, y) ∈ R and (y, z) ∈ S} .

In particular the set of all relations on X is a monoid. Given a commutative ring k and a finite set X, let R be the k-algebra of the monoid of all relations on X (having this monoid as a k-basis).

Throughout this paper, X will denote a finite set of cardinality n. We say that a relation R on X is inessential if there exists a set Y with Card(Y) < Card(X) and two relations S ⊆ X × Y and T ⊆ Y × X such that R = ST. Otherwise, R is called essential. The set of all inessential relations on X span a two-sided ideal I of R. We define E = R/I. It is clear that E is a k-algebra having as a k-basis the set of all essential relations on X. The purpose of this paper is to explore the concept of essential relation and to study the structure of E.

We shall define a nilpotent ideal N of E and describe completely the quotient P = E/N. More precisely, P is isomorphic to a product of matrix algebras over suitable group algebras, the product being indexed by the set of all (partial) order relations on X, up to permutation. Consequently, we know the Jacobson radical J(E) and we find all the simple E-modules.

The idea of passing to the quotient by all elements obtained from something smaller is widely used in the representation theory of finite groups. In the theory of G-algebras, the notion of Brauer quotient is of this kind (see [The]). In the more recent development of the theory of biset functors for finite groups (see [Bo]), the same idea plays a key role in [BST]. The analogous idea for sets instead of groups yields the notion of essential relation, which does not seem to have been studied. It is the purpose of this paper to fill this gap.

Date: October 28, 2013.

2000 Mathematics Subject Classification. 06A99, 08A99, 16D99, 16N99.

2. Essential relations

Given a correspondence R ⊆ X × Y between a set X and a set Y, then for every a ∈ X and b ∈ Y we write

aR = {y ∈ Y | (a, y) ∈ R}  and  R_{b} = {x ∈ X | (x, b) ∈ R} .

We call _{a}R a column of R and R_{b} a row of R.

We first characterize inessential relations. Any subset of X ×Y of the form U ×V will be called a block (where U ⊆ X and V ⊆ Y).

2.1. Lemma. Let X, Y, Z be finite sets.

(a) Let R ⊆ X × Z be a correspondence between X and Z. Then R factorizes through Y if and only if R can be decomposed as a union of blocks indexed by the set Y.

(b) Let R be a relation on X, where X has cardinality n. Then R is inessential if and only if R can be decomposed as a union of at most n − 1 blocks.

Proof : (a) If R factorizes through Y, then R = ST, where S ⊆ X × Y and T ⊆ Y × Z. Then we can write

R = ⋃_{y∈Y} S_{y} ×_{y}T ,

as required.

Suppose conversely that R = ⋃_{y∈Y} U_{y} × V_{y}, where each U_{y} is a subset of X and each V_{y} is a subset of Z. Then we define

S = ⋃_{y∈Y} U_{y} × {y} ⊆ X × Y  and  T = ⋃_{y∈Y} {y} × V_{y} ⊆ Y × Z .

Then S is a correspondence between X and Y, and U_{y} = S_{y}, the y-th row of S. Similarly, T is a correspondence between Y and Z, and V_{y} = _{y}T, the y-th column of T.

We now claim that R = ST. If (x, z) ∈ R, then there exists y ∈ Y such that (x, z) ∈ U_{y} × V_{y}. It follows that (x, y) ∈ S and (y, z) ∈ T, hence (x, z) ∈ ST, proving that R ⊆ ST. If now (x, z) ∈ ST, then there exists y ∈ Y such that (x, y) ∈ S and (y, z) ∈ T. It follows that x ∈ S_{y} = U_{y} and z ∈ _{y}T = V_{y}, hence (x, z) ∈ U_{y} × V_{y} ⊆ R, proving that ST ⊆ R. We have shown that R = ST, proving the claim.

(b) This follows immediately from (a).

2.2. Corollary. Let R be a relation on X. If two rows of R are equal, then R is inessential. If two columns of R are equal, then R is inessential.

Proof : Suppose that _{a}R = _{b}R = V. Then

R = (\{a, b\} × V) ∪ ( ⋃_{{c∈X \atop c≠a,c≠b}}\{c\} ×_{c}R ) ,

a union of n − 1 blocks, where n = Card(X). The proof for rows is similar.

2.3. Corollary. Let R be a relation on X. If a row of R is empty, then R is inessential. If a column of R is empty, then R is inessential.

Proof : Assume that _{a}R = ∅. Then

R = ⋃_{{c∈X \atop c≠a}} \{c\} ×_{c}R ,

a union of n − 1 blocks, where n = Card(X). The proof for rows is similar.

2.4. Corollary. Let R be a relation on X. If R is an equivalence relation different from the equality relation (i.e. R ≠ Δ where Δ is the diagonal of X × X), then R is inessential.

Proof : Suppose that a and b are equivalent and a ≠ b. Then the rows R_{a} and R_{b} are equal and Corollary 2.2 applies.

We need a few basic facts about reflexive relations. Recall that a relation S on X is reflexive if S contains Δ = {(x, x) | x ∈ X}. Moreover, a preorder is a relation which is reflexive and transitive, while an order is a preorder which is moreover antisymmetric. (Note that, throughout this paper, the word “order” stands for “partial order”.) Associated to a preorder R, there is an equivalence relation ∼_{R} defined by x ∼_{R} y if and only if (x, y) ∈ R and (y, x) ∈ R. Then ∼_{R} is the equality relation if and only if R is an order.

We will often use the containment of relations on X (as subsets of X × X). Note that if R ⊆ S, then RT ⊆ ST and T R ⊆ T S for any relation T on X. If S is a reflexive relation, then S ⊆ S^{2} ⊆ S^{3} … and there exists m ∈ ℕ such that S^{m} = S^{m+1}, hence S^{m} = S^{N} for all N ≥ m. The relation \overline{S} := S^{m} is called the transitive closure of S. It is reflexive and transitive, that is, a preorder. Note that any preorder is an idempotent relation.

2.5. Proposition. Let R be a preorder on a finite set X of cardinality n.

(a) If R is not an order, then R is inessential.

(b) If R is an order and if Q is a reflexive relation contained in R, then Q is essential. In particular, if R is an order, then R is essential.

(c) If R is a total order, then R is maximal among essential relations.

Proof : (a) If R is not an order, then the associated equivalence relation ∼_{R} is not the equality relation. Let a and b be equivalent under ∼_{R} with a ≠ b. Then, by transitivity of R, the rows R_{a} and R_{b} are equal. By Corollary 2.2, R is inessential.

(b) Suppose now that R is an order and that Q is reflexive with Q ⊆ R. We claim that, if a ≠ b, then (a, a) and (b, b) cannot belong to a block contained in Q. This is because, if (a, a), (b, b) ∈ U ×V ⊆ Q, then (a, b) ∈ U ×V (because a ∈ U and b ∈ V) and (b, a) ∈ U × V (because b ∈ U and a ∈ V), and therefore (a, b) ∈ Q and (b, a) ∈ Q, hence (a, b) ∈ R and (b, a) ∈ R, contrary to antisymmetry. It follows that, in any expression of Q as a union of blocks, the diagonal elements (a, a) all lie in different blocks, so that the number of blocks is at least n. This shows that Q is essential.

(c) Without loss of generality, we can assume that the total order R is the usual total order on the set X = {1, 2, …, n}, i.e. (x, y) ∈ R ⇔ x ≤ y. Let S be a relation strictly containing R. Then S−R ≠ ∅ and we choose (j, i) ∈ S−R with i maximal, and then j maximal among all x with (x, i) ∈ S−R. In other words, (j, i) ∈ S, but j > i because (j, i) ∉ R, and moreover

(x, y) ∈ S−R ⇒ y ≤ i  and  (x, i) ∈ S−R ⇒ x ≤ j .

If i = j − 1, then the rows S_{i} and S_{j} are equal, so S is inessential by Corollary 2.2. Assume now that j − 1 > i. Then we claim that

S = (S_{i} × {i, j}) ∪ (S_{j−1} × {j−1, j}) ∪ ( ⋃_{k≠i,j−1,j} S_{k} × {k}) .

To show that the first block is contained in S, let x ∈ S_{i}. Then x ≤ j if (x, i) ∈ S−R, and also x ≤ j if (x, i) ∈ R, i.e. x ≤ i. Hence x ≤ j in both cases, and therefore (x, j) ∈ R ⊂ S. This shows that S_{i} × {j} ⊆ S.

To show that the second block is contained in S, let x ∈ S_{j−1}. Then (x, j−1) cannot belong to S−R, by maximality of i (because j−1 > i). Thus (x, j−1) ∈ R, that is, x ≤ j−1. Then x < j, hence (x, j) ∈ S. This shows that S_{j−1} × {j} ⊆ S.

Next we show that S is contained in the union of the blocks above. This is clear for any (x, y) ∈ S such that y ≠ j. Now take (x, j) ∈ S. By maximality of i and since j > i, we have (x, j) ∈ R, that is, x ≤ j. If x = j, then (j, j) ∈ S_{i} × {i, j} because (j, i) ∈ S, that is, j ∈ S_{i}. If x < j, then x ≤ j−1, hence (x, j−1) ∈ S, that is x ∈ S_{j−1}, and therefore (x, j) ∈ S_{j−1} × {j−1, j}.

This proves the claim about the block decomposition. It follows that S is a union of n − 1 blocks, so S is inessential.

2.6. Example. Let n = Card(X). Let Δ be the diagonal of X × X and let R = (X × X) − Δ. It is not difficult to see that R is essential if 2 ≤ n ≤ 4. However, for n ≥ 5, we prove that R is inessential. Without loss of generality, we can choose X = {1, …, n}. If U ⊆ X, we write U^{c} for the complement of U in X. Then it is easy to prove that R is equal to

( ⋃_{i=1}^{n−3}{i, i+3}^{c}×{i, i+3})∪({n−2, n−1, n}^{c}×{n−2, n−1, n})∪({1, 2, 3}^{c}×{1, 2, 3}).

This is a union of n − 1 blocks, so R is inessential.

3. Permutations

As before, X denotes a finite set. We let Σ be the symmetric group on X, that is, the group of all permutations of X. For any σ ∈ Σ, we define

Δ_{σ} = { (σ(x), x) ∈ X × X | x ∈ X } .

This is actually the graph of the map σ^{−1}, but the choice is made so that Δ_{σ}Δ_{τ} = Δ_{στ} for all σ, τ ∈ Σ. With a slight abuse, we shall often call Δ_{σ} a permutation. We also write Δ = Δ_{id}.

The group Σ has a left action on the set of all relations, σ acting via left multiplication by Δ_{σ}. Similarly, Σ also acts on the right on the set of relations. It is useful to note how multiplication by Δ_{σ} behaves. Given any relation R on X,

(x, y) ∈ R ⟺ (σ(x), y) ∈ Δ_{σ}R ⟺ (x, σ^{−1}(y)) ∈ RΔ_{σ} .

3.1. Lemma. Let R be a relation on X and let Δ_{σ} be a permutation.

(a) R is essential if and only if Δ_{σ}R is essential.

(b) Δ_{σ} is essential.

(c) The left action of Σ on the set of all essential relations is free.

Proof : (a) If R factorizes through a set of cardinality smaller than Card(X), then so does Δ_{σ}R. The converse follows similarly using multiplication by Δ_{σ^{−1}}.

(b) This follows from (a) by taking R = Δ (which is essential by Proposition 2.5 because it is an order).

(c) Suppose that Δ_{σ}R = R for some σ ≠ id. Then

(x, y) ∈ R ⟺ (σ(x), y) ∈ R ,

hence _{x}R = _{σ(x)}R. Since σ ≠ id, two columns of R are equal and so R is inessential by Corollary 2.2. Thus if R is essential, Δ_{σ}R ≠ R for all σ ≠ id.

Our next result will be essential in our analysis of essential relations.

3.2. Theorem. Any essential relation contains a permutation.

We shall provide two different proofs. The first is direct, while the second uses a theorem of Philip Hall. In fact, a relation containing a permutation is called a Hall relation in a paper of Schwarz [Sch], because of Hall’s theorem, so Theorem 3.2 asserts that any essential relation is a Hall relation.

First proof : Let R be a relation on X and let n = Card(X). We have to prove that, if R is essential, then there exists σ ∈ Σ such that R contains Δ_{σ^{−1}}, that is, RΔ_{σ} contains Δ (or in other words RΔ_{σ} is reflexive). Let D_{σ} = RΔ_{σ} ∩ Δ and suppose that Card(D_{σ}) < n, for all σ ∈ Σ. Then we have to prove that R is inessential.

We choose τ ∈ Σ such that Card(D_{σ}) ≤ Card(D_{τ}), for all σ ∈ Σ. We let S = RΔ_{τ} and we aim to prove that S is inessential (hence R too by Lemma 3.1). Note that D_{τ} ⊆ S by construction. Define

A = {a ∈ X | (a, a) ∈ D_{τ} } , in other words D_{τ} = {(a, a) | a ∈ A} .

In particular Card(A) = Card(D_{τ}) < n. By maximality of D_{τ}, we have the following property :

Card(SΔ_{σ} ∩ Δ) ≤ Card(A) , ∀ σ ∈ Σ . (∗)

Given x, y ∈ X, define a path from x to y to be a sequence x_{0}, x_{1}, …, x_{r} of elements of X such that x_{0} = x, x_{r} = y, and (x_{i}, x_{i+1}) ∈ S for all i = 0, …, r − 1. We write x ⇝ y to indicate that there is a path from x to y, and also x → y whenever (x, y) ∈ S (path of length 1). Define A^{c} to be the complement of A in X (so A^{c} is nonempty by assumption). Define also

A_{1} = {a ∈ A | there exists z ∈ A^{c} and a path z ⇝ a} ,
A_{2} = {a ∈ A | there exists z ∈ A^{c} and a path a ⇝ z} .

We claim that there is no path from an element of A_{1} to an element of A_{2}. Suppose by contradiction that there is a path a_{1} ⇝ a_{2} with a_{i} ∈ A_{i}. Then there exists z_{i} ∈ A^{c} and paths z_{1} ⇝ a_{1} ⇝ a_{2} ⇝ z_{2}, in particular z_{1} ⇝ a ⇝ z_{2} with a ∈ A. In the path z_{1} ⇝ a, let w_{1} be the element of A^{c} closest to a, so that the path w_{1} ⇝ a does not contain any element of A^{c} except w_{1}. Similarly, let w_{2} be the element of A^{c} closest to a in the path a ⇝ z_{2} , so that the path a ⇝ w_{2} does not contain any element of A^{c} except w_{2}. We obtain a path w_{1} ⇝ a ⇝ w_{2} having all its elements in A except the two extremities w_{1} and w_{2}. By suppressing cycles within A, we can assume that all elements of A in this path are distinct. We end up with a path

w_{1} → x_{1} → ⋯ → x_{r} → w_{2}

where x_{1}, …, x_{r} ∈ A are all distinct.

Let σ ∈ Σ be the cycle defined by σ(w_{1}) = x_{1}, σ(x_{i}) = x_{i+1} for 1 ≤ i ≤ r − 1, σ(x_{r}) = w_{2}, and finally σ(w_{2}) = w_{1} in case w_{2} ≠ w_{1}. In case w_{2} = w_{1}, then σ(w_{2}) is already defined to be σ(w_{2}) = σ(w_{1}) = x_{1}. We emphasize that σ(y) = y for all the other elements y ∈ X. Then we obtain :

(w_{1}, x_{1}) ∈ S  hence  (w_{1}, w_{1}) ∈ SΔ_{σ} ,
(x_{i}, x_{i+1}) ∈ S  hence  (x_{i}, x_{i}) ∈ SΔ_{σ} ,
(x_{r}, w_{2}) ∈ S  hence  (x_{r}, x_{r}) ∈ SΔ_{σ} ,
(y, y) ∈ S  hence  (y, y) ∈ SΔ_{σ} ,  ∀ y ∈ A − {x_{1}, …, x_{r}} .

Thus we obtain (a, a) ∈ SΔ_{σ}, ∀ a ∈ A, but also (w_{1}, w_{1}) ∈ SΔ_{σ}. Therefore Card(SΔ_{σ} ∩ Δ) > Card(A), contrary to Property (∗). This proves the claim that there is no path from A_{1} to A_{2}.

In particular, A_{1} ∩A_{2} = ∅ because if a ∈ A_{1} ∩A_{2} we would have a path of length zero from A_{1} to A_{2} (since (a, a) ∈ S). Let A_{3} be the complement of A_{1} ∪ A_{2} in A. Thus X is the disjoint union of the 4 subsets A^{c}, A_{1}, A_{2}, and A_{3}.

We now claim the following :

(a) There is no relation between A^{c} and A^{c}, that is, S ∩ (A^{c} × A^{c}) = ∅.

(b) There is no relation between A^{c} and A_{2} ∪ A_{3}, that is, S ∩ (A^{c} × A_{2}) = ∅

and S ∩ (A^{c} × A_{3}) = ∅.

(c) There is no relation between A_{1} and A^{c}, that is, S ∩ (A_{1} × A^{c}) = ∅.

(d) There is no relation between A_{1} and A_{2}, that is, S ∩ (A_{1} × A_{2}) = ∅.

(e) There is no relation between A_{1} and A_{3}, that is, S ∩ (A_{1} × A_{3}) = ∅.

To prove (a), suppose that (w, z) ∈ S where w, z ∈ A^{c}. Choose ρ ∈ Σ such that ρ(a) = a for all a ∈ A and ρ(w) = z. Then (a, a) ∈ SΔ_{ρ} for all a ∈ A but also (w, w) ∈ SΔ_{ρ}, contrary to Property (∗).

To prove (b), we note that the definition of A_{1} implies that, if (z, a) ∈ S with z ∈ A^{c} and a ∈ A, then a ∈ A_{1}. Thus a ∉ A_{2} ∪ A_{3}.

To prove (c), suppose that (a, z) ∈ S with a ∈ A and z ∈ A^{c}. Then a ∈ A_{2} by the definition of A_{2} and in particular a ∉ A_{1}.

Property (d) follows immediately from the previous claim that there is no path from A_{1} to A_{2}.

To prove (e), suppose that (a_{1}, a_{3}) ∈ S with a_{1} ∈ A_{1} and a_{3} ∈ A_{3}. Then by the definition of A_{1}, there is a path z ⇝ a_{1} → a_{3} where z ∈ A^{c}, but this means that a_{3} ∈ A_{1}, a contradiction.

It follows that the relation S has the property that there is no relation between A^{c} ∪ A_{1} and A^{c} ∪ A_{2} ∪ A_{3}. Therefore S is the union of the columns indexed by (A^{c} ∪ A_{1})^{c} = A_{2} ∪ A_{3} and the lines indexed by (A^{c} ∪ A_{2} ∪ A_{3})^{c} = A_{1}, that is,

S = ( ⋃_{b∈A_{2}∪A_{3}} _{b}S) ∪ ( ⋃_{a∈A_{1}} S_{a}) .

Since Card(A_{2} ∪ A_{3}) + Card(A_{1}) = Card(A), we obtain a union of Card(A) blocks. But Card(A) < n by assumption, so S is inessential, as was to be shown.

Second proof : Let R be an essential relation on X. For any subset A of X, define

R_{A} = {x ∈ X | ∃ a ∈ A such that (x, a) ∈ R} = ⋃_{a∈A} R_{a} .

Then R decomposes as a union of blocks

R = ( ⋃_{y∉A}(R_{y} × {y})) ⋃ ( ⋃_{x∈R_{A}}({x} ×_{x}R)) .

Since R is essential, Card(X − A) + Card(R_{A}) cannot be strictly smaller than Card(X). Therefore Card(R_{A}) ≥ Card(A), for all subsets A of X, that is

Card ( ⋃_{a∈A} R_{a}) ≥ Card(A) .

This is precisely the assumption in a theorem of Philip Hall (see Theorem 5.1.1 in [HaM], or [HaP] for the original version which is slightly different). The conclusion is that there exist elements x_{y} ∈ R_{y}, where y runs over X, which are all distinct. In other words σ : y ↦ x_{y} is a permutation and

(σ(y), y) = (x_{y}, y) ∈ R for all y ∈ X .

This means that R contains Δ_{σ}, as required.

3.3. Corollary. Let R be an essential relation on X. Then there exists m ∈ ℕ such that R^{m} is a preorder.

Proof : By Theorem 3.2, R contains Δ_{σ} for some σ ∈ Σ. If σ has order k in the group Σ, then R^{k} contains Δ_{σ^{k}} = Δ, so R^{k} is reflexive. Then the transitive closure of R^{k} is some power R^{kt}. This is reflexive and transitive, that is, a preorder.

We know that any order is an essential relation (Proposition 2.5), hence contains a permutation (Theorem 3.2). But in fact, we have a more precise result.

3.4. Lemma. If R is an order on X, then R contains a unique permutation, namely Δ.

Proof : Suppose that R is reflexive and transitive and contains a nontrivial permutation Δ_{σ}. Then σ contains a nontrivial k-cycle, say on x_{1}, …, x_{k}, for some k ≥ 2. It follows that (x_{i+1}, x_{i}) ∈ R for 1 ≤ i ≤ r − 1, hence (x_{k}, x_{1}) ∈ R by transitivity of R. Now we also have (x_{1}, x_{k}) ∈ R because σ(x_{k}) = x_{1}. Thus the relation R is not antisymmetric, hence cannot be an order.

In the same vein, we have the following more general result.

3.5. Lemma. Let R be an order and let S, S′ be two relations on X. The following two conditions are equivalent :

(a) Δ ⊆ S′S ⊆ R.

(b) There exists a permutation Δ_{σ} such that : Δ ⊆ Δ_{σ^{−1}}S ⊆ R and Δ ⊆ S′Δ_{σ} ⊆ R.

Moreover, in condition (b), the permutation σ is unique.

Proof : If (b) holds, then

Δ = Δ^{2} ⊆ (S′Δ_{σ})(Δ_{σ^{−1}}S) = S′S ⊆ R^{2} = R ,

so (a) holds.

If (a) holds, then S′S is essential, by Proposition 2.5. It follows that S is essential, and therefore S contains a permutation Δ_{σ}, by Theorem 3.2. Then we obtain

Δ ⊆ Δ_{σ^{−1}}S  and  S′Δ_{σ} ⊆ S′S ⊆ R .

Similarly, S′ is essential, hence contains a permutation Δ_{τ}, and we obtain

Δ ⊆ S′Δ_{τ^{−1}}  and  Δ_{τ} S ⊆ S′S ⊆ R .

Now R contains Δ_{τ} Δ_{σ} = Δ_{τσ} and Lemma 3.4 implies that τσ = id, that is, τ = σ^{−1}. Then (b) follows.

If moreover S contains a permutation Δ_{ρ} (that is, Δ ⊆ Δ_{ρ^{−1}}S), then

Δ_{σ^{−1}ρ} = Δ_{σ^{−1}}Δ_{ρ} ⊆ S′S ⊆ R ,

and so σ^{−1}ρ = id by Lemma 3.4, proving the uniqueness of σ.

4. The essential algebra

Let X be a finite set and let k be a commutative ring. We shall be mainly interested in the cases where k is either the ring ℤ of integers or a field, but it is convenient to work with an arbitrary commutative ring.

Let R be the k-algebra of the monoid of all relations on X. This monoid is a k-basis of R and the product in the monoid defines the algebra structure. The set of all inessential relations on X spans a two-sided ideal I of R. We define E = R/I and call it the essential algebra. It is clear that E is a k-algebra having as a k-basis the set of all essential relations on X. Moreover, if R and S are essential relations but RS is inessential, then RS = 0 in E.

Both R and E have an anti-automorphism, defined on the basis elements by R ↦ R^{op}, where (x, y) ∈ R^{op} if and only if (y, x) ∈ R. It is easy to see that (RS)^{op} = S^{op}R^{op}.

As before, we let Σ be the symmetric group of all permutations of X. We first describe an obvious quotient of E.

4.1. Lemma. Let H be the k-submodule of the essential algebra E spanned by the set of all essential relations which strictly contain a permutation. Then H is a two-sided ideal of E and E/H ≅ kΣ, the group algebra of the symmetric group Σ.

Proof : Let us write ⊂ for the strict containment relation. Let R be an essential relation such that Δ_{σ} ⊂ R and let S be any essential relation. Then S contains a permutation Δ_{τ}, by Theorem 3.2. We obtain

Δ_{στ} = Δ_{σ}Δ_{τ} ⊂ RΔ_{τ} ⊆ RS ,

showing that RS ∈ H. Similarly SR ∈ H and therefore H is a two-sided ideal of E.

The quotient E/H has a k-basis consisting of all the permutations Δ_{σ}, for σ ∈ Σ. Moreover, they multiply in the same way as permutations, so E/H is isomorphic to the group algebra of the symmetric group Σ.

If k is a field, it follows, not surprisingly, that every irreducible representation of the symmetric group Σ gives rise to a simple E-module. In short, the representation theory of the symmetric group Σ is part of the representation theory of E.

We now want to describe another E-module, which is simple when k is a field. We fix a total order T on X (e.g. the usual total order on X = {1, …, n}). Then any other total order on X is obtained by permuting the elements of X. Since permuting via σ corresponds to conjugation by Δ_{σ}, we see that {T_{σ} := Δ_{σ}T Δ_{σ^{−1}} | σ ∈ Σ} is the set of all total orders on X. All of them are maximal essential relations on X, by Proposition 2.5.

4.2. Lemma. Let T be a total order on X.

(a) If ρ ∈ Σ, then T Δ_{ρ}T = 0 in E if ρ ≠ id and otherwise T ΔT = T^{2} = T.

(b) The set {T_{σ} := Δ_{σ}T Δ_{σ^{−1}} | σ ∈ Σ} is a set of pairwise orthogonal idempotents of E.

Proof : (a) T T_{ρ} contains both T and T_{ρ} (because both T and T_{ρ} contain Δ). Since T ≠ T_{ρ} if ρ ≠ id, the product T T_{ρ} contains strictly T and is therefore inessential by Proposition 2.5. Thus T Δ_{ρ}T is also inessential, that is, T Δ_{ρ}T = 0. On the other hand T^{2} = T because any preorder is idempotent.

(b) It follows from (a) that

T_{σ}T_{τ} = Δ_{σ}T Δ_{σ^{−1}τ} T Δ_{τ^{−1}} = \{ \begin{matrix}0 & if σ ≠ τ , \\ Δ_{σ}T Δ_{σ^{−1}} = T_{σ} & if σ = τ , \end{matrix}

as was to be shown.

4.3. Proposition. Fix a total order T on X. Let L be the k-submodule of the essential algebra E spanned by the set {Δ_{σ}T | σ ∈ Σ}. Then L is a left ideal of E and is free of rank n! as a k-module, where n = Card(X). If k is a field, then L is a simple E-module of dimension n! .

Proof : Write S_{σ} = Δ_{σ}T, for all σ ∈ Σ. Let R be an essential relation on X. Then Δ_{τ} ⊆ R for some τ ∈ Σ by Theorem 3.2. Therefore Δ ⊆ Δ_{τ^{−1}}R and this implies that

S_{σ} = ΔS_{σ} ⊆ Δ_{τ^{−1}}RS_{σ}  and  T = Δ_{σ^{−1}}S_{σ} ⊆ Δ_{σ^{−1}}Δ_{τ^{−1}}RS_{σ} .

If this containment is strict, then Δ_{σ^{−1}}Δ_{τ^{−1}}RS_{σ} is inessential (by Proposition 2.5) and so RS_{σ} is inessential too (by Lemma 3.1). Otherwise S_{σ} = Δ_{τ^{−1}}RS_{σ}, hence RS_{σ} = Δ_{τ} S_{σ} = Δ_{τσ}T = S_{τσ}. Therefore, in the algebra E, either RS_{σ} = 0 or RS_{σ} = S_{τσ}. This proves that L is a left ideal of E.

Clearly L has rank n! with basis {S_{σ} | σ ∈ Σ}. The action of E on L induces a k-algebra map

ϕ : E ⟶ M_{n!}(k)

and L can be viewed as an M_{n!}(k)-module (consisting of column vectors with entries in k). By Lemma 4.2, the action of Δ_{τ} T Δ_{ρ^{−1}} on basis elements is given by

(Δ_{τ} T Δ_{ρ^{−1}}) · S_{σ} = (Δ_{τ} T Δ_{ρ^{−1}}) · Δ_{σ}T = \{ \begin{matrix}0 & if ρ ≠ σ , \\ S_{τ} & if ρ = σ . \end{matrix}

This means that ϕ(Δ_{τ} T Δ_{ρ^{−1}}) is the elementary matrix with a single nonzero entry 1 in position (τ, ρ). Therefore the map ϕ is surjective. This implies that, if k is a field, the module L is simple as an E-module, because the space of column vectors is a simple M_{n!}(k)-module.

5. A nilpotent ideal

The purpose of this section is to construct a suitable nilpotent ideal N of the essential algebra E. We shall later pass to the quotient by N and describe the quotient E/N. In order to find nilpotent ideals, the following well-known result is often useful.

5.1. Lemma. Let k be a commutative ring and let B be a k-algebra which is finitely generated as a k-module. Let I be a two-sided ideal of B which is k-linearly spanned by a set of nilpotent elements of B.

(a) If k is a field, then I is a nilpotent ideal of B.

(b) If k = ℤ and if B is a finitely generated free ℤ-module, then I is a nilpotent ideal of B.

(c) Suppose that B is defined over ℤ, that is, B ≅ k⊗_{ℤ}B_{ℤ} for some ℤ-algebra B_{ℤ} which is finitely generated free as a ℤ-module. Suppose that I is defined over ℤ, that is, I ≅ k ⊗_{ℤ} I_{ℤ}, where I_{ℤ} is a two-sided ideal of B_{ℤ} which is ℤlinearly spanned by a set of nilpotent elements of B_{ℤ}. Then I is a nilpotent ideal of B.

Proof : (a) The assumption still holds after extending scalars to an algebraic closure of k. Therefore we can assume that k is algebraically closed. Let J(B) be the Jacobson radical of B. Then J(B) = ⋂_{i=1}^{r} M_{i}, where M_{i} is a maximal two-sided ideal of B. Moreover, by Wedderburn’s theorem, B/M_{i} is isomorphic to a matrix algebra M_{n_{i}}(k), because k is algebraically closed. We will show that I ⊆ M_{i}, for all i = 1, …, r. It then follows that I ⊆ J(B), so I is nilpotent (because it is well-known that the Jacobson radical of a finite-dimensional k-algebra is nilpotent).

Let \overline{I} be the image of I in B/M_{i}. Then \overline{I} is spanned by nilpotent elements of M_{n_{i}}(k). But any nilpotent matrix has trace zero (because its characteristic polynomial is X^{n_{i}} and the coefficient of X^{n_{i}−1} is the trace, up to sign). It follows that \overline{I} is contained in Ker(tr), which is a proper subspace of M_{n_{i}}(k). Now \overline{I} is a two-sided proper ideal of the simple algebra M_{n_{i}}(k), hence \overline{I} = \{0\}, proving that I ⊆ M_{i}.

(b) Let F be a basis of B as a ℤ-module. Extending scalars to ℚ, we see that F is a ℚ-basis of the ℚ-algebra ℚ ⊗_{ℤ} B and B embeds in ℚ ⊗_{ℤ} B. By part (a), the ideal ℚ ⊗_{ℤ} I is nilpotent in ℚ ⊗_{ℤ} B. Since I embeds in ℚ ⊗_{ℤ} I, it follows that I is nilpotent.

(c) By part (b), I_{ℤ} is a nilpotent ideal of B_{ℤ}. Extending scalars to k, we see that I is a nilpotent ideal of B.

Recall that Σ denotes the symmetric group on X and that, if R is a reflexive relation, then \overline{R} denotes the transitive closure of R.

5.2. Lemma. If S = Δ_{τ^{−1}}RΔ_{τ} where τ ∈ Σ and R is a reflexive relation, then \overline{S} = Δ_{τ^{−1}} \overline{R}Δ_{τ}.

Proof : We have \overline{R} = R^{m} for some m and we obtain

S^{m} = (Δ_{τ^{−1}}RΔ_{τ})^{m} = Δ_{τ^{−1}}R^{m}Δ_{τ} = Δ_{τ^{−1}} \overline{R}Δ_{τ} .

Therefore S^{m} is a preorder, because it is conjugate to a preorder, and so \overline{S} = S^{m} = Δ_{τ^{−1}} \overline{R}Δ_{τ}.

5.3. Theorem. Let F be the set of all reflexive essential relations on X. Let N be the k-submodule of the essential algebra E generated by all elements of the form (S − \overline{S})Δ_{σ} with S ∈ F and σ ∈ Σ (where \overline{S} denotes the transitive closure of S).

(a) N is a nilpotent two-sided ideal of E. In particular, N is contained in the Jacobson radical J(E).

(b) The quotient algebra P = E/N has a k-basis consisting of all elements of the form SΔ_{σ}, where S runs over the set of all orders on X and σ runs over the symmetric group Σ.

Proof : (a) Let E_{1} be the subalgebra of E which is k-linearly generated by the set F of all reflexive essential relations. It is clearly a subalgebra since the product of two reflexive relations is reflexive. Let N_{1} be the k-submodule of E_{1} generated by all elements of the form S − \overline{S} with S ∈ F. We claim that N_{1} is a two-sided ideal of E_{1}.

If T ∈ F, then \overline{T \overline{S}} = \overline{T S} (because \overline{T S} contains both T and \overline{S}, hence \overline{T \overline{S}}, and \overline{T \overline{S}} contains both T and S, hence \overline{T S}). Therefore

T (S − \overline{S}) = (T S − \overline{T S}) − (T \overline{S} − \overline{T S}) = (T S − \overline{T S}) − (T \overline{S} − \overline{T \overline{S}}) .

Note that if T S is inessential (hence zero in E_{1}), then its transitive closure \overline{T S} cannot be an order by Proposition 2.5 and is therefore also zero in E_{1} (again by Proposition 2.5). Thus, in the expression above, we obtain either generators of N_{1} or zero. The same argument works for right multiplication by T (or use the antiautomorphism of E) and this proves the claim.

The ideal N_{1} is invariant under conjugation by Σ because, for every σ ∈ Σ,

Δ_{σ^{−1}}(S − \overline{S})Δ_{σ} = Δ_{σ^{−1}}SΔ_{σ} − Δ_{σ^{−1}} \overline{S}Δ_{σ} = Δ_{σ^{−1}}SΔ_{σ} − \overline{Δ_{σ^{−1}}SΔ_{σ}}

by Lemma 5.2. Therefore the generators of N can also be written Δ_{σ}(S′ − \overline{S′}) with S′ ∈ F and σ ∈ Σ (namely S′ = Δ_{σ^{−1}}SΔ_{σ}). It follows that N = N_{1}Δ_{Σ} = Δ_{Σ}N_{1}, where we write for simplicity Δ_{Σ} = {Δ_{σ} | σ ∈ Σ}.

If R is an essential relation on X, then R contains a permutation Δ_{σ} (for some σ ∈ Σ) by Theorem 3.2, so R = QΔ_{σ} with Q ∈ F, and also R = Δ_{σ}Q′ where Q′ = Δ_{σ^{−1}}QΔ_{σ}. Since N_{1} is an ideal of E_{1}, it follows that N is invariant by right and left multiplication by R. Thus N is a two-sided ideal of E.

The generators of N_{1} are nilpotent, because if \overline{S} = S^{m}, then

\begin{matrix}(S − \overline{S})^{m} = (S − S^{m})^{m} = & ∑_{j=0}^{m} \binom{m}{j}(−1)^{j}S^{m−j}S^{mj} \\ = & ( ∑_{j=0}^{m} \binom{m}{j}(−1)^{j})S^{m} = (1 − 1)^{m}S^{m} = 0 . \end{matrix}

Thus N_{1} is a nilpotent ideal of E_{1}, by Lemma 5.1 (because clearly E_{1} and N_{1} are defined over ℤ). Since N_{1} is invariant under conjugation by Σ, we obtain N^{n} = (N_{1}Δ_{Σ})^{n} = N_{1}^{n}Δ_{Σ} for every n ∈ ℕ. Since N_{1}^{m} = 0 for some m, the ideal N is nilpotent.

(b) In the quotient algebra E/N, any reflexive relation Q is identified with its transitive closure \overline{Q}. Moreover, by Theorem 3.2, any essential relation R on X can be written R = QΔ_{σ}, with Q reflexive, and QΔ_{σ} is identified with \overline{Q}Δ_{σ} in the quotient algebra E/N. Note that \overline{Q} is a preorder and that \overline{Q} is zero in E if it is not an order, by Proposition 2.5.

On each basis element R of E, the effect of passing to the quotient by N consists of just two possibilities.

• If R can be written R = QΔ_{σ}, with Q reflexive and \overline{Q} is not an order, then R is identified with \overline{Q}Δ_{σ}, so R is zero in E/N because \overline{Q} is zero.

• If R can be written R = QΔ_{σ}, with Q reflexive and \overline{Q} is an order, then R is identified with an element of the form SΔ_{σ} where S is an order (namely S = \overline{Q}).

In the second case, Δ_{σ} is the unique permutation contained in R (or in other words the expression R = QΔ_{σ} is the unique decomposition of R as a product of a reflexive relation and a permutation). This is because if Δ_{σ′} ⊆ R, we obtain

Δ_{σ′σ^{−1}} = Δ_{σ′}Δ_{σ^{−1}} ⊆ RΔ_{σ^{−1}} = Q ⊆ \overline{Q} ,

so that σ′σ^{−1} = id since \overline{Q} is an order (Lemma 3.4). Thus σ′ = σ. This uniqueness property shows, on the one hand, that both possibilities cannot occur simultaneously and, on the other hand, that in the second case the order S = \overline{Q} is uniquely determined by R.

It follows that the nonzero images in E/N of the basis elements of E form a k-basis of E/N consisting of (the images of) the elements SΔ_{σ}, where S is an order and σ ∈ Σ.

The quotient algebra P = E/N will be called the algebra of permuted orders on X, because every basis element SΔ_{σ} is obtained from the order S by applying a permutation σ to the rows of S. Moreover, Δ_{σ} is the unique permutation contained in SΔ_{σ}, because Δ is the unique permutation contained in S by Lemma 3.4. This defines a Σ-grading on P :

P = ⨁_{σ∈Σ} P_{σ} ,

where P_{σ} is spanned by the set of all permuted orders containing Δ_{σ}. Clearly P_{σ} · P_{τ} = P_{στ}, so we have indeed a Σ-grading. We also write P_{1} := P_{id} and call it the algebra of orders on X. Moreover, P_{σ} = Δ_{σ}P_{1} = P_{1}Δ_{σ}, so that the product in P is completely determined by the product in the subalgebra P_{1} and the product in the symmetric group Σ. Hence we first need to understand the subalgebra P_{1}.

6. The algebra of orders

Let P_{1} be the algebra of orders on X defined above. It has a k-basis O consisting of all orders on X. The product of basis elements R, S ∈ O will be written R · S and is described as follows.

6.1. Lemma. Let · be the product in the k-algebra P_{1}.

(a) Let R, S ∈ O. Then the product R · S is equal to the transitive closure of R ∪ S if this closure is an order, and zero otherwise.

(b) The product · is commutative.

Proof : (a) By definition of the ideal N, the product RS in the algebra P = E/N is identified with the transitive closure \overline{RS}, which is also the transitive closure of R ∪ S, because the inclusions

R ∪ S ⊆ RS ⊆ (R ∪ S)^{2} ⊆ \overline{R ∪ S} ⊆ \overline{RS}

force the equality \overline{R ∪ S} = \overline{RS}. Now \overline{RS} is a preorder. If this is an order, then R·S = \overline{RS}. If this preorder is not an order, then it is zero in E (by Proposition 2.5), hence also zero in P_{1}.

(b) This follows from (a) and the fact that R ∪ S = S ∪ R.

6.2. Theorem.

(a) There exists a k-basis {f_{R} | R ∈ O} of P_{1}, consisting of mutually orthogonal idempotents whose sum is 1, and such that, for every R ∈ O, the ideal generated by f_{R} is free of rank one as a k-module.

(b) P_{1} is isomorphic to a product of copies of k, indexed by O :

P_{1} ≅ ∏_{R∈O} k·f_{R} .

Proof : We know that P_{1} is commutative, with a basis O consisting of all orders on X. Any such basis element is idempotent. Moreover O is a partially ordered set with respect to the containment relation and we make it a lattice by adding an element ∞ and defining R ∨ S = ∞ whenever the transitive closure of R ∪ S is not an order, while R ∨ S is the transitive closure of R ∪ S otherwise. The greatest lower bound of R and S is just the intersection R ∩ S.

Now define g_{R} = R if R ∈ O and g_{∞} = 0. By Lemma 6.1, these elements satisfy the condition g_{R} · g_{S} = g_{R∨S}. Therefore Theorem 10.1 of the appendix applies. We let

f_{R} = ∑_{{S∈O \atop R⊆S}} μ(R, S)S ,

where μ denotes the Möbius function of the poset O, so by Möbius inversion, we have

R = ∑_{{S∈O \atop R⊆S}} f_{S} .

The transition matrix from {R ∈ O} to {f_{R} | R ∈ O} is upper-triangular, with 1 along the main diagonal, hence invertible over ℤ. It follows that {f_{R} | R ∈ O} is a k-basis of P_{1}. By Theorem 10.1 of the appendix, {f_{R} | R ∈ O} is a set of mutually orthogonal idempotents in P_{1} whose sum is 1. Moreover, by the same theorem,

f_{R} · T = \{ \begin{matrix}f_{R} & if T ⊆ R , \\ 0 & if T ⊈ R . \end{matrix}

Since T runs over a k-basis of P_{1}, this proves that the ideal P_{1}f_{R} generated by f_{R} is equal to the rank one submodule k·f_{R} spanned by f_{R}. Thus we obtain

P_{1} ≅ ∏_{R∈O} P_{1}f_{R} = ∏_{R∈O} k·f_{R} ,

as was to be shown.

Note that if k is a field, then each idempotent f_{R} is primitive.

7. The algebra of permuted orders

We know from the end Section 5 that the algebra P of permuted orders is Σ-graded

P = ⨁_{σ∈Σ} P_{σ} .

If R, S ∈ O and σ, τ ∈ Σ, then the product in P satisfies

(RΔ_{σ})(SΔ_{τ}) = (R · (Δ_{σ}SΔ_{σ^{−1}}))Δ_{σ}Δ_{τ} = (R · (Δ_{σ}SΔ_{σ^{−1}}))Δ_{στ} ,

where · denotes the product in P_{1} described in Lemma 6.1 . Note that this definition makes sense because Δ_{σ}SΔ_{σ^{−1}} is an order, since S is. Note also that we can write the basis elements as Δ_{σ}S with S ∈ O, because RΔ_{σ} = Δ_{σ}(Δ_{σ^{−1}}RΔ_{σ}) and Δ_{σ^{−1}}RΔ_{σ} ∈ O.

Instead of O, we can use the basis {f_{R} | R ∈ O} of P_{1}, consisting of the idempotents of P_{1} defined in Theorem 6.2. The group Σ acts by conjugation on the set O of all orders, hence also on the set {f_{R} | R ∈ O}. We first record the following easy observation.

7.1. Lemma. Let R be an order and let f_{R} be the corresponding idempotent of P_{1}. For every σ ∈ Σ,

Δ_{σ}f_{R}Δ_{σ^{−1}} = f_{^{σ}R} ,

where ^{σ}R := Δ_{σ}RΔ_{σ^{−1}}.

Proof : This follows immediately from the definition of f_{R} in Section 6.

Since P = ⨁_{σ∈Σ} P_{σ}, this has a k-basis {Δ_{σ}f_{R} | σ ∈ Σ , R ∈ O}. We now describe the product in P with respect to this basis.

7.2. Lemma. The product of basis elements of P is given by :

(Δ_{τ} f_{S})(Δ_{σ}f_{R}) = \{ \begin{matrix}0 & if S ≠ ^{σ}R , \\ Δ_{τσ}f_{R} & if S = ^{σ}R , \end{matrix}

for all S, R ∈ O and all τ, σ ∈ Σ.

Proof : (Δ_{τ} f_{S})(Δ_{σ}f_{R}) = Δ_{τ} f_{S}f_{^{σ}R}Δ_{σ}. This is zero if S ≠ ^{σ}R. Otherwise we obtain Δ_{τ} f_{^{σ}R}Δ_{σ} = Δ_{τ} Δ_{σ}f_{R} = Δ_{τσ}f_{R}.

7.3. Corollary. Let R be an order and let f_{R} be the corresponding idempotent of P_{1}. The left ideal Pf_{R} has a k-basis {Δ_{σ}f_{R} | σ ∈ Σ}.

Proof : We have (Δ_{τ} f_{S})f_{R} = \{ \begin{matrix}0 & if S ≠ ^{σ}R , \\ Δ_{τ} f_{R} & if S = ^{σ}R , \end{matrix} and we know that the set

{Δ_{σ}f_{R} | σ ∈ Σ} is part of the basis of P.

Now we introduce central idempotents in P. Let R be an order, let Σ_{R} be the stabilizer of R in Σ, and denote by [Σ/Σ_{R}] a set of coset representatives. By Lemma 7.1, Σ_{R} is also the stabilizer of f_{R} and we define

e_{R} = ∑_{σ∈[Σ/Σ_{R}]} Δ_{σ}f_{R}Δ_{σ^{−1}} = ∑_{σ∈[Σ/Σ_{R}]} f_{^{σ}R} ,

the sum of the Σ-orbit of f_{R}.

7.4. Lemma. Let [Σ\O] be a set of representatives of the Σ-orbits in O. The set {e_{R} | R ∈ [Σ\O]} is a set of orthogonal central idempotents of P, whose sum is 1_{P} = Δ.

Proof : We compute

Δ_{τ} f_{S} e_{R} = ∑_{σ∈[Σ/Σ_{R}]}Δ_{τ} f_{S} f_{^{σ}R} = \{ \begin{matrix}0 & if S does not belong to the orbit of R , \\ Δ_{τ} f_{S} & if S = ^{σ}R . \end{matrix}

On the other hand

e_{R} Δ_{τ} f_{S} = ∑_{σ∈[Σ/Σ_{R}]} f_{^{σ}R} Δ_{τ} f_{S} = ∑_{σ∈[Σ/Σ_{R}]} f_{^{σ}R} f_{^{τ}S} Δ_{τ} .

This is zero if ^{τ}S does not belong to the Σ-orbit of ^{σ}R, that is, if S does not belong to the Σ-orbit of R, while if ^{τ}S = ^{σ}R, then we get f_{^{τ}S} Δ_{τ} = Δ_{τ} f_{S}. This shows that e_{R} is central.

We know that {f_{R} | R ∈ O} is a set of orthogonal idempotents with sum 1. Since we have just grouped together the Σ-orbits, it is clear that the set {e_{R} | R ∈ [Σ\O]} is also a set of orthogonal idempotents of P, whose sum is 1_{P} = Δ.

It follows from Lemma 7.4 that P ≅ ∏_{R∈[Σ\O]} Pe_{R} and we have to understand the structure of each term.

7.5. Theorem. Let R be an order on X and let Σ_{R} be its stabilizer in Σ. Then

Pe_{R} ≅ M_{|Σ:Σ_{R}|}(kΣ_{R}) ,

a matrix algebra of size |Σ : Σ_{R}| on the group algebra kΣ_{R}. In other words

P ≅ ∏_{R∈[Σ\O]} M_{|Σ:Σ_{R}|}(kΣ_{R}) .

Proof : By Corollary 7.3, the left ideal Pf_{R} is a free k-submodule of P spanned by the set {Δ_{σ}f_{R} | σ ∈ Σ}. The group Σ_{R} acts on the right on this set, because f_{R}Δ_{h} = Δ_{h}f_{R} for every h ∈ Σ_{R}. It follows that Pf_{R} is a free right kΣ_{R}-module with basis {Δ_{σ}f_{R} | σ ∈ [Σ/Σ_{R}]}.

Clearly, the left action of P commutes with the right action of kΣ_{R}. The left action of P on this free right kΣ_{R}-module induces a k-algebra map

ϕ_{R} : P ⟶ M_{|Σ:Σ_{R}|}(kΣ_{R}) .

By Lemma 7.2, e_{R} acts as the identity on Pf_{R}, while e_{S} acts by zero if S does not belong to the Σ-orbit of R. Therefore we get a k-algebra map

ϕ_{R} : Pe_{R} ⟶ M_{|Σ:Σ_{R}|}(kΣ_{R}) ,

because ϕ_{R}(e_{S}) = 0 whenever S does not belong to the Σ-orbit of R. Putting all these maps together, we obtain a k-algebra map

ϕ = ∏_{R∈[Σ\O]} ϕ_{R} : P ⟶ ∏_{R∈[Σ\O]} M_{|Σ:Σ_{R}|}(kΣ_{R}) .

Lemma 7.2 shows that, if ρ, σ, τ ∈ [Σ/Σ_{R}] and g ∈ Σ_{R}, we have

(Δ_{τ} f_{R}Δ_{g}Δ_{ρ^{−1}}) · Δ_{σ}f_{R} = \{ \begin{matrix}0 & if ρ ≠ σ , \\ Δ_{τ} f_{R}Δ_{g} & if ρ = σ , \end{matrix}

using the fact that f_{R}Δ_{g} = Δ_{g}f_{R}. This means that ϕ_{R}(Δ_{τ} f_{R}Δ_{g}Δ_{ρ^{−1}}) is the elementary matrix with a single nonzero entry equal to Δ_{g} in position (τ, ρ). Moreover, we also have ϕ_{S}(Δ_{τ} f_{R}Δ_{g}Δ_{ρ^{−1}}) = 0 whenever S does not belong to the Σ-orbit of R. Therefore the map ϕ is surjective.

Finally, we prove that ϕ is an isomorphism. It suffices to do this in the case where k = ℤ, because all the algebras are defined over ℤ (that is, they are obtained by extending scalars from ℤ to k) and the algebra map ϕ is also defined over ℤ. Now if k = ℤ, then all algebras under consideration are finitely generated free ℤmodules and we know that the map ϕ is surjective. So it suffices to show that the source and the target of ϕ have the same rank as ℤ-modules. The rank of P is |Σ| Card(O). On the other hand,

rank(M_{|Σ:Σ_{R}|}(kΣ_{R})) = |Σ : Σ_{R}|^{2}|Σ_{R}| = |Σ : Σ_{R}| |Σ| .

Summing over R ∈ [Σ\O], we obtain

∑_{R∈[Σ\O]} |Σ : Σ_{R}| |Σ| = |Σ| ∑_{R∈[Σ\O]} Card(orbit of R) = |Σ| Card(O) ,

as was to be shown.

7.6. Remark. Since a matrix algebra M_{r}(A) is Morita equivalent to A (for any k-algebra A), it follows from Theorem 7.5 that the algebra P is Morita equivalent to a product of group algebras, namely B = ∏_{R∈[Σ\O]} kΣ_{R}. The bimodule which provides the Morita equivalence is M = ⨁_{R∈[Σ\O]} Pf_{R}, which is clearly a left P-module by left multiplication, and a right module for each group algebra kΣ_{R}, acting by right multiplication on the summand Pf_{R}, and acting by zero on the other summands Pf_{S}, where S ≠ R in [Σ\O]. Notice that Pf_{R} is the bimodule appearing in the proof of Theorem 7.5.

The bimodule inducing the inverse Morita equivalence is M^{∨} = ⨁_{R∈[Σ\O]} f_{R}P. Indeed we, obtain

M ⊗_{B} M^{∨} ≅ ⨁_{S∈[Σ\O]} ⨁_{R∈[Σ\O]} Pf_{S}f_{R}P = ⨁_{R∈[Σ\O]} Pf_{R}P = P

and on the other hand

\begin{matrix}M^{∨} ⊗_{P} M ≅ & ⨁_{S∈[Σ\O]} ⨁_{R∈[Σ\O]} f_{S}Pf_{R} = ⨁_{R∈[Σ\O]} f_{R}Pf_{R} \\ = & ⨁_{R∈[Σ\O]} kΣ_{R}·f_{R} ≅ ⨁_{R∈[Σ\O]} kΣ_{R} = B . \end{matrix}

Each module Pf_{R} has rank |Σ|, because it has a k-basis {Δ_{σ}f_{R} | σ ∈ Σ}, but we view it as a free right kΣ_{R}-module of rank |Σ : Σ_{R}|.

8. Simple modules for the essential algebra

By standard commutative algebra, any simple E-module is actually a module over k/m ⊗_{k} E, where m is a maximal ideal of k. Replacing k by the quotient k/m, we assume from now on that k is a field. Let E be the essential algebra of Section 5 and let P = E/N be the algebra of permuted orders. Since N is a nilpotent ideal and since nilpotent ideals act by zero on simple modules, any simple E-module can be viewed as a simple P-module. So we work with P and we wish to describe all simple left P-modules.

There is a general procedure for constructing all simple modules for the algebra of a semigroup S, using equivalence classes of maximal subgroups of S, see Theorem 5.33 in [CP], or Section 3 of [HK] for a short presentation. But our previous results allow for a very direct and easy approach, so we do not need to follow the method of [CP].

First notice that the simple P_{1}-modules are easy to describe, because P_{1} is a product of copies of k (by Theorem 6.2). More precisely, P_{1} ≅ ∏_{R∈O} k · f_{R} and each one-dimensional space k ·f_{R} is a simple P_{1}-module (where R runs through the set O of all orders).

8.1. Theorem. Assume that k is a field. Let W be the set of all pairs (R, V), where R is an order on X and V is a simple kΣ_{R}-module up to isomorphism. The group Σ acts on W via ^{σ}(R, V) := (^{σ}R, ^{σ}V), where ^{σ}R = Δ_{σ}RΔ_{σ^{−1}} and ^{σ}V is the conjugate module, a module for the group algebra kΣ_{^{σ}R} = k[σΣ_{R} σ^{−1}].

(a) The set of isomorphism classes of simple P-modules is parametrized by the set Σ\W of Σ-conjugacy classes of pairs (R, V) ∈ W.

(b) The simple module corresponding to (R, V) under the parametrization of

part (a) is

S_{R,V} = W_{R} ⊗_{k} V ,

where W_{R} is the unique (up to isomorphism) simple module for the matrix algebra M_{|Σ:Σ_{R}|}(k) and W_{R} ⊗ V is viewed as a module for the algebra

M_{|Σ:Σ_{R}|}(k) ⊗_{k} kΣ_{R} ≅ M_{|Σ:Σ_{R}|}(kΣ_{R}) ,

which is one of the factors of the decomposition of P in Theorem 7.5.

(c) The simple P-module S_{R,V} is also isomorphic to Pf_{R} ⊗_{kΣ_{R}} V, with its natural structure of P-module under left multiplication.

(d) The simple P-module S_{R,V} has dimension |Σ : Σ_{R}| · dim(V).

Proof : By Theorem 7.5, any simple P-module is a simple module for one of the factors M_{|Σ:Σ_{R}|}(kΣ_{R}), where R belongs to a set [Σ\O] of representatives of Σ-orbits in O. In view of the isomorphism

M_{|Σ:Σ_{R}|}(kΣ_{R}) ≅ M_{|Σ:Σ_{R}|}(k) ⊗_{k} kΣ_{R} ,

any such simple module is isomorphic to a tensor product W_{R} ⊗_{k} V as in the statement. This proves (a) and (b).

By Theorem 7.5, Pe_{R} ≅ M_{|Σ:Σ_{R}|}(kΣ_{R}) and its identity element e_{R} decomposes as a sum of orthogonal idempotents e_{R} = ∑_{σ∈[Σ/Σ_{R}]} f_{^{σ}R}. Cutting by the idempotent f_{R}, we obtain the left ideal Pf_{R}, which is a free right kΣ_{R}-module, isomorphic to the space of column vectors with coefficients in kΣ_{R}. Now Pf_{R} is the bimodule providing the Morita equivalence between M_{|Σ:Σ_{R}|}(kΣ_{R}) and kΣ_{R} (see Remark 7.6). Therefore, for any simple left kΣ_{R}-module V, the corresponding simple module for Pe_{R} ≅ M_{|Σ:Σ_{R}|}(kΣ_{R}) is the left P-module Pf_{R} ⊗_{kΣ_{R}} V. Since Pf_{R} is the space of column vectors with coefficients in kΣ_{R}, while W_{R} is the space of column vectors with coefficients in k, we get Pf_{R} ≅ W_{R} ⊗_{k} kΣ_{R}. Therefore our simple P-module is

Pf_{R} ⊗_{kΣ_{R}} V ≅ W_{R} ⊗_{k} kΣ_{R} ⊗_{kΣ_{R}} V ≅ W_{R} ⊗_{k} V ≅ S_{R,V} ,

proving (c).

Finally, the dimension is

dim(S_{R,V}) = dim(W_{R} ⊗_{k} V) = dim(W_{R}) · dim(V) = |Σ : Σ_{R}| · dim(V) ,

proving (d).

8.2. Example. Consider the trivial order Δ. Then Σ_{Δ} = Σ and the matrix algebra reduces to

M_{|Σ:Σ_{Δ}|}(kΣ_{Δ}) ≅ M_{1}(k) ⊗_{k} kΣ ≅ kΣ .

The simple module W_{Δ} for the algebra M_{1}(k) is just k and the simple module S_{Δ,V} = W_{Δ} ⊗_{k} V ≅ V is just a simple kΣ-module. In that case, the central idempotent e_{S} of P acts by zero on V for any order S ≠ Δ, hence f_{S} too (because f_{S} e_{S} = f_{S}). Then R = ∑_{R⊆S} f_{S} also acts by zero for any order R ≠ Δ. For any essential reflexive relation Q with Q ≠ Δ, the action of Q is equal to the action of \overline{Q} (because Q − \overline{Q} belongs to the nilpotent ideal N), and therefore Q also acts by zero on V. Then so does the action of the essential relation Δ_{σ}Q containing the permutation Δ_{σ}. This shows that the simple modules S_{Δ,V} ≅ V are just the modules for kΣ viewed as a quotient algebra as in Lemma 4.1.

8.3. Example. Consider a total order T. Then Σ_{T} = {id} and the matrix algebra reduces to

M_{|Σ:Σ_{T} |}(kΣ_{T}) ≅ M_{n!}(k) ⊗_{k} k ≅ M_{n!}(k) .

In that case, there is unique simple kΣ_{T} -module, namely V = k, the trivial module for the trivial group. We obtain the single simple module S_{T,k} = W_{T} ⊗_{k} k ≅ W_{T} for the algebra M_{n!}(k). Equivalently, with the approach of part (c) of Theorem 8.1, we have f_{T} = T (by maximality of T in O) and so

S_{T,k} = Pf_{T} ⊗_{kΣ_{T}} V = PT ⊗_{k} k ≅ PT .

So we obtain just the left ideal Pf_{T} = PT, which turns out to be simple in that case. But it is also the left ideal L appearing in Proposition 4.3. So we have recovered the simple module of Proposition 4.3.

We also mention another byproduct of Theorem 7.5.

8.4. Theorem. If the characteristic of the field k is zero or > n, then P is a semi-simple k-algebra.

Proof : It suffices to see that each factor in the decomposition of Theorem 7.5 is semi-simple. Now we have the isomorphism

M_{|Σ:Σ_{R}|}(kΣ_{R}) ≅ M_{|Σ:Σ_{R}|}(k) ⊗_{k} kΣ_{R} ,

and M_{|Σ:Σ_{R}|}(k) is a simple algebra. Moreover the group algebra kΣ_{R} is semi-simple by Maschke’s theorem, because the characteristic of k does not divide the order of the group Σ_{R}, by assumption. The result follows.

Every simple P-module S_{R,V} is a simple R-module, because of the successive quotients R → E → P. We now give a direct description of the action on S_{R,V} of an arbitrary relation in R. Since S_{R,V} ≅ Pf_{R} ⊗_{kΣ_{R}} V, it suffices to describe the action on Pf_{R}, and for this we can work again with an arbitrary commutative base ring k. Recall that Pf_{R} has a basis {Δ_{σ}f_{R} | σ ∈ Σ}.

8.5. Proposition. Let k be a commutative ring. Let R be an order on X and let Q be an arbitrary relation (in the k-algebra R). The action of Q on Pf_{R} is described on the basis elements as follows :

Q · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{τσ}f_{R} & if ∃ τ ∈ Σ such that Δ ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

Proof : Suppose first that S is an order. By Lemma 7.2, the action of f_{S} is given by

f_{S} · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{σ}f_{R} & if S = ^{σ}R , \\ 0 & otherwise . \end{matrix}

Now S = ∑_{{T ∈O \atop S⊆T}} f_{T} and the action of f_{T} is nonzero only if T = ^{σ}R. So we obtain the

action of S as follows :

S · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{σ}f_{R} & if S ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

Next we suppose that S is reflexive and that its transitive closure \overline{S} is an order. Since S−\overline{S} belongs to the nilpotent ideal N of Section 5, which acts by zero because P = E/N, the action of S coincides with the action of \overline{S}. Moreover, the condition \overline{S} ⊆ ^{σ}R is equivalent to S ⊆ ^{σ}R, because ^{σ}R is transitive. Therefore the action of S is the following :

S · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{σ}f_{R} & if S ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

Now suppose that S is reflexive and that \overline{S} is not an order. Then \overline{S} is inessential by Proposition 2.5, hence zero in E. So \overline{S} acts by zero, and since S − \overline{S} acts by zero, the action of S is also zero. On the other hand, S cannot be contained in σR, otherwise \overline{S} ⊆ ^{σ}R, which would force \overline{S} to be an order since ^{σ}R is an order. Therefore the condition S ⊆ ^{σ}R is never satisfied in that case. So the previous formula still holds, because we have zero on both sides :

S · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{σ}f_{R} & if S ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

Now suppose that Q contains a permutation Δ_{τ}. Then S = Δ_{τ^{−1}}Q is reflexive and Q = Δ_{τ} S. Thus the action of Q is :

Q · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{τ} Δ_{σ}f_{R} & if S ⊆ ^{σ}R , \\ 0 & otherwise , \end{matrix}

= \{ \begin{matrix}Δ_{τσ}f_{R} & if Δ_{τ^{−1}}Q ⊆ ^{σ}R , \\ 0 & otherwise , \end{matrix}

= \{ \begin{matrix}Δ_{τσ}f_{R} & if Δ ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

The last equality holds because the condition Δ_{τ^{−1}}Q ⊆ ^{σ}R is equivalent to Δ ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R, since S = Δ_{τ^{−1}}Q is reflexive. This proves the result for such a relation Q.

Finally if Q does not contain a permutation, then Q is inessential by Theorem 3.2, hence acts by zero. On the other hand the condition that there exists τ ∈ Σ such that Δ ⊆ Δ_{τ^{−1}}Q cannot be satisfied since Q does not contain a permutation. Therefore the previous formula still holds, because we have zero on both sides :

Q · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{τσ}f_{R} & if Δ ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R , \\ 0 & otherwise . \end{matrix}

This proves the result in all cases.

8.6. Remark. In the description of the algebra P (Theorem 7.5) and in the description of its simple modules (Theorem 8.1), we may wonder which groups appear as Σ_{R} for some order R. The answer is that the group Σ_{R} is arbitrary. More precisely, by a theorem of Birkhoff [Bi] (and further improvements by Thornton [Tho] and Barmak–Minian [BaM]), any finite group is isomorphic to Σ_{R} for some order R on a suitable finite set X. However, for a given finite set X, it is not clear which isomorphism classes of groups Σ_{R} appear.

Another question is to determine whether or not the simple modules of Theorem 8.1 are absolutely simple. But again this depends on the group Σ_{R}, because the field k may or may not be a splitting field for the group algebra kΣ_{R}.

9. A branching rule

In this section, we let X = {1, …, n} for simplicity. In order to let n vary, we use a superscript (n) for all objects depending on n, such as X^{(n)} for the set X, Σ^{(n)} for the symmetric group on X^{(n)}, O^{(n)} for the set of all orders on X^{(n)}, P_{1}^{(n)} for the algebra of orders on X^{(n)}, P^{(n)} for the algebra of permuted orders on X^{(n)}, etc.

In the representation theory of the symmetric group Σ^{(n)}, there are well-known branching rules, describing the restriction of simple modules to the subgroup Σ^{(n−1)} of all permutations of X^{(n−1)}, and the induction of simple modules from Σ^{(n−1)} to Σ^{(n)}. In a similar fashion, working again over an arbitrary commutative base ring k, we will describe how modules for P^{(n−1)} behave under induction to P^{(n)}. For this we need to view the former as a subalgebra of the latter. We first define

ϕ : P_{1}^{(n−1)} ⟶ P_{1}^{(n)} , ϕ(R) = R ∪ {(n, n)} ,

for any order R on X^{(n−1)}. It is clear that ϕ(R) is an order on X^{(n)}. Since Σ^{(n−1)} is a subgroup of Σ^{(n)} (by fixing the last letter n), the map ϕ clearly extends to an injective algebra homomorphism ϕ : P^{(n−1)} ⟶ P^{(n)}.

Now we want to compute the image under ϕ of the idempotents f_{R}^{(n−1)}. For a given order R on X^{(n−1)}, we define

S_{R} = {S ∈ O^{(n)} | S ∩ (X^{(n−1)} × X^{(n−1)}) = R} .

9.1. Lemma. Let R be an order on X^{(n−1)} and let f_{R}^{(n−1)} be the corresponding idempotent of P_{1}^{(n−1)}.

(a) If S is an order on X^{(n)} and if f_{S}^{(n)} is the corresponding idempotent of P_{1}^{(n)}, then

ϕ(f_{R}^{(n−1)}) · f_{S}^{(n)} = \{ \begin{matrix}f_{S}^{(n)} & if S ∈ S_{R} , \\ 0 & otherwise . \end{matrix}

(b) ϕ(f_{R}^{(n−1)}) = ∑_{S∈S_{R}} f_{S}^{(n)}.

Proof : We have f_{R}^{(n−1)} = ∑_{{Y ∈O^{(n−1)} \atop R⊆Y}} μ(R, Y)Y and ϕ(Y) = Y ∪ \{(n, n)\}. There-

fore, using part (a) of Theorem 10.1, we obtain

ϕ(f_{R}^{(n−1)}) · f_{S}^{(n)} = ∑_{{Y ∈O^{(n−1)} \atop R⊆Y}} μ(R, Y)(Y ∪ \{(n, n)\}) · f_{S}^{(n)}

= ( ∑_{{Y ∈O^{(n−1)} \atop R⊆Y, Y ∪\{(n,n)\}⊆S}} μ(R, Y))f_{S}^{(n)}

= ( ∑_{{Y ∈O^{(n−1)} \atop R⊆Y ⊆S∩(X^{(n−1)}×X^{(n−1)})}} μ(R, Y))f_{S}^{(n)} .

We get zero if R ⊈ S ∩ (X^{(n−1)} × X^{(n−1)}) and also if R ⊂ S ∩ (X^{(n−1)} × X^{(n−1)}) (by the definition of the Möbius function). If now R = S ∩ (X^{(n−1)} × X^{(n−1)}), that is, if S ∈ S_{R}, then the sum reduces to μ(R, R) = 1 and we obtain f_{S}^{(n)}, proving (a).

Now we have

ϕ(f_{R}^{(n−1)}) = ∑_{S∈O^{(n)}} ϕ(f_{R}^{(n−1)}) · f_{S}^{(n)} = ∑_{S∈S_{R}} f_{S}^{(n)} ,

proving (b).

9.2. Theorem. Let R be an order on X^{(n−1)}, let f_{R}^{(n−1)} be the corresponding idempotent of P_{1}^{(n−1)}, and let V be a kΣ_{R}^{(n−1)}-module. Then, inducing to P^{(n)} the P^{(n−1)}-module S_{R,V} = P^{(n−1)}f_{R}^{(n−1)} ⊗_{kΣ_{R}^{(n−1)}} V, we obtain

P^{(n)} ⊗_{P^{(n−1)}}(P^{(n−1)}f_{R}^{(n−1)} ⊗_{kΣ_{R}^{(n−1)}} V )

≅ ⨁_{S∈S_{R}} P^{(n)}f_{S}^{(n)} ⊗_{kΣ_{S}^{(n)}} Ind_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{S}^{(n)}} Res_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{R}^{(n−1)}} V .

Proof : Using Lemma 9.1, we obtain

P^{(n)} ⊗_{P^{(n−1)}}(P^{(n−1)}f_{R}^{(n−1)} ⊗_{kΣ_{R}^{(n−1)}} V )

= P^{(n)}ϕ(f_{R}^{(n−1)}) ⊗_{kΣ_{R}^{(n−1)}} V

≅ ⨁_{S∈S_{R}} P^{(n)}f_{S}^{(n)} ⊗_{kΣ_{R}^{(n−1)}} V

≅ ⨁_{S∈S_{R}} P^{(n)}f_{S}^{(n)} ⊗_{kΣ_{S}^{(n)}} kΣ_{S}^{(n)} ⊗_{k[Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}]} k[Σ_{R}^{(n−1)} ∩ Σ_{S}^{(n)}] ⊗_{kΣ_{R}^{(n−1)}} V

≅ ⨁_{S∈S_{R}} P^{(n)}f_{S}^{(n)} ⊗_{kΣ_{S}^{(n)}} Ind_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{S}^{(n)}} Res_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{R}^{(n−1)}} V ,

proving the result.

Assume for simplicity that the base ring k is a field of characteristic zero and let

V be a simple kΣ_{R}^{(n−1)}-module. The kΣ_{S}^{(n)}-module Ind_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{S}^{(n)}} Res_{Σ_{R}^{(n−1)}∩Σ_{S}^{(n)}}^{Σ_{R}^{(n−1)}} V

is a direct sum of simple modules W, and each W gives rise to a simple P^{(n)}- module P^{(n)}f_{S}^{(n)} ⊗_{kΣ_{S}^{(n)}} W. Moreover, every such simple P^{(n)}-module occurs with multiplicities, appearing for instance whenever we have σ running in a set of representatives of cosets [Σ_{R}^{(n−1)}/Σ_{R}^{(n−1)} ∩ Σ_{S}^{(n)}]. For any such σ, we have ^{σ}S ∈ S_{R} and also ^{σ}V ≅ V, because V is a kΣ_{R}^{(n−1)}-module and σ ∈ Σ_{R}^{(n−1)}. Therefore the corresponding term in the direct sum is

P^{(n)}f_{^{σ}S}^{(n)} ⊗_{kΣ_{R}^{(n−1)}} V ≅ P^{(n)}f_{^{σ}S}^{(n)} ⊗_{kΣ_{R}^{(n−1)}} ^{σ}V ,

but this gives rise to the same simple P^{(n)}-modules as the ones coming from S, by Theorem 8.1. Thus the multiplicity of these simple P^{(n)}-modules is at least |Σ_{R}^{(n−1)}/Σ_{R}^{(n−1)} ∩ Σ_{S}^{(n)}|.

10. Appendix on Möbius inversion

In this appendix, we prove a general result on Möbius inversion involving idempotents in a ring. This was already used by the first author in other contexts (see Section 6.2 of [Bo]) and can be of independent interest.

Let (P, ≤) be a finite lattice. Write 0 for the minimal element of P and write x ∨ y for the least upper bound of x and y in P.

10.1. Theorem. Let P be a finite lattice. Let {g_{x} | x ∈ P } be a family of elements in a ring A such that g_{0} = 1 and g_{x}g_{y} = g_{x∨y} for all x, y ∈ P. For every x ∈ P, define

f_{x} = ∑_{{y∈P \atop x≤y}} μ(x, y)g_{y} ,

where μ denotes the Möbius function of the poset P.

(a) For all x, y ∈ P, we have g_{z}f_{x} = f_{x}g_{z} = \{ \begin{matrix}f_{x} & if z ≤ x , \\ 0 & if z ≰ x . \end{matrix}

(b) The set {f_{x} | x ∈ P } is a set of mutually orthogonal idempotents in P whose sum is 1.

Note that our assumption implies that every g_{x} is idempotent, because x ∨ x = x.

Proof : By Möbius inversion, we have

g_{x} = ∑_{{y∈P \atop x≤y}} f_{y} ,

and in particular 1 = g_{0} = ∑_{y∈P} f_{y}.

Next we compute products. If x, z ∈ P, then

\begin{matrix}f_{x}g_{z} = & ( ∑_{{y∈P \atop x≤y}} μ(x, y)g_{y})g_{z} = ∑_{{y∈P \atop x≤y}} μ(x, y) g_{y}g_{z} = ∑_{{y∈P \atop x≤y}} μ(x, y) g_{y∨z} \\ = & ∑_{{w∈P \atop x∨z≤w}} ( ∑_{{y∈P \atop x≤y, y∨z=w}} μ(x, y))g_{w} . \end{matrix}

Note that g_{z}f_{x} = f_{x}g_{z} because g_{z}g_{y} = g_{z∨y} = g_{y∨z} = g_{y}g_{z}. If x is strictly smaller than x ∨ z, then the inner sum runs over the set of all elements y in the interval [x, w] := {v ∈ P | x ≤ v ≤ w} such that y ∨ (x ∨ z) = w. But we have

∑_{{x≤y \atop y∨z=w}} μ(x, y) = ∑_{{x≤y \atop y∨(x∨z)=w}} μ(x, y) = 0 ,

by a well-known property of the Möbius function (Corollary 3.9.3 in [St]). Thus f_{x}g_{z} = 0 if x is strictly smaller than x ∨ z, that is, if z ≰ x.

If now x = x ∨ z, that is, z ≤ x, we get y = y ∨ z (because z ≤ x ≤ y), hence y = w, so that the inner sum has a single term for y = w. In that case, we get

f_{x}g_{z} = ∑_{{w∈P \atop x≤w}} μ(x, w) g_{w} = f_{x} .

Therefore

f_{x}g_{z} = \{ \begin{matrix}f_{x} & if z ≤ x , \\ 0 & if z ≰ x , \end{matrix}

proving (a).

If now x, u ∈ P, then

f_{x}f_{u} = ∑_{{y∈P \atop u≤y}} μ(u, y) f_{x}g_{y} = ∑_{{y∈P \atop u≤y≤x}} μ(u, y) f_{x} .

If u ≰ x, the sum is empty and we get zero. If u < x, then ∑_{u≤y≤x} μ(u, y) = 0 by

the very definition of the Möbius function. This shows that f_{x}f_{u} = 0 if u ≠ x. Finally, if u = x, then we get f_{x}f_{x} = f_{x}, thus f_{x} is idempotent, and the proof is complete.

10.2. Corollary. Let P be a finite lattice. Write t for the maximal element of P and write x ∧ y for the greatest lower bound of x and y in P. Let {g_{x} | x ∈ P } be a family of elements in a ring A such that g_{t} = 1 and g_{x}g_{y} = g_{x∧y} for all x, y ∈ P. For every x ∈ P, define

f_{x} = ∑_{{y∈P \atop y≤x}} μ(y, x)g_{y} ,

where μ denotes the Möbius function of the poset P. Then the set {f_{x} | x ∈ P } is a set of mutually orthogonal idempotents in P whose sum is 1.

Proof : This follows from Theorem 10.1 by using the opposite ordering on P.

References

[BaM] J.A. Barmak, E.G. Minian. Automorphism groups of finite posets, Discrete Math. 309 (2009), 3424–3426.

[Bi] G. Birkhoff. On groups of automorphisms, Rev. Un. Mat. Argentina 11 (1946), 155–157.

[Bo] S. Bouc. Biset functors for finite groups, Springer Lecture Notes in Mathematics no. 1990 (2010).

[BST] S. Bouc, R. Stancu, J. Thévenaz. Simple biset functors and double Burnside ring, J. Pure Appl. Alg. 217 (2013), 546–566.

[CP] A.H. Clifford, G.B. Preston. Algebraic theory of semigroups, Vol. I, Mathematical Surveys 7, American Mathematical Society, Providence, 1961.

[HaM] M. Hall. Combinatorial Theory, John Wiley & Sons, New York, 1986.

[HaP] P. Hall. On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30.

[HK] J.C. Harris, N.J. Kuhn. Stable decompositions of classifying spaces of finite abelian p-groups, Math. Proc. Cambridge Philos. Soc. 103 (1988), 427–449.

[Sch] S. Schwarz. The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Math. J. 23(98) (1973), 151–163.

[St] R. P. Stanley. Enumerative Combinatorics, Vol. I, Wadsworth & Brooks/Cole, Monterey, 1986.

[The] J. Thévenaz. G-Algebras and Modular Representation Theory, Oxford Science Publications, Oxford, 1995.

[Tho] M.C. Thornton. Spaces with given homeomorphism groups, Proc. Amer. Math. Soc. 33 (1972), 127–131.

Serge Bouc, CNRS-LAMFA, Université de Picardie - Jules Verne, 33, rue St Leu, F-80039 Amiens Cedex 1, France.

serge.bouc@u-picardie.fr

Jacques Thévenaz, Section de mathématiques, EPFL, Station 8, CH-1015 Lausanne, Switzerland.

Jacques.Thevenaz@epfl.ch