Category of all partitions

Definitions

Partitions

Let $k,l\in\mathbb{N}_0$ , by a partition of $k$ upper and $l$ lower points we mean herre a partition of the set $\{1,\dots,k\}\sqcup\{1,\dots,l\}\approx\{1,\dots,k+l\}$ , that is, a decomposition of the set of $k+l$ points into non-empty disjoint subsets, called blocks. The first $k$ points are called upper and the last $l$ points are called lower. The set of all partitions on $k$ upper and $l$ lower points is denoted $\Pscr(k,l)$ . We denote the union $\Pscr:=\bigcup_{k,l\in\N_0}\Pscr(k,l)$ .

We illustrate partitions graphically by putting $k$ points in one row and $l$ points on another row below and connecting by lines those points that are grouped in one block. All lines are drawn between those two rows.

Below, we give an example of two partitions $p\in\Pscr(3,4)$ and $q\in\Pscr(4,4)$ defined by their graphical representation. The first set of points is decomposed into three blocks, whereas the second one is into five blocks. In addition, the first one is an example of a non-crossing partition, i.e. a partition that can be drawn in a way that lines connecting different blocks do not intersect (following the rule that all lines are between the two rows of points). On the other hand, the second partition has one crossing.

$p= \BigPartition{ \Pblock 0 to 0.25:2,3 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1,4 \Pline (2.5,0.25) (2.5,0.75) } \qquad q= \BigPartition{ \Psingletons 0 to 0.25:1,4 \Psingletons 1 to 0.75:1,4 \Pline (2,0) (3,1) \Pline (3,0) (2,1) \Pline (2.75,0.25) (4,0.25) }$

A block containing a single point is called a singleton. In particular, the partitions containing only one point are called singletons and for clarity denoted by an arrow $\singleton\in\Pscr(0,1)$ and $\upsingleton\in\Pscr(1,0)$ .

The category structure

Let us fix a complex number $\delta\in\C$ . Let us denote $\Part_\delta(k,l)$ the vector space of formal linear combination of partitions $p\in\Pscr(k,l)$ . That is, $\Part_\delta(k,l)$ is a vector space, whose basis is $\Pscr(k,l)$ .

Now, we are going to define some operations on $\Part_\delta$ . First, let us define those operations just on partitions.

The tensor product of two partitions $p\in\Pscr(k,l)$ and $q\in\Pscr(k',l')$ is the partition $p\otimes q\in \Pscr(k+k',l+l')$ obtained by writing the graphical representations of $p$ and $q$ “side by side”.

$\BigPartition{ \Pblock 0 to 0.25:2,3 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1,4 \Pline (2.5,0.25) (2.5,0.75) } \otimes \BigPartition{ \Psingletons 0 to 0.25:1,4 \Psingletons 1 to 0.75:1,4 \Pline (2,0) (3,1) \Pline (3,0) (2,1) \Pline (2.75,0.25) (4,0.25) } = \BigPartition{ \Pblock 0 to 0.25:2,3 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1,4,5,8 \Psingletons 1 to 0.75:5,8 \Pline (2.5,0.25) (2.5,0.75) \Pline (6,0) (7,1) \Pline (7,0) (6,1) \Pline (6.75,0.25) (8,0.25) }$

For $p\in\Pscr(k,l)$ , $q\in\Pscr(l,m)$ we define their composition $qp\in\Part_\delta(k,m)$ by putting the graphical representation of $q$ below $p$ identifying the lower row of $p$ with the upper row of $q$ . The upper row of $p$ now represents the upper row of the composition and the lower row of $q$ represents the lower row of the composition. Each extra loop that appears in the middle and is not connected to any of the upper or the lower points, transforms to a multiplicative factor $\delta$ .

$\BigPartition{ \Psingletons 0 to 0.25:1,4 \Psingletons 1 to 0.75:1,4 \Pline (2,0) (3,1) \Pline (3,0) (2,1) \Pline (2.75,0.25) (4,0.25) } \cdot \BigPartition{ \Pblock 0 to 0.25:2,3 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1,4 \Pline (2.5,0.25) (2.5,0.75) } = \BigPartition{ \Pblock 0.5 to 0.75:2,3 \Pblock 1.5 to 1.25:1,2,3 \Psingletons 0.5 to 0.75:1,4 \Pline (2.5,0.75) (2.5,1.25) \Psingletons -0.5 to -0.25:1,4 \Psingletons 0.5 to 0.25:1,4 \Pline (2,-0.5) (3,0.5) \Pline (3,-0.5) (2,0.5) \Pline (2.75,-0.25) (4,-0.25) } = \delta^2 \BigPartition{ \Pblock 0 to 0.25:2,3,4 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1 \Pline (2.5,0.25) (2.5,0.75) }$

For $p\in\Pscr(k,l)$ we define its involution $p^*\in\Pscr(l,k)$ by reversing its graphical representation with respect to the horizontal axis.

$\left( \BigPartition{ \Pblock 0 to 0.25:2,3 \Pblock 1 to 0.75:1,2,3 \Psingletons 0 to 0.25:1,4 \Pline (2.5,0.25) (2.5,0.75) } \right)^* = \BigPartition{ \Pblock 1 to 0.75:2,3 \Pblock 0 to 0.25:1,2,3 \Psingletons 1 to 0.75:1,4 \Pline (2.5,0.25) (2.5,0.75) }$

Now we can extend the definition of tensor product and composition on the vector spaces $\Part_\delta(k,l)$ linearly. We extend the definition of the involution antilinearly. These operations are called the category operations on partitions.

The set of all natural numbers with zero $\N_0$ as a set of objects together with the spaces of linear combinations of partitions $\Part_\delta(k,l)$ as sets of morphisms between $k\in\N_0$ and $l\in\N_0$ with respect to those operations form a monoidal $*$ -category. All objects in the category are self-dual. This category is called the (linear) category of all partitions.

Representation theory of the symmetric group

Linear maps associated to partitions

Suppose the parameter $\delta$ is now a natural number $N\in\N$ . For every partition $p\in\Pscr(k,l)$ we define a linear map $T_p\colon(\C^N)^{\otimes k}\to(\C^N)^{\otimes l}$ as

$T_p(e_{i_1}\otimes\cdots\otimes e_{i_k})=\sum_{j_1,\dots,j_l=1}^N\delta_p(\mathbf{i},\mathbf{j})(e_{j_1}\otimes\cdots\otimes e_{j_l}),$

where $\mathbf{i}=(i_1,\dots,i_k)$ , $\mathbf{j}=(j_1,\dots,j_l)$ and the symbol $\delta_p(\mathbf{i},\mathbf{j})$ is defined as follows. Let us assign the $k$ points in the upper row of $p$ by the numbers $i_1,\dots,i_k$ (from left to right) and the $l$ points in the lower row by $j_1,\dots,j_l$ (again from left to right). Then $\delta(\mathbf{i},\mathbf{j})=1$ if the points belonging to the same block are assigned the same numbers. Otherwise $\delta(\mathbf{i},\mathbf{j})=0$ .

As an example, we can express $\delta_p$ and $\delta_q$ , where $p$ and $q$ come from the example above, using multivariate $\delta$ function as follows

$\delta_p(\mathbf{i},\mathbf{j})=\delta_{i_1i_2i_3j_2j_3},\quad \delta_q(\mathbf{i},\mathbf{j})=\delta_{i_2j_3j_4}\delta_{i_3j_2}.$

We extend this definition to the linear spaces $\Part_N(k,l)$ linearly, i.e. $\delta_{\alpha p+q}=\alpha\delta_p+\delta_q$ and hence $T_{\alpha p+q}=\alpha T_p+T_q$ .

Intertwiners for the symmetric group

Proposition. The map $T_\bullet\colon p\mapsto T_p$ is a monoidal unitary functor. That is, we have the following

$T_{p\otimes q}=T_p\otimes T_q$ ,
$T_{qp}=T_qT_p$ whenever one of the sides makes sense,
$T_{p^*}=T_p^*$ .

Note that the proposition is true only if the category parameter $\delta$ indeed coincide with the dimension $N$ of the $\C^N$ vector spaces.

Consider the symmetric group $S_N$ and denote by $u$ the representation of $S_N$ by permutation matrices. For any $k,l\in\N_0$ denote the intertwiner spaces

$\FundRep_{S_N}(k,l):=\Rep_{S_N}(u^{\otimes k},u^{\otimes l}):=\{T\colon(\C^N)^{\otimes k}\to(\C^N)^{\otimes l}\mid Tu^{\otimes k}=u^{\otimes l}T\}.$

Proposition. It holds that

$\FundRep_{S_N}(k,l)=\{T_p\mid p\in\Part(k,l)\}.$

That is, the functor $T$ maps the category of partitions $\Part$ to the category generated by the fundamental representation $u$ .

So the category of all partitions can be used to model the representation theory of the symmetric group. Note however that the functor $T$ is not injective, so it does not provide a category isomorphism.

Note that this result can be also understood as a generalization of the Schur–Weyl duality.

Table of Contents

Category of all partitions

Definitions

Partitions

The category structure

Representation theory of the symmetric group

Linear maps associated to partitions

Intertwiners for the symmetric group

Completing the category

User Tools

Site Tools

Table of Contents

Category of all partitions

Definitions

Partitions

The category structure

Representation theory of the symmetric group

Linear maps associated to partitions

Intertwiners for the symmetric group

Completing the category

Page Tools