%% ProcCrac.tex Expose Cracovie sept 2000. version Proceedings % Corrections 28 sept 2000 % \documentclass[a4paper,12pt]{article} \usepackage{amsmath,amsfonts,amsthm} \begin{document} \title{\bf Youngs's Representations of the Symmetric Group } \author{ Alain Lascoux\\ \small CNRS, Institut Gaspard Monge, Universit\'e de Marne-la-Vall\'ee\\ \small 77454 Marne-la-Vall\'ee Cedex, France\\ \small Alain.Lascoux@univ-mlv.fr } \date{September 2000} \maketitle \def\s{\scriptstyle } \def\a{\alpha} \def\b{\beta} \def\l{\lambda} \def\L{\Lambda} \def\G{\Gamma} \def\ss{\sigma} \def\d{\partial} \def\P{\psi} \def\bu{$\bullet$\quad} \def\S{{\mathfrak S}} \def\Sym{{\mathfrak Sym}} \def\LR{\Longleftrightarrow} \def\lr{\leftrightarrow} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\A{{\mathbb A}} \def\B{{\mathbb B}} \def\C{{\mathbb C}} \def\un{{\overline 1}} \def\carre{\clubsuit} \catcode`\@=11 \def\petitematrice#1{\null\vcenter {\normalbaselines \m@th \ialign {\hfil $##$\hfil &&\thinspace \hfil $##$\hfil\crcr \mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr \mathstrut \crcr \noalign {\kern -\baselineskip }}}} \def\moyennematrice#1{\null\vcenter {\normalbaselines \m@th \ialign {\hfil $##$\hfil &&\ \hfil $##$\hfil\crcr \mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr \mathstrut \crcr \noalign {\kern -\baselineskip }}}} \newdimen\squaresize \squaresize=14pt \newdimen\thickness \thickness=0.7pt \def\square#1{\hbox{\vrule width \thickness \vbox to \squaresize{\hrule height \thickness\vss \hbox to \squaresize{\hss#1\hss} \vss\hrule height\thickness} \unskip\vrule width \thickness} \kern-\thickness} \def\vsquare#1{\vbox{\square{$#1$}}\kern-\thickness} \def\blank{\omit\hskip\squaresize} \def\young#1{ \vbox{\smallskip\offinterlineskip \halign{&\vsquare{##}\cr #1}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} We describe the different matrices, due to Young, representing the symmetric group, by reading the same graph with various labellings. Orthogonal idempotents are obtained in the like manner. The only mathematical tools needed for these constructions are comparison of integers and addition of vectors. \end{abstract} Young's purpose was to decompose functions -- nowadays one would say \lq\lq tensors" -- into components according to their type of symmetry. In other words, he wanted to generalize the decomposition $$ f(x,y) = {1\over 2}\bigl( f(x,y) + (f(y,x) \bigr) + {1\over 2}\bigl( f(x,y) - (f(y,x) \bigr) $$ for functions of two variables to the case of more variables (cf. [Ro]). He first rewrote the preceding equation into $$ 1 = {1\over 2}(1+\sigma) + {1\over 2}(1-\sigma) \ , $$ where $\sigma$ is the transposition of $x,y$, and thus moved to the study of equations in the group algebra of the symmetric group. He produced different families of idempotents, and, as a by-product, he obtained various matrices representing the symmetric group (we shall refer to [JK], [Ru] for the traditional approach). A new impetus to the description of representations was given by the notions of {\it Gelfand-Tsetlin basis} (cf. [OV]), of maximal commutative subalgebras and of Yang-Baxter equation, which allow to reinterpret the constructions of Young in a simpler manner. As a matter of fact, the only mathematical tools which we require in this text are \bu Given two numbers $a$, $b$, decide whether $a\geq b$ or not \bu compute their difference $a-b$. \bu add vectors and test whether the result is a permutation. \medskip Now, introducing various initial elements associated to a given partition, ones generates labelled graphs from which one reads the matrices representing simple transpositions, as well as orthogonal idempotents. One also can directly write other matrices of representation from addition of vectors. We shall illustrate all these constructions on the partition [3,2], while giving the precise initial data for any partition. There will be some variations, to simplify labellings, in the way a partition is represented graphically by diagrams of boxes in the different quarters of the plane. When using the term \lq\lq word" instead of integral vector, we refer to computations in the free algebra, as a proper way of handling such objects as Young tableaux (cf. [LLT2]). For example, $[3,5,1,2,4]$ can be seen as the word $x_3 x_5 x_1 x_2 x_4$, as well as the Young tableau $\petitematrice{3&5\cr 1&2&4}$\ . \smallskip For a start, take the word $[1,0,2,1,0]$, vertical reading of $\petitematrice{1&2\cr 0&1\cr &0} $, and given any two adjacent letters, $a,b$, transpose them iff $a> b$. \smallskip Iterating and recording positions by colors $\ss_1,\ss_2,\ldots$, one gets a colored graph. $$ \begin{matrix} && 1\ 0\ 2\ 1\ 0 \cr && \Big\downarrow \, {}^{\sigma_2}\cr && 1\ 2\ 0\ 1\ 0 \cr & {}^{\sigma_1} \swarrow &&\searrow {}^{\sigma_3} \cr 2\ 1\ 0\ 1\ 0 &&&& 1\ 2\ 1\ 0\ 0 \cr & {}_{\sigma_3} \searrow && \swarrow {}_{\sigma_1} \cr && 2\ 1\ 1\ 0\ 0 \end{matrix} \eqno(\G1)$$ For a general partition $\b =[\b_1,\b_2,\ldots]$ (written increasingly), the starting word is $[\cdots (\b_3-1,\ldots,0) (\b_2-1,\ldots,0)(\b_1-1,\ldots,0) ]$ and can be visualized (as we have done for $[2,3]$) on the north-east diagram with column lengths the partition, each bottom box being occupied by 0, columns being occupied by consecutive numbers. Now, we keep the same graph, but interpret each word as describing the levels occupied by letters $1,2,\ldots$ in the diagram of [3,2]: $$\begin{matrix} && \young{3\cr 2&5\cr1&4\cr} \cr && \Big\downarrow \, {}^{s_3}\cr && \young{4\cr 2&5\cr1&3\cr} \cr & {}^{s_4}\! \swarrow &&\searrow \!{}^{s_2} \cr \young{5\cr 2&4\cr1&3\cr} &&&& \young{4\cr 3&5\cr1&2\cr} \cr & {}_{s_2}\! \searrow && \swarrow \! {}_{s_4} \cr && \young{5\cr 3&4\cr1&2\cr} \cr \end{matrix} \eqno(\G2) $$ The vertices of the graph are now exactly all the {\it standard Young tableaux} of a given shape, and the edges are the transpositions of consecutive letters. The labelling of edges has been changed $s_i \lr \ss_{n-i}$ (we could also have read positions from the right). \medskip We did not record values which were exchanged. Label vertices differently once more, and label arrows by the inverse of the {\bf differences} of the values exchanged ($\un$ stands for -1)~: $$\begin{matrix} && 0\ \un\ 2\ 1\ 0 \cr && \Big\downarrow \, {1\over 3}\cr \noalign{\kern 5pt} && 0\ 2\ \un\ 1\ 0 \cr & {1\over 2} \swarrow &&\searrow {1\over 2} \cr 2\ 0\ \un\ 1\ 0 &&&& 0\ 2\ 1\ \un\ 0 \cr & {1\over 2} \searrow && \swarrow {1\over 2} \cr && 2\ 0\ 1\ \un\ 0 \end{matrix} \eqno(\G3) $$ \def\long{\hbox to 1.3cm {\rightarrowfill} } The initial vector is the \lq\lq vector of contents", that is, the diagonal positions of the boxes in the diagram $$ \raise -10pt \hbox{$\young{0&1&2 \cr \un &0\cr}$} \quad {\buildrel{\s read}\over \long} \quad [0,1,2,\un,0] \quad {\buildrel{\s reverse}\over \long} \qquad [0,\un,2,1,0] $$ \medskip How to read matrices from the last graph~? The underlying vector space has a basis coded by the vertices of the graph. To represent any simple transposition $s_i$, one first erase all edges which are not labelled by $s_i$. One is left with isolated vertices (corresponding to 1-dimensional representations of $\S_2$), and pairs of vertices connected by an edge, corresponding to 2-dimensional representations. In this last case, if $\b$ is the parameter written on the edge, then the matrix representing $s_i$ on the subspace generated by the two vertices is $$\left[\, \petitematrice{ -\b & \sqrt{1-\b^2}\cr \sqrt{1-\b^2} & \b\cr}\, \right] \ .$$ In the one-dimensional case, if $i,i+1$ is a subword of the vertex, then the restriction of the representation is trivial (i.e. the submatrix is 1), otherwise it is the alternating representation (submatrix $= -1$). The full matrix $M_i$ representing $s_i$ is composed of these elementary matrices. The reader can check that the elements $\neq \pm 1$ of the following matrices constitute elementary $2\times 2$ matrices with entries $\pm \b$ or $\sqrt{1-\b^2}$ given by the graph $(\Gamma3)$. $$ M_1= \left[ \begin{matrix} -1& 0& 0& 0& 0\cr\cr 0& -1& 0& 0& 0\cr\cr 0& 0& 1& 0& 0\cr\cr 0& 0& 0& 1& 0\cr\cr 0& 0& 0& 0& 1 \end{matrix} \right] \qquad M_2= \left[ \begin{matrix} {1\over 2}& 0& 0& 0& {\sqrt{3}\over 2} \cr\cr 0& {1\over 2}& {\sqrt{3}\over 2} & 0& 0\cr\cr 0& {\sqrt{3}\over 2} & {-1\over 2}& 0& 0\cr\cr 0& 0& 0& 1& 0\cr\cr {\sqrt{3}\over 2} & 0& 0& 0& {-1\over 2} \end{matrix}\right]$$ \medskip $$M_3 = \left[ \begin{matrix} -1& 0& 0& 0& 0\cr\cr 0& 1& 0& 0& 0\cr\cr 0& 0& {1\over 3}& {\sqrt{8}\over 3} & 0\cr\cr 0& 0& {\sqrt{8}\over 3} & -{1\over 3}& 0\cr\cr 0& 0 & 0& 0& 1 \end{matrix} \right] \qquad M_4= \left[ \begin{matrix} {1\over 2}& {\sqrt{3}\over 2} & 0& 0& 0\cr\cr {\sqrt{3}\over 2}& -{1\over 2} & 0& 0& 0\cr\cr 0& 0& -{1\over 2}& 0& {\sqrt{3}\over 2}\cr\cr 0& 0& 0& 1 & 0\cr\cr 0& 0& {\sqrt{3}\over 2} & 0& {1\over 2} \end{matrix} \right] $$ Young's theorem is that these matrices represent the symmetric group, i.e. satisfy the braid relations. Only the relations $M_i M_{i+1}M_i = M_{i+1}M_i M_{i+1}$ are not immediate, but their proof amounts to check Yang-Baxter equation (see below), and finally reduces to the fact that the \lq\lq contents" choosen by Young are a \lq\lq distance" satisfying the additivity: $$ (a-b) +(b-c)= (a-c)$$ as required by Yang-Baxter's rule of choosing spectral parameters (cf. [Ya], [LLT1]). To see that Young's matrices can be interpreted as equations in the group algebra of $\S_n$, one needs now another reading of the graph. The vertices, whatever equivalent labelling is choosen (tableaux, contents, etc.), will be interpreted as element of the group algebra of $\S_n$, and an oriented edge of color $i$ and parameter $\b$ will be \smallskip \centerline{\bf \lq\lq multiplication by $(s_i+\b) \frac{1}{\sqrt{ 1-\b^2}}$" } \medskip Non-physicists usually require $\b \neq {1\over 0},\, 1 $. The braid relation $M_i M_{i+1}M_i = M_{i+1}M_i M_{i+1}$ is now seen graphically as \setbox2=\hbox{$\bullet$} \setbox31=\hbox{$ {1\over v} $} \setbox32=\hbox{$\, \nearrow$} \setbox3=\hbox{\kern 8mm\box31\box32} \setbox41=\hbox{$ \nwarrow$} \setbox42=\hbox{$\, {1\over u}$} \setbox4=\hbox{{\box41 \box42}\kern 8mm} \setbox5=\hbox{$\bullet$} \setbox6=\hbox{$\bullet $} \setbox7=\hbox{${1\over u+v} \, \bigg\uparrow$\kern 8.8mm} \setbox8=\hbox{\kern 8.8mm$\bigg\uparrow \, {1\over u+v}$} \setbox9=\hbox{$\bullet$} \setbox10=\hbox{$\bullet$} \setbox11=\hbox{\kern 8mm$ {1\over u} \ \nwarrow$} \setbox12=\hbox{$ \nearrow \ {1\over v} $\kern 8mm} %\setbox13=\hbox{$\bullet$} {\def\quad{\kern -2mm} $$ \begin{matrix} &\copy2 \cr \box3 & &\box4\cr \box5 & &\box6 \cr\noalign{\vskip 1mm}\box7 & &\box8 \cr\noalign{\vskip 1mm}\box9 & &\box10 \cr {\raise -3pt\box11} & &{\raise -3pt \box12} \cr & \box2 \cr \end{matrix}$$ } that is ({\it Yang-Baxter equation}) $$ (s+ {1\over u})\, (s'+{1\over u+v})\, (s+ {1\over v}) = (s'+ {1\over v})\, (s+{1\over u+v})\, (s'+ {1\over u}) \eqno(\star)$$ which is checked directly in the group algebra of $\S_3$. \smallskip Instead of using the basis $1,s,s',ss', s's, ss's$ of the group algebra of $\S_3$, one prefers the Yang-Baxter basis \quad $1,\ (s+ {1\over u}),\ (s'+ {1\over v}),\ (s+ {1\over u})\, (s'+{1\over u+v}),\hfill\break (s'+ {1\over v})\, (s+{1\over u+v}),\ (s+ {1\over u})\, (s'+{1\over u+v})\, (s+ {1\over v})$, the change of basis being triangular. \medskip We shall keep the same edges, but instead of starting from a bottom element equal to 1, we shall use a more sophisticated element to get irreducible representations. \smallskip Let us first notice that there are 2 distinguished elements in $\C[\S_n]$, which correspond to the two 1-dimensional representations: $$ \left\{\ \begin{matrix} \carre &= &\sum_{\ss\in \S} \ss \cr \nabla &= &\sum_{\ss \in \S} (-1)^{\ell(\ss)}\, \ss \end{matrix} \right. $$ One has more general elements by taking sums over a Young subgroup (that is, a direct product of symmetric groups diagonally embedded). \smallskip Thus for any composition $J$ of $n$ (denoting the order of the successive symmetric group composing a Young subgroup), one has two elements $$\carre_J \ ,\ \nabla_J \ . $$ Studying the product (that he denoted $P(t)N(t)$) of the sum of all permutations preserving the rows of a given tableau, multiplied by the alternating sum of the permutations fixing the columns of the same tableau, Young ([Y], QS1) found 1-dimensional spaces from which it is easy to write idempotents. This construction can be rewritten as follows. \smallskip\noindent Lemma(Young).\ {\sl For two conjugate compositions $I$, $J$, then the spaces \hfill\break $\carre_J \, \C[\S_n]\, \nabla_I$ and $ \nabla_I \, \C[\S_n]\, \carre_J$ are 1-dimensional.} \medskip Take $J$ to be a partition $\l$, and let $\mu$ be the conjugate partition. Then $$ \carre_\l \ \C[\S_n]\ \nabla_\mu\ \C[\S_n]\ \carre_\l $$ is still 1-dimensional. It contains a unique idempotent $\xi_\l$. Similarly $$ \nabla_\mu \carre_\l \ \C[\S_n]\ \carre_\l\ \C[\S_n]\ \nabla_\mu $$ contains another unique idempotent $\xi_\l^{top}$. \smallskip To have a precise expression of these two idempotents (i.e. to give their decomposition in the basis of permutations), one needs to handle double cosets. Non reduced expressions are easier to write : Young took, up to scalars, $P(t) N(t) P(t)$ and $N(t') P(t') N(t')$, with $t$ and $t'$ the bottom and top tableaux respectively (in the second graph). One can also use a coding of elements of the group algebra as polynomials to obtain compact expressions (cf. [La?]). \smallskip Now we are ready to describe the orthogonal idempotents. Take the graph with vertices labelled by the contents of Young tableaux of shape $\l$, put $\xi_\l^0:= \xi_\l$ in the bottom place and play the Yang-Baxter game ~: a path in the graph means a product of factors $(s_i+\b) /\sqrt{1-\b^2}$, as indicated by the labelling of edges. $$ \begin{matrix} && \xi_\l^4\quad \cr\cr && \Big\uparrow\! s_3\!+\! {1\over 3}\cr\cr && \xi_\l^3\quad \cr\cr & s_4+{1\over 2} \nearrow &&\nwarrow s_2\!+\!{1\over 2} \cr\cr \xi_\l^1 &&&& \xi_\l^2 \cr\cr & s_2\!+\!{1\over 2} \nwarrow && \nearrow s_4\!+\! {1\over 2} \cr\cr && \xi_\l^0\quad \cr \end{matrix} \eqno(\G4) $$ \medskip For any pair of vertices $t,t'$, let $\phi(t,t')$ be the evaluation of a path from $t$ to $t'$ in the Yang-Baxter graph (with proper normalization, i.e. adding the factors $1/\sqrt{1-\b^2}$ that we have not written). Define $$e_{t,t'}:= \phi(t,t^0)\, \xi_\l\, \phi(t^0,t') $$ Then the $e_{t,t'}$ are {\bf Young's orthogonal units}, the $e_{t,t}$ are {\bf Young's orthogonal idempotents} ([Y],QS4); they are a complete system of mutually orthogonal idempotents. Thus, the orthogonal idempotents (written $\xi^i_\l$ instead of $e_{t,t}$) are obtained from the bottom one by following any path (even non reduced), and multiplying left and right, at each step, by the factor $(s_i+\b) /\sqrt{1-\b^2}$ or $(s_i-\b) /\sqrt{1-\b^2}$ according to the orientation of the edge. One could also have started from the top of the graph, using the idempotent $\xi_\l^{top}$ instead. As we have said, both these idempotents were explicited by Young. He obtained the others by a not too easy orthonormalization process that we shall bypass ([Y], QS3). Notice that expanding the idempotents in the basis of permutations gives the entries of Young's matrices. \smallskip Modern proof is very easy, because it was realized by Jucys [Ju] that Young had found in fact a {\it Gelfand-Tsetlin basis} of the group algebra. The $e_{t,t'}$ are simultaneous two-sided eigenvectors of the {\it Jucys-Murphy} elements which constitute a maximal commutative subalgebra of $\C[\S_n]$ ( Jucys-Murphy elements are just sums of transpositions: $J_k:= \sum_{i