8c. Meanders, trace

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

Let us discuss now the positivity property of the Temperley-Lieb trace, constructed as indicated in Theorem 8.21. This is something quite subtle, which in the operator algebra context, that of the original paper of Jones , comes for free, or almost, and more on this in chapter 16 below. In the meantime, we will present a more pedestrian approach to the question, based on pure combinatorics, due to Di Francesco .

The positivity will come from a systematic study of the partitions. Let us start with:

Definition

Let [math]P(k)[/math] be the set of partitions of [math]\{1,\ldots,k\}[/math], and [math]\pi,\sigma\in P(k)[/math].

• We write [math]\pi\leq\sigma[/math] if each block of [math]\pi[/math] is contained in a block of [math]\sigma[/math].
• We let [math]\pi\vee\sigma\in P(k)[/math] be the partition obtained by superposing [math]\pi,\sigma[/math].

Also, we denote by [math]|.|[/math] the number of blocks of the partitions [math]\pi\in P(k)[/math].

As an illustration here, at [math]k=2[/math] we have [math]P(2)=\{||,\sqcap\}[/math], and we have:

[[math]] ||\leq\sqcap [[/math]]

Also, at [math]k=3[/math] we have [math]P(3)=\{|||,\sqcap|,\sqcap\hskip-3.2mm{\ }_|\,,|\sqcap,\sqcap\hskip-0.7mm\sqcap\}[/math], and the order relation is as follows:

[[math]] |||\ \leq\ \sqcap|\ ,\ \sqcap\hskip-3.2mm{\ }_|\ ,\ |\sqcap\ \leq\ \sqcap\hskip-0.7mm\sqcap [[/math]]

In order to study the Gram matrix [math]G_k(\pi,\sigma)=N^{|\pi\vee\sigma|}[/math], and more specifically to compute its determinant, we will use several standard facts about the partitions. We have:

Definition

The Möbius function of any lattice, and so of [math]P[/math], is given by

[[math]] \mu(\pi,\sigma)=\begin{cases} 1&{\rm if}\ \pi=\sigma\\ -\sum_{\pi\leq\tau \lt \sigma}\mu(\pi,\tau)&{\rm if}\ \pi \lt \sigma\\ 0&{\rm if}\ \pi\not\leq\sigma \end{cases} [[/math]]

with the construction being performed by recurrence.

As an illustration here, for [math]P(2)=\{||,\sqcap\}[/math], we have by definition:

[[math]] \mu(||,||)=\mu(\sqcap,\sqcap)=1 [[/math]]

Also, [math]|| \lt \sqcap[/math], with no intermediate partition in between, so we obtain:

[[math]] \mu(||,\sqcap)=-\mu(||,||)=-1 [[/math]]

Finally, we have [math]\sqcap\not\leq||[/math], and so we have as well the following formula:

[[math]] \mu(\sqcap,||)=0 [[/math]]

Thus, as a conclusion, we have computed the Möbius matrix [math]M_2(\pi,\sigma)=\mu(\pi,\sigma)[/math] of the lattice [math]P(2)=\{||,\sqcap\}[/math], the formula being as follows:

[[math]] M_2=\begin{pmatrix}1&-1\\ 0&1\end{pmatrix} [[/math]]

Back to the general case now, the main interest in the Möbius function comes from the Möbius inversion formula, which states that the following happens:

[[math]] f(\sigma)=\sum_{\pi\leq\sigma}g(\pi)\quad \implies\quad g(\sigma)=\sum_{\pi\leq\sigma}\mu(\pi,\sigma)f(\pi) [[/math]]

In linear algebra terms, the statement and proof of this formula are as follows:

Theorem

The inverse of the adjacency matrix of [math]P(k)[/math], given by

[[math]] A_k(\pi,\sigma)=\begin{cases} 1&{\rm if}\ \pi\leq\sigma\\ 0&{\rm if}\ \pi\not\leq\sigma \end{cases} [[/math]]

is the Möbius matrix of [math]P[/math], given by [math]M_k(\pi,\sigma)=\mu(\pi,\sigma)[/math].

Show Proof

This is well-known, coming for instance from the fact that [math]A_k[/math] is upper triangular. Indeed, when inverting, we are led into the recurrence from Definition 8.23.

■

Now back to our Gram matrix considerations, we have the following key result:

Proposition

The Gram matrix [math]G_{\pi\sigma}=N^{|\pi\vee\sigma|}[/math] decomposes as a product of upper/lower triangular matrices, [math]G_k=A_kL_k[/math], where

[[math]] L_k(\pi,\sigma)= \begin{cases} N(N-1)\ldots(N-|\pi|+1)&{\rm if}\ \sigma\leq\pi\\ 0&{\rm otherwise} \end{cases} [[/math]]

and where [math]A_k[/math] is the adjacency matrix of [math]P(k)[/math].

Show Proof

We have indeed the following computation:

[[math]] \begin{eqnarray*} G_k(\pi,\sigma) &=&N^{|\pi\vee\sigma|}\\ &=&\#\left\{i_1,\ldots,i_k\in\{1,\ldots,N\}\Big|\ker i\geq\pi\vee\sigma\right\}\\ &=&\sum_{\tau\geq\pi\vee\sigma}\#\left\{i_1,\ldots,i_k\in\{1,\ldots,N\}\Big|\ker i=\tau\right\}\\ &=&\sum_{\tau\geq\pi\vee\sigma}N(N-1)\ldots(N-|\tau|+1) \end{eqnarray*} [[/math]]

According now to the definition of [math]A_k,L_k[/math], this formula reads:

[[math]] \begin{eqnarray*} G_k(\pi,\sigma) &=&\sum_{\tau\geq\pi}L_k(\tau,\sigma)\\ &=&\sum_\tau A_k(\pi,\tau)L_k(\tau,\sigma)\\ &=&(A_kL_k)(\pi,\sigma) \end{eqnarray*} [[/math]]

Thus, we are led to the formula in the statement.

■

As an illustration for the above result, at [math]k=2[/math] we have [math]P(2)=\{||,\sqcap\}[/math], and the above decomposition [math]G_2=A_2L_2[/math] appears as follows:

[[math]] \begin{pmatrix}N^2&N\\ N&N\end{pmatrix} =\begin{pmatrix}1&1\\ 0&1\end{pmatrix} \begin{pmatrix}N^2-N&0\\N&N\end{pmatrix} [[/math]]

We are led in this way to the following formula, due to Lindstöm :

Theorem

The determinant of the Gram matrix [math]G_k[/math] is given by

[[math]] \det(G_k)=\prod_{\pi\in P(k)}\frac{N!}{(N-|\pi|)!} [[/math]]

with the convention that in the case [math]N \lt k[/math] we obtain [math]0[/math].

Show Proof

If we order [math]P(k)[/math] as usual, with respect to the number of blocks, and then lexicographically, [math]A_k[/math] is upper triangular, and [math]L_k[/math] is lower triangular. Thus, we have:

[[math]] \begin{eqnarray*} \det(G_k) &=&\det(A_k)\det(L_k)\\ &=&\det(L_k)\\ &=&\prod_\pi L_k(\pi,\pi)\\ &=&\prod_\pi N(N-1)\ldots(N-|\pi|+1) \end{eqnarray*} [[/math]]

Thus, we are led to the formula in the statement.

■

Getting now to what we wanted to do, namely computation of the Gram determinant for the lattice of noncrossing pairings, which will provide us with the desired positivity properties of the Temperley-Lieb trace, let us begin with some examples. We will need:

Proposition

We have a bijection [math]NC(k)\simeq NC_2(2k)[/math], constructed by fattening and shrinking, as follows:

• The application [math]NC(k)\to NC_2(2k)[/math] is the “fattening” one, obtained by doubling all the legs, and doubling all the strings too.
• Its inverse [math]NC_2(2k)\to NC(k)[/math] is the “shrinking” application, obtained by collapsing pairs of consecutive neighbors.

Show Proof

This is something self-explanatory, and in order to see how this works, let us discuss an example. Consider a noncrossing partition, say the following one:

[[math]] \xymatrix@R=10pt@C=10pt{ \ar@{-}[rrrrrrr]&&&&&&&\\ &\ar@{-}[rr]&&&&\ar@{-}[r]&&\\ 1\ar@{-}[uu]&2\ar@{-}[u]&3\ar@{-}[u]&4\ar@{-}[u]&5\ar@{-}[uu]&6\ar@{-}[u]&7\ar@{-}[u]&8\ar@{-}[uu] } [[/math]]

Now let us “fatten” this partition, by doubling everything, as follows:

[[math]] \xymatrix@R=10pt@C=10pt{ \ar@{=}[rrrrrrr]&&&&&&&\\ &\ar@{=}[rr]&&&&\ar@{=}[r]&&\\ 11'\ar@{=}[uu]&22'\ar@{=}[u]&33'\ar@{=}[u]&44'\ar@{=}[u]&55'\ar@{=}[uu]&66'\ar@{=}[u]&77'\ar@{=}[u]&88'\ar@{=}[uu] } [[/math]]

Now by relabeling the points [math]1,\ldots,16[/math], what we have is indeed a noncrossing pairing. As for the reverse operation, that is obviously obtained by “shrinking” our pairing, by collapsing pairs of consecutive neighbors, that is, by identifying [math]1=2[/math], then [math]3=4[/math], then [math]5=6[/math], and so on, up to [math]15=16[/math]. Thus, we are led to the conclusion in the statement.

■

At the level of the associated Gram matrices, the result is as follows:

Proposition

The Gram matrices of [math]NC_2(2k)\simeq NC(k)[/math] are related by

[[math]] G_{2k,n}(\pi,\sigma)=n^k(\Delta_{kn}^{-1}G_{k,n^2}\Delta_{kn}^{-1})(\pi',\sigma') [[/math]]

where [math]\pi\to\pi'[/math] is the shrinking operation, and [math]\Delta_{kn}[/math] is the diagonal of [math]G_{kn}[/math].

Show Proof

In the context of the bijection from Proposition 8.27, we have:

[[math]] |\pi\vee\sigma|=k+2|\pi'\vee\sigma'|-|\pi'|-|\sigma'| [[/math]]

We therefore have the following formula, valid for any [math]n\in\mathbb N[/math]:

[[math]] n^{|\pi\vee\sigma|}=n^{k+2|\pi'\vee\sigma'|-|\pi'|-|\sigma'|} [[/math]]

Thus, we are led to the formula in the statement.

■

Getting back now to our business, namely computation of the Gram determinant for the lattice of noncrossing pairings, we first have the following elementary result:

Proposition

The first Gram matrices and determinants for [math]NC_2[/math] are

[[math]] \det\begin{pmatrix}N^2&N\\N&N^2\end{pmatrix}=N^2(N^2-1) [[/math]]

[[math]] \det\begin{pmatrix} N^3&N^2&N^2&N^2&N\\ N^2&N^3&N&N&N^2\\ N^2&N&N^3&N&N^2\\ N^2&N&N&N^3&N^2\\ N&N^2&N^2&N^2&N^3 \end{pmatrix}=N^5(N^2-1)^4(N^2-2) [[/math]]

with the matrices being written by using the lexicographic order on [math]NC_2(2k)[/math].

Show Proof

The formula at [math]k=2[/math], where [math]NC_2(4)=\{\sqcap\sqcap,\bigcap\hskip-4.9mm{\ }_\cap\,\}[/math], is clear. At [math]k=3[/math] however, things are tricky. We have [math]NC(3)=\{|||,\sqcap|,\sqcap\hskip-3.2mm{\ }_|\,,|\sqcap,\sqcap\hskip-0.7mm\sqcap\}[/math], and the corresponding Gram matrix and its determinant are, according to Theorem 8.26:

[[math]] \det\begin{pmatrix} N^3&N^2&N^2&N^2&N\\ N^2&N^2&N&N&N\\ N^2&N&N^2&N&N\\ N^2&N&N&N^2&N\\ N&N&N&N&N \end{pmatrix}=N^5(N-1)^4(N-2) [[/math]]

By using Proposition 8.28, the Gram determinant of [math]NC_2(6)[/math] is given by:

[[math]] \begin{eqnarray*} \det(G_{6N}) &=&\frac{1}{N^2\sqrt{N}}\times N^{10}(N^2-1)^4(N^2-2)\times\frac{1}{N^2\sqrt{N}}\\ &=&N^5(N^2-1)^4(N^2-2) \end{eqnarray*} [[/math]]

Thus, we have obtained the formula in the statement.

■

In general, such tricks won't work, because [math]NC(k)[/math] is strictly smaller than [math]P(k)[/math] at [math]k\geq4[/math]. However, following Di Francesco , we have the following result:

Theorem

The determinant of the Gram matrix for [math]NC_2[/math] is given by

[[math]] \det(G_{kN})=\prod_{r=1}^{[k/2]}P_r(N)^{d_{k/2,r}} [[/math]]

where [math]P_r[/math] are the Chebycheff polynomials, given by

[[math]] P_0=1\quad,\quad P_1=X\quad,\quad P_{r+1}=XP_r-P_{r-1} [[/math]]

and [math]d_{kr}=f_{kr}-f_{k,r+1}[/math], with [math]f_{kr}[/math] being the following numbers, depending on [math]k,r\in\mathbb Z[/math],

[[math]] f_{kr}=\binom{2k}{k-r}-\binom{2k}{k-r-1} [[/math]]

with the convention [math]f_{kr}=0[/math] for [math]k\notin\mathbb Z[/math].

Show Proof

This is something quite technical, obtained by using a decomposition as follows of the Gram matrix [math]G_{kN}[/math], with the matrix [math]T_{kN}[/math] being lower triangular:

[[math]] G_{kN}=T_{kN}T_{kN}^t [[/math]]

Thus, a bit as in the proof of the Lindstöm formula, we obtain the result, but the problem lies however in the construction of [math]T_{kN}[/math], which is non-trivial. See .

■

Let us record as well the following result, also from Di Francesco :

Theorem

The determinant of the Gram matrix for [math]NC[/math] is given by

[[math]] \det(G_{kN})=(\sqrt{N})^{a_k}\prod_{r=1}^kP_r(\sqrt{N})^{d_{kr}} [[/math]]

where [math]P_r[/math] are the Chebycheff polynomials, given by

[[math]] P_0=1\quad,\quad P_1=X\quad,\quad P_{r+1}=XP_r-P_{r-1} [[/math]]

and [math]d_{kr}=f_{kr}-f_{k,r+1}[/math], with [math]f_{kr}[/math] being the following numbers, depending on [math]k,r\in\mathbb Z[/math],

[[math]] f_{kr}=\binom{2k}{k-r}-\binom{2k}{k-r-1} [[/math]]

with the convention [math]f_{kr}=0[/math] for [math]k\notin\mathbb Z[/math], and where [math]a_k=\sum_{\pi\in P(k)}(2|\pi|-k)[/math].

Show Proof

This follows indeed from Theorem 8.30, by using Proposition 8.28.

■

We refer to the literature for more on the above, which is first class combinatorics.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].