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.

Let $B_n$ be the group of signed permutations, which is a Coxeter group acting on $\mathbb{R}^n$ with Coxeter generators $\sigma_i=(i\; i+1)\in S_n$ and the change of sign $\tau(x_1,x_2,\dots,x_n)=(-x_1,x_2,\dots,x_n)$.

So the elements can be represented by the action on the vector $(1,2,\dots,n)$ as words $w$ in the signed alphabet $\{\pm 1,\dots,\pm n\}$ where the $|w_i|$ form a permutation. Moreover, $$ \operatorname{inv}(w)=|\{i<j:w(i)>w(j)\}|+|\{i<j: w(i)+w(j)<0\}|+|\{i: w(i)<0\}|. $$ Supposedly $\operatorname{inv}(w)$ is just the minimum length of an expression for $w$ written as a product of the Coxeter generators.

How does that characterization follow from this definition? Thank you.

share|improve this question
    
Dear moderators, I registered an account. Can it be merged with the old unregistered one: math.stackexchange.com/users/6742/hobbie? Thanks. –  Hobbie Feb 6 '12 at 22:38
    
Have you looked in Combinatorics of Coxeter Groups by Bjorner/Brenti? I'm fairly certain it is in there. –  Michael Joyce Feb 6 '12 at 22:42
    
@MichaelJoyce I know Proposition 1.5.2 proves something similar, but there they use a different definition for the inversion number of elements of $S_n$. –  Hobbie Feb 6 '12 at 23:30
    
@Hobbie: I've merged your accounts. –  Zev Chonoles Feb 7 '12 at 1:55
1  
This is quite straightforward, if you are familiar with the language of root systems. All you need to do is to count how many positive roots get mapped to negative roots, and that's precisely what the claimed formula does. The dirty work (=that this number is equal to the minimum length of the group element as a product of generators) has then been done for you in full generality! –  Jyrki Lahtonen Jul 6 '12 at 19:58
show 3 more comments

1 Answer

I cannot find the proof you are looking for in the book by D. E. Taylor that ego suggested in the comments either. But you can use the techniques of the section "Reflections and the Strong Exchange Condition" on pages 94-96 for a proof (my answer is independent of the book, for connections see the comment at the end).


In your case you have the set $R = \{(1\;-1)\} \stackrel{.}{\cup} \{(i\;i+1)(-i\;-i-1) \mid i \in [n-1]\}$ of involutions generating the Coxeter group $W = \langle R\rangle$, which is a subgroup of the symmetric group on $[n] \cup -[n]$ (using the notation $[n] := \{1, \dots, n\}$).

For the set $T = \{wrw^{-1} \mid w \in W, r \in R\}$ of all conjugates of the generating involutions in $R$ (defined in equation (9.20) of the book) you should be able to check $T = T_1 \stackrel{.}{\cup} T_2 \stackrel{.}{\cup} T_3$ for $$T_1 := \{(i\;-i)\mid i\in[n]\}$$ $$T_2 := \{(i\;j)(-i\;-j) \mid i, j \in [n], i<j\}$$ $$T_3 := \{(i\;-j)(-i\;j) \mid i, j \in [n], i<j\}$$ $T$ consists of two different conjugacy classes: $T_1$ are the conjugates of $(1\;-1)$), and $T_2\stackrel{.}{\cup}T_3$ the conjugates of all the other elements of $R$.

$W$ acts on $T$ by conjugation, which induces an action on the power set $\mathcal{P}(T)$ of $T$. With the symmetric difference as addition, the power set $\mathcal{P}(T)$ becomes an elementary abelian $2$-group, on which $W$ acts. Define $D'(w) = D'_1(w) \stackrel{.}{\cup} D'_2(w) \stackrel{.}{\cup} D'_3(w)$ for $w \in W$ with $$D'_1(w) = \{(i\;-i) \in T_1 \mid i\in [n] \mbox{ and } w(i)<0\}$$ $$D'_2(w) = \{(i\;j)(-i\;-j) \in T_2 \mid i, j\in [n], i<j\mbox{ and } w(i)>w(j)\}$$ $$D'_3(w) = \{(i\;-j)(-i\;j) \in T_3 \mid i, j\in [n], i<j\mbox{ and } w(i)+w(j) < 0\}$$ The cardinality of $D'(w)$ is just inv$(w)$ from your question.

Claim: (a) $D'(r) = \{r\}$ for $r \in R$

(b) $D'(w_1w_2) = w_2^{-1}D'(w_1)w_2+D'(w_2)$ for $w_1, w_2 \in W$

The first statement is easily verified, we show the second one:

For this, observe that an element $(i\;-i)$ of the conjugacy class $T_1$ is contained in $D'(w)$ if and only if $\frac{w(i)}{i}<0$ for $i \in [n]\cup-[n]$.

Now $(i\;-i) \in D'(w_1w_2)$ is the same as $0 > \frac{w_1(w_2(i))}{i} = \frac{w_1(w_2(i))}{w_2(i)}\cdot \frac{w_2(i)}{i}$, which in turn is equivalent to either $ D'(w_1) \ni (w_2(i)\;-w_2(i)) = w_2(i\;-i)w_2^{-1}$ or $(i\;-i) \in D'(w_2)$, i.e., $(i\;-i) \in w_2^{-1}D'(w_1)w_2+D'(w_2)$.

An element $(i\;j)(-i\;-j)$ of the conjugacy class $T_2\cup T_3$, where $i, j\in [n]\cup -[n]$, $i\ne j$ and $i\ne -j$, is contained in $D'(w)$ if and only if $\frac{w(j)-w(i)}{j-i}<0$ (check this by considering the two cases $i\cdot j>0$ and $i\cdot j<0$ and by considering what happens if you replace $i$ and $j$ by $-i$ and $-j$).

So $(i\;j)(-i\;-j) \in D'(w_1w_2)$ is equivalent to $0 > \frac{w_1(w_2(j))-w_1(w_2(i))}{j-i} = \frac{w_1(w_2(j))-w_1(w_2(i))}{w_2(j)-w_2(i)}\cdot \frac{w_2(j)-w_2(i)}{j-i}$, which is the same as $(i\;j)(-i\;-j) \in w_2^{-1}D'(w_1)w_2+D'(w_2)$.

Having proven the claim, one can easily deduce the formula for the length by induction:

Because of (a) we may assume that $l(w) > 1$, and write $w = s\cdot v\cdot t$ with $s, t \in R$ and $l(v) = l(w)-2$. Per induction $|D'(v)|+1 = l(v)+1 = l(v\cdot t) = |D'(v\cdot t)| \stackrel{(b)}{=} |tD'(v)t + D'(t)| \stackrel{(a)}{=} |tD'(v)t + \{t\}|$, i.e., $t \not\in D'(v)$. As $v\ne w = svt$ we get $t \ne v^{-1}sv$, and hence $t\not\in \{v^{-1}sv\} + D'(v) \stackrel{(a)}{=} v^{-1}D'(s)v + D'(v) \stackrel{(b)}{=} D'(s\cdot v)$. It follows $D'(w) \stackrel{(b)}{=} tD'(s\cdot v)t \stackrel{.}{\cup} \{t\}$ and therefore the induction step.


The claim is a variant of (9.22) in Taylor's book:

For $D(w) := wD'(w)w^{-1}$ you get $D(r) = r\{r\}r = \{r\}$ as $r$ has order 2. Also $D(w_1w_2) = w_1D'(w_1)w_1^{-1}+w_1w_2D'(w_2)w_2^{-1}w_1^{-1} = D(w_1)+w_1D(w_2)w_1^{-1}$ showing that D fulfills (9.22).

This condition on $D$ is quite powerful. Taylor uses it to derive the strong exchange property (with Corollary 9.26 implying the formula for the length), and that it is equivalent to $(W, R)$ being a Coxeter system.

share|improve this answer
add comment

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.