Temperley–Lieb Diagram Algebra and Catalan Basis

Take basis diagrams $D:m\to n$ and $E:n\to p$. After identifying the intermediate boundary points, every glued interior point has degree two and every exterior endpoint has degree one. Each connected component is therefore a path with two exterior endpoints or a closed cycle. Keeping the paths and deleting the cycles produces a matching of the exterior labels. The glued arcs are disjoint in the stacked rectangle, so their path components are a representative of a noncrossing pairing; hence the output is again a basis diagram. The number of cycles is the number of cycle components of this finite graph, independent of how its arcs are drawn. Thus the rule is well defined on pairings, and the free-module bases in [F1] give a unique $R$-bilinear extension.

For basis diagrams $A:m\to n$, $B:n\to p$, and $C:p\to q$, glue all three layers at once. The resulting graph has the same exterior paths and the same total number of cycle components regardless of whether the first interface or the second interface is glued first. Any cycle already removed after composing $B\circ A$ is a component disjoint from the remaining interface, so it contributes one factor $\delta$ in either parenthesization and cannot reconnect to $C$. Hence $(C\circ B)\circ A=C\circ (B\circ A)$ on basis diagrams; $R$-bilinearity gives associativity on all morphisms.

Gluing the vertical matching $1_n$ to either boundary of a diagram creates no cycle and leaves every exterior pair unchanged. Thus $1_n\circ D=D=D\circ 1_m$ for each basis diagram $D:m\to n$, and then for every morphism by bilinearity.

Horizontal juxtaposition of basis diagrams is a noncrossing pairing and extends bilinearly by [F3]. For composable pairs of basis diagrams, the two sides of the bifunctor composition law are the same disjoint union of the two stacked graphs; their cycle counts add, so their products agree. Juxtaposition of vertical identity matchings is the vertical identity on the summed object, so juxtaposition preserves identities. By [F5], it is a bifunctor.

For three object labels, both bracketings of horizontal juxtaposition have the same left, middle, and right blocks: the total size is $(m+m^{\mathrm{\prime }})+m^{\mathrm{\prime }\mathrm{\prime }}=m+(m^{\mathrm{\prime }}+m^{\mathrm{\prime }\mathrm{\prime }})$ by [F9], while the middle block starts at offset $m$ and the right block at offset $m+m^{\mathrm{\prime }}$ in both bracketings. The same offsets label the boundary points of the juxtaposed diagrams, so their pairings are literally equal as well. Juxtaposition with the empty $0$-diagram changes neither labels nor matchings. The associator and unitors therefore have identity components between strictly equal functors. For every morphism, their naturality equations reduce to equality of that morphism on both sides; their inverses are themselves identity transformations. The pentagon and triangle equations of [F7] are equalities of identity morphisms, so the category is strict monoidal with unit $0$.

Take the morphism class to be the disjoint union of the modules $M_R(m,n)$, with each element tagged by its source and target, as required in [F4]. Composition and identities satisfy [F4] by steps 1.1, 2.1 and 2.2, so these data form a category. Its tensor bifunctor and unit satisfy [F7] by steps 3.1–4.1. For each $n$, define $\eta (r)=r{1}_n$. Module addition gives $\eta (r+s)=\eta (r)+\eta (s)$; bilinearity and $1_n{1}_n=1_n$ give $\eta (rs)=(rs)1_n=(r{1}_n)(s{1}_n)$; and $\eta (1_R)=1_n$. For every $x\in \mathrm{End}(n)$, $(r{1}_n)x=r(1_{n}x)=rx=x(r{1}_n)$, so $\eta$ is central. The composition laws make $\mathrm{End}(n)$ a unital associative ring; [F8] therefore identifies it as a unital $R$-algebra with the diagram basis stated in [F1].

Read the $2n$ boundary labels in their fixed cyclic order. Given a noncrossing pairing, mark the earlier endpoint of each pair by an opening parenthesis and the later endpoint by a closing parenthesis. The resulting word has equal numbers of each kind. In every prefix, each closing endpoint is paired with an earlier opening endpoint in that prefix, so the number of closes never exceeds the number of opens; hence the word is balanced. This construction also applies at $n=0$, where it gives the empty word.

Conversely, scan a balanced word from left to right, placing each opening position on a stack and pairing each closing position with the most recently placed unmatched opening. At the end the stack is empty because the total numbers agree. The pairs are nested or disjoint, so they do not interlace. For a noncrossing pairing, the same rule recovers its original partners: if a close at position $j$ were paired with an earlier open $i$ while a later open $k$ between them remained unmatched until after $j$, then its eventual partner $l>j$ would give interlacing pairs $\{i,j\}$ and $\{k,l\}$, contrary to [F1]. Thus the two constructions are inverse bijections.

Replace each opening bracket by an up-step and each closing bracket by a down-step. Equality of the bracket counts gives total height zero, and the prefix inequality proved in step 1.1 gives nonnegative prefix heights; hence this is a Dyck path of semilength $n$. Reading its step word recovers the bracket word, so [F3] gives a bijection. By [F2] the bracket-word set is finite of size $C_n$. Composing this bijection with the two inverse constructions in steps 1.1 and 2.1 proves that $\mathcal{D}(n,n)$ is in bijection with Dyck paths and has size $C_n$. The free-module definition in [F1] makes these diagrams a basis of ${\mathrm{T}\mathrm{L}}_n(R,\delta )$; no coefficient is changed in this count.

A monomial is a finite word in $u_1,\dots ,u_{n-1}$. Regard two words related by commuting letters at distance greater than one as equivalent for the moment. Each such commutation class is finite. If a representative has a square $u_i{u}_i$ or a consecutive triple $u_i{u}_{i\pm 1}{u}_i$, use the corresponding relation in [F1]; the generator length drops by one or two. After at most the original length many such drops, the process stops, leaving either zero (if the accumulated scalar is zero) or a word for which no representative under commutations has a square or such a triple. Call the latter word reduced.

Encode $N(j,k)$ by a grid path from $(0,0)$ to $(n,n)$: move east to $x=j_1$, north to $y=k_1$, east to $x=j_2$, north to $y=k_2$, and continue through $(j_r,k_r)$, then move east to $x=n$ and north to $y=n$. For the empty word use east from $(0,0)$ to $(n,0)$ and then north to $(n,n)$. The inequalities $k_i\le j_i$, $j_i<j_{i+1}$ and $k_i<k_{i+1}$ say exactly that this path stays in $y\le x$. Conversely, in any path from $(0,0)$ to $(n,n)$ using east and north steps and staying in $y\le x$, record each positive vertical run whose $x$-coordinate is less than $n$ by its endpoint $(j_i,k_i)$; omit the forced final vertical run at $x=n$. There is no vertical run at $x=0$, every recorded run is preceded by a positive horizontal run, and consecutive recorded coordinates strictly increase in both coordinates. The path condition gives $k_i\le j_i$, while $j_i<n$ and $k_i<n$ by construction. Thus the corners recover exactly one admissible parameter list; if there are no recorded runs, it is the empty word. The parameterization itself has no duplicate formal words: within each block the indices decrease consecutively, while at every block boundary the next index $j_{i+1}$ is strictly greater than the preceding endpoint $k_i$; hence the block boundaries are exactly the strict ascents in the index sequence and uniquely recover all $(j_i,k_i)$. Mapping east to up and north to down sends $x-y$ to the height, so these paths are exactly the Dyck paths in [F2]. This also covers $n=0$, where the path and word are empty.

In a nonempty reduced word with maximal index $m$, that index occurs only once. Prove this by induction on $m$. The case $m=1$ follows from $u_1^2=\delta u_1$. If two consecutive occurrences of $u_m$ surround a nonempty subword $U$, all indices in $U$ are below $m$ and $U$ is reduced. Let $a$ be its maximal index. By induction $u_a$ occurs once in $U$. If $a<m-1$, every letter of $U$ commutes with $u_m$, so the two copies of $u_m$ can be made adjacent and shortened. If $a=m-1$, write $U=A{u}_{m-1}B$ with all letters of $A,B$ below $m-1$; these commute with $u_m$, so the subword $u_{m}U{u}_m$ can be reordered to $A{u}_m{u}_{m-1}{u}_{m}B$ and shortened by the adjacent triple relation. Either contradicts reducedness. The empty intervening word shortens directly by the square relation.

We now expose a terminal descending block by commutations. Start with the unique maximal letter $u_m$ from step 2.1 and let the current block be $B=u_m$; write the commutation-equivalent word as $U^{\mathrm{\prime }}BV$. More generally, suppose $B=u_m{u}_{m-1}\cdots u_r$ and the remaining tail is $V$. If $V$ contained a letter $u_s$ with $s\ge r$, choose the largest such $s$ and its first occurrence in $V$. The earlier occurrence of $u_s$ lies in $B$, and every letter between these two copies has index below $s$: the part of $B$ after its $u_s$ has indices below $s$, and the chosen tail prefix has no index above $s$ or earlier copy of $u_s$. This intervening subword is reduced. If it is empty, the two $u_s$ give a square. Otherwise let $a<s$ be its maximal index. If $a\le s-2$, every intervening generator commutes with $u_s$, so the two copies can be made adjacent. If $a=s-1$, step 2.1 applied to the intervening subword says that $u_{s-1}$ occurs there exactly once; all its other letters commute with $u_s$, so commutations expose $u_s{u}_{s-1}{u}_s$. Each case contradicts reducedness. Hence every letter in $V$ has index at most $r-1$. If $u_{r-1}$ occurs in $V$, take its first occurrence: every earlier tail letter has index at most $r-2$ and commutes with every letter of $B$, so move those letters before $B$ and append $u_{r-1}$. If $u_{r-1}$ does not occur, every letter of $V$ has index at most $r-2$; move all of them before $B$ and stop. This proves $U=U^{\mathrm{\prime }}B$ with $B=u_m{u}_{m-1}\cdots u_k$ and all indices of the reduced prefix $U^{\mathrm{\prime }}$ below $m$. Induction on the maximal index of $U^{\mathrm{\prime }}$ yields descending consecutive blocks with maxima strictly increasing from left to right. If successive block endpoints had $k_i\ge k_{i+1}$, the next block contains $u_{k_i+1}{u}_{k_i}$ because $j_{i+1}>j_i\ge k_i$. The letters between the preceding $u_{k_i}$ and that $u_{k_i+1}$ have indices at least $k_i+2$, so commute with $u_{k_i}$; this exposes $u_{k_i}{u}_{k_i+1}{u}_{k_i}$, contradicting reducedness. Thus the endpoints also increase, giving the parameters in the Statement.

By [F3], the normal-form set has $C_n$ elements. Step 1.1 reduces every monomial to a scalar multiple of a word, and step 3.1 puts that reduced word into ${\mathcal{N}}_n$. Since every element of $P_n(R,\delta )$ is a finite linear combination of monomials by [F1], the images of ${\mathcal{N}}_n$ span the presented algebra. No division by $\delta$ or other scalar is used.

In the stack $d_i^2$, all strands outside positions $i,i+1$ pass straight through. In the two affected positions, the cup of the upper copy joins to the cap of the lower copy to form exactly one closed cycle; the remaining exterior path connections are the same cap and cup as in $d_i$. The stack rule [F2] therefore gives $d_i^2=\delta d_i$.

Restrict to positions $i,i+1,i+2$ in the stack with upper factor $d_i$, middle factor $d_{i+1}$ and lower factor $d_i$. The upper cap and lower cup are the exterior cap and cup of the result. The remaining path starts at the exterior top point $i+2$: it follows the upper through strand to the first interface, the middle cap to position $i+1$, the upper cup to position $i$, the middle through strand to the second interface, the lower cap to position $i+1$, the middle cup to position $i+2$, and the lower through strand to exterior bottom point $i+2$. Thus the two remaining exterior endpoints are joined exactly as in $d_i$, and all six interface points lie on this path; no closed component is formed. The product is therefore $d_i{d}_{i+1}{d}_i=d_i$. Reflecting this three-position stack horizontally about its middle strand preserves stacking and loop counts while interchanging $d_i$ and $d_{i+1}$, so it gives $d_{i+1}{d}_i{d}_{i+1}=d_{i+1}$.

If $\mathrm{\mid }i-j\mathrm{\mid }>1$, the two cup-cap diagrams modify disjoint pairs of positions. In either stack order, each affected pair has the same cap and cup and every other strand is vertical; no component joins the two disjoint position intervals and no closed cycle forms. Hence the resulting boundary matching is the same and $d_i{d}_j=d_j{d}_i$.

The images $d_i$ satisfy every defining relation of $P_n(R,\delta )$ by steps 1.1–1.3. The quotient universal property in [F4] gives the unique unital $R$-algebra homomorphism ${\pi }_n$ with ${\pi }_n(u_i)=d_i$. For $n=0$ and $n=1$ the generator and relation sets are empty, and the unique map sends the scalar unit to the diagram identity.

For $n=0$ the only diagram is the empty identity; for $n=1$ the only diagram is the single through strand. Both are the empty product of generators. Now let $n\ge 2$. A through strand joins a top point to a bottom point; let $t$ be their number. The other top points are paired into caps and the other bottom points into cups, so there are $p=(n-t)\mathrm{/}2$ caps and $p$ cups. The through strands occur in the same left-to-right order at top and bottom, since a reversed pair of through strands would interlace and violate noncrossing in [F1].

Regard a cap on consecutive positions as one symbol $C$ occupying two positions and a through endpoint as a symbol $T$ occupying one. In each maximal interval with no through endpoints, replace the noncrossing cap matching by consecutive adjacent caps; do the corresponding operation on the bottom cups. This gives a flat diagram with the same through endpoints and the same order-preserving through strands. The baseline product $d_1{d}_3\cdots d_{2p-1}$ has $p$ adjacent caps and cups followed by $t$ through strands, with $p,t$ as in step 1.1. Whenever a top cap at $(i-1,i)$ is followed by a through strand at $i+1$, stacking $d_i$ above that diagram changes the top symbols $CT$ to $TC$: tracing the glued endpoints sends the former through strand to $i-1$ and makes the cap occupy $(i,i+1)$. The cap of the generator and the old through component join into a path meeting the exterior boundary, so no cycle is created. Thus left multiplication by these generators performs each adjacent $CT\mapsto TC$ top swap and leaves the bottom cap/cup pairing unchanged. Sorting from $C^p{T}^t$ to the prescribed top pattern takes finitely many swaps. For the bottom, if a cup at $(i-1,i)$ is followed by a through endpoint at $i+1$, stack $d_i$ below; its top cap joins the old cup path to the through path, moving the through endpoint to $i-1$ and placing the bottom cup at $(i,i+1)$. These are distinct paths, so no cycle forms. Right multiplication therefore performs the corresponding bottom $CT\mapsto TC$ swaps while leaving the top pairing unchanged. Sorting the bottom pattern is finite as well. The resulting flat diagram has both prescribed patterns and the same order-preserving through strands.

It remains to restore each nested cap or cup in the flat diagram of step 2.1. A cap island is the matching on a consecutive interval $i,i+1,\dots ,i+2q-1$ whose endpoints are all paired internally and whose outermost cap joins $i$ to $i+2q-1$; the cup version is defined analogously. In the flat diagram those points have simple caps $(i,i+1),(i+2,i+3),\dots ,(i+2q-2,i+2q-1)$. For $q=1$ no generator is needed. For $q>1$, stacking $d_{i+1}{d}_{i+3}\cdots d_{i+2q-3}$ above them creates the outer cap $(i,i+2q-1)$ and leaves $q-1$ simple caps on the interior endpoints. To verify this, start with the rightmost factor: its glued bottom cup meets endpoints belonging to two distinct cap paths, so their union is a path with exterior endpoints rather than a cycle; it replaces those two adjacent simple caps by one outer cap and one interior simple cap. Each preceding factor performs the same merge with the next simple cap to the left, extending the outer cap by two endpoints while preserving the remaining interior simple caps. Thus no closed component is created at any stage. The reflected product below restores the corresponding bottom cup island by the same path check.

The cap intervals of a noncrossing matching are nested or disjoint, because interlacing pairs are excluded by [F1]. Thus they form a finite nesting forest. Process maximal islands first and then recursively process the smaller islands inside each one; every child interval is strictly shorter than its parent, so induction on interval length terminates. Apply the same construction to top caps and bottom cups. The order-preserving through strands stay fixed, and the final top and bottom pairings are exactly those of $D$. Every step is a stack of one of the $d_i$ and the path checks in steps 2.1 and 3.1 show that it creates no closed cycle.

The homomorphism ${\pi }_n$ is well defined by [F1], and it is surjective by [F2], because its image contains every diagram basis vector.

Let $q:R^{({\mathcal{N}}_n)}\to P_n(R,\delta )$ send the standard basis vector indexed by $N$ to the class of $N$. It is $R$-linear by [F5] and surjective by [F3]. Hence $S:={\pi }_n\circ q:R^{({\mathcal{N}}_n)}\to R^{(\mathcal{D}(n,n))}$ is surjective, using the diagram basis in [F4].

The explicit path encodings in [F3] and [F4] give a bijection between ${\mathcal{N}}_n$ and $\mathcal{D}(n,n)$ by composing the first with the inverse of the second. Both finite free modules in step 2.1 therefore have rank $C_n$. This rank is positive: the identity matching belongs to $\mathcal{D}(n,n)$ by [F10], so [F4] implies $C_n\ge 1$. Order the standard bases by this bijection. For each basis vector $e_N$, the coordinates of $S(e_N)$ are the $N$th column of a matrix $A$; [F5] gives the finite-basis map representation, and [F6] identifies composition with matrix multiplication. Thus $S$ is represented by a square matrix $A$ of size $C_n$.

Step 2.1 established that $S$ is surjective. For each member of the finite basis indexed by $\mathcal{D}(n,n)$, choose one preimage under $S$; only finitely many choices are made. By [F5] these assignments extend linearly to a right inverse $B$ of $S$. With the bases fixed in step 3.1, $B$ is represented by a square matrix and $S\circ B=I_{C_n}$, so $AB=I_{C_n}$.

Taking determinants and using [F7] gives $\det (A)\det (B)=\det (I_{C_n})=1$ by [F9]. Since $R$ is commutative, $\det (B)$ is a two-sided inverse of $\det (A)$, so $\det (A)$ is a unit.

By [F8], $A$ is invertible, hence $S$ is an isomorphism. If $q(x)=0$, then $S(x)=0$ and injectivity of $S$ gives $x=0$; thus the already-surjective $q$ is an isomorphism. For any $y\in P_n(R,\delta )$ with ${\pi }_n(y)=0$, choose $x$ with $q(x)=y$ using surjectivity of $q$; then $S(x)=0$, whence $x=0$ and $y=0$. Thus ${\pi }_n$ is injective as well as surjective, proving the claimed isomorphism and the basis assertion.