I am studying cluster algebra structures on the coordinate rings of partial flag varieties, as defined in the paper Partial flag varieties and preprojective algebras by Geiss, Leclerc and Schröer. One way of writing down such a cluster structure is to give an initial seed, and indeed the paper gives an algorithm for producing such a seed. The input data for the algorithm is a particular kind of reduced expression for the longest element in a Weyl group.

Let $\Delta$ be a (simply laced) Dynkin diagram, and let $K$ be a subset of its nodes; this data defines a flag variety (in at least two ways, depending on convention, but this will not be important for my question). Denote the full subgraph of $\Delta$ on $K$ by $\Delta_K$, and let the corresponding Weyl groups be $W(\Delta_K)\leq W(\Delta)$.

To run Geiss-Leclerc-Schröer's algorithm for various examples, I want to compute a reduced expression for the longest word of $W(\Delta)$, such that it begins with a reduced expression for the longest word of $W(\Delta_K)$.

There are published tables giving an expression for the longest word of $W(\Delta)$ for each $\Delta$, but when $\Delta$ is not very small (and depending on $K$), it can be somewhat arduous to adjust these expressions to the form I want (and difficult to do this without typos!). Hence my question:

Does anybody know of any software (ideally something like a Java applet) that would make this computation easier to do?

It wouldn't need to actually produce the answer entirely by itself, as I imagine the form I am looking for is too unusual for this to have been implemented. But even something in which the user could click on the letters to apply commutation or braid relations would make it easier to avoid errors.

Sage can (apparently) compute all reduced words for any given element of a Weyl group, but this times out whenever $\Delta$ is non-tiny (and going through the list looking for a word of the right form would be an unenviable task).

  • 1
    $\begingroup$ I wrote some fairly naive Magma code that can do this. (This can be ported to other systems relatively easily too.) It's not public but I'd be happy to share it with you. I won't guarantee that it will be more effective than what you have tried though! $\endgroup$ – Jan Grabowski Nov 25 '13 at 17:12
  • $\begingroup$ That would probably be very useful! I am essentially still using pen and paper at the moment - I haven't programmed anything for a while, so it seemed more economical to check to see if something already existed before I invested too much time into building it myself. $\endgroup$ – Matthew Pressland Nov 25 '13 at 17:28

I think you can use minimal coset representatives for this.

Each $w \in W(\Delta)$ can be uniquely written as $w_K w^K$ where $w_K \in W(\Delta_K)$ and $l(w_K) + l(w^K) = l(w)$. The element $w^K$ is called minimal left coset representative (and all of this works also for the opposite side) and the set of these is usually denoted by $W^K$. Now the Bruhat order descend to $W^K$ and you basically want the minimal (or maximal, depending on convention) element of it. I am not sure whether there is a general formula and I'd wager that chances are there is. Nevertheless, there's an algorithm that computes these minimal coset representatives in reasonable time. I've produced a patch for sage few weeks ago.

The algorithm:

  1. Write $1$ over the nodes of your Dynkin diagram that doesn't belong to $K$ and write $0$ elsewhere.
  2. Apply root reflections with respect to roots over which there is a positive number and treat those numbers as coefficients in the basis of fundamental weights.
  3. Terminate when you arrive at a Dynkin diagram decorated only with nonpositive numbers.

The minimal representative of the longest element is then the product of simple reflections from the starting diagram to the last one. (You may need to reverse the order.)

Edit: I've just remembered that Sage contains code for computing minimal representatives (and of course also reduced expressions). The documentation is here.

So you just need to write something like



| cite | improve this answer | |
  • $\begingroup$ Thanks, this looks like the kind of thing I'm after - I will try to understand it properly (and compute something with it) tomorrow. $\endgroup$ – Matthew Pressland Nov 25 '13 at 18:10
  • $\begingroup$ That worked perfectly, thanks a lot! $\endgroup$ – Matthew Pressland Nov 26 '13 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.