Partition algebra explained

The partition algebra is an associative algebra with a basis of set-partition diagrams and multiplication given by diagram concatenation. Its subalgebras include diagram algebras such as the Brauer algebra, the Temperley–Lieb algebra, or the group algebra of the symmetric group. Representations of the partition algebra are built from sets of diagrams and from representations of the symmetric group.

Definition

Diagrams

A partition of

2k

elements labelled

1,\bar1,2,\bar2,...,k,\bark

is represented as a diagram, with lines connecting elements in the same subset. In the following example, the subset

\{\bar1,\bar4,\bar5,6\}

gives rise to the lines

\bar1-\bar4,\bar4-\bar5,\bar5-6

, and could equivalently be represented by the lines

\bar1-6,\bar4-6,\bar5-6,\bar1-\bar5

(for instance).

For

n\inC

and

k\inN*

, the partition algebra

Pk(n)

is defined by a

C

-basis made of partitions, and a multiplication given by diagram concatenation. The concatenated diagram comes with a factor

nD

, where

D

is the number of connected components that are disconnected from the top and bottom elements.

Generators and relations

The partition algebra

Pk(n)

is generated by

3k-2

elements of the type

These generators obey relations that include

2
s
i

=1,sisi+1si=si+1sisi+1,

2
p
i

=npi,

2=
b
i

bi,pibipi=pi

Other elements that are useful for generating subalgebras include

In terms of the original generators, these elements are

ei=bipipi+1bi,li=sipi,ri=pisi

Properties

The partition algebra

Pk(n)

is an associative algebra. It has a multiplicative identity

The partition algebra

Pk(n)

is semisimple for

n\inC-\{0,1,...,2k-2\}

. For any two

n,n'

in this set, the algebras

Pk(n)

and

Pk(n')

are isomorphic.

The partition algebra is finite-dimensional, with

\dimPk(n)=B2k

(a Bell number).

Subalgebras

Eight subalgebras

Subalgebras of the partition algebra can be defined by the following properties:

1,2,...,2k

, or size

1,2

, or only size

2

.

n

is absent, or can be eliminated by

pi\to

1
n

pi

.

Combining these properties gives rise to 8 nontrivial subalgebras, in addition to the partition algebra itself:

NotationName Generators DimensionExample

Pk(n)

Partition

si,pi,bi

B2k

PPk(n)

Planar partition

pi,bi

1
2k+1

\binom{4k}{2k}

RBk(n)

Rook Brauer

si,ei,pi

k
\sum
\ell=0

\binom{2k}{2\ell}(2\ell-1)!

Mk(n)

Motzkin

ei,li,ri

k
\sum
\ell=0
1
\ell+1

\binom{2\ell}{\ell}\binom{2k}{2\ell}

Bk(n)

si,ei

(2k-1)!

TLk(n)

Temperley–Lieb

ei

1
k+1

\binom{2k}{k}

Rk

Rook

si,pi

k
\sum
\ell=0

\binom{k}{\ell}2\ell!

PRk

Planar rook

li,ri

\binom{2k}{k}

CSk

Symmetric group

si

k!

The symmetric group algebra

CSk

is the group ring of the symmetric group

Sk

over

C

. The Motzkin algebra is sometimes called the dilute Temperley–Lieb algebra in the physics literature.

Properties

The listed subalgebras are semisimple for

n\inC-\{0,1,...,2k-2\}

.

Inclusions of planar into non-planar algebras:

PPk(n)\subsetPk(n),Mk(n)\subsetRBk(n),TLk(n)\subsetBk(n),PRk\subsetRk

Inclusions from constraints on subset size:

Bk(n)\subsetRBk(n)\subsetPk(n),TLk(n)\subsetMk(n)\subsetPPk(n),CSk\subsetRk

Inclusions from allowing top-top and bottom-bottom lines:

Rk\subsetRBk(n),PRk\subsetMk(n),CSk\subsetBk(n)

We have the isomorphism:
2)
PP
k(n

\congTL2k(n),\left\{\begin{array}{l}pi\mapstone2i-1\bi\mapsto

1
n

e2i\end{array}\right.

More subalgebras

In addition to the eight subalgebras described above, other subalgebras have been defined:

propPk

is generated by diagrams whose blocks all propagate, i.e. partitions whose subsets all contain top and bottom elements. These diagrams from the dual symmetric inverse monoid, which is generated by

si,bipi+1bi+1

.

QPk(n)

is generated by subsets of size at least two. Its generators are

si,bi,ei

and its dimension is
2k
1+\sum
j=1

(-1)j-1B2k-j

.

Uk

is generated by subsets with as many top elements as bottom elements. It is generated by

si,bi

.

An algebra with a half-integer index

k+12
is defined from partitions of

2k+2

elements by requiring that

k+1

and

\overline{k+1}

are in the same subset. For example,
P
k+12
is generated by

si\leq,bi\leq,pi\leq

so that

Pk\subset

P
k+12

\subsetPk+1

, and

\dim

P
k+12

=B2k+1

.

Periodic subalgebras are generated by diagrams that can be drawn on an annulus without line crossings. Such subalgebras include a translation element

u=

such that

uk=1

. The translation element and its powers are the only combinations of

si

that belong to periodic subalgebras.

Representations

Structure

For an integer

0\leq\ell\leqk

, let

D\ell

be the set of partitions of

k+\ell

elements

1,2,...,k

(bottom) and

\bar1,\bar2,...,\bar\ell

(top), such that no two top elements are in the same subset, and no top element is alone. Such partitions are represented by diagrams with no top-top lines, with at least one line for each top element. For example, in the case

k=12,\ell=5

:

Partition diagrams act on

D\ell

from the bottom, while the symmetric group

S\ell

acts from the top. For any Specht module

Vλ

of

S\ell

(with therefore

|λ|=\ell

), we define the representation of

Pk(n)

l{P}λ=CD|λ|

CS|λ|

Vλ .

The dimension of this representation is

\diml{P}λ=fλ

k
\sum
\ell=|λ|

\left\{{k\atop\ell}\right\}\binom{\ell}{|λ|},

where

\left\{{k\atop\ell}\right\}

is a Stirling number of the second kind,

\binom{\ell}{|λ|}

is a binomial coefficient, and

fλ=\dimSλ

is given by the hook length formula.

A basis of

l{P}λ

can be described combinatorially in terms of set-partition tableaux: Young tableaux whose boxes are filled with the blocks of a set partition.

Assuming that

Pk(n)

is semisimple, the representation

l{P}λ

is irreducible, and the set of irreducible finite-dimensional representations of the partition algebra is

Irrep\left(Pk(n)\right)=\left\{l{P}λ\right\}0\leq.

Representations of subalgebras

Representations of non-planar subalgebras have similar structures as representations of the partition algebra. For example, the Brauer-Specht modules of the Brauer algebra are built from Specht modules, and certain sets of partitions.

In the case of the planar subalgebras, planarity prevents nontrivial permutations, and Specht modules do not appear. For example, a standard module of the Temperley–Lieb algebra is parametrized by an integer

0\leq\ell\leqk

with

\ell\equivk\bmod2

, and a basis is simply given by a set of partitions.

The following table lists the irreducible representations of the partition algebra and eight subalgebras.

AlgebraParameterConditionsDimension

Pk(n)

λ

0\leq

\lambda\leq k

fλ

k
\sum
\ell=|λ|

\left\{{k\atop\ell}\right\}\binom{\ell}{|λ|}

PPk(n)

\ell

0\leq\ell\leqk

\binom{2k}{k+\ell}-\binom{2k}{k+\ell+1}

RBk(n)

λ

0\leq

\lambda\leq k

fλ\binom{k}{|λ|}

\left\lfloork-|λ|\right\rfloor
2
\sum
m=0

\binom{k-|λ|}{2m}(2m-1)!

Mk(n)

\ell

0\leq\ell\leqk

\left\lfloork-\ell\right\rfloor
2
\sum
m=0

\binom{k}{\ell+2m}\left\{\binom{\ell+2m}{m}-\binom{\ell+2m}{m-1}\right\}

Bk(n)

λ

\begin{array}{c}0\leq

\lambda\leq k \\ \lambda\equiv k\bmod 2\end

fλ\binom{k}{|λ|}(k-

\lambda-1)!

TLk(n)

\ell

\begin{array}{c}0\leq\ell\leqk\\ell\equivk\bmod2\end{array}

\binom{k}{k+\ell
2
} -\binom

Rk

λ

0\leq

\lambda\leq k

fλ\binom{k}{|λ|}

PRk

\ell

0\leq\ell\leqk

\binom{k}{\ell}

CSk

λ

\lambda=k

fλ

The irreducible representations of

propPk

are indexed by partitions such that

0<|λ|\leqk

and their dimensions are

fλ\left\{{k\atop|λ|}\right\}

. The irreducible representations of

QPk

are indexed by partitions such that

0\leq|λ|\leqk

. The irreducible representations of

Uk

are indexed by sequences of partitions.

Schur-Weyl duality

Assume

n\inN*

.For

V

a

n

-dimensional vector space with basis

v1,...,vn

, there is a natural action of the partition algebra

Pk(n)

on the vector space

V

. This action is defined by the matrix elements of a partition

\{1,\bar1,2,\bar2,...,k,\bark\}=\sqcuphEh

in the basis
(v
j1

v
jk

)

:

\left(\sqcuphEh\right)

j\bar,j\bar,...,j\bar
j1,j2,...,jk

=

1
r,s\inEh\impliesjr=js

.

This matrix element is one if all indices corresponding to any given partition subset coincide, and zero otherwise. For example, the action of a Temperley–Lieb generator is

ei

\left(v
j1

v
ji

v
ji+1

v
jk

\right) =

\delta
ji,ji+1
n
\sum
j=1
v
j1

vjvj

v
jk

.

Duality between the partition algebra and the symmetric group

Let

n\geq2k

be integer.Let us take

V

to be the natural permutation representation of the symmetric group

Sn

. This

n

-dimensional representation is a sum of two irreducible representations: the standard and trivial representations,

V=[n-1,1][n]

.

Then the partition algebra

Pk(n)

is the centralizer of the action of

Sn

on the tensor product space

V

,

Pk(n)\cong

End
Sn

\left(V\right).

Moreover, as a bimodule over

Pk(n) x Sn

, the tensor product space decomposes into irreducible representations as

V=oplus0\leql{P}λV[n-|λ|,λ],

where

[n-|λ|,λ]

is a Young diagram of size

n

built by adding a first row to

λ

, and

V[n-|λ|,λ]

is the corresponding Specht module of

Sn

.

Dualities involving subalgebras

The duality between the symmetric group and the partition algebra generalizes the original Schur-Weyl duality between the general linear group and the symmetric group. There are other generalizations. In the relevant tensor product spaces, we write

Vn

for an irreducible

n

-dimensional representation of the first group or algebra:
Tensor product spaceGroup or algebraDual algebra or groupComments

\left(Vn-1

k
V
1\right)

Sn

Pk(n)

The duality for the full partition algebra

\left(Vn-2V1 ⊕

k
V
1\right)

Sn-1

P
k+12

(n)

Case of a partition algebra with a half-integer index
k
V
n

GLn(C)

Sk

The original Schur-Weyl duality
k
V
n

O(n)

Bk(n)

Duality between the orthogonal group and the Brauer algebra

\left(Vn

k
V
1\right)

O(n)

RBk(n+1)

Duality between the orthogonal group and the rook Brauer algebra
k
V
n

Rn

propPk

Duality between the rook algebra and the totally propagating partition algebra
k
V
2

gl(1

1)

PRk-1

Duality between a Lie superalgebra and the planar rook algebra
k
V
n-1

Sn

QPk(n)

Duality between the symmetric group and the quasi-partition algebra
r
V
n

*\right)
\left(V
n

GLn(C)

Br,s(n)

Duality involving the walled Brauer algebra.

Further reading