Diagram Algebras

A diagram algebra is an algebra whose basis you can draw. An element of the partition algebra $P_n(δ)$ is a set partition of $2n$ points — a top row $1…n$ and a bottom row $1'…n'$ — pictured as two rows of dots with each block joined up:

#A diagram is a picture

Three strands. The block {1, 2, −1, −2} joins both rows; {3, −3} runs straight down.

source · editable

<graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, 2, -1, -2], [3, -3]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"77px"}' /> <graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, -1], [2, -2], [3, -3]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"77px"}' /> <graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, -2], [2, -1], [3, -3]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"77px"}' />

Multiplication is geometric, and it is the whole subject: stack $a$ above $b$, glue $a$'s bottom row to $b$'s top row, read off which outer points are now connected, and throw the middle away. A block that ends up living entirely in the discarded middle was a closed loop, and each closed loop contributes a factor of the loop parameter$δ$. So the algebra is defined over $\mathbb{Z}[δ]$, and $δ$ stays a symbol here unless you give it a value.

The lattice of subalgebras

Where the hypercomplex families differed only in a square and a commutation rule, these differ only in which diagrams are admitted — and each restriction is closed under stacking, so each one is a subalgebra. That is the whole parameterisation:

Algebra	Diagrams admitted	Dimension	Sequence
PartitionAlgebra(n)	all set partitions of $2n$	$B(2n)$	Bell
PlanarPartitionAlgebra(n)	planar ones	$C(2n)$	Catalan
BrauerAlgebra(n)	perfect matchings	$(2n-1)!!$	double factorial
TemperleyLiebAlgebra(n)	planar perfect matchings	$C(n)$	Catalan
MotzkinAlgebra(n)	planar, blocks of size ≤ 2	$M(2n)$	Motzkin
RookAlgebra(n)	partial permutations	$\sum \binom{n}{k}^2 k!$	rook
SymmetricGroupAlgebra(n)	permutations	$n!$	factorial

Every one of those dimensions is a sequence enumeratio already counts — which is the point of putting these here rather than anywhere else.

#Dimensions are the counting sequences

B(6) = 203, and the catalogue's own BellNumber agrees.

In$\mathrm{AlgebraDimension}(\mathrm{PartitionAlgebra}(3))$Out$203$In$\mathrm{BellNumber}(6)$Out$203$In$\mathrm{AlgebraDimension}(\mathrm{TemperleyLiebAlgebra}(4))$Out$14$In$\mathrm{CatalanNumber}(4)$Out$14$

source · editable

<notatio-cell value="AlgebraDimension(PartitionAlgebra(3))" data-allow-mismatch="children" /> <notatio-cell value="BellNumber(6)" data-allow-mismatch="children" /> <notatio-cell value="AlgebraDimension(TemperleyLiebAlgebra(4))" data-allow-mismatch="children" /> <notatio-cell value="CatalanNumber(4)" data-allow-mismatch="children" />

The dimension comes from the closed form, so it answers well past the point where listing the basis would be useful.

#Dimension without enumeration

In$\mathrm{AlgebraDimension}(\mathrm{PartitionAlgebra}(6))$Out$4\,213\,597$In$\mathrm{AlgebraDimension}(\mathrm{BrauerAlgebra}(8))$Out$2\,027\,025$In$\mathrm{Basis}(\mathrm{TemperleyLiebAlgebra}(3))$Out$\bigl\lbrack\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, -1\bigr\rbrack, \bigl\lbrack-2, -3\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack, \bigl\lbrack2, 3\bigr\rbrack, \bigl\lbrack-2, -3\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -3\bigr\rbrack, \bigl\lbrack2, 3\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack, \bigl\lbrack2, -2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)\bigr\rbrack$

source · editable

<notatio-cell value="AlgebraDimension(PartitionAlgebra(6))" data-allow-mismatch="children" /> <notatio-cell value="AlgebraDimension(BrauerAlgebra(8))" data-allow-mismatch="children" /> <notatio-cell value="Basis(TemperleyLiebAlgebra(3))" data-allow-mismatch="children" />

The product, and where δ comes from

Write a diagram as Diagram([[1,2],[-1,-2]]) — blocks of signed labels, positive on the top row and negative on the bottom. The Temperley–Lieb generator $e_1$ is the cup-cap: it joins the two top points to each other and the two bottom points to each other.

Stack $e_1$ on itself and the middle closes a loop — which is exactly the relation $e_1^2 = δ e_1$, the defining relation of the Temperley–Lieb algebra.

#e₁² = δe₁

The cup-cap squared: one closed loop, so one factor of δ.

In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack)⊗\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack)$Out$δ\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack)$

source · editable

<graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, 2], [-1, -2]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"53px"}' /> <notatio-cell value="CircleTimes(Diagram([[1, 2], [-1, -2]]), Diagram([[1, 2], [-1, -2]]))" data-allow-mismatch="children" />

The product is the ordered one — NonCommutativeMultiply, or infix ⊗, the same head the hypercomplex units use. A diagram algebra is not commutative, so × is the wrong home for it, for exactly the reason set out there.

The other Temperley–Lieb relations fall out of the same stacking:

#e₁e₂e₁ = e₁ in TL₃

No loop closes, and the result is e₁ back again — no δ in sight.

In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)⊗\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack2, 3\bigr\rbrack, \bigl\lbrack-2, -3\bigr\rbrack, \bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack)⊗\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)$Out$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack\bigr\rbrack)$

source · editable

<notatio-cell value="CircleTimes( Diagram([[1, 2], [-1, -2], [3, -3]]), Diagram([[2, 3], [-2, -3], [1, -1]]), Diagram([[1, 2], [-1, -2], [3, -3]]), )" data-allow-mismatch="children" />

Containment tells the subalgebras apart

Because each algebra is a class of diagrams, membership is a real question with a real answer — and it is how the inclusions become checkable. The crossing $s_1$ is a Brauer diagram and a permutation, but not planar, so it is not Temperley–Lieb.

#Which algebra is this diagram in?

In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -2\bigr\rbrack, \bigl\lbrack2, -1\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)∈\mathrm{BrauerAlgebra}(3)$Out$\mathrm{True}$In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -2\bigr\rbrack, \bigl\lbrack2, -1\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)∈\mathrm{TemperleyLiebAlgebra}(3)$Out$\mathrm{False}$In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)∈\mathrm{TemperleyLiebAlgebra}(3)$Out$\mathrm{True}$In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack-1, -2\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack\bigr\rbrack)∈\mathrm{SymmetricGroupAlgebra}(3)$Out$\mathrm{False}$

source · editable

<graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, -2], [2, -1], [3, -3]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"77px"}' /> <notatio-cell value="Diagram([[1, -2], [2, -1], [3, -3]]) in BrauerAlgebra(3)" data-allow-mismatch="children" /> <notatio-cell value="Diagram([[1, -2], [2, -1], [3, -3]]) in TemperleyLiebAlgebra(3)" data-allow-mismatch="children" /> <notatio-cell value="Diagram([[1, 2], [-1, -2], [3, -3]]) in TemperleyLiebAlgebra(3)" data-allow-mismatch="children" /> <notatio-cell value="Diagram([[1, 2], [-1, -2], [3, -3]]) in SymmetricGroupAlgebra(3)" data-allow-mismatch="children" />

A diagram is also a Show of a StrandDiagram: its points are addresses (a slot and a level, the in side at level 0), its strands are blocks, and a click picks them. Click a strand and the strands that cross it light up red, and the strand itself gold; shift-click to pick several.

#Click a strand

Crosses(Selected) lights the strands crossing the pick; SameBlock(Selected) the block it is in. The cup and cap on the right cross nothing.

source

<Show Variables="[_s -> Variable(Automatic, [])]" Selection="_s" ImageSize="[Automatic, 240]">
  <StrandDiagram
    ColorRules="[Crosses(Selected) -> Red, SameBlock(Selected) -> Gold, True -> Gray]"
    BoundaryStyle="[
      Crosses(Selected) -> Directive(Red, AbsoluteThickness(3)),
      SameBlock(Selected) -> Directive(Gold, AbsoluteThickness(3)),
      True -> Directive(Teal, AbsoluteThickness(1.8))
    ]"
  >
    <Diagram>
      <ToExpression value="[[1, -3], [2, -1], [3, -2], [4, 5], [-4, -5]]" />
    </Diagram>
  </StrandDiagram>
</Show>

A block of three points is a partition diagram and nothing smaller — Brauer and below admit only blocks of size two.

#Bigger blocks leave the matchings behind

In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2, -1\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack, \bigl\lbrack-2\bigr\rbrack\bigr\rbrack)∈\mathrm{PartitionAlgebra}(3)$Out$\mathrm{True}$In$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2, -1\bigr\rbrack, \bigl\lbrack3, -3\bigr\rbrack, \bigl\lbrack-2\bigr\rbrack\bigr\rbrack)∈\mathrm{BrauerAlgebra}(3)$Out$\mathrm{False}$

source · editable

<graphics-box class="inline-figure" value='Show(StrandDiagram(Diagram([[1, 2, -1], [3, -3], [-2]])), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" style='{"width":"77px"}' /> <notatio-cell value="Diagram([[1, 2, -1], [3, -3], [-2]]) in PartitionAlgebra(3)" data-allow-mismatch="children" /> <notatio-cell value="Diagram([[1, 2, -1], [3, -3], [-2]]) in BrauerAlgebra(3)" data-allow-mismatch="children" />

The orbit basis

The diagram basis $d_λ$ is the obvious one — one element per set partition — but it is not the one the partition algebra's representation theory is written in. That is the orbit basis $x_λ$, and the difference is a quantifier:

$d_λ$ asks for those points to be connected. $x_λ$ asks for them to be connected and nothing else.

So a diagram is the union of the orbits that refine it, and the two bases are related by summing over the partition lattice and inverting:

$$d_λ = \sum_{μ \succeq λ} x_μ, \qquad x_λ = \sum_{μ \succeq λ} μ_Π(λ, μ)\, d_μ .$$

#A quantifier, as a change of basis

The coarsest partition has nothing above it, so the two bases agree there.

In$\mathrm{InOrbitBasis}(\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack))$Out$\mathrm{OrbitDiagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack)+\mathrm{OrbitDiagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack)$In$\mathrm{InDiagramBasis}(\mathrm{OrbitDiagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack))$Out$\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack)-\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack)$In$\mathrm{InOrbitBasis}(\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack))$Out$\mathrm{OrbitDiagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack)$In$\mathrm{DiagramCoarsenings}(\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack))$Out$\bigl\lbrack\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack\bigr\rbrack)\bigr\rbrack$

source · editable

<notatio-cell value="InOrbitBasis(Diagram([[1], [-1]]))" data-allow-mismatch="children" /> <notatio-cell value="InDiagramBasis(OrbitDiagram([[1], [-1]]))" data-allow-mismatch="children" /> <notatio-cell value="InOrbitBasis(Diagram([[1, -1]]))" data-allow-mismatch="children" /> <notatio-cell value="DiagramCoarsenings(Diagram([[1], [-1]]))" data-allow-mismatch="children" />

The Möbius function is the partition lattice's, not the Boolean one's:

$$μ_Π(λ, μ) = \prod_{B ∈ μ} (-1)^{k_B - 1} (k_B - 1)!,$$

with $k_B$ the number of $λ$-blocks inside the block $B$. That is worth setting beside the Hopf-algebra bases, which come from the same kind of inversion over the Boolean lattice, where the Möbius function is only a sign. The factorials here are the difference between merging any set of blocks and merging only adjacent ones — and they are checked against the recursion $\sum_{λ ≤ ν ≤ μ} μ_Π(λ,ν) = 0$ rather than taken on faith.

#Möbius over the partition lattice

Merging four points into one block: (−1)³·3! = −6. Coarsening is partitioning the blocks, so there are Bell(4) = 15 ways.

In$\mathrm{PartitionMobius}(\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1\bigr\rbrack, \bigl\lbrack2\bigr\rbrack, \bigl\lbrack-1\bigr\rbrack, \bigl\lbrack-2\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, 2, -1, -2\bigr\rbrack\bigr\rbrack))$Out$-6$In$\mathrm{PartitionMobius}(\mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack), \mathrm{Diagram}(\bigl\lbrack\bigl\lbrack1, -1\bigr\rbrack\bigr\rbrack))$Out$1$In$\mathrm{BellNumber}(4)$Out$15$

source · editable

<notatio-cell value="PartitionMobius(Diagram([[1], [2], [-1], [-2]]), Diagram([[1, 2, -1, -2]]))" data-allow-mismatch="children" /> <notatio-cell value="PartitionMobius(Diagram([[1, -1]]), Diagram([[1, -1]]))" data-allow-mismatch="children" /> <notatio-cell value="BellNumber(4)" data-allow-mismatch="children" />

What the orbit basis buys is a statement that has no clean form in the diagram basis at all: the map onto the centraliser algebra of the symmetric group acting on $V^{⊗ n}$ kills $x_λ$ exactly when $λ$ has more blocks than $δ$. Specialising the loop parameter to an integer therefore just deletes basis elements — which is why the subject is written in $x$.

Things worth knowing

The loop parameter is a free symbol. These algebras are defined over $\mathbb{Z}[δ]$, so a product returns a $δ$-power times a diagram and leaves $δ$ alone. Substitute a value when you want one — at $δ = 1$ the Brauer algebra degenerates, and the interesting representation theory lives at special values.

A diagram must partition all $2n$ points. Diagram([[1,-1],[2]]) is missing $-2$, so it is malformed and is left exactly as written rather than read as having an implicit singleton. Diagrams also normalise: blocks come back in canonical order, so a written diagram and a computed one are the same expression.

Two libraries, one set of heads. Basis, AlgebraDimension and Element are the members of a FiniteDimensionalAlgebra protocol, and each family's type conforms to it: TemperleyLiebAlgebra(4) is a diagram_algebra, CliffordAlgebra(3) a clifford_algebra, and the heads dispatch on the type. That is what lets the diagram algebras and the hypercomplex units live on one engine, and what makes adding a third family a matter of declaring one conformance.

What is not here yet. Representation theory: the cell / standard modules, the semisimplicity criteria (which fail at special δ), and the Jones basic construction. The Jones polynomial via the Temperley–Lieb trace is the obvious next thing to build, and it would tie these diagrams to the knot-theory side of the catalogue.