## Reflection Groups

Last update: 20 March 2012

## The symmetric group

The symmetric group is the group of permutations of 1,2,...,$n,$ i.e. the group of bijections $w:\left\{1,2,...,n\right\}\to \left\{1,2,...,n\right\}$ under the operation of composition. There are multiple notations for permutations:

1. Two line notation: where $w\left(i\right)$ in the second line is below $i$ in the first line. $w= 1 2 3 4 5 6 4 1 6 2 5 3$
2. Cycle notation: Where $\left({i}_{1},{i}_{2},...,{i}_{r}\right)$ indicates Cycles of length 1 are usually dropped from the notation. $w=(142)(36)(5) =(142)(36).$
3. Matrix notation: where the $w\left(i\right)$th entry of the $ith$ column is 1 and all other entries are 0. $w= 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0$
4. Diagram notation: where the $i$th dot in the top row is connected to the $w\left(i\right)$th dot in the bottom row. $w=$
The symmetric group ${S}_{n}$ is the group of $n×n$ permutation matrices and $\mathrm{Card}\left({S}_{n}\right)=n!.$

The transpositions in ${S}_{n}$ are the permutations (in cycle notation). The simple transpositions are

The symmetric group ${S}_{n}$ can be presented by generators ${s}_{1},{s}_{2},...,{s}_{n-1}$ and relations

 Proof. There are three things to show: The simple transpositions in ${S}_{n}$ satisfy the given relations. The simple transpositions generate ${S}_{n}.$ The group given by generators ${s}_{1},...,{s}_{n-1}$ and relations as in the statement of the theorem has order $\le n!.$ The following pictures show that the simple transpositions satisfy the given relations. $=$ $= =$ $= =$ The diagram of any permutation can be "stretched" to guarantee that no more than two edges cross at any given point. Then $w$ can be written as a product of simple transpositions corresponding to these crossings. $w= = = s1s3 s5s4 s5s3.$ Let ${G}_{n}$ be the free group generated by symbols ${s}_{1},{s}_{2},...,{s}_{n-1}$ modulo the relations in the statement of the theorem. Let ${G}_{n-1}$ be the subgroup generated by ${s}_{1},{s}_{2},...,{s}_{n-2}.$ We will show that Every element $w\in {G}_{n}$ can be written in the form $w={w}_{1}{s}_{n-1}{w}_{2},$ with ${w}_{1},{w}_{2}\in {G}_{n-1}.$ Every element $w\in {G}_{n}$ can be written in the form and $a\in {G}_{n-1}.$ Since ${s}_{n-1}^{2}=1$ every element $w\in {G}_{n}$ can be written in the form By induction, either ${w}_{2}\in {G}_{n-2}$ or ${w}_{2}=a{s}_{n-2}b$ where $a,b\in {G}_{n-2}.$ In the first case $w = w1sn-1 w2sn-1 w3sn-1 ⋯ wl-1 sn-1 wl = w1w2 sn-1 sn-1 w3 sn-1 ⋯ wl-1 sn-1 wl = w1w2 sn-1 w3 sn-1 ⋯ wl-1 sn-1 wl,$ and in the second case $w = w1 sn-1 w2 sn-1 w3 sn-1 ⋯ wl-1 sn-1 wl = w1 sn-1a sn-2b sn-1 w3 sn-1 ⋯ wl-1 sn-1 wl = w1a sn-1 sn-2 sn-1b w3 sn-1 ⋯ wl-1 sn-1 wl = w1a sn-2 sn-1 sn-2b w3 sn-1 ⋯ wl-1 sn-1 wl = w1′ sn-1 w3′ sn-1 ⋯ wl-1 sn-1 wl$ where ${w}_{1}^{\prime }={w}_{1}a{s}_{n-2}\in {G}_{n-1}$ and ${w}_{3}^{\prime }={s}_{n-2}b{w}_{3}\in {G}_{n-1}.$ In either case the number of ${s}_{n-1}$ factors in the expression of $w$ has been reduced. The statement in (1) follows by induction. By (1) any element $w\in {G}_{n}$ is either an element of ${G}_{n-1}$ or can be written in the form $w={w}_{1}{s}_{n-1}{w}_{2},$ with ${w}_{1},{w}_{2}\in {G}_{n-1}.$ In the first case $w=w{s}_{n-1}\cdots {s}_{l}$ with $l=n$ and the statement is satisfied. If $w={w}_{1}{s}_{n-1}{w}_{2}$ then, by induction, ${w}_{2}=a{s}_{n-2}{s}_{n-3}\cdots {s}_{l},$ for some $1\le l\le n-2$ and $a\in {G}_{n-2}.$ So $w=w1 sn-1a sn-2 ⋯sl = w1a sn-1 ⋯sl = w1′ sn-1 ⋯sl,$ where ${w}_{1}^{\prime }={w}_{1}a\in {G}_{n-1}.$ Statement (2) follows. From (2) it follows that $\mathrm{Card}\left({G}_{n}\right)\le \mathrm{Card}\left({G}_{n-1}\right)\cdot n,$ and, by induction, that $\mathrm{Card}\left({G}_{n}\right)\le n!.$ Since ${S}_{n}$ is a quotient of ${G}_{n}$ and $\mathrm{Card}\left({S}_{n}\right)=n!$ we have ${G}_{n}\cong {S}_{n}.$ $\square$

A partition of $n$ is a collection of boxes in a corner (gravity goes up and to the left) and pushes the boxes tightly into the corner). $λ= (RG 3.1)$ If ${\lambda }_{i}$ is the number of boxes in row $i$ then $\lambda =\left({\lambda }_{1}\ge {\lambda }_{2}\ge \cdots \right)$ is a sequence of nonnegative integers and we write $\lambda ⊢n.$ For example, the partition in (RG 3.1) is $\lambda =\left(55311\right)$ and $\lambda ⊢15.$ A standard tableau of shape $\lambda$ is a filling $T$ of the boxes of $\lambda$ with $1,2,...,n$ such that

1. the rows of $T$ are increasing left to right,
2. the columns of $T$ are increasing top to bottom.
For example, $T= 1 2 5 6 10 3 4 7 12 15 8 9 14 11 16 18 13 17$ is a standard tableau of shape $\lambda =\left(55311\right).$ The rows and columns of the partition $\lambda$ are numbered as for matrices, The number $c\left(b\right)$ is the content of the box $b.$ $0 1 2 3 4 -1 0 1 2 3 -2 -1 0 -3 -2 -1 -4 -5 Contents of boxes$

1. The irreducible representations ${S}^{\lambda }$ of the symmetric group ${S}_{n}$ are indexed by partitions $\lambda$ with $n$ boxes.
2. $\mathrm{dim}{S}^{\lambda }=$ # of standard tableaux of shape $\lambda .$
3. The irreducible ${S}_{n}-$module ${S}^{\lambda }$ is given by with basis $\left\{{v}_{T}\right\}$ and with ${S}_{n}$ action given by $sivT = ( 1 c(T(i+1)) - c(T(i)) ) vT + ( 1+ 1 c(T(i+1)) - c(T(i)) ) vsiT ,$ where
1. ${s}_{i}=\left(i,i+1\right),$
2. $c\left(T\left(i\right)\right)$ is the content of the box containing $i$ in $T,$
3. ${s}_{i}T$ is the same as $T$ except that $i$ and $i+1$ are switched,
4. ${v}_{{v}_{i}T}=0$ if ${s}_{i}T$ is not standard.

 Proof. There are four things to show: The ${S}^{\lambda }$ are ${S}_{n}-$modules, The ${S}^{\lambda }$ are non-isomorphic, The ${S}^{\lambda }$ are all irreducible, The ${S}^{\lambda },$$\lambda ⊢n,$ are all irreducible ${S}_{n}-$modules. In order to show that ${S}^{\lambda }$ is an ${S}_{n}-$module there are three relations to check ${s}_{i}^{2}=1,$ ${s}_{i}{s}_{j}={s}_{j}{s}_{i},$ if $|i-j|>1,$ sisi+1si=si+1sisi+1. The action of ${s}_{i}$ preserves the subspace $S$ spanned by the vectors ${v}_{Q}$ indexed by the standard tableaux in the set $\left\{Q,{s}_{i}Q\right\}.$ Depending on the relative positions of the boxes containing $i$ and $i+1$ this space is either one or two dimensional. $Case (A) Case (B) Case (C)$ In Case (A) the space $S$ is one dimensional and ${s}_{i}$ acts by the matrix $M\left({s}_{i}\right)=1.$ In Case (B), $S$ is one dimensional and ${s}_{i}$ acts by the matrix $M\left({s}_{i}\right)=-1.$ In Case (C), $S$ is two dimensional and ${s}_{i}$ acts on the subspace $S$ by a matrix of the form $M(si) = 1 a-b 1+ 1 b-a 1+ 1 a-b 1 b-a .$ In cases (A) and (B) it is immediate that $M{\left({s}_{i}\right)}^{2}=1$ and in case (C), since $\mathrm{Tr}\left(M\left({s}_{i}\right)\right)=0$ and $\mathrm{det}\left(M\left({s}_{i}\right)\right)=-1,$ it follows from the Cayley-Hamilton theorem that $M{\left({s}_{i}\right)}^{2}=\mathrm{Id}.$ The action of ${s}_{i}$ and ${s}_{j}$ commute if $|i-j|>1$ because ${s}_{i}$ only moves $i$ and $i+1$ in $T$ and ${s}_{j}$ only moves $j$ and $j+1.$ The condition $|i-j|>1$ guarantees that $\left\{i,i+1\right\}$ and $\left\{j,j+1\right\}$ do not intersect. According to the formulas for the action, ${s}_{i}$ and $si+1$ preserve the subspace $S$ spanned by the vectors ${v}_{Q}$ indexed by the standard tableaux $Q$ in the set $\left\{L,{s}_{i}L,{s}_{i+1}L,{s}_{i}{s}_{i+1}L,{s}_{i+1}{s}_{i}L,{s}_{i}{s}_{i+1}{s}_{i}L\right\}.$ Depending on the relative positions of the boxes containing in $L,$ this space is either 1, 2, 3, or 6 dimensional. Representative cases are when these boxes are positioned in the following ways. $Case (1) Case (2) Case (3) Case (4)$ In Case (1) the space $S$ is one dimensional and spanned by the vector ${v}_{Q}$ corresponding to the standard tableau $a$ $b$ $c$ where $a=i,b=i+1,$ and $c=i+2.$ The action of ${T}_{i}$ and ${T}_{i+1}$ on $S$ is given by the matrices $M(si) = (1), and M(si+1) = (1),$ respectively. In case (2) the space $S$ is two dimensional and spanned by the vectors ${v}_{Q}$ corresponding to the standard tableaux $a$ $b$ $c$ $\phantom{\rule{2em}{0ex}}$ $a$ $c$ $b$ where $a=i,b=i+1,$ and $c=i+2.$ The action of ${T}_{i}$ and ${T}_{i+1}$ on $S$ is given by the matrices $M(si) = 1 0 0 -1 and M(si+1) = 1 2 3 2 1 2 - 1 2 .$ In case (3) the space $S$ is three dimensional and spanned by the vectors ${v}_{Q}$ corresponding to the standard tableaux $c$ $a$ $b$ $\phantom{\rule{2em}{0ex}}$ $b$ $a$ $c$ $\phantom{\rule{2em}{0ex}}$ $a$ $b$ $c$ where $a=i,b=i+1,$ and $c=i+2.$ The action of ${T}_{i}$ and ${T}_{i+1}$ on $S$ is given by the matrices $M(Ti) = 1 0 0 0 1 x1-x3 1+ 1 x3-x1 0 1+ 1 x1-x3 1 x3-x1 and ϕS(Ti+1) = 1 x2-x3 1+ 1 x3-x2 0 1+ 1 x2-x3 1 x3-x2 0 0 0 1$ respectively, where and ${x}_{3}=c\left(L\left(i+2\right)\right).$ In case (4) the space $S$ is six dimensional and spanned by the vectors ${v}_{Q}$ corresponding to the standard tableaux $c$ $b$ $a$ $\phantom{\rule{2em}{0ex}}$ $c$ $a$ $b$ $\phantom{\rule{2em}{0ex}}$ $b$ $c$ $a$ $\phantom{\rule{2em}{0ex}}$ $a$ $c$ $b$ $\phantom{\rule{2em}{0ex}}$ $b$ $a$ $c$ $\phantom{\rule{2em}{0ex}}$ $a$ $b$ $c$ where $a=i,b=i+1,$ and $c=i+2.$ The action of ${T}_{i}$ and ${T}_{i+1}$ on $S$ is given by the matrices $M(si) = 1 x1-x2 1+ 1 x2-x1 0 0 0 0 1+ 1 x1-x2 1 x2-x1 0 0 0 0 0 0 1 x1-x3 1+ 1 x3-x1 0 0 0 0 1+ 1 x1-x3 1 x3-x1 0 0 0 0 0 0 1 x2-x3 1+ 1 x3-x2 0 0 0 0 1+ 1 x2-x3 1 x3-x2$ and $M(si+1) = 1 x2-x3 0 1+ 1 x3-x2 0 0 0 0 1 x1-x3 0 0 1+ 1 x3-x1 0 1+ 1 x2-x3 0 1 x3-x2 0 0 0 0 0 0 1 x1-x2 0 1+ 1 x2-x1 0 1+ 1 x1-x3 0 0 1 x3-x1 0 0 0 0 1+ 1 x1-x2 0 1 x2-x1$ where and ${x}_{3}=c\left(L\left(i+2\right)\right).$ In each case we compute directly the products $M\left({s}_{i}\right)M\left({s}_{i+1}\right)M\left({s}_{i}\right)$ and $M\left({s}_{i+1}\right)M\left({s}_{i}\right)M\left({s}_{i+1}\right)$ and verify that they are equal. Let $T$ be a standard tableau with $n$ boxes and let ${T}^{-}$ be the standard tableau $T$ except with the box containing $n$ removed. Then $T$ is the unique standard tableau given by adding a box (containing $n$) to ${T}^{-}$ in the diagonal of boxes with content $c\left(T\left(n\right)\right).$ Thus, by induction on the number of boxes in $T,$ For example: if $\left(c\left(T\left(1\right)\right),c\left(T\left(2\right)\right),...,c\left(T\left(n\right)\right)\right)=\left(0,1,-1,0,2,-2,-1,-3,1,3,2,-4,-3,-5,-6\right)$ then $T= 1 2 5 10 3 4 9 11 6 7 8 13 12 14 15$ It follows that the vector ${v}_{T}$ is, up to constant multiples, the unique vector in all the ${S}^{\lambda }$ such that ${x}_{k}{v}_{T}=c\left(T\left(k\right)\right){v}_{T},$ for all $1\le k\le n.$ This proves that the ${S}^{\lambda }$ are nonisomorphic. Let us show that ${S}^{\lambda }$ is irreducible. Let $N$ be a nonzero submodule of ${S}^{\lambda }$ and let $n=\sum _{T}{a}_{T}{v}_{T}$ be a nonzero vector in $N.$ Fix $T$ such that ${a}_{T}\ne 0.$ It follows from the lemma and the fact that $T$ is determined by the sequence $\left(c\left(T\left(1\right)\right),...,c\left(T\left(n\right)\right)\right)$ that the element in $ℂ{S}_{n}$ given by for all standard tableaux $S$ of shape $\lambda .$ So $\left(1/{a}_{T}\right){p}_{T}n={v}_{T}\in N.$ Let $Q$ be a standard tableau of shape $\lambda$ and let $k$ be minimal such that $k+1$ is southwest (strictly south and strictly west) of $k$ in $Q.$ $k$ $k+1$ In $k$ exists then ${s}_{k}W$ is a standard tableau and if $k$ doesn't exist then $Q$ is the column reading tableau, i.e. $Q$ is given by filling the boxes of $\lambda$ sequentially down columns from left to right. $C= 1 6 9 12 14 2 7 10 13 15 3 8 11 4 5 Column reading tableau$ By repeating the procedure with ${s}_{k}Q$ in place of $Q$ repeatedly we construct a sequence $Q,sk1Q, sk2sk1Q,..., skr⋯sk2sk1Q = C,$ which ends at the column reading tableau $C.$ By concatenating this sequence with a similar sequence for $T,$ $T,{s}_{{l}_{1}}T,...,{s}_{{l}_{m}}\cdots {s}_{{l}_{2}}{s}_{{l}_{1}}T=C$ we obtain a sequence $T,{s}_{{l}_{1}}T,...,C,...,{s}_{{k}_{1}}Q,Q={s}_{{k}_{1}}\cdots {s}_{{k}_{r}}{s}_{{l}_{m}}\cdots {s}_{{l}_{1}}T$ of standard tableaux of shape $\lambda$ which begins at $T$ and ends at $Q.$ If $P$ is a standard tableau in this sequence and ${v}_{P}\in N$ and ${s}_{k}P$ is the next standard tableau in the sequence, then $( sk- 1 c(P(k+1))-c(P(k)) )vP = ( 1+ 1 c(P(k+1))-c(P(k)) )vP = ( c(P(k+1))-c(P(k))+1 c(P(k+1))-c(P(k)) )vskP.$ Since ${s}_{k}P$ is standard, $c\left(P\left(k+1\right)\right)-c\left(P\left(k\right)\right)+1\ne 0$ and so it follows that ${v}_{{s}_{k}P}\in N.$ Thus since ${v}_{T}\in N$ it follows that ${v}_{Q}\in N.$ So ${v}_{Q}\in N$ for all standard tableaux of shape $\lambda .$ So $N$ contains a basis of ${S}^{\lambda }.$ So $N={S}^{\lambda }.$ So $N$ is irreducible. Let ${f}^{\lambda }$ be the number of standard tableaux of shape $\lambda .$ Then $n! = ∑λ⊢n(fλ)2.$ The proof is accomplished by giving a bijection between The matching of $w\in {S}_{n}$ with a pair $\left(P,Q\right)$ is accomplished by a recursive algorithm which begins with $\left({P}_{0},{Q}_{0}\right)=\left(\varnothing ,\varnothing \right)$ and, at step $i,$ "inserts" $w\left(i\right)$ into $\left({P}_{i-1},{Q}_{i-1}\right)$ to obtain $\left({P}_{i},{Q}_{i}\right).$ The output of the algorithm is the pair of tableaux $\left(P,Q\right)=\left({P}_{n},{Q}_{n}\right).$ The insertion step for inserting $w\left(i\right)$ into $\left({P}_{i-1},{Q}_{i-1}\right):$ Place $w\left(i\right)$ into the first column of ${P}_{i-1}$ as follows. If $w\left(i\right)$ is greater than all entries of column 1 of ${P}_{i-1}$ then place $w\left(i\right)$ at the end of column 1. Otherwise there is a unique entry in column 1 which can be replaced by $w\left(i\right)$ and preserve the standardness condition. (This is the smallest entry larger than $w\left(i\right).$) If $w\left(i\right)$ displaces an entry from column 1 then the displaced entry is inserted into column 2 (in exactly the same way that $w\left(i\right)$ was inserted into column 1). The displaced entries are successively inserted into the next column, and the process continues until there is no displaced entry. The resulting standard tableau is ${P}_{i},$ which contains one more box than ${P}_{i-1}.$ The tableau ${Q}_{i}$ is obtained by adding a box filled with $i$ to ${Q}_{i-1}$ so that ${P}_{i}$ and ${Q}_{i}$ are the same shape. To show that the algorithm produces a bijection it is necessary to confirm that the process can be reversed. To see this note that, given $\left({P}_{i},{Q}_{i}\right),$ the position of the box containing $i$ in ${Q}_{i}$ tells which box of ${P}_{i}$ must be "uninserted" to obtain ${P}_{i-1}.$ The column by column insertion of this box will bump out an entry from column 1 of ${P}_{i}$ and this entry is $w\left(i\right)$ for the permutation $w$ which corresponds to the pair $\left(P,Q\right).$ $\square$

Define elements ${x}_{k},$ $1\le k\le n,$ in the group algebra $ℂ{S}_{n}$ of the symmetric group by $x1=0, and xk = ∑i where $\left(i,k\right)\in {S}_{n}$ is the transposition which switches $i$ and $k$. The action of ${x}_{k}$ on the ${S}_{n}-$module ${S}^{\lambda }$ is given by where $c\left(T\left(k\right)\right)$ is the content of the box containing $k$ in $T.$

 Proof. The proof is by induction on $k$ using the relation $xk = sk-1 xk-1 sk-1 + sk-1.$ Clearly, ${x}_{1}{v}_{T}=0=c\left(T\left(1\right)\right){v}_{T}$ for all standard tableaux $T.$ By the induction assumption and the definition of the action of ${s}_{k-1}$ on ${S}^{\lambda },$ $xkvT = (sk-1xk-1sk-1+sk-1)vT = sk-1 (xk-1sk-1+1)vT = sk-1 ( c(T(k-1)) c(T(k))-c(T(k-1)) vT + c(T(k)) ( 1+ c(T(k-1)) c(T(k))-c(T(k-1)) )vsk-1T +vT ) = sk-1 ( c(T(k)) c(T(k))-c(T(k-1)) vT + c(T(k)) ( 1+ c(T(k-1)) c(T(k))-c(T(k-1)) )vsk-1T +vT ) = c(T(k)) sk-1 sk-1 vT = c(T(k))vT.$ $\square$

## Notes and References

Where are these from?

References?