Last update: 9 April 2013

The partition algebra $\u2102{A}_{k}\left(n\right)$ is the centralizer algebra of ${S}_{n}$ acting on the $k\text{-fold}$ tensor product ${B}^{\otimes k}$ of its $n\text{-dimensional}$ permutation representation $V\text{.}$ The partition algebra $\u2102{A}_{k+\frac{1}{2}}\left(n\right)$ is the centralizer algebra of the restriction of ${V}^{\otimes k}$ to ${S}_{n-1}\subseteq {S}_{n}\text{.}$ We apply the theory of the basic construction (generalized matrix algebras) to the tower of partition algebras $\u2102{A}_{0}\left(n\right)\subseteq \u2102{A}_{\frac{1}{2}}\frac{1}{2}\left(n\right)\subseteq \u2102{A}_{1}\left(n\right)\subseteq \u2102{A}_{1\frac{1}{2}}\left(n\right)\subseteq \dots \text{.}$ Our main results are:

- a presentation on generators and relations for $\u2102{A}_{k}\left(n\right);$
- a derivation of “Specht modules” from the basic construction;
- a proof that $\u2102{A}_{k}\left(n\right)$ is semisimple if and only if $k\le (n+1)/2$ (except for a few special cases);
- Murphy elements for $\u2102{A}_{k}\left(n\right);$ and
- an exposition on the theory of the basic construction and semisimple algebras.

A centerpiece of representation theory is the Schur–Weyl duality, which says that:

- the general linear group ${GL}_{n}\left(\u2102\right)$ and the symmetric group ${S}_{k}$ both act on tensor space $${V}^{\otimes k}=\underset{\underset{k\hspace{0.17em}\text{factors}}{\u23df}}{V\otimes \dots \otimes V},\phantom{\rule{2em}{0ex}}\text{with}\phantom{\rule{2em}{0ex}}\text{dim}\left(V\right)=n,$$
- these two actions commute, and
- each action generates the full centralizer of the other, so that
- as a $({GL}_{n}\left(\u2102\right),{S}_{k})\text{-bimodule,}$ the tensor space has a multiplicity free decomposition, $$\begin{array}{cc}{V}^{\otimes k}\cong \underset{\lambda}{\u2a01}{L}_{{GL}_{n}}\left(\lambda \right)\otimes {S}_{k}^{\lambda},& \text{(0.1)}\end{array}$$ where the ${L}_{{GL}_{n}}\left(\lambda \right)$ are irreducible ${GL}_{n}\left(\u2102\right)\text{-modules}$ and the ${S}_{k}^{\lambda}$ are irreducible ${S}_{k}\text{-modules.}$

The decomposition in (0.1) essentially makes the study of the representations of ${GL}_{n}\left(\u2102\right)$ and the study of representations of the symmetric group ${S}_{k}$ two sides of the same coin.

The group ${GL}_{n}\left(\u2102\right)$ has interesting subgroups,

$${GL}_{n}\left(\u2102\right)\supseteq {O}_{n}\left(\u2102\right)\supseteq {S}_{n}\supseteq {S}_{n-1},$$and corresponding centralizer algebras,

$$\u2102{S}_{k}\subseteq \u2102{B}_{k}\left(n\right)\subseteq \u2102{A}_{k}\left(n\right)\subseteq \u2102{A}_{k+\frac{1}{2}}\left(n\right),$$which are combinatorially defined in terms of the “multiplication of diagrams” (see Section 1) and which play exactly analogous “Schur–Weyl duality” roles with their corresponding subgroup of ${GL}_{n}\left(\u2102\right)\text{.}$ The Brauer algebras $\u2102{B}_{k}\left(n\right)$ were introduced in 1937 by Brauer [Bra1937]. The partition algebras $\u2102{A}_{k}\left(n\right)$ arose in the early 1990s in the work of Martin [Mar1991,Mar1994,Mar1996,Mar2000] and later, independently, in the work of Jones [Jon1993]. Martin and Jones discovered the partition algebra as a generalization of the Temperley–Lieb algebra and the Potts model in statistical mechanics. The partition algebras $\u2102{A}_{k+\frac{1}{2}}\left(n\right)$ appear in [Mar2000] and [MRo1998], and their existence and importance were pointed out to us by Grood [Gro2006]. In this paper we follow the method of [Mar2000] and show that if the algebras $\u2102{A}_{k+\frac{1}{2}}\left(n\right)$ are given the same stature as the algebras ${A}_{k}\left(n\right),$ then well-known methods from the theory of the “basic construction” (see Section 4) allow for easy analysis of the whole tower of algebras

$$\u2102{A}_{0}\left(n\right)\subseteq \u2102{A}_{\frac{1}{2}}\left(n\right)\subseteq \u2102{A}_{1}\left(n\right)\subseteq \u2102{A}_{1\frac{1}{2}}\left(n\right)\subseteq \dots ,$$all at once.

Let $\ell \in \frac{1}{2}{\mathbb{Z}}_{\ge 0}\text{.}$ In this paper we prove:

- A presentation by generators and relations for the algebras $\u2102{A}_{\ell}\left(n\right)\text{.}$
- $\u2102{A}_{\ell}\left(n\right)$ has $$\text{an ideal}\phantom{\rule{2em}{0ex}}\u2102{I}_{\ell}\left(n\right),\phantom{\rule{2em}{0ex}}\text{with}\phantom{\rule{2em}{0ex}}\frac{\u2102{A}_{\ell}\left(n\right)}{\u2102{I}_{\ell}\left(n\right)}\cong \u2102{S}_{\ell},$$ such that $\u2102{I}_{\ell}\left(n\right)$ is isomorphic to a “basic construction” (see Section 4). Thus the structure of the ideal $\u2102{I}_{\ell}\left(n\right)$ can be analyzed with the general theory of the basic construction and the structure of the quotient $\u2102{A}_{\ell}\left(n\right)/\left(\u2102{I}_{\ell}\left(n\right)\right)$ follows from the general theory of the representations of the symmetric group.
- The algebras $\u2102{A}_{\ell}\left(n\right)$ are in “Schur–Weyl duality” with the symmetric groups ${S}_{n}$ and ${S}_{n-1}$ on ${V}^{\otimes k}\text{.}$
- The general theory of the basic construction provides a construction of “Specht modules” for the partition algebras, i.e. integral lattices in the (generically) irreducible $\u2102{A}_{\ell}\left(n\right)\text{-modules.}$
- Except for a few special cases, the algebras $\u2102{A}_{\ell}\left(n\right)$ are semisimple if and only if $\ell \le (n+1)/2\text{.}$
- There are “Murphy elements” ${M}_{i}$ for the partition algebras that play exactly analogous roles to the classical Murphy elements for the group algebra of the symmetric group. In particular, the ${M}_{i}$ commute with each other in $\u2102{A}_{\ell}\left(n\right),$ and when $\u2102{A}_{\ell}\left(n\right)$ is semisimple each irreducible $\u2102{A}_{\ell}\left(n\right)\text{-module}$ has a unique, up to constants, basis of simultaneous eigenvectors for the ${M}_{i}\text{.}$

The primary new results in this paper are (a) and (f). There has been work towards a presentation theorem for the partition monoid by Fitzgerald and Leech [FLe1998], and it is possible that by now they have proved a similar presentation theorem. The statement in (b) has appeared implicitly and explicitly throughout the literature on the partition algebra, depending on what one considers as the definition of a “basic construction”. The treatment of this connection between the partition algebras and the basic construction is explained very nicely and thoroughly in [Mar2000]. We consider this connection an important part of the understanding of the structure of the partition algebras. The Schur–Weyl duality for the partition algebras $\u2102{A}_{k}\left(n\right)$ appears in [Mar1991,Mar2000], and [MRo1998] and was one of the motivations for the introduction of these algebras in [Jon1993]. The Schur–Weyl duality for $\u2102{A}_{k+\frac{1}{2}}\left(n\right)$ appears in [Mar2000] and [MRo1998]. Most of the previous literature (for example [Mar1996,MWo1999,MWo1998,DWa2000]) on the partition algebras has studied the structure of the partition algebras using the “Specht” modules of (d). Our point here is that their existence follows from the general theory of the basic construction. This is a special case of the fact that quasi-hereditary algebras are iterated sequences of basic constructions, as proved by Dlab and Ringel [DRi1989]. The statements about the semsimplicity of $\u2102{A}_{\ell}\left(n\right)$ have mostly, if not completely, appeared in the work of Martin and Saleur [Mar1996,MSa1994]. The Murphy elements for the partition algebras are new. Their form was conjectured by Owens [Owe2002], who proved that the sum of the first $k$ of them is a central element in $\u2102{A}_{k}\left(n\right)\text{.}$ Here we prove all of Owens’ theorems and conjectures (by a different technique than he was using). We have not taken the next natural step and provided formulas for the action of the generators of the partition algebra in the “seminormal” representations. We hope that someone will do this in the near future.

The “basic construction” is a fundamental tool in the study of algebras such as the partition algebra. Of course, like any fundamental construct, it appears in the literature and is rediscovered over and over in various forms. For example, one finds this construction in Bourbaki [Bou1990, Chapter 2, Section 4.2, Remark 1], in [Bro1955,Bro1955-2], in [GHJ1989, Chapter 2], and in the wonderful paper of Dlab and Ringel [DRi1989] where it is explained that this construction is also the algebraic construct that “controls” the theory of quasi-hereditary algebras, recollement, and highest weight categories [CPS1988] and some aspects of the theory of perverse sheaves [MVi1987].

Though this paper contains new results in the study of partition algebras we have made a distinct effort to present this material in a “survey” style so that it may be accessible to non-experts and to newcomers to the field. For this reason we have included, in Sections 4 and 5, expositions, from scratch, of

- the theory of the basic construction (see also [GHJ1989, Chapter 2]), and
- the theory of semisimple algebras, in particular, Maschke’s theorem, the Artin–Wedderburn theorem, and the Tits deformation theorem (see also [CRe1987, Sections 3B and 68]).

Here the reader will find statements of the main theorems which are in exactly the correct form for our applications (generally difficult to find in the literature), and short slick proofs of all the results on the basic construction and on semisimple algebras that we need for the study of the partition algebras.

There are two sets of results on partition algebras that we have not had the space to treat in this paper:

- the “Frobenius formula”, “Murnaghan–Nakayama” rule, and orthogonality rule for the irreducible characters given by Halverson [Hal2001] and Farina–Halverson [FHa2003], and
- the cellularity of the partition algebras proved by Xi [Xi1999] (see also Doran and Wales [DWa2000]).

The techniques in this paper apply, in exactly the same fashion, to the study of other diagram algebras; in particular, the planar partition algebras $\u2102{P}_{k}\left(n\right),$ the Temperley–Lieb algebras $\u2102{T}_{k}\left(n\right),$ and the Brauer algebras $\u2102{B}_{k}\left(n\right)\text{.}$ It was our original intent to include in this paper results (mostly known) for these algebras analogous to those which we have proved for the algebras $\u2102{A}_{\ell}\left(n\right),$ but the restrictions of time and space have prevented this. While perusing this paper, the reader should keep in mind that the techniques we have used do apply to these other algebras.

This is an excerpt of a paper entitled *Partition algebras*, written by Tom Halverson (Mathematics and Computer Science, Macalester College, Saint Paul, MN 55105, United States)
and Arun Ram.

This research was supported in part by National Science Foundation Grant DMS-0100975. This research was also supported in part by the National Science Foundation (DMS-0097977) and the National Security Agency (MDA904-01-1-0032).