Map from Bruhat stratification to Catalan stratification for the space of totally nonnegative upper-triangular matrices

Question

$\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.

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.