Can Matsumoto's theorem for the symmetric group be proved using a monovariant?

Question

This is a question that can be asked for any Coxeter group, but for the sake of simplicity I will restrict myself to symmetric groups. Recall the main definitions:

Let $n$ be a nonnegative integer. The symmetric group $S_n$ consists of the permutations of the set $\left[n\right] := \left\{1,2,\ldots,n\right\}$. For each $i \in \left[n-1\right]$, we let $s_i$ be the $i$-th simple transposition; this is the permutation in $S_n$ that swaps $i$ with $i+1$ while leaving all other elements of $\left[n\right]$ unchanged. It is well-known that the symmetric group $S_n$ can be presented as the group with generators $s_1, s_2, \ldots, s_{n-1}$ and relations

• $s_i^2 = 1$ for all $i \in \left[n-1\right]$,

• $s_i s_j = s_j s_i$ for all $i,j \in \left[n-1\right]$ satisfying $\left|i-j\right| > 1$,

• $s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}$ for all $i \in \left[n-2\right]$.

This is known as the Coxeter-Moore presentation of $S_n$.

Let us take a look at the combinatorics of this presentation. If $w \in S_n$, then

• a Coxeter word for $w$ shall mean a tuple $\left(i_1, i_2, \ldots, i_k\right) \in \left[n-1\right]^k$ satisfying $w = s_{i_1} s_{i_2} \ldots s_{i_k}$;

• a reduced word for $w$ shall mean a Coxeter word for $w$ that has the smallest length among all Coxeter words for $w$.

For example, the cycle $\left(1,2,3\right)$ has reduced word $s_1 s_2$ and a (non-reduced) Coxeter word $s_3 s_1 s_3 s_2$. (The typical permutation has many reduced words and infinitely many Coxeter words.)

Given a reduced word $\mathbf{i} = \left(i_1, i_2, \ldots, i_k\right)$ of $w$, we can obtain other reduced words of $w$ by the following transformations:

• We can pick two adjacent entries $i_u$ and $i_{u+1}$ of $\mathbf{i}$ that satisfy $\left|i_u - i_{u+1}\right| > 1$, and swap them. This is called a commutation move; for example, we can use such a move to transform $\left(1,2,3,1,2\right)$ into $\left(1,2,1,3,2\right)$.

• We can pick three adjacent entries $i_u$, $i_{u+1}$ and $i_{u+2}$ of $\mathbf{i}$ that satisfy $i_u = i_{u+2} = i_{u+1} \pm 1$, and replace them by $i_{u+1}$, $i_u$ and $i_{u+1}$, respectively. This is called a braid move; for example, we can use such a move to transform $\left(1,2,1,3,2\right)$ into $\left(2,1,2,3,2\right)$, and we can use another such move to transform this result further into $\left(2,1,3,2,3\right)$.

Theorem (Matsumoto's theorem for the symmetric group). Let $w \in S_n$. Then, any two reduced words of $w$ can be transformed into one another by a sequence of commutation moves and braid moves.

This theorem is often illustrated by drawing the graph whose vertices are the reduced words of a given $w \in S_n$, with two vertices $\mathbf{i}$ and $\mathbf{j}$ being joined by an edge if the reduced word $\mathbf{j}$ can be obtained from $\mathbf{i}$ by a single commutation move or braid move. Page 6 of Yuval Roichman's SLC67 slides shows such a graph.

An elementary proof of Matsumoto's theorem appears, e.g., in the LLPT notes (Chapter SYM, Proposition (2.6)). Most texts on Coxeter groups prove it as well, in one or the other (usually more general) form. Some (I believe) derive it from the PBW property of the Hecke algebra. However, these proofs (to my knowledge) are rather tricky, and appear to rely on massaging the reduced words until they either begin or end with the same letter. (Not sure about the Hecke-based proof, but the proof in the LLPT notes definitely works this way.)

I am a bit surprised that the seemingly more natural monovariant approach is never used:

• assigning a number (or some other kind of object in a totally ordered set) to each reduced word (for example, we could assign $\sum_{j=1}^k j^2 i_j$ to the reduced word $\left(i_1, i_2, \ldots, i_k\right)$);

• then showing that if $\mathbf{i}$ is any reduced word, then we can apply a braid or commutation move to $\mathbf{i}$ that decreases this number, unless $\mathbf{i}$ has some specific property that characterizes it uniquely (there are several known choices of "canonical" reduced word for a permutation $w$ -- it could be one of them, or a new one);

• then concluding by the monovariance principle (as the set of reduced expressions of $w$ is finite).

(Intuitively, this sort of reasoning is the first thing one might try. After all, one can think of transforming reduced words as pulling a string around the surface of a permutahedron, while keeping the ends of the string fixed on two vertices; the permutahedron being convex, there should be a way to pull it "all the way down" without it getting stuck. The monovariant would then be responsible for defining the meaning of "down".)

Alternatively, and to some extent equivalently, I'm surprised to have never seen a diamond lemma argument for the theorem.

Question: Do such proofs of Matsumoto's theorem exist? Or are there some obstructions to them?

Answer 1

Adriano Garsia gives a proof of essentially this form in his book "The Saga of Reduced Factorizations of Elements of the Symmetric Group". See Theorem 1.1.2 for details. In particular, Garsia's argument does not rely on the exchange lemma. Basically, the idea is to show the minimal value $i$ occuring in a reduced word can be made to occur once. Then separating the reduced word into two, $(\textbf{a},i,\textbf{b})$ we can do the same to $\textbf{a},\textbf{b}$ to obtain $(\dots,i+1,\dots,i,\dots, i+1,\dots)$ and so on. Eventually this procedure results in a canonical form. If the first step can be interpreted using a monovariant argument, the whole proof can be viewed through that lense.