Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I vaguely know that by looking at the inversions of a permutation, you can write down the reduced word expressing the permutation as a product of adjacent transpositions $s_i = (i,i+1)$. However, I am a little unclear on what order you check the inversions, or if there is a simple way to do it without multiplying your original permutation by all the transpositions you've found so far.

Is there a simple algorithmic description of how to convert a permutation's inversion set to its reduced word?

Secondly, I'd actually like to do this in the signed permutation group (whose elements are monomial matrices with nonzero entries taken from $\{1,-1\}$; a monomial matrix is like a permutation matrix except the nonzero entries don't have to be $1$).

I'm a little unclear on when you look for the sign changes, but possibly this is due in large part to not having a specific algorithm for the plain permutations.

Is there a simple algorithmic description of how to convert a signed permutation's inversion set and positions of $-1$s to its reduced word?

Example:

The permutation $$\pi = (1,2,3) = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{bmatrix}$$ has inversion set $$\{ \{1,3\}, \{2,3\} \}$$ since $1 < 3$ but $\pi(3) < \pi(1)$ and $2 < 3$ but $\pi(3) < \pi(2)$. The $\{2,3\}$ is pretty clearly caused by $(2,3)$ and so we need to multiply by something to invert $\{(1,3)\}$. Since already know $(2,3)$ is used, that moves the $3$ to a $2$, and $\{1,2\}$ is caused by $(1,2)$. Now depending on which order you apply your functions, we get the product of $(1,2)$ and $(2,3)$ is $(1,2,3)$.

How did I know to use $\{2,3\}$ first? Should I really transform the inversion set by every adjacent transposition I discover?

What if it was $$\sigma = (1,\bar 2,3) = \begin{bmatrix} . & -1 & . \\ . & . & 1 \\ 1 & . & . \end{bmatrix}$$ with the same inversion set as before, but with the $2$nd column negated? When do we take of the negative?

share|improve this question
    
@Henning, I have a feeling it might be an answer (at least for unsigned ones). I have this suspicion that I look for adjacent inversions (like {2,3} or {i,i+1}), and there will ALWAYS be one. Use it, then adjust the inversion set. There will still always be one. I think this is bubble sorting, but I'm not sure. –  Jack Schmidt Jul 27 '12 at 0:21
    
My second suspicion is that if the first row has the -1 in it (the 1 has the bar), then you throw in the special -1 generator and un-bar the one. otherwise, ignore the -1s and bars. I'm going to code this up and check it, but I really want a good intuitive understanding of this. –  Jack Schmidt Jul 27 '12 at 0:23
    
(Second suspicion is quite wrong. Take the identity matrix and flip some signs.) –  Jack Schmidt Jul 27 '12 at 0:55
    
This is a special case of a length reduction in crystallographic finite reflection groups. A useful way of expressing this in terms of the corresponding root system goes as follows. If $\sigma(\alpha)<0$ for some simple root $\alpha$, then $\ell(\sigma s_\alpha)=\ell(\sigma)-1$. Rinse. Repeat. As @Henning pointed out, in the case of a root system of type $A_n$ this leads to bubble sorting. The other root systems lead to slight generalization. If you also allow reflections with respect to hyperplanes determined by non-simple roots, then you get analogues of shell sorting. –  Jyrki Lahtonen Jul 27 '12 at 18:45

1 Answer 1

up vote 2 down vote accepted

While counting inversions is a great way to calculate the (Coxeter) length, it turns out a related notion called descents is better for factorizing the element. (Note that my answer is basically unrelated to “inversion length”, which appears to be a hot topic in computational biology).

For a permutation $\sigma$, the Coxeter length $\ell(\sigma)$ is the length of the shortest sequence of adjacent transpositions $s_i=(i,i+1)$ whose product is $\sigma$. For instance $\ell(s_1 \cdot s_2 \cdot s_3) = 3$, but $\ell(s_1 \cdot s_1 \cdot s_2) = \ell(s_2) = 1$. For a signed permutation (a permutation of $\{\pm1,\ldots,\pm n\}$ such that $\sigma(-i)=-\sigma(i)$), we define the Coxeter length similarly, except there is now one more generator allowed: $s_0 = [\bar1]$ which takes $1$ to $-1$ and fixes $i$ if $|i| \geq 2$.

The Coxeter length can be calculating from so-called inversion sets:

$$\begin{array}{rcl} \ell(\sigma) &=& \left| \{(i,j) : 1 \leq i < j \leq n \mid \sigma(i) > \sigma(j) \}\right| \\ &+& \left| \{(i,j) : 1 \leq i \leq j \leq n \mid \sigma(-i) > \sigma(j) \} \right| \end{array}$$ where the bottom line is defined to be $0$ for a plain permutation (which agrees with the value calculated from the signed permutation that agrees with $\sigma$ on $\{1,\ldots,n\}$).

Any element in the first of those inversion sets is a place where the permutation is “out of order”. One can either swap $i$ and $j$ on the input side, or swap $\sigma(i)$ and $\sigma(j)$ on the output side.

For unsigned permutations this leads to a fairly obvious factorization method. The key observation is that we can always find an inversion where the two numbers are adjacent. On the output side this seems a bit fantastical, but on the input side it is obvious: in order to check if a sequence is sorted, you just move along checking if $\sigma(i) < \sigma(i+1)$. If all of those check out, then the transitive property of $<$ implies everything checks out (and so you have the identity permutation!). Otherwise we have our magical $\{i,i+1\}$ we needed to pull off one factor of $s_i$ on the input side.

Thus we define the (input-side) descent set to be: $$\newcommand{\des}{\operatorname{des}} \des(\sigma) = \{ i : 1 \leq i \leq n \mid \sigma(i) > \sigma(i+1) \}$$

And we have the relation that $\ell( s_i \sigma ) < \ell(\sigma)$, that is that an input-side $s_i$ is going to be cancelled by a hidden $s_i$ that is already there, if and only if $i \in \des(\sigma)$. Thus every reduced factorization of $\sigma$ is found by pulling out one generator $s_i$ from each descent set $\des(\sigma)$ and replacing $\sigma$ with $s_i \cdot \sigma$. [The actual replacement need not be done in code, compare to partial pivoting elimination versus explicitly moving the rows around in memory.]

For signed permutations, one gets the “obvious” thing (which is extremely close to my suspicion, but my suspicion radically mishandled negative numbers):

$$\des(\sigma) = \{ i : 0 \leq i \leq n ~|~ \sigma(i) > \sigma(i+1) \}$$

where we extend signed permutation to $\{-n,\ldots,n\}$ by defining $\sigma(0)=0$. Again, this easily becomes a full factorization algorithm by replacing $\sigma$ by $s_i \sigma$ for $i \in \des(\sigma)$ until $\des(\sigma)$ is empty.

This is discussed (probably with the inputs on the right) in Bjørner–Brenti (2005), page 248 and surrounds.

  • Bjørner, Anders; Brenti, Francesco. Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005. xiv+363 pp. ISBN: 978-3540-442387; 3-540-44238-3 MR2133266 DOI:10.1007/3-540-27596-7
share|improve this answer
    
(Also thanks to Henning for making me consider bubble-sort. The input/output problem had previously kept me from understanding this approach. Once resolved Henning's answer made the unsigned case perfectly clear. Then I found Bjørner–Brenti's "this-just-works" definition, which was obvious once you realized taking absolute values was dumb.) –  Jack Schmidt Jul 27 '12 at 18:22
    
Another good source is chapter 9 of the book The Geometry of the Classical Groups by D.E. Taylor (combined with my answer to math.stackexchange.com/questions/106462/…) –  j.p. Jul 29 '12 at 16:57
    
@jug: thanks. I liked the answer (and remember liking the book). I'll check the book during the week. Your answer only makes some sense without the book. The vector space over Z/2Z looks like it will make some calculations easier, but I think need the book to see which calculations those will be. –  Jack Schmidt Jul 29 '12 at 22:51
    
From (9.22) in the book rsp. Claim (a) and (b) in my answer you can easily deduce that $\mathop{des}(\sigma)$ is essentially the same as $\mathop{D}(\sigma)\cap R$ (with $R$ the set of Coxeter generators): just identify $0$ with $(1\; -1)$ and $i>0$ with $(i\; i+1)$. –  j.p. Jul 30 '12 at 13:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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