🔢 mathematics

Faithful linear and relational representations of diagram categories and monoids

This paper establishes faithful involutive tensor representations of the partition category and related diagram categories using zero-one matrices over idempotent semirings, proving that dimensions based on powers of two are minimal and leveraging floating component counts to construct representations for twisted variants, while also providing lower-dimensional representations for Brauer and Temperley–Lieb categories.

Original authors: James East, Marianne Johnson, Mark Kambites

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: James East, Marianne Johnson, Mark Kambites

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a set of building blocks. These aren't just simple bricks; they are complex shapes made of strings connecting dots. In the world of mathematics, these are called diagrams. They are used to represent how things connect, split, or merge. Mathematicians have been studying these for decades because they appear in physics, biology, and computer science.

The paper you are asking about is like a new, highly efficient instruction manual for translating these complex string diagrams into a language that computers and algebraists love: matrices (grids of numbers).

Here is the breakdown of what the authors, James East, Marianne Johnson, and Mark Kambites, have discovered, explained simply.

1. The Problem: Too Many Ways to Connect

Think of a Partition as a way of grouping people at a party. You might have a group of three people chatting in the corner, two people talking elsewhere, and one person standing alone.

The Old Way: To study these groupings, mathematicians often used "transformation representations." Imagine trying to describe the party by listing every single person and exactly who they are talking to. This works, but it gets huge very quickly. For a party of $n$ people, the description size explodes.
The Goal: The authors wanted to find a "shorthand" or a more compact way to describe these groupings using matrices (grids of 0s and 1s) without losing any information. They wanted the smallest possible grid that still tells the whole story.

2. The Big Discovery: The "Power of 2" Magic

The authors found a brilliant way to turn any partition diagram into a grid of 0s and 1s.

The Trick: Instead of looking at the people (dots) directly, they look at all possible groups (subsets) of people. If you have 3 people, there are $2^3 = 8$ possible groups (nobody, just person A, just B, A and B, etc.).
The Result: They proved that you can represent the entire system of these diagrams using a grid of size $2^n \times 2^n$ .
Why it's special: They showed that this size ( $2^n$ $2^{n}$ ) is the absolute minimum possible if you want to keep two important features:
1. Faithfulness: The grid must tell the difference between every single unique diagram. No two different diagrams can look the same in the grid.
2. Involutive & Tensor: The grid must respect the "mirror image" nature of the diagrams (flipping them upside down) and how you can stack two diagrams side-by-side.

Analogy: Imagine trying to describe a complex knot. The old way was to list every inch of the rope. The new way is to take a photo of the knot from a specific angle that captures the whole shape in a single, compact image. The authors proved that their "photo" is the smallest possible image that still lets you reconstruct the knot perfectly.

3. The "Floating" Secret

One of the most interesting parts of their discovery is how they handle "floating components."

When you connect two diagrams together (like snapping two Lego structures), sometimes a piece of string gets trapped in the middle, disconnected from the top or bottom.
The authors' matrices are clever enough to count these "floating" pieces automatically. The number of floating pieces changes the math inside the grid. This allows them to create a new kind of "twisted" version of these diagrams, which is useful for more complex mathematical structures.

4. Smaller Grids for Special Cases

The authors didn't stop at the general case. They looked at two famous, simpler types of diagrams:

The Brauer Category: Here, every connection must be a pair (like dance partners).
The Temperley-Lieb Category: Here, the connections cannot cross over each other (like a non-tangled necklace).

For these specific types, they found even smaller grids!

For the Temperley-Lieb diagrams, the size of the grid follows the Fibonacci sequence (1, 1, 2, 3, 5, 8...). This is much smaller than the $2^n$ power of 2.
Analogy: If the general rule is "you need a 100-page book to describe the story," they found that for the "no-crossing" stories, you only need a 13-page booklet, and for the "pairing" stories, you need a 50-page booklet.

5. What This Means (According to the Paper)

The paper is purely about mathematical representation.

They have built a "dictionary" that translates diagram language into matrix language.
They proved this dictionary is the most efficient one possible for certain rules.
They showed that for specific, simpler types of diagrams, you can use an even more efficient dictionary (Fibonacci numbers).

What they did NOT claim:

They did not claim this solves a specific physics problem today.
They did not claim this will immediately improve computer algorithms (though it might help in the future).
They did not claim this works for every possible mathematical ring (they had to use specific types of number systems called "semirings" to make the math work).

Summary

Think of this paper as the invention of a super-compressed file format for mathematical diagrams.

Before: You needed a massive, clumsy file to save the data.
Now: They found a way to zip it down to the smallest size theoretically possible without losing a single bit of information.
Bonus: For certain types of diagrams (the non-crossing ones), they found an even better compression algorithm based on the famous Fibonacci numbers.

This gives mathematicians a powerful new tool to study these structures, knowing they are working with the most efficient representation possible.

Technical Summary: Faithful Linear and Relational Representations of Diagram Categories and Monoids

Problem Statement
Diagram algebras and monoids (such as the partition, Brauer, and Temperley–Lieb algebras) are fundamental structures in mathematics and physics, arising in statistical mechanics, knot theory, and representation theory. While these structures are well-understood combinatorially, their linear representations—specifically faithful matrix representations over rings and semirings—have historically been studied with a focus on transformation representations. Transformation representations (actions on sets) often yield high degrees (dimensions), such as the partition monoid $P_n$ having a transformation degree related to Bell numbers.

The central problem addressed in this work is the construction of faithful linear representations of diagram categories and monoids that are significantly more efficient (lower dimension) than their transformation counterparts. Furthermore, the authors seek representations that preserve the rich algebraic structure of these objects, specifically the involution (dagger structure) and the tensor product (monoidal structure), which are often lost in standard transformation representations.

Methodology
The authors develop a unified framework for representing diagram categories as categories of matrices over semirings. The methodology proceeds through the following steps:

Definition of the Mapping: For the partition category $\mathcal{P}$ , the authors define a mapping $\phi: \mathcal{P} \to \mathcal{M}(K)$ , where $K$ is a unital semiring. For a partition $a \in \mathcal{P}_{m,n}$ , the image $\hat{a}$ is a $2^m \times 2^n$ zero-one matrix. The rows and columns are indexed by the subsets of $[m]$ and $[n]$ , respectively. The entry $\hat{a}_{X,Y}$ is $1$ if and only if the set $X \cup Y'$ is a union of blocks of the partition $a$ , and $0$ otherwise.
Analysis of Composition: The core technical challenge is determining when this mapping preserves composition. The product of two partitions $a$ and $b$ involves a "product graph" $\Pi(a,b)$ . The authors introduce the concept of intertwining sets (subsets $Z \subseteq [n]$ such that $X \cup Z'$ is a union of $a$ -blocks and $Z \cup Y'$ is a union of $b$ -blocks). They prove that the number of such sets for a given pair $(X,Y)$ is exactly $2^{\Phi(a,b)}$ , where $\Phi(a,b)$ is the number of "floating components" (connected components of $\Pi(a,b)$ lying entirely in the middle row) in the product graph.
Semiring Constraints: The mapping $\phi$ is shown to be a category morphism if and only if the semiring $K$ is additively idempotent (i.e., $1+1=1$ ). In such semirings, the sum of $2^{\Phi(a,b)}$ ones collapses to $1$, ensuring that the matrix product $\hat{a}\hat{b}$ correctly reflects the partition product $ab$.
Extension to Twisted Categories: The authors adapt this construction to twisted partition categories ( $\mathcal{P}_\Phi$ ) and $d$ -twisted categories ( $\mathcal{P}_{\Phi,d}$ ). By introducing scalar factors (powers of 2) and working over rings of specific characteristics (characteristic 0 or $2d+1$ ), they construct faithful representations that account for the twisting parameters.
Reduction for Subcategories: For the Brauer ( $\mathcal{B}$ ) and Temperley–Lieb ( $\mathcal{TL}$ ) categories, the authors exploit structural properties (such as block sizes and planarity) to reduce the matrix dimensions. They identify specific subsets of indices (e.g., subsets of odd cardinality for Brauer, "even-gap" subsets for Temperley–Lieb) that allow for faithful representations in strictly smaller dimensions than the general partition case.

Key Contributions and Results

Faithful Involutive Tensor Representation of $\mathcal{P}$ : The main result (Theorem 3.11) establishes that for any non-trivial additively idempotent semiring $K$ , the map $\phi$ is a faithful, involutive, tensor category representation of the partition category $\mathcal{P}$ into the matrix category $\mathcal{M}(K)$ . The dimension of the image of the endomorphism monoid $\mathcal{P}_n$ is $2^n$ .
Minimality of Dimensions: The authors prove (Theorem 3.14) that for any faithful involutive tensor representation of $\mathcal{P}$ , $\mathcal{B}$ , or $\mathcal{TL}$ over any unital semiring, the dimension of the image of $\mathcal{C}_n$ must be of the form $d^n$ for some integer $d \ge 2$ . Thus, the $2^n$ dimension achieved by their construction is minimal for the partition category.
Twisted Representations: The paper provides faithful representations for twisted partition categories $\mathcal{P}_\Phi$ over characteristic 0 semirings (Theorem 4.1) and $d$ -twisted categories $\mathcal{P}_{\Phi,d}$ over rings of characteristic $2d+1$ (Theorem 4.3). These representations encode the floating component counts via scalar factors.
Reduced Representations for $\mathcal{B}$ and $\mathcal{TL}$ :
- For the Brauer category $\mathcal{B}$ , the authors construct faithful representations on the odd-degree subcategory $\mathcal{B}_{odd}$ with dimensions $2^{n-1}$ (Theorem 5.2).
- For the Temperley–Lieb category $\mathcal{TL}$ , the authors construct a faithful representation where the dimension of the image of $\mathcal{TL}_n$ is the $n$ -th Fibonacci number, $f_n$ (Theorem 6.14). This is achieved by restricting the matrix indices to "even-gap" subsets.
Connection to Diagram Algebras: The paper investigates the relationship between these category representations and the classical linear diagram algebras (e.g., $P_n(K, \delta)$ ). While the representation of the linear partition category $P(K, 2)$ is not faithful (Example 7.2), the restriction to the Temperley–Lieb algebra $TL(K, 2)$ is shown to be faithful (Theorem 7.4), recovering known Brauer representations as a special case.

Significance and Claims
The paper claims that its primary contribution is the construction of minimal faithful involutive tensor representations for diagram categories over idempotent semirings.

Efficiency: The representations are significantly more efficient than transformation representations. For instance, the transformation degree of $P_n$ grows roughly as $B(n)$ (Bell numbers), whereas the matrix dimension here is $2^n$ .
Structural Preservation: Unlike transformation representations, these matrix representations preserve the involution (as matrix transposition) and the tensor structure (as Kronecker product), retaining algebraic information lost in other approaches.
Combinatorial Insight: The construction reveals a deep connection between the algebraic structure of diagram monoids and the combinatorics of "floating components" in product graphs. The number of floating components directly dictates the scalar factors required for twisted representations.
Open Questions: The authors modestly note that while the dimensions are minimal for tensor-preserving representations, it remains an open question whether smaller faithful representations exist if the tensor structure is not required (Question 8.1 and 8.2). They also highlight the difficulty of determining effective dimensions for specific monoids over arbitrary rings computationally for large $n$ .

In summary, the paper provides a rigorous, unified, and optimal (within the class of tensor-preserving representations) linear framework for studying diagram categories, bridging combinatorial diagram theory with linear algebra over semirings.