Permutation Weyl group and inversion length

Permutation matrices and the monomial subgroup. Let $n\ge 1$, let $q$ be a prime power, let $G={\mathrm{GL}}_n({\mathbb{F}}_q)$ with diagonal torus $T$ and standard flag $V_0⊊\cdots ⊊V_n$ as in Standard subgroups of finite general linear groups, and let $S_n:=\mathrm{Sym}(\{1,\dots ,n\})$ be the symmetric group of the set $\{1,\dots ,n\}$ (The symmetric group $\mathrm{Sym}(X)$: the bijections of a set $X$ under composition, $\mathrm{Sym}(X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements), so that permutations are composed as functions and an element $\sigma \in S_n$ is written in one-line notation as the list $\sigma (1),\sigma (2),\dots ,\sigma (n)$.

For $\sigma \in S_n$ the permutation matrix $P_{\sigma }\in G$ is the matrix with $(P_{\sigma }{)}_{ij}=\{\begin{array}{ll}1,& i=\sigma (j),\\ 0,& i\mathrm{\ne }\sigma (j),\end{array}$ that is, the $j$-th column of $P_{\sigma }$ is the standard basis vector $e_{\sigma (j)}$, so that the $j$-th column has its unique entry $1$ in row $\sigma (j)$. In particular $P_{\mathrm{i}\mathrm{d}}=I_n$, and multiplying matrices gives $P_{\sigma }{P}_{\tau }=P_{\sigma \circ \tau }(\sigma ,\tau \in S_n),$ because the $(i,k)$ entry of $P_{\sigma }{P}_{\tau }$ is ${\sum }_j(P_{\sigma }{)}_{ij}(P_{\tau }{)}_{jk}$, which is $1$ exactly when $j=\tau (k)$ and $i=\sigma (j)=\sigma (\tau (k))$, and $0$ otherwise. A matrix $m\in G$ is monomial when every row and every column of $m$ has exactly one nonzero entry. The monomial subgroup of $G$ is $N:=\{m\in G:m\text{ is monomial}\}\mathrm{.}$ Every $m\in N$ has a unique expression $m=t{P}_{\sigma },t=\mathrm{diag}(t_1,\dots ,t_n)\in T,\sigma \in S_n,$ namely with $\sigma (j)$ the row of the nonzero entry of column $j$ and $t_{\sigma (j)}$ that entry; conversely $t{P}_{\sigma }$ is monomial with nonzero entries $t_i$ in the rows and columns determined by $\sigma$. Consequently $N=T\cdot \{P_{\sigma }:\sigma \in S_n\}=\{P_{\sigma }{t}^{\mathrm{\prime }}:\sigma \in S_n,t^{\mathrm{\prime }}\in T\},$ since diagonal matrices may be moved across a permutation matrix. $N$ is a subgroup of $G$: it contains $I_n=P_{\mathrm{i}\mathrm{d}}$, the product $m{m}^{\mathrm{\prime }}$ of monomial matrices is monomial because the unique nonzero entry of each column of $m^{\mathrm{\prime }}$ is transported to a unique nonzero entry of the corresponding column of $m{m}^{\mathrm{\prime }}$, and the inverse of a monomial matrix is monomial since permuting and rescaling rows and columns can be undone. Moreover $T\le N$ and $T⊴N$.

The Weyl group. Define the sign permutation of a monomial matrix by $w:N⟶S_n,w(t{P}_{\sigma }):=\sigma ,$ which is well defined by the uniqueness of the decomposition. It is a group homomorphism: if $m=t{P}_{\sigma }$ and $m^{\mathrm{\prime }}=t^{\mathrm{\prime }}{P}_{\tau }$, then $t^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}:=P_{\sigma }{t}^{\mathrm{\prime }}{P}_{\sigma }^{-1}$ is diagonal, so $m{m}^{\mathrm{\prime }}=t{t}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}{P}_{\sigma }{P}_{\tau }=t{t}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}{P}_{\sigma \tau }$ by Matrix multiplication is associative, unital, distributive, and compatible with scalar multiplication, whence $w(m{m}^{\mathrm{\prime }})=\sigma \circ \tau =w(m)w(m^{\mathrm{\prime }})$. Its kernel is exactly $T$, since $w(t{P}_{\sigma })=\mathrm{i}\mathrm{d}$ says $\sigma =\mathrm{i}\mathrm{d}$ and then $t{P}_{\mathrm{i}\mathrm{d}}=t$. Being a surjective homomorphism, $w$ has kernel $T⊴N$ by Normal subgroup: invariance under conjugation, and the induced map on cosets $W:=N\mathrm{/}T⟶S_n,mT⟼w(m),$ is well defined (left multiplication by an element of $T=\ker w$ does not change $w$) and is an isomorphism of groups, with inverse $\sigma \mapsto P_{\sigma }T$; here $N\mathrm{/}T$ is the quotient group of The quotient group $G\mathrm{/}N$ and coset product $(gN)(hN)=ghN$. We call $W=N\mathrm{/}T\cong S_n$ the (split) Weyl group of $G$. Note that $W$ is defined as a quotient of the monomial subgroup $N$ and not as the quotient $N_G(T)\mathrm{/}T$ of the normaliser of $T$ inside $G$: at $q=2$ the torus $T$ is trivial and $N_G(T)\mathrm{/}T$ is all of $G$, while $N\mathrm{/}T\cong S_n$ still holds. For $\sigma \in S_n$ we write $w_{\sigma }$ for the class of $P_{\sigma }$ in $W$, so that $w_{\sigma }{w}_{\tau }=w_{\sigma \tau }$ and the isomorphism above sends $w_{\sigma }$ to $\sigma$; we write $1:=w_{\mathrm{i}\mathrm{d}}$ for the identity of $W$.

Simple reflections. For $1\le i<n$ let $s_i:=(ii+1)\in S_n$ be the adjacent transposition of $i$ and $i+1$ (The symmetric group $\mathrm{Sym}(X)$: the bijections of a set $X$ under composition), and put ${\mathbf{s}}_i:=w_{s_i}=P_{s_i}T\in W\mathrm{.}$ The elements ${\mathbf{s}}_1,\dots ,{\mathbf{s}}_{n-1}$ are the simple reflections of $W$; they generate $W$, because the adjacent transpositions generate $S_n$ (The adjacent transpositions $(12),(23),\dots ,(n-1n)$ generate $S_n$) and $w$ is surjective.

Inversion length. For $\sigma \in S_n$ the inversion set and length are $\mathrm{Inv}(\sigma ):=\{(i,j):1\le i<j\le n,\sigma (i)>\sigma (j)\},\mathrm{\ell }(\sigma ):=\mathrm{\#}\mathrm{Inv}(\sigma ),$ and for $w_{\sigma }\in W$ we set $\mathrm{\ell }(w_{\sigma }):=\mathrm{\ell }(\sigma )$, which is well defined because every element of $W$ has the form $w_{\sigma }$ for exactly one $\sigma$. Thus $\mathrm{\ell }(1)=0$ and $\mathrm{\ell }(w_{s_i})=1$ for every $i$, a single inversion being created by the transposition of adjacent entries. Length is invariant under inversion of the permutation: the map $(i,j)\mapsto (\sigma (j),\sigma (i))$ is a bijection from $\mathrm{Inv}(\sigma )$ to $\mathrm{Inv}({\sigma }^{-1})$ — if $i<j$ and $\sigma (i)>\sigma (j)$, then setting $a:=\sigma (j)<b:=\sigma (i)$ gives $a<b$ while ${\sigma }^{-1}(a)=j>i={\sigma }^{-1}(b)$ — hence $\mathrm{\ell }(w^{-1})=\mathrm{\ell }(w)(w\in W)\mathrm{.}$ We stress that $\mathrm{\ell }$ is here defined combinatorially as an inversion count and that no Coxeter-theoretic description of it as a minimal word length is used on this page.

Parabolic Weyl subgroups. Let $\alpha =(a_1,\dots ,a_r)$ be a composition of $n$ with blocks $I_1,\dots ,I_r$ and standard parabolic $P_{\alpha }$ and Levi $L_{\alpha }$ (Compositions, partial flags, and standard parabolics). The standard parabolic subgroup of $W$ attached to $\alpha$ is $W_{\alpha }:=\{\sigma \in S_n:\sigma (I_i)=I_i\text{ for every }1\le i\le r\},$ the group of permutations preserving each block of $\alpha$ as a set; it is isomorphic to $S_{a_1}\times \cdots \times S_{a_r}$ by restriction to the blocks, and its elements are exactly the $\sigma$ whose length is the sum of the lengths of the restrictions $\sigma {\mathrm{\mid }}_{I_i}$. In terms of the monomial subgroup, a monomial matrix lies in $P_{\alpha }$ exactly when its permutation matrix has $\sigma (I_i)=I_i$ for all $i$, that is, exactly when $\sigma \in W_{\alpha }$; consequently $N\cap P_{\alpha }=N\cap L_{\alpha }=T\cdot \{P_{\sigma }:\sigma \in W_{\alpha }\},W_{\alpha }=w(N\cap P_{\alpha }),$ and $\{P_{\sigma }:\sigma \in W_{\alpha }\}$ is a complement to $T$ in $N\cap P_{\alpha }$: its intersection with $T$ is $\{I_n\}$ and every element has the unique form $t{P}_{\sigma }$. The two extreme cases are $W_{(n)}=S_n,W_{(1^n)}=\{1\},$ corresponding to $P_{(n)}=G=L_{(n)}$ and to $P_{(1^n)}=B$ with $L_{(1^n)}=T$ and $W_{(1^n)}=w(T)=\{1\}$: the single block of $(n)$ is preserved by every permutation, while each singleton block of $(1^n)$ must be fixed, so only the identity survives.