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

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?

• For the symmetric group, I think one could derive a proof of this type pretty easily using results from Sami Assaf's paper "A inversion statistic for reduced words" arxiv.org/abs/1808.01281 May 11, 2021 at 14:12
• @darijgrinberg I've read the paper carefully. the stated Theorems are all correct. a bit of care might be required to make the proof you desire self-contained May 11, 2021 at 16:52
• On a tangential note, I'd like to try to persuade you against using the term "Coxeter word". In the broader context of combinatorial group theory, we just have "words" and perhaps "reduced words". If you were going to modify the noun "word" in some way, the best thing would be to name the alphabet. After all, in Coxeter groups, there are other good choices of alphabets, so saying "Coxeter word" doesn't really help much. Also, saying "Coxeter word" leans in the direction of confusing people about "Coxeter elements". May 12, 2021 at 1:40
• My favorite proof of this property uses the fact that the weak order is a lattice. (That fact is not too hard to prove, especially for the symmetric group.) From that point of view, reduced words for $w$ are just maximal chains from the identity to $w$. Instead of always moving down in some arbitrary notion of "down" (which must necessarily really be "sideways" on the permutohedron), the proof works by moving two chains closer to each other, in terms of how many initial edges they share. May 12, 2021 at 1:50
• The proof I have in mind is probably equivalent to the "massaging" Darij doesn't like, but the whole point is that the lattice property makes it quite simple to make the words start with the same letter. (As part of the argument, you need to know something about rank-2 Coxeter groups, but what could be more natural than having a proof about Coxeter groups come down to a rank-2 fact?) May 12, 2021 at 1:52

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.