$\DeclareMathOperator\SL{SL}$This question came up in a class "Total Positivity and Cluster Algebras" being taught by Chris Fraser.

Let $N^+$ denote the space of uni-upper-triangular matrices in $\SL(n,\mathbb{R})$, and $N^+_{\geq 0} \subseteq \SL_{\geq 0}(n,\mathbb{R})$ the totally nonnegative parts of these spaces.

There are two stratifications of $N^+_{\geq 0}$ that I want to compare.

The first is what I'll call the Catalan stratification. It's the stratification based on the location of nonzero entries for a matrix $M \in N^+_{\geq 0}$, which can easily be seen to necessarily lie below/to the left of a Dyck path. E.g., one stratum in the case $n=5$ is: $$ \begin{pmatrix} 1 & * & * & 0 & 0 \\ 0 & 1 & * & * & 0 \\ 0 & 0 & 1 & * & 0 \\ 0 & 0 & 0 & 1 & * \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$ where the $*$'s denote the nonzero entries. So there are $C_n = \frac{1}{n+1}\binom{2n}{n}$ many strata here, and the closure relation among these strata is just containment of Dyck paths.

The second is more sophisticated; I'll call it the Bruhat stratification. For $1 \leq i \leq n-1$, let $x_i(t)$ denote the matrix with $1$'s along the main diagonal, $t$ in the $i$th spot right above the main diagonal, and $0$'s elsewhere. It's a theorem of Lusztig that for any permutation $w \in S_n$ and any reduced word $(i_1,i_2,\dotsc,i_\ell)$ of $w$, the map $(t_1,\dotsc,t_\ell)\to x_{i_1}(t_1)\dotsb x_{i_\ell}(t_\ell)$ is a homeomorphism of $\mathbb{R}_{>0}^{\ell}$ onto $Y^o_w := B^{-1}wB^{-1} \cap N^+_{\geq 0}$, where $B^-$ are the lower-triangular matrices in $\SL(n,\mathbb{R})$. (See Hersh - Regular cell complexes in total positivity for background on this.) So we have a stratification of $N^+_{\geq 0}$ indexed by permutations in $S_n$, and the closure relations among these strata is the (strong) Bruhat order on these permutations.

Question: Is it true that every Catalan stratum is a union of Bruhat strata? If so, what's the resulting map from permutations to Dyck paths?

I suspect the map from permutations to Dyck paths might be something like the "Cambrian congruences" of Nathan Reading. But I also suspect that this question may have already been studied somewhere.

  • $\begingroup$ Though with the Cambrian congruences you get the Tamari lattice, whereas the Dyck path order is a different thing: it's a distributive lattice. So now I'm not so sure... $\endgroup$ Nov 18, 2020 at 23:05
  • 1
    $\begingroup$ I might be misunderstanding the Bruhat strata, but I don't see how for instance the Catalan stratum with just a single star in the top right corner can contain any Bruhat stratum. $\endgroup$
    – lambda
    Nov 19, 2020 at 1:11
  • 1
    $\begingroup$ Have you tried finding your map using findstat.org/MapFinder?Domain=Cc0001&Codomain=Cc0005 ? $\endgroup$
    – FindStat
    Nov 19, 2020 at 8:22
  • 2
    $\begingroup$ @ChristianStump: okay, I wrote some Sage code (cocalc.com/share/363023871ecc3c464c7e3400be3b647ccf5eba8d/…), and with this was able to generate data for $n=4$, which FindStat said must be the map (findstat.org/MapsDatabase/Mp00127) which sends a permutation to its Dyck path of left-to-right maxima. $\endgroup$ Nov 19, 2020 at 17:28
  • 1
    $\begingroup$ @SamHopkins congratulations! $\endgroup$ Nov 19, 2020 at 17:41

1 Answer 1


The Catalan strata are unions of Bruhat strata, and the resulting map from permutations to Dyck paths is indeed given by taking the left-to-right maxima.

There is a way to parametrize totally nonnegative matrices by writing them as Lindström-Gessel-Viennot matrices for a certain weighted directed graph. This is explained nicely in the first section of "Total positivity: tests and parametrizations", by Fomin and Zelevinsky, where the directed graph is depicted in figure 2. They explain the parametrization for general matrices, but if you want to restrict to uni-upper-triangular ones then simply keep just the part of the graph with blue edges.

This combinatorial picture is then refined to also parametrize $Y^o_w$. They construct a directed graph for every reduced word $(i_1,\dots,i_{\ell})$. See figures 4 and 5, where for your case you only have blue edges.

Now, for every permutation $w$ you have a canonical reduced word of the form $$(m_1,m_1+1,\dots,n_1)(m_2,m_2+1,\dots n_2)\cdots (m_k,m_k+1\dots n_k)$$ where $n\geq n_1>n_2>\cdots >n_k\geq 1$ and $n_i\geq m_i\geq 1$, which is just the first reduced word for $w$ in the reverse lex order. By drawing the associated directed graph we can find out exactly which matrix entries will be nonzero! The $ij$ entry is nonzero if and only if there is a way to travel from source $i$ to sink $j$. This already means that each $Y^o_w$ sits inside a unique Catalan stratum, and therefore each Catalan stratum is a union of Bruhat strata.

In order to get the description of the map from permutations to Dyck paths there are probably many ways to see it. I reasoned as follows: a pair $(m_i,n_i)$ from above is "redundant" if there is some other pair $(m_j,n_j)$ with $n_j>n_i$ and $m_j\le m_i$. Removing all the redundant blocks from the reduced word can be seen not to affect which matrix entries are nonzero, therefore it stays within the same Catalan stratum. This produces a 321 avoiding permutation which has the same convex hull as $w$ from the upper right corner (See corollary 5.8 in "Some Combinatorial Aspects of Reduced Words in Finite Coxeter Groups"). Incidentally, this 321 permutation also represents the lowest dimensional Bruhat cell in the Catalan stratum.

  • $\begingroup$ Terrific! I guess the one further question I might have is whether this LRM map plays nicely with the two partial orders (Bruhat order and the distributive lattice of Dyck paths)- e.g. is it a lattice congruence? But that's a purely combinatorial question, I suppose, independent of the geometry. $\endgroup$ Nov 20, 2020 at 14:58
  • 1
    $\begingroup$ @SamHopkins: Looking at the $S_3$ example on the findstat link given above, we can see that the map is not a lattice homomorphism. There is no lattice congruence on the weak order on $S_3$ that has 4 singleton congruence classes and a class $\{312,321\}$. $\endgroup$ Nov 21, 2020 at 2:05
  • $\begingroup$ @NathanReading: thanks! (I guess the other natural remaining question is if this can be extended to other types, but of course that would belong in another MO question.) $\endgroup$ Nov 21, 2020 at 2:12
  • 1
    $\begingroup$ @SamHopkins: For that question, I would start with the Stembridge reference that Gjergji Zaimi gave. $\endgroup$ Nov 21, 2020 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.