$\DeclareMathOperator\SL{SL}$This question came up in a class ["Total Positivity and Cluster Algebras" being taught by Chris Fraser](https://sites.google.com/site/cmfraser37/teaching/8680).


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](https://arxiv.org/azbs/0711.1348) 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.



Map from Bruhat stratification to Catalan stratification for the space of totally nonnegative upper-triangular matrices
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"](https://arxiv.org/abs/math/9912128), 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"](https://www.ams.org/journals/tran/1997-349-04/S0002-9947-97-01805-9/)). Incidentally, this 321 permutation also represents the lowest dimensional Bruhat cell in the Catalan stratum.


