Partition algebras

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 9 April 2013

Partition algebras

For k12>0 and n, the partition algebra Ak(n) is the associative algebra over with basis Ak,

Ak(n)=-span {dAk}, and multiplication defined byd1d2= n(d1d2),

where, for d1,d2Ak, d1d2 is the product in the monoid Ak and is the number of blocks removed from the middle row when constructing the composition d1d2. For example,

ifd1= andd2= then d1d2= =n2 , (2.1)

since two blocks are removed from the middle row. There are inclusions of algebras given by

Ak-12 Ak 1 k d 1 k d and Ak-1 Ak-12 1 k-1 d 1 k d (2.2)

For d1,d2Ak, define

d1d2, if the set partitiond2 is coarser than the set partitiond1,

i.e., i and j in the same block of d1 implies that i and j are in the same block of d2. Let {xdAkdAk} be the basis of Ak uniquely defined by the relation

d=dd xd, for alldAk. (2.3)

Under any linear extension of the partial order the transition matrix between the basis {ddAk} of Ak(n) and the basis {xddAk} of Ak(n) is upper triangular with 1s on the diagonal and so the xd are well defined.

The maps

ε12:Ak Ak-12, ε12:Ak-12 Ak-1and trk:Ak.

Let k>0. Define linear maps

ε12: Ak Ak-12 1 k d 1 k d and ε12: Ak-12 Ak-1 1 k d 1 k-1 d

so that ε12(d) is the same as d except that the block containing k and the block containing k are combined, and ε12(d) has the same blocks as d except with k and k removed. There is a factor of n in ε12(d) if the removal of k and k reduces the number of blocks by 1. For example,

ε12 (A A) = , ε12 (A A) = ,

and

ε12 (A A) = , ε12 (A A) =n .

The map ε12 is the composition Ak-12 Akε1 Ak-1. The composition of ε12 and ε12 is the map

ε1: Ak Ak-1 1 k d 1 k-1 d . (2.4)

By drawing diagrams it is straightforward to check that, for k>0,

ε12 (α1ba2) = a1ε12 (b)a2, fora1,a2 Ak-12,b Ak ε12 (α1ba2) = a1ε12 (b)a2, fora1,a2 Ak-1,b Ak-12 ε1 (α1ba2) = a1ε1 (b)a2, fora1,a2 Ak-1,b Ak (2.5)

and

pk+12b pk+12 = ε12(b) pk+12 = pk+12 ε12(b), forbAk pkb pk = ε12(b) pk = pk ε12(b), forbAk-12 ekbek = ε1(b)ek = ekε1(b), forbAk. (2.6)

Define trk:Ak and trk-12:Ak by the equations

trk(b)= trk-12 (ε12(b)), forbAk, andtrk-12 (b)=trk-1 (ε12(b)), forbAk-12 , (2.7)

so that

trk(b)= ε1k(b), forbAk,and trk-12(b) =ε1k-1ε12 (b),forb Ak-12. (2.8)

Pictorially trk(d)=nc where c is the number of connected components in the closure of the diagram d,

trk(d)= d ,fordAk. (2.9)

The ideal Ik(n)

For k120 define

Ik(n)= -span{dIk}. (2.10)

By (1.3),

Ik(n) is an ideal ofAk(n) andAk(n) /Ik(n) Sk, (2.11)

since the set partitions with propagating number k are exactly the permutations in the symmetric group Sk (by convention S+12=S for >0; see (2.2)).

View Ik(n) as an algebra (without identity). Since Ak(n)/IkSk and Sk is semisimple, Rad(Ak(n)) Ik(n). Since Ik(n)/Rad(Ak(n)) is an ideal in Ak(n)/Rad(Ak(n)) the quotient Ik(n)/Rad(Ak(n)) is semisimple. Therefore Rad(Ik(n)) Rad(Ak(n)). On the other hand, since Rad(Ak(n)) is an ideal of nilpotent elements in Ak(n), it is an ideal of nilpotent elements in Ik(n) and so Rad(Ak(n)) Rad(Ak(n)). Thus

Rad(Ak(n))= Rad(Ik(n)). (2.12)

Let k0. By (2.5) the maps

ε12:Ak Ak-12and ε12: Ak-12 Ak-1

are (Ak-12,Ak-12)-bimodule and (Ak-1,Ak-1)-bimodule homomorphisms, respectively. The corresponding basic constructions (see Section 4) are the algebras

Ak(n) Ak-12(n) Ak(n)and Ak-12(n) Ak-1(n) Ak-12(n) (2.13)

with products given by

(b1b2) (b3b4)= b1ε12 (b2b3)b4 ,and (c1c2) (c3c4)= c1ε12 (c2c3)c4, (2.14)

for b1,b2, b3,b4 Ak(n), and for c1,c2, c3,c4 Ak-12(n).

Let k12>0. Then, by the relations in (2.6) and the fact that

everydIk can be written asd=d1 pkd2,with d1,d2 Ak-12, (2.15)

the maps

Ak-12(n) Ak-1(n) Ak-12(n) Ik(n) b1b2 b1pkb2 (2.16)

are algebra isomorphisms. Thus the ideal Ik(n) is always isomorphic to a basic construction (in the sense of Section 4).

Representations of the symmetric group

A partition λ is a collection of boxes in a corner. We shall conform to the conventions in [Mac1995] and assume that gravity goes up and to the left, i.e.,

Numbering the rows and columns in the same way as for matrices, let

λi = the number of boxes in rowiof λ, λj = the number of boxes in columnjof λ,and λ = the total number of boxes inλ. (2.17)

Any partition λ can be identified with the sequence λ=(λ1λ2) and the conjugate partition to λ is the partition λ= ( λ1, λ2, ) . The hook length of the box b of λ is

h(b)= (λi-i)+ (λj-j) +1,ifb is in position(i,j) of λ. (2.18)

Write λn if λ is a partition with n boxes. In the example above, λ=(553311) and λ18.

See [Mac1995, Section I.7] for details on the representation theory of the symmetric group. The irreducible Sk-modules Skλ are indexed by the elements of

S^k= {λn}and dim(Skλ)= k!bλh(b) . (2.19)

For λS^k and μS^k-1,

ResSk-1Sk (Skλ) λ/ν= Sk-1νand IndSk-1Sk (Sk-1μ) ν/μ= Skν, (2.20)

where the first sum is over all partitions ν that are obtained from λ by removing a box, and the second sum is over all partitions ν which are obtained from μ by adding a box (this result follows, for example, from [Mac1995, Section I.7 Example 22(d)]).

The Young lattice is the graph S^ given by setting

vertices on levelk:S^k ={partitionsλwithkboxes} ,and an edgeλμ,λ S^k,μ S^k+1if μis obtained fromλ by adding a box. (2.21)

It encodes the decompositions in (2.20). The first few levels of S^ are given by

k=0: k=1: k=2: k=3: k=4:

For μS^k define

S^kμ= { T= ( T(0), T(1),, T(k) ) | T(0)=, T(k)=μ,and ,for each, T() S^and T() T(+1) is an edge inS^ }

so that S^kμ is the set of paths from S^0 to μS^k in the graph S^. In terms of the Young lattice,

dim(Skμ)= Card(S^kμ) . (2.22)

This is a translation of the classical statement (see [Mac1995, Section I.7.6(ii)]) that dim(Skμ) is the number of standard Young tableaux of shape λ (the correspondence is obtained by putting the entry in the box of λ which is added at the th step T(-1)T() of the path).

Structure of the algebra Ak(n)

Build a graph A^ by setting

vertices on levelk:A^k ={partitionsμk-μ0} , vertices on levelk+12: A^k+1= A^k ={partitionsμk-μ0} , an edgeλμ,λ A^k,μ A^k+12 ifλ=μor if μis obtained fromλ by removing a box, an edgeμλ,μ A^k+12,λ A^k+1 ifλ=μor if λis obtained fromμ by adding a box. (2.23)

The first few levels of A^ are given by

k=0: k=0+12: k=1: k=1+12: k=2: k=2+12: k=3:

The following result is an immediate consequence of the Tits deformation theorem, Theorems 5.10 and 5.13 in this paper (see also [CRe1987, (68.17)]).

Theorem 2.24.

  1. For all but a finite number of n the algebra Ak(n) is semisimple.
  2. If Ak(n) is semisimple then the irreducible Ak(n)-modules, Akμ are indexed by elements of the set A^k={partitionsμk-μ0}, and dim(Akμ)= (number of paths from A^0 to μA^k in the graph A^).

Let

A^kμ= { T= ( T(0), T(12),, T(k-12), T(k) ) | T(0)=, T(k)=μ, and,for each, T() A^and T() T(+12) is an edge inA^ }

sothat A^kμ is the set of paths from A^0 to μA^k in the graph A^. If μS^k then μA^k and μA^k+12 and, for notational convenience in the following theorem,

identify P= ( P(0), P(1),, P(k) ) S^kμ with the corresponding P= ( P(0), P(0), P(1), P(1),, P(k-1), P(k-1), P(k) ) A^kμ, andP= ( P(0), P(0), P(1), P(1),, P(k-1), P(k-1), P(k), P(k) ) A^k+12μ.

For 120 and n such that A(n) is semisimple let χA(n)μ, μA^, be the irreducible characters of A(n). Let tr:A(n) be the traces on A(n) defined in (2.8) and define constants trμ(n), μA^, by

tr= μA^ trμ(n) χA(n)μ. (2.25)

Theorem 2.26.

  1. Let n and let k120. Assume that trλ(n)0, for allλ A^,12 0,<k. Then the partition algebras A(n) are semisimple for all 120, k. (2.27) For each 120, k-12, define εμλ= tr-12λ(n) tr-1μ(n) for each edgeμλ, μA^-1, λA^-12 ,in the graphA^. Inductively define elements in A(n) by ePQμ= 1εμτεμγ eP-Tτp eTQ-γ, forμA^ ,μ-1, P,QA^μ, (2.28) where τ=P(-12), γ=Q(-12), R-=(R(0),,R(-12)) for R=(R(0),,R(-12),R())A^μ and T is an element of A^-1μ (the element ePQλ does not depend on the choice of T). Then define ePQλ= (1-z)sPQλ ,forλ S^,P,Q S^λ, wherez= μA^μ-1 PA^μ ePPμ (2.29) and {sPQλλS^,P,QS^λ} is any set of matrix units for the group algebra of the symmetric group S. Together, the elements in (2.28) and (2.29) form a set of matrix units in A(n).
  2. Let n0 and let k12>0 be minimal such that trkλ(n)=0 for some λA^k. Then Ak+12(n) is not semisimple.
  3. Let n0 and k12>0. If Ak(n) is not semisimple then Ak+j(n) is not semisimple for j>0.

Proof.

(a) Assume that A-1(n) and A-12(n) are both semisimple and that tr-1μ(n)0 for all μA^-1. If λA^-12 then εμλ0 if and only if tr-12λ(n)0, and, since the ideal I(n) is isomorphic to the basic construction A-12(n) A-1(n) A-12(n) (see (2.13)), it then follows from Theorem 4.28 that I(n) is semisimple if and only if tr-1μ(n)0 for all λA^-12. Thus, by(2.12), if A-1(n) and A-12(n) are both semisimple and tr-1μ(n)0 for all μA^-1 then

A(n) is semisimple if and only if tr-12λ (n)0for all λA^-12 . (2.30)

By Theorem 4.28, when tr-12λ(n)0 for all λA^-12, the algebra I(n) has matrix units given by the formulas in (2.28). The element z in (2.29) is the central idempotent in A(n) such that I(n)=zA(n). Hence the complete set of elements in (2.28) and (2.29) form a set of matrix units for A(n). This completes the proof of (a) and (b) follows from Theorem 4.28(b).

(c) Part (g) of Theorem 4.28 shows that if A-1(n) is not semisimple then A(n) is not semisimple.

Specht modules

Let A be an algebra. An idempotent is a nonzero element pA such that p2=p. A minimal idempotent is an idempotent p which cannot be written as a sum p=p1+p2 with p1p2=p2p1=0. If p is an idempotent in A and pAp=p then p is a minimal idempotent of A since, if p=p1+p2 with p12=p1, p22=p2, and p1p2=p2p1=0, then pp1p=kp for some constant p and so kp1=kpp1=pp1pp1=p1 giving that either p1=0 or k=1, in which case p1=pp1p=p.

Let p be an idempotent in A. Then the map

(pAp)op EndA(Ap), pbp ϕpbp whereϕpbp (ap)=(ap) (pbp)=apbp, forapAp, (2.31)

is a ring isomorphism.

If p is a minimal idempotent of A and Ap is a semisimple A-module then Ap must be a simple A-module. To see this suppose that Ap is not simple so that there are A-submodules V1 and V2 of Ap such that Ap=V1V2. Let ϕ1,ϕ2EndA(Ap) be the A-invariant projections on V1 and V2. By (2.31) ϕ1 and ϕ2 are given by right multiplication by p1=pp1p and p2=pp2p, respectively, and it follows that p=p1+p2, V1=Ap1, V2=Ap2, and Ap=Ap1Ap2. Then p12= ϕ1(p1)= ϕ12(p)=p1 and p1p2= ϕ2(p1)= ϕ2(ϕ1(p)) =0. Similarly p22=p2 and p2p1=0. Thus p is not a minimal idempotent.

If p is an idempotent in A and Ap is a simple A-module then

pAp=EndA (Ap)op= (p·1·p)=p,

by (2.31) and Schur’s lemma (Theorem 5.3).

The group algebra of the symmetric group Sk over the ring is

Sk,=Sk andSk= Sk,, (2.32)

where the tensor product is defined via the inclusion . Let λ=(λ1,λ2,,λ) be a partition of k. Define subgroups of Sk by

Sλ=Sλ1× ×Sλand Sλ= Sλ1×× Sλr, (2.33)

where λ=(λ1,λ2,,λr) is the conjugate partition to λ, and let

1λ=wSλ wandελ =wSλ (-1)(w)w. (2.34)

Let τ be the permutation in Sk that takes the row reading tableau of shape λ to the column reading tableau of shape λ For example for λ=(553311),

τ= ( 2,7,8,12,9,16,14, 4,15,10,18,6 ) (3,11)(5,17), since τ· 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 = 1 7 11 15 17 2 8 12 16 18 3 9 13 4 10 14 5 6 .

The Specht module for Sk is the Sk-module

Sk,λ=im ΨSk= (Sk)pλ, wherepλ=1λ τελ τ-1,and (2.35)

where ΨSk is the Sk-module homomorphism given by

ΨSk: (Sk)1λ ι Sk π (Sk)τελτ-1 b1λ b1λ b1λτελτ-1 (2.36)

By induction and restriction rules for the representations of the symmetric groups, the Sk-modules (Sk)1λ and (Sk)τελτ-1 have only one irreducible component in common and it follows (see [Mac1995, Section I.7, Example 15]) that

Skλ= Sk,λ is the irreducibleSk-module indexed by λ, (2.37)

once one shows that ΨSk is not the zero map.

Let k12>0. For an indeterminate x, define the [x]-algebra by

Ak,=[x] -span{dAk} (2.38)

with multiplication given by replacing n with x in (2.1). For each n,

Ak(n)= [x] Ak,, where the-module homomorphism evn: [x] , x n (2.39)

is used to define the tensor product. Let λ be a partition with k boxes. Let b pk(k-λ) denote the image of bAλ, under the map given by

Aλ, Ak, b b ...........................k-|λ| ,ifkis an integer, and Aλ+12, Ak, b b ...........................k-|λ|-12 ,ifk-12is an integer.

For k12>0, define an Ak,-module homomorphism

ΨAk: Ak,tλ ψ1 Ak,sλ ψ2 Ak,/Iλ, btλ btλsλ btλsλ, (2.40)

where Iλ, is the ideal

Iλ,= [x]-span {dAkdhas propogating number<λ}

and tλ,sλAk, are defined by

tλ=1λ pk(k-λ) andsλ= τελτ-1 pk(k-λ). (2.41)

The Specht module for Ak(n) is the Ak,-module

Ak,λ=im ΨAk= ( image of Ak,eλ Ak,/ Iλ, ) ,whereeλ= pλ pk(k-λ). (2.42)

Proposition 2.43. Let k12>0, and let λ be a partition with k boxes. If n such that Ak(n) is semisimple, then

Akλ(n)= [x] Ak,λ is the irreducibleAk (n)-module indexed byλ,

where the tensor product is defined via the -module homomorphism in (2.39).

Proof.

Let r=λ. Since

Ar(n)/ Ir(n)Sr

and pλ is a minimal idempotent of Sr, it follows from (4.20) that eλ, the image of eλ in (Ak(n))/ (Ir(n)), is a minimal idempotent in (Ak(n))/ (Ir(n)). Thus

( Ak(n) Ir(n) ) eλ is a simple (Ak(n))/ (Ir(n)) -module.

Since the projection Ak(n) (Ak(n))/ (Ir(n)) is surjective, any simple (Ak(n))/ (Ir(n))-module is a simple Ak(n)-module.

Notes and References

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).

page history