\documentclass[12pt]{article}

%%%%%%%%%%%%%%%%%%%%%%
% Packages
%%%%%%%%%%%%%%%%%%%%%%

\usepackage[latin1]{inputenc}
%\usepackage[francais]{minitoc}
%\usepackage[francais]{babel}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{frenchle}
\usepackage{enumerate}
\usepackage{maple2e}
\usepackage{times}
\usepackage{vaucanson}
\usepackage{stmaryrd}
\usepackage{graphicx}

\usepackage{minitoc}

\usepackage{fancyheadings}
\usepackage{makeidx}



%%%%%%%%%%%%%%%%%%%%%%
% Affichage date et l'heure courante %\isodayandtime% 
%%%%%%%%%%%%%%%%%%%%%%
\begingroup
\count0=\time \divide\count0by60 % Hour
\count2=\count0 \multiply\count2by-60 \advance\count2by\time
% Min
\def\2#1{\ifnum#1<10 0\fi\the#1}
\xdef\isodayandtime{\centerline{\2\day-\2\month-\the\year\space\2{\count0}:%
\2{\count2}}}
\endgroup

%%%%%%%%%%%%%%%%%%%%%%
% Affichage Maple
%%%%%%%%%%%%%%%%%%%%%%

\def\emptyline{\vspace{12pt}}
\def\maplemultiline#1{\begin{eqnarray*}#1\end{eqnarray*}}
\DefineParaStyle{Maple Output}
\DefineParaStyle{Warning}
\DefineCharStyle{2D Math}
\DefineCharStyle{2D Output}

%%%%%%%%%%%%%%%%%%%%%%
% Mise en page
%%%%%%%%%%%%%%%%%%%%%%

\textheight 240mm
\textwidth 160mm
\hoffset -14mm
\voffset -26mm
\parindent= 0pt
\setcounter{section}{-1}

%%%%%%%%%%%%%%%%%%%%%%
% Fontes
%%%%%%%%%%%%%%%%%%%%%%

\font\twelvesym=msbm10 at 12pt
\font\tensym=msbm10
\font\sevensym=msbm7
\font\fivesym=msbm5

\font\twelvegoth=eufb10 at 12pt
\font\tengoth=eufb10
\font\sevengoth=eufb7
\font\fivegoth=eufb5

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}
\def\fns{\footnotesize}

%%%%%%%%%%%%%%%%%%%%%%
% Fl\^eches et traits
%%%%%%%%%%%%%%%%%%%%%%

\def\ra{\rightarrow}
\def\da{\downarrow}
\def\sw{\swarrow}
\def\se{\searrow}
\def\ne{\nearrow}
\def\lra{\leftrightarrow}
\def\Lra{\Longrightarrow}
\def\ul#1{\underline{#1}}

%%%%%%%%%%%%%%%%%%%%%%
% Divers
%%%%%%%%%%%%%%%%%%%%%%

\def\b{$\bullet\ $}
\def\mod{{\rm mod}}
\def\quo{{\rm quo}}
\def\irem{{\rm rem}}
\def\peb#1{\lfloor #1\rfloor}
\def\peh#1{\lceil #1\rceil}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
\def\que{{\bf Question}}
\def\rep{{\bf Reponse}}
\def\pointir{\unskip . --- \ignorespaces}
\def\nequiv{\equiv\hspace{-9pt}\slash\hspace{9pt}}
\def\ra{\rightarrow}
\def\lra{\leftrightarrow}
\def\mup{MuPAD}
\def\tr#1#2{{\rm trunc}(#1,#2)}
\def\l{\langle}
\def\r{\rangle}


%%%%%%%%%%%%%%%%%%%%%%
% \'Enonc\'es
%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{example}{Exemple}[section]
\newtheorem{exercice}{Exercice}[section]
\newtheorem{note}[example]{Note}
\newtheorem{exo}[example]{Exercice}
\newtheorem{mexo}[example]{Exercice Machine}
\newtheorem{exm}[example]{Exerc. Machine}
\newtheorem{theorem}[example]{Th\'eor\`eme}
\newtheorem{corollary}[example]{Corollaire}
\newtheorem{definition}[example]{D\'efinition}
\newtheorem{proposition}[example]{Proposition}
\newtheorem{prdef}[example]{Proposition/Definition}
\newtheorem{algorithme}[example]{Algorithme}
\newtheorem{lemma}[example]{Lemme}
\newtheorem{remark}[example]{Remarque}
\newtheorem{appli}[example]{Applications}


\def\Preuve{\medskip\noindent {\it Preuve --- \ }}
\def\cqfd{\hfill $\square$ \bigskip}
\def\Proof{\medskip\noindent {\it Proof --- \ }}


%%%%%%%%%%%%%%%%%%%%%%
% Lettres
%%%%%%%%%%%%%%%%%%%%%%

\def\A{{\mathcal A}}
\def\B{{\mathbb B}}
\def\K{{\mathbb K}}
\def\E{{\mathbb E}}
\def\F{{\mathbb F}}
\def\M{{\mathcal M}}
\def\N{{\mathbb N}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\X{{\mathbb X}}
\def\Cl{\mathcal{C}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\ep{\epsilon}
\def\om{\omega}
\def\si{\sigma}
\def\Si{{\Sigma}}
\def\Q{{\mathbb Q}}
\def\SG{\frak{S}}
\def\V{\mathbb{V}}

%%%%%%%%%%%%%%%%%%%%%%
% Divers
%%%%%%%%%%%%%%%%%%%%%%

\def\b{$\bullet\ $}
\def\hs{\hbox to 3mm{}}
\def\ra{\rightarrow}
\def\mod{{\rm mod}}
\def\quo{{\rm quo}}
\def\irem{{\rm rem}}
\def\peb#1{\lfloor #1\rfloor}
\def\peh#1{\lceil #1\rceil}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
\def\binomial#1#2{\begin{pmatrix} #1 \cr #2\end{pmatrix}}

\def\la{\leftarrow}
\def\da{\downarrow}
\def\ua{\uparrow}
\def\sea{\searrow}
\def\swa{\swarrow}
\def\mref#1{(\ref{#1})}
\def\up#1{\raise 1ex\hbox{\fns#1}}
\def\cls{$\clubsuit$}
\def\sps{$\spadesuit$}
\def\hes{$\heartsuit$}
\def\dis{$\diamondsuit$}
\def\fst{{\bf F\hspace{-1mm}St}}

%%%%%%%%%%%%%%%%%%%%%%
% Sauts
%%%%%%%%%%%%%%%%%%%%%%

\def\ss{\smallskip}
\def\ms{\medskip}
\def\bs{\bigskip}
\def\small{\footnotesize}
\def\b{$\Bullet\ $}
\def\gcr{\hfill\cr}
\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\btu{\bigtriangleup}
\def\Box{\triangle}
\def\mhs{\hbox to 1cm{}}

%%%%%%%%%%%%%%%%%%%%%%
% Operateurs et espaces
%%%%%%%%%%%%%%%%%%%%%%

\def\scal#1#2{\langle #1 | #2 \rangle}
\def\kd#1#2{\delta{#1#2}}
\def\ncs#1#2{#1\langle\langle #2\rangle\rangle}
\def\rncs#1#2{#1^{\rm rat}\langle\langle #2\rangle\rangle}
\def\ncp#1#2{#1\langle #2\rangle}
\def\func#1#2{{\cal F}(#1,#2)}
\def\End{\mathrm{End}}
\def\Aut{\mathrm{Aut}}
\def\Hom{\mathrm{Hom}}
\def\ev{{espace vectoriel} }
\def\sev{{sous espace vectoriel }}
\def\Endo{{\mathfrak E}{\rm nd}}

%%%%%%%%%%%%%%%%%%%%%%

\author{\sc G. H. E. Duchamp \& Christophe Tollu \& Frédéric Toumazet
\footnote{Pri\`ere de nous signaler les erreurs.}}

\title{Notes du cours de ``Calcul Symbolique, Fonctions Sym\'etriques et Sp\'eciales''\\ 
MMI 2006-2007.\\
(Version provisoire)}

\date{}
\begin{document}

\maketitle

\isodayandtime

\tableofcontents

\section{Pr\'eambule}

Ce cours est commun aux \'etudiants originaires des fili\`eres Informatique et Math\'ematique. 
Il est con\c cu de fa\c con \`a permettre aux \'etudiants des deux sensiblilt\'es 
\begin{itemize}
\item d'acqu\'erir des \'elements de culture g\'en\'erale scientifique n'auraient pas \'et\'e acquis pendant leur parcours (comme les liens entre alg\`ebre, combinatoire, analyse et g\'eom\'etrie)
\item d'unifier les disciplines classiques et certains th\`emes innovants   
\end{itemize}
Les illustrations seront faites en Maple et Mupad, mais le contenu de l'enseignement est, bien entendu, ind\'ependant du langage.

\ss
Le poly correspond \`a un programme maximal. Seule une partie de celui-ci sera trait\'ee cette ann\'ee (cette partie sera d\'elimit\'ee pendant le Forum). 
Les exercices qui sont l\`a pour aider \`a la compr\'ehension du cours.\\
II se peut que vous ne compreniez pas certains \'enonc\'es, dans ce cas choisissez que les questions que vous 
\^etes capables d'aborder ... et contactez-nous rapidement pour le d\'ecodage du reste.\\

\ss
Les parties en {\small petits caract\`eres} sont des suppl\'ements et ne sont pas obligatoires.

\section{Introduction}

Le cours qui suit est un mélange entre Mathématiques et Informatique. En particulier toutes les notions seront \ul{effectives} et \ul{implémentables}. Le cours débute par une description assez large et plutôt théorique, mais nous verrons très tôt 
\begin{itemize}
	\item des exemples complètement dévissés
	\item une implémentation et des programmes
\end{itemize}

La première partie décrit les liens entre les notions suivantes

\bs
\begin{figure}[h]
\begin{center}
\LargePicture\VCDraw{
\begin{VCPicture}{(0,0)(10,6)}
\ChgEdgeLabelScale{0.7}
\StateVar[\shortstack{Théorie des représentations : $k$ corps, $\Si$ structuré}]{(2,1)}{A}
\StateVar[\shortstack{Automates : $k$ semi-anneau, $\Si$ alphabet}]{(9,3)}{B}
\StateVar[\shortstack{Actions}]{(5,5)}{C}

\ArcL{C}{B}{}
\ArcR{C}{A}{}
\Edge{B}{A}{}
\Edge{A}{B}{}

\end{VCPicture}}
\end{center}
\caption{Les différents domaines de ce cours.}
\label{exemple2} 
\end{figure} 

\section{Graphes et structures de transition}

L'élément le plus complet de ces modèles est la flêche

\ms
\begin{figure}[h]
\begin{center}
\LargePicture\VCDraw{
\begin{VCPicture}{(0,0)(10,2)}
\ChgEdgeLabelScale{1}
\State[q_1]{(2,1)}{A}
\State[q_2]{(7,1)}{B}

%\ArcL{A}{B}{a|w}
\EdgeL{A}{B}{a|w}

\end{VCPicture}}
\end{center}
\end{figure} 


\begin{enumerate}[i)]
	\item $q_1,q_2\in Q$ $Q$ est un ensemble (fini ou infini d'états) 
	\item $a$ est le symbole qui agit
	\item $\al\in k$ est un coefficient. L'ensemble ($k$) des coefficients est muni de deux lois $+,\times$, 
	\ul{associatives}, $+$ est \ul{commutative} et $\times$ soit \ul{distributive} (à droite et à gauche) sur $+$. 
\end{enumerate}

Nous verrons plus bas que ces propriétés sont nécessaires au bon fonctionnement du modèle. Si $f$ est la flêche ci-dessus nous noterons 

\renewcommand{\labelitemi}{$\bullet$}

\begin{itemize}
	\item $\al(f)=q_1$, source ou origine de $f$ 
	\item $\be(f)=q_2$, but ou extrémité de $f$
	\item $\lambda(f)=a$, étiquette de $f$
	\item $weight(f)$, poids, coût ou coefficient de transition de $f$
\end{itemize}

On appelle \ul{chemin} toute suite finie $c=f_1f_2\cdots f_n$ de flêches telle que\\ 
$(\forall j<n)(\be(f_j)=\al(f_{j+1}))$. On étend aussitôt les notions précédentes aux chemins par (avec $c=f_1f_2\cdots f_n$)

\begin{equation}\label{extension}
\left.
\begin{array}{l}
	\bullet\ \al(c)=\al(f_1),\textrm{ source ou origine de } c\\ 
	\bullet\ \be(c)=\be(f_n),\textrm{ but ou extrémité de } c\\
	\bullet\ \lambda(c)=\lambda(f_1)\lambda(f_2)\cdots \lambda(f_n)\textrm{ (concaténation dans } \Sigma^*\textrm{)},\textrm{  étiquette de } c\\
	\bullet\ weight(c)=weight(f_1)weight(f_2)\cdots weight(f_n)\textrm{ (produit dans } k \textrm{), poids de } c.
\end{array}
\right\}	
\end{equation}

\bs
Lorsque l'on a deux chemins $c_1=f_1f_2\cdots f_{n_1}$ et $c_2=f_{n_1+1}f_{n_1+2}\cdots f_n$ \ul{consécutifs} (c'est à dire que $\be(c_1)=\al(c_2)$), on définit leur concaténation $c_1c_2$ par  $f_1f_2\cdots f_{n_1}f_{n_1+1}f_{n_1+2}\cdots f_n$.\\
On vérifie facilement que les formules \mref{extension} sont encore vraies pour des suites (concaténables) de chemins ce qui permet de considérer les flêches comme des chemins de longueur $1$.
 

Le poids d'un ensemble de chemins de m\^eme source, but et \'etiquette est la somme des poids 
des chemins  de cet ensemble. Ainsi, si on a deux chemins (de même étiquette) 
le poids de cet ensemble de chemins est $\al+\be$. 

\bs
\begin{figure}[h]
\begin{center}
\LargePicture\VCDraw{
\begin{VCPicture}{(0,0)(10,2)}
\ChgEdgeLabelScale{0.7}
\State[q_1]{(2,1)}{A}
\State[q_r]{(7,1)}{B}

\ArcL{A}{B}{u|\al}
%\ArcR{A}{B}{u|\be}
%\EdgeL{A}{B}{u|\al}
\EdgeR{A}{B}{u|\be}

\end{VCPicture}}
\end{center}
\end{figure} 

On a donc que les poids se multiplient en s\'erie et 
s'aditionnent en parall\`ele. Les diagrammes suivants montrent la n\'ecessit\'e des propriétés exigées pour $+$ et $\times$.

\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Diagramme 	& Identit\'e 	& Nom \\
\hline
\hline
$\ \ \ \stackrel{a|\al}{\ra}$ &&\\
$p  \stackrel{a|\be}{\ra} q$ & $\al+(\be+\ga)=(\al+\be)+\ga$ & Associativit\'e de $+$\\
$\ \ \ \stackrel{a|\ga}{\ra}$ &&\\
\hline
$p {\stackrel{a|\al}{\ra} \atop \stackrel{a|\be}{\ra}} q$ & $\al+\be=\be+\al$ & Commutativit\'e de $+$\\
\hline
$p\stackrel{a|\al}{\ra} q \stackrel{b|\be}{\ra} r \stackrel{c|\ga}{\ra} s$ &
$\al(\be\ga)=(\al\be)\ga$ & Associativit\'e de $\times$\\
\hline
$p {\stackrel{a|\al}{\ra} \atop \stackrel{a|\be}{\ra}} q \stackrel{b|\ga}{\ra} r$ & $(\al+\be)\ga=\al\ga+\be\ga$ &
Distributivit\'e (droite) de $\times$ sur $+$\\
\hline
$p\stackrel{a|\al}{\ra} q {\stackrel{b|\be}{\ra} \atop \stackrel{b|\ga}{\ra}} r $ & $\al(\be+\ga)=\al\be+\al\ga$ &
Distributivit\'e (gauche) de $\times$ sur $+$\\
\hline
\end{tabular}
\end{center}

\begin{remark} i) La plupart du temps on a des éléments neutres pour $+$ et $\times$. S'il n'y sont pas, on peut montrer qu'il est possible de les rajouter\footnote{en langage académique cette opértion se nomme l'``adjonction''.}.\\
ii) Les règles ``multiplier'' en série et ``ajouter'' en parallèle sont - aussi - celles des probabilités.
\end{remark} 

\begin{exo}\label{aut1} On considère l'automate probabiliste de la figure \mref{f1}.\\
a) D\'eterminer la fonction génératrice de probabilité 
\begin{equation}
	\sum_{n\geq 0}p_nz^n
\end{equation}
où $p_n$ est la probabilité de passer de l'entrée (avec probabilité d'entrée $p_e$) à la sortie (avec probabilité de sortie $p_s$) avec un chemin de longueur $n$.\\ 
des chemins réussis  de l'automate probabilite  de la figure \mref{f1}.
b) D\'eterminer la fonction $\{P,F\}^*\mapsto \R$ d\'etermin\'ee par l'automate ci-dessous (les charges d'entr\'ee et de sortie sont $p_e,p_s$).\\ 

\begin{figure}[h]\label{aut1}
\begin{center}
\LargePicture
\VCDraw{
\begin{VCPicture}{(0,0)(8,3)}
\ChgEdgeLabelScale{0.6}
\State[1]{(-2,1)}{A}
\State[2]{(2,1)}{B}
\State[3]{(6,1)}{C}
\State[4]{(10,1)}{D}

\InitialR{w}{A}{p_e}
\EdgeL{A}{B}{\IOL{P}{(0.5)}}
\LoopN{A}{\IOL{F}{(0.5)}}
\EdgeL{B}{C}{\IOL{F}{(0.5)}}
\ArcL{C}{B}{\IOL{P}{(0.5)}}
\EdgeL{C}{D}{\IOL{F}{(0.5)}}
\LoopN{B}{\IOL{P}{(0.5)}}
\FinalR{e}{D}{p_s}
\end{VCPicture}}
\end{center}
\caption{Un automate propos\'e par les \'etudiants}\label{f1}
\end{figure}
\end{exo}

{\bf Correction de l'exercice} \mref{aut1} a) Les matrices de transition étant notées $M_P,M_F$, si on ne compte que la longueur des chemins, on a la matrice de transition unique $M=M_P+M_F$. Il est facile de voir (par récurrence par exemple) que $M^k[i,j]$ est la probabilité de passer de l'état $i$ à l'état $j$ en $k$ coups (i.e. avec un chemin de longueur $k$) d'où $p_n=p_eM^n[1,4]p_s$. Par suite, la SG de probabilité est 
\begin{equation}
	\sum_{n\geq 0}p_nz^n=\sum_{n\geq 0}p_eM^n[1,4]p_sz^n= p_ep_s(\sum_{n\geq 0}M^nz^n)[1,4]=
	p_ep_s(1-zM)^{-1}[1,4]
\end{equation}

ceci se calcule avec la programme ci-dessous.

\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{with(linalg):}{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}
Warning, the protected names norm and trace have been redefined and
unprotected
\end{maplettyout}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{Mp:=matrix(4,4,[0,1/2,0,0,0,1/2,0,0,0,1/2,0,0,0,0,0,0]); }{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{Mp := matrix([[0, 1/2, 0, 0], [0, 1/2, 0, 0], [0, 1/2, 0, 0], [0, 0,
0, 0]]);}{%
\[
\mathit{Mp} :=  \left[ 
{\begin{array}{rcrr}
0 & {\displaystyle \frac {1}{2}}  & 0 & 0 \\ [2ex]
0 & {\displaystyle \frac {1}{2}}  & 0 & 0 \\ [2ex]
0 & {\displaystyle \frac {1}{2}}  & 0 & 0 \\ [2ex]
0 & 0 & 0 & 0
\end{array}}
 \right] 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{Mf:=matrix(4,4,[1/2,0,0,0,0,0,1/2,0,0,0,0,1/2,0,0,0,0]);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{Mf := matrix([[1/2, 0, 0, 0], [0, 0, 1/2, 0], [0, 0, 0, 1/2], [0, 0,
0, 0]]);}{%
\[
\mathit{Mf} :=  \left[ 
{\begin{array}{crcc}
{\displaystyle \frac {1}{2}}  & 0 & 0 & 0 \\ [2ex]
0 & 0 & {\displaystyle \frac {1}{2}}  & 0 \\ [2ex]
0 & 0 & 0 & {\displaystyle \frac {1}{2}}  \\ [2ex]
0 & 0 & 0 & 0
\end{array}}
 \right] 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{M:=matadd(Mp,Mf);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{M := matrix([[1/2, 1/2, 0, 0], [0, 1/2, 1/2, 0], [0, 1/2, 0, 1/2],
[0, 0, 0, 0]]);}{%
\[
M :=  \left[ 
{\begin{array}{cccc}
{\displaystyle \frac {1}{2}}  & {\displaystyle \frac {1}{2}}  & 0
 & 0 \\ [2ex]
0 & {\displaystyle \frac {1}{2}}  & {\displaystyle \frac {1}{2}} 
 & 0 \\ [2ex]
0 & {\displaystyle \frac {1}{2}}  & 0 & {\displaystyle \frac {1}{
2}}  \\ [2ex]
0 & 0 & 0 & 0
\end{array}}
 \right] 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{I4:=matrix(4,4,(i,j)->if i=j then 1 else 0 fi);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{I4 := matrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0,
1]]);}{%
\[
\mathit{I4} :=  \left[ 
{\begin{array}{rrrr}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array}}
 \right] 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{M2:=matadd(I4,M,1,-z);}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{M2 := matrix([[1-1/2*z, -1/2*z, 0, 0], [0, 1-1/2*z, -1/2*z, 0], [0,
-1/2*z, 1, -1/2*z], [0, 0, 0, 1]]);}{%
\[
\mathit{M2} :=  \left[ 
{\begin{array}{cccc}
1 - {\displaystyle \frac {z}{2}}  &  - {\displaystyle \frac {z}{2
}}  & 0 & 0 \\ [2ex]
0 & 1 - {\displaystyle \frac {z}{2}}  &  - {\displaystyle \frac {
z}{2}}  & 0 \\ [2ex]
0 &  - {\displaystyle \frac {z}{2}}  & 1 &  - {\displaystyle 
\frac {z}{2}}  \\ [2ex]
0 & 0 & 0 & 1
\end{array}}
 \right] 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\mapleinline{active}{1d}{inverse(M2)[1,4];}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\mapleinline{inert}{2d}{z^3/(-2+z)/(-4+2*z+z^2);}{%
\[
{\displaystyle \frac {z^{3}}{( - 2 + z)\,( - 4 + 2\,z + z^{2})}} 
\]
%
}
\end{maplelatex}

\end{maplegroup}
\begin{maplegroup}
\begin{mapleinput}
\end{mapleinput}

\end{maplegroup}

finalement, la série cherchée est 
\begin{equation}
	\frac{t^3p_ep_s}{(2-t)(4-2t-t^2)}=p_ep_s\bigg(
	\frac{1}{8}t^3+\frac{1}{8}t^4+\frac{1}{8}t^5+\frac{7}{64}t^6+\frac{3}{32}t^7+\frac{5}{64}t^8+\frac{33}{512}t^9+\cdots\bigg)
\end{equation}
	
\ss
b) La série cherchée se calcule selon le même principe, il s'agit de remplacer 
$\sum_{n\geq 0}M^nz^n$ ({\small $=(1-zM)^{-1}$}), i.e. l'étoile de $zM$ par l'étoile de $P M_P +F M_F$, ce qui se fait par les formules \mref{blockstar}.

\subsection{Applications}

\subsubsection{Chaînes de Markov à une matrice}

\subsubsection{Plusieurs matrices}

\subsection{Co\^uts et poids}

\section{Décomposition}

\subsection{Cadre général}
Un graphe pondéré détermine une \ul{structure de transition} qui est équivalente à la donnée d'une application $\Si\mapsto End(V)$.

Cela revient à se donner une famille de matrices $\{M_\al\}_{\al\in \Si}$ ou d'opérateurs $\{\varphi_\al\}_{\al\in \Si}$ qui agissent sur un espace vectoriel $V$, soit une application\footnote{On rappelle que $\End(V)$ désigne l'espace des applications linéaires 
$V\mapsto V$.} 
$\mu\ :\ \Si\mapsto \End(V)$. Les opérateurs $\varphi_\al$ sont souvent appelés \ul{actions} de $\Si$ sur $V$.\\
Une telle structure est appelée \ul{représentation linéaire} de l'ensemble $\Si$ et $V$ s'appelle alors un $\Si$-module. Si $\Si$ est doué d'une structure supplémentaire (monoïde, groupe, algèbre associative, algèbre de Lie, algèbre de Hopf, de Jordan, $C^*$-algèbre, superalgèbre), il faut, de plus, vérifier la compatibilité de cette structure suppémentaire avec $\mu$ (on demande en général que $\mu$ soit un morphisme).  

\begin{definition}\label{morph_mod}
	Soit $(\mu_\al)_{\al\in \Si}$ une famille d'opérateurs agissant sur un \ev $V$.\\ 
i) On dit que qu'un sous-espace $W\subset V$ est 
	
\begin{itemize}
	\item \ul{stable} si $(\forall \al\in \Si)(\mu_\al(W)\subset W)$
	\item \ul{irréductible} si pour tout sous-espace stable $(0)\subset W_1\subset W$, on a $W_1=(0)$ ou $W_1=W$. 
\end{itemize}

ii) Si $V=\oplus_{i\in I}V_i$ et que les $V_i$ sont stables on dit que $V=\oplus_{i\in I}V_i$ est une décomposition de $V$.

iii) Soient deux $\Si$-modules $U$ et $V$. On dit qu'une application linéaire $\varphi\ :\ U\mapsto V$ est $\Si$-linéaire si elle commute avec tous les $\mu_\al$ soit

\begin{equation}
	(\forall \al\in \Si)(\forall v\in U)(\varphi\circ\mu_\al(v)=\mu_\al\circ\varphi(v)).
\end{equation}
On dit aussi que $\varphi$ est un morphisme de $\Si$-modules. On note $\Hom_\Si(U,V)$ l'ensemble des applications $\Si$-linéaires $U\mapsto V$ (resp. $\End_\Si(U)$ si $U=V$.     
\end{definition}

\begin{remark}
i) On n'a pas toujours de décomposition de $V$ en plusieurs irréductibles non nuls, comme le montre le cas d'un seul opérateur dont la matrice dans une base de $V$ est {\tiny $\begin{pmatrix} 1 & 0\cr 1 & 1\end{pmatrix}$}.\\
ii) Si $V$ admet une décomposion en irréductibles (c'est toujours le cas, nous le verrons, pour les groupes finis) on dit que $V$ est semi-simple ou complètement réductible.\\
iii) Avec la notation précédente, l'ensemble des applications (seulement !) linéaires $U\mapsto V$ se note $\Hom_k(U,V)$.\\
\end{remark}

\begin{exo}
(Généralités) Soit $X$ un ensemble. Pour $n,k\in \N$, la classe de Burnside $B(n,k)$ est l'ensemble des applications $f\ :\ X\mapsto X$ telles que $f^n=f^{n+k}$ où $f^n$ est la suite d'applications définies par 
\begin{equation}
	f^0=Id_X\ ;\ f^{n+1}=f\circ f^n
\end{equation}
{\small{\bf Remarque}\pointir C'est la ``puissance compositionnelle'' définie, pour $n>0$ par $f^n=\underbrace{f\circ f\cdots \circ f}_{\textrm{$n$ fois}}$}.

Deux classes sont courantes : $B(1,1)$, les idempotents et $B(0,2)$, les involutions (resp. projecteurs ou symétries dans le cas d'applications linéaires).\\ 
1) Soit $V$ un $k$-\ev et $p$, un projecteur de $V$.\\
a) Montrer que $V=ker(p)\oplus im(p)=V_0\oplus V_1$\\
b) Ici $\Si=\{p\}$ Montrer que 
\begin{equation}
\End_\Si(V)=\{f\in \End(V)| f(V_0)\subset V_0,\ f(V_1)\subset f(V_1)\}	
\end{equation}
2) a) On suppose que $1/2\in k$. Soit $s$ une symétrie de $V$. Montrer que
\begin{equation}
p_{(1)}=\frac{1}{2}(s+Id)\ \textrm{ et }\ p_{(-1)}=\frac{1}{2}(s-Id)	
\end{equation}
sont des projecteurs.\\ 
b) On pose $\Si_{1}=\{s\}\ ;\ \Si_{2}=\{p_{(-1)},p_{(1)}\}$. Montrer que $\End_{\Si_1}(V)=\End_{\Si_2}(V)$.\\
c) À l'aide de (1.b) et (2.b), caractériser $\End_{\Si_1}(V)$. 
\end{exo}

\`A ce stade, on ne peut véritablement décider si une action est ``à droite'' ou ``à gauche'' (et, à vrai dire, on peut les noter du côté que l'on veut). Si on veut garder trace de la succession des actions, c'est la structure de mot qu'il faut utiliser et étendre $\mu$ en une application 
$$
\bar\mu\ :\ \Si^*\mapsto \End(V)
$$ 
qui transforme la concaténation en composition. Là, selon que les actions sont notées à droite ou à gauche on aura
\begin{equation}
\bar\mu(uv)=\bar\mu(u)\circ\bar\mu(v) \textrm{ ou bien } \bar\mu(uv)=\bar\mu(v)\circ\bar\mu(u).
\end{equation}

Ceci nous amène à la structure minimale pour ``préparer les actions'', c'est la notion de représentation d'un semigroupe\footnote{Un semigroupe est un ensemble muni d'une loi associative.}.

\begin{definition}\label{rep_semigp}
Soit $(G,\ast)$ un semigroupe et $(\mu_\al)_{\al\in G}$ une représentation de $G$ dans $V$. On dit que $\mu$ est une représentation ``à gauche'' si 
\begin{equation}
(\forall u,v\in G) (\mu_{\al\ast \be}=\mu_\al\circ\mu_\be)
\end{equation}	
et ``à droite'' si 
\begin{equation}
(\forall u,v\in G) (\mu_{\al\ast \be}=\mu_\be\circ\mu_\al).
\end{equation}	
\end{definition}

\begin{note}
	Cette définition est conditionnée par le déplacement des parenthèses en effet, si l'on note $q.\al$ (resp. $\al.q$) pour $\mu_\al(q)$ dans le cas d'une représentation à droite (resp. à gauche), on a $(q.\al).\be=q.(\al\ast\be)$ (resp. $\al.(\be.q)=(\al\ast\be).q$).
\end{note}

\begin{example}
Nous considérons le groupe symétrique $\SG_3=\{[123],[132],[213],[231],[312],[321]\}$ agissant sur les coordonnées de l'espace (ambiant) par permutation des coordonnées des vecteurs. Nous notons $(e_i)_{i=1,2,3}$ la base canonique. Soit 
$$
e_1=(1,0,0)\ ;\ e_2=(0,1,0)\ ;\ e_3=(0,0,1)
$$
Comme le groupe symétrique est engendré par $\si_1=[213]$ et $\si_2=[132]$, il suffit de coder les actions de ces générateurs sur l'espace décrit à l'aide de ses vecteurs de base.

\bs
\begin{figure}[h]
\begin{center}
\LargePicture\VCDraw{
\begin{VCPicture}{(0,0)(10,2)}
\ChgEdgeLabelScale{0.7}
\State[e_1]{(0,1)}{A}
\State[e_2]{(5,1)}{B}
\State[e_3]{(10,1)}{C}

\EdgeR{A}{B}{\sigma_1}
\EdgeR{B}{A}{}
\EdgeR{B}{C}{\sigma_2}
\EdgeR{C}{B}{}
\LoopW{A}{\sigma_2}
\LoopE{C}{\sigma_1}

\end{VCPicture}}
\end{center}
\caption{Le $\SG_3$-module $k^3$.}
\label{exemple1} 
\end{figure} 
\end{example}

{\sc Décomposition en sous-modules irréductibles}\pointir\\
On remarque d'abord que le vecteur $e_{123}=e_1+e_2+e_3=(1,1,1)$ est invariant par le groupe. Donc la droite $k.e_{123}$.\\ 
Le produit scalaire usuel $\scal{(x,y,z)}{(x',y',z')}=xx'+yy'+zz'$ (ici $k=\R$, pour $\C$ prendre le premier vecteur conjugué) est invariant par $\SG_3$ (voir exercice \mref{scal_inv}). Par suite, le plan $(e_{123})^\perp$ (d'équation $x+y+z=0$ est invariant). Ce plan est engendré par $e_{1}-e_{2}=(1,-1,0)$ et $e_{2}-e_{3}=(0,1,-1)$. Ce module est décrit dans la figure \mref{exemple2}.

\bs
\begin{figure}[h]
\begin{center}
\LargePicture\VCDraw{
\begin{VCPicture}{(0,0)(10,2)}
\ChgEdgeLabelScale{0.7}
\StateVar[e_1-e_2]{(2,1)}{A}
\StateVar[e_2-e_3]{(7,1)}{B}

\EdgeR{B}{A}{\sigma_1|1}
\LoopW{A}{\sigma_1|-1,\sigma_2|1}

\ArcL{A}{B}{\sigma_2|1}
\LoopE{B}{\sigma_2|-1, \sigma_1|1}

\end{VCPicture}}
\end{center}
\caption{Un sous-module du $\SG_3$-module $k^3$.}
\label{exemple2} 
\end{figure} 

\begin{exo}
	Montrer que le module de la figure \ref{exemple2} est irréductible. 
\end{exo}

\begin{exo} 
{\sc Décomposition de la repésentation régulière gauche de $\SG_3$ dans $\R[\SG_3]$.}\pointir \\
Dans tout l'exercice, $G=\SG_3$.\\ 
Les données sont les suivantes :
\begin{itemize}
	\item l'espace est celui des fonctions $G\mapsto \R$, notées comme des sommes $f:=\sum_{h\in G}f(h)h$. Cet espace est noté $\R[G]$. 
	\item les éléments de $G$ sont notés comme des listes et celui qui est à gauche agit par valeurs sur celui qui est à droite.

\begin{eqnarray}
&	G=\SG_3=\Big\{[123],[132],[213],[231],[312],[321]\Big\} &\cr
&	g_1.g_2=\Big[g_1[g_2[1]],g_1[g_2[2]],g_1[g_2[3]]\Big] &
\end{eqnarray}
	\item $G$ agit sur les fonctions par linéarité soit
\begin{equation}
	g.(\sum_{h\in G}f(h)h)=\sum_{h\in G}f(h)g.h
\end{equation}
\end{itemize}

\ss
{\small
{\bf Remarque}\pointir	On définit de même l'action à droite (mais nous n'en aurons besoin que plus tard) par
\begin{equation}
	(\sum_{h\in G}f(h)h).g=\sum_{h\in G}f(h)h.g
\end{equation}
}

1) Montrer que, pour tout $g\in G$, l'application $\rho(g)\ :\ \R[G]\mapsto \R[G]$ est linéaire.\\
2) Montrer que c'est bien une représentation du groupe $G$ au sens où 

\begin{equation}
(\forall g_1,g_2\in G)(\rho(g_1.g_2)=\rho(g_1)\circ \rho(g_2))
\end{equation}
(il suffit de montrer l'égalité des images sur une base).\\
3) Montrer que les droites 
\begin{equation}
	D_1=\R(\sum_{g\in G}g)\ ;\ D_{-1}=\R(\sum_{g\in G}(-1)^{inv(g)}g)
\end{equation}
sont invariantes par $\rho$.\\
4) Soit $w_1=[123]-[213]+[132]-[231]$. Décrire le module $W_1$ engendré par $w_1$ sous l'action de $\rho$.\\
5) a) Calculer $w_2=w_1.[213]$. Soit $W_2$ le module engendré par $w_2$, montrer que l'on a
\begin{equation}\label{split3}
	\R[G]= W_1\oplus W_2\oplus D_{1}\oplus D_{-1}= W_1\oplus W_2\oplus W_3\oplus W_4
\end{equation}
b) Soit $1_{\R[G]}=e_1+e_2+e_3+e_4$, la décomposition de $1_{\R[G]}$ selon la somme directe \mref{split3}. Montrer que 

\begin{tabular}{cc}
i) $(\forall i,j\in [1..4])(e_ie_j=\delta_{ij}e_i)=\delta_{ij}e_j)$  &\hspace{1cm} ii) $\R[G]e_i=W_i$
\end{tabular}
\end{exo}

{\bf Commentaire}\pointir 
 La propriété b)i) entraine que les $e_i$ sont idempotents (i.e. vérifient $ee=e$). Si une famille d'éléments vérifie b)i), on dit que c'est une {\it famille d'idempotents orthogonaux}. Si, de plus, $1=\sum_{i}e_i$, on dit que la famille est {\it complète}. Et si, de plus, tous les $W_i=\A e_i$ sont irréductibles, on dit que c'est une {\it Famille Complète d'Idempotents Orthogonaux Minimaux} (FCIOM). On verra qu'une telle famille est l'outil de décomposition de $\C[G]$ comme somme d'algèbres de matrices. 

\hfill$\diamondsuit$\\



\subsection{Décomposition automatique de modules}\label{dec}

Cet algorithme est l'\oe uvre de Schützenberger \cite{BR,FE,S,Ei}. En effet, il fut inventé pour l'optimisation des automates à multiplicités \cite{BR}.

\ss
Un automate à multiplicités dans \(k\) est défini par la donnée d'un 
quintuplet \((\Si,Q,I,T,F)\) \cite{BR} 
où 

\begin{itemize}
	\item  \(\Si\) est l'alphabet (de commande)
	\item  \(Q\) est l'ensemble fini des états
	\item  \(I\subset Q\) est l'ensemble des états initiaux
	\item  \(F\subset Q\) est l'ensemble des états finaux
	\item  \(T\subset Q\times  A\times k\times Q\) contient les arcs orientés reliant les états entre eux. 
\end{itemize}	

Les actions sont notées à droite pour être compatibles avec la séquentialité des mots. Des données précédentes, on déduit la \ul{représentation linéaire} $(\lambda,\mu,\gamma)$ de l'automate. 	

\bs
Nous ne toucherons pas dans ce cours, plus centré sur les représentations, à la très belle et très générale théorie des automates (qui appartient en propre à l'Informatique Théorique), mais verrons comment on peut appliquer quelques-uns de ses concepts au calcul dans les modules.\\
Dans le cas (bien particulier) où l'ensemble des coefficients est un corps (ou même un anneau) ces deux théories sont équivalentes puisque, vue de la théorie des représentations, les automates sont essentiellement la donnée d'un $\Si$-module engendré par un seul vecteur (dit \ul{cyclique}) avec une fonction d'observation (i.e. une forme linéaire) et leurs sorties sont donc déterminées par une combinaison de coefficients matriciels.   

\bs
La première étape de l'algorithme de minimisation d'un $k$-automate (c'est à dire l'optimisation du nombre de ses états à fonctionnement équivalent), donné par sa
représentation linéaire $(\lambda,\mu,\gamma)$ à multiplicités
dans un corps (commutatif ou non) $k$ (dû à Sch\"utzenberger), est la
construction d'un ensemble préfixe\footnote{suffixe si le actions sont à gauche.} $P$ tel que l'orbite
$\lambda\mu(P)$ soit une base de $\lambda\mu(k\langle\langle
A\rangle\rangle)$ \cite{BR,FE,S}. Ce même processus permet aussi d'obtenir un certificat 
$\rm{cert}(M)$ vérifiant si un $\Si$-module M engendré par une seul vecteur est décomposable ou non.

\ss 
La structure de ce paragraphe est la suivante. Dans un  premier temps, nous 
présenterons l'algorithme de décomposition d'un module. La première étape sera le
 calcul de l'ensemble suffixe qui correspond à la réduction à gauche de la 
théorie de minimisation. La deuxième étape sera le calcul des endomorphismes 
et des projecteurs. Puis, nous appliquerons notre algorithme pour décomposer des 
modules définis sur l'algèbre du groupe symétrique et aussi sur l'algèbre de 
Hecke à $q=0$.
%
\subsection*{Décomposition de modules}

Dans la pratique, on a besoin de passer aux combinaisons linéaires d'opérateurs et donc, par rapport à ce qui a été fait juste avant la définition \mref{rep_semigp}, une deuxième extension aux combinaisons linéaires de mots (les polynômes non commutatifs $\ncp{k}{\Si}$) est nécessaire.\\ 
Nous présentons l'algorithme dans le cadre général d'une algèbre d'opérateurs (associative) sur un \ev de dimension finie $V$. Il peut être compris avec $\A=\ncp{k}{\Si}$.\\
\begin{definition}
	Un \ev $\A$ sur un corps $k$ est muni d'une structure d'algèbre (ou $k$-algèbre) par la donnée d'un produit $(x,y)\ra xy$, bilinéaire $\A\times \A\mapsto \A$. L'algèbre est dite \ul{commutative}, \ul{associative}, \ul{unitaire} si la produit l'est. Dans la suite, une algèbre associative, avec unité (unitaire) sera désignée par AAU.
\end{definition}

Soit $\A$ une algèbre associative sur un corps (commutatif ou non) $k$ engendrée par une ensemble $S$.  
Soit $M$ est un $\A$-module à gauche. 
On considère le sous-module $\A\cdot m$, ayant pour générateur $m\in M$. 
La première étape dans le processus de décomposition d'un tel module est le calcul 
d'un ensemble suffixe. On notera par  $\text{ann}(m)=\{a\in\A : a\cdot m=0\}$ 
l'ensemble des annulateurs de $m$. C'est un idéal à gauche de $\A$.
%
\subsection{Calcul de l'ensemble suffixe}
%
On commence par construire  une partie suffixe $P\subset S^*$ tel que 
$P\cdot m$ soit une base de $\A\cdot m$. 

\bigskip
\noindent
Soit 
$E:=\{(s_i,s)\in S\times P\ |\ s_is\notin P\}$. Pour  
$(s_i,s)\in E$, on a :  
\begin{equation}
s_is.m=\sum_{s'\in P} \alpha_{s_is,s'} s'.m
\end{equation}
et les différences $R:=\left\{s_is-\sum_{s'\in P} 
\alpha_{s_is,s'}s'\right\}_{(s_i,s)\in E}$ 
forment un ensemble complet de générateurs de $\text{ann}(m)$.
Donc, la première étape du processus de décomposition est le calcul d'un 
ensemble suffixe $P\subset S^*$ où on a recours à la théorie de 
minimisation et plus précisément la deuxième étape du processus à savoir 
l'algorithme de réduction à gauche qui consiste à calculer une base de 
$\A\cdot m$. On modifie cet algorithme pour qu'il
 puisse garder trace des relateurs qui apparaissent
 au cours du calcul de l'ensemble suffixe et pour obtenir ainsi un test qui 
permettra de choisir les idempotents de 
$\End_{\A}(\A\cdot m)$ parmi les projecteurs de $\End_k(\A\cdot m)$. 

\bigskip
\noindent
L'algorithme suivant permet donc de trouver un 
ensemble suffixe de $S^*$ et l'ensemble des relateurs. Il prend en entrée 
l'ensemble  $S$ et un générateur  $m\in M$ 
et retourne en sortie l'ensemble suffixe $P$ et l'ensemble des relateurs 
$R$.

\noindent
\begin{tabular}{llllllllllllllllllllllllllllllllll}
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\hline
\end{tabular}
\begin{tabbing}
{\bf Algorithme} {\it suffixe}\\
\begin{tabular}{llllllllllllllllllllllllllllllllll}
\hline
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\end{tabular}\\
{\bf Entrée :}\quad\quad \=  l'ensemble $S$\\
	         \> un générateur $m\in M$\\
{\bf Sortie :} 	 \> un ensemble suffixe $P\subset S^*$\\
                 \> un ensemble des relateurs $R$\\
{\bf Début}\\
{\it 1}.\,\,$(P,Y,R):=(\emptyset,\{\varepsilon\},\emptyset)$\\
{\it 2}.\,\,{\bf Tant que } $Y\neq \emptyset$ {\bf faire } \\
{\it 3}.\quad\quad retirer un mot $y$ de $Y$\\
{\it 4}.\quad\quad{\bf Si} $y\cdot m\notin\mbox{span}
                                             (p\cdot m:p\in P)$ {\bf alors} \\
{\it 5}.\>$(P,Y):=(P\cup\{y\},(Y-\{y\})\cup yS)$\\
{\it 6}.\quad\quad {\bf Sinon} \\
{\it 7}.\> Il existe une relation  $y.m=\sum_{p\in P}\alpha_pp\cdot m$\\
        \>$(P,Y,R):=(P,(Y-\{y\}),R\cup\{y-\sum_{p\in P}\alpha_pp\})$\\
{\it 8}.\quad\quad {\bf Fin\_si}\\
{\it 9}.\,\,{\bf Fin\_faire}\\
{\it 10}.\,\,{\bf retourner} $(P,R)$\\
{\bf Fin.}
\end{tabbing}
\begin{tabular}{llllllllllllllllllllllllllllllllll}

%\hline
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\end{tabular} 

\noindent
L'ensemble $P$ est un ensemble suffixe et l'algorithme se termine. En effet, 
l'ensemble $P$ est un ensemble suffixe à chaque étape de l'algorithme. Ceci 
est évident en fait dès le début avec $P=\{\varepsilon\}$. Ensuite, si 
$y\in Y\subseteq S^*$ est accepté, tous les suffixes de $y$ sont 
dans $P$. Soit $|s|$ la longueur du mot $s\in S^*$. 
Puisque l'espace $\A\cdot m$ est de dimension finie, il existe un 
entier positif $l$ tel que :
\begin{center}
span($s\cdot m:s\in S^*$)=span($s\cdot m:s\in S^*$ et $|s|<l$).
\end{center} 
On a $P\subseteq \{s\in S^*:|s|<l\}$ et 
$Y\subseteq \{s\in S^*:|s|<l+1\}$. L'ensemble devient vide 
durant l'algorithme et alors l'algorithme se termine.
\begin{lemma}\label{l1}
L'ensemble $P\cdot m=\{s\cdot m:s\in P\}$ est une base de l'espace 
$\A\cdot m$.
\end{lemma}
\noindent
{\bf Preuve}\hspace{2mm} Soit $C=SP- P$ le code suffixe complet 
associé à l'ensemble  $P$ \cite{BR}. On a la décomposition 
$S^\ast= P \sqcup S^\ast CP$ du mono\"{i}de libre. Si 
$s_is\in C$, il existe un relateur  
$s_is-\sum_{s'\in P}\alpha_{s'}s'\in R$. 
Soit maintenant $s_i\in S$ et $s_is\in CS^\ast S$. on a 
alors par induction : 
\begin{align*}
s_is\cdot m&=\sum_{s'\in P}\alpha_{s'}s_is'\cdot m\\
&=\sum_{s_is'\in P}\alpha_{s'}s_is'\cdot m+
\sum_{s_is\notin P}\sum_{s''\in P}\alpha_{s'}
\beta_{s_is'}^{s''}s''\cdot m. 
\end{align*}
Et donc  $s_is\cdot m\in\mbox{span}(s\cdot m:s\in P)$. 
\hfill \cqfd

\bigskip
\noindent
D'après le lemme  \ref{l1}, l'algorithme suffixe calcule une description 
complète de l'espace\\ 
$\A\cdot m$. On  remarque que l'ensemble des relateurs
 dépend du choix du mot $y\in Y$. Soit\\ 
 $m=ab^2+b\in \mathbb Q\l a,b\r$. 
Les actions étant données par les formules de décalage (quotients de Eilenberg \cite{Ei}).  
La figure \ref{pfQ} donne l'ensemble suffixe et l'ensemble des relateurs de 
$\mathcal{A}.m$. Chaque transition en trait continu représente une action qui aboutit à 
un nouvel élément de la base et chaque transition en trait discontinu 
donne un relateur.  
L'ensemble des relateurs peut être différent si les mots sont choisis selon l'ordre 
lexicographique gradué ou selon l'ordre lexicographique usuel.
%  
\begin{figure}
\begin{center}
\SmallPicture\VCDraw{
\begin{VCPicture}{(-1,-5)(12,2)}
\StateVar[ab^2+b]{(3,1)}{A}
\State[b^2]{(1,-1)}{B}
\State[\varepsilon]{(5,-1)}{C}
\State[b]{(3,-3)}{E}
%
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeR{A}{B}{a}
\EdgeL{A}{C}{b}
\EdgeL{B}{E}{b}
\ChgStateLineStyle{dotted}
\State[0]{(-1,-3)}{D}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\EdgeR{B}{D}{a}
\ArcL{E}{D}{a}
\EdgeR{E}{C}{b}
%
\RstEdgeLineStyle
\RstStateLineStyle
%
\StateVar[ab^2+b]{(11,1)}{F}
\State[b^2]{(9,-1)}{G}
\State[b]{(11,-3)}{I}
\State[\varepsilon]{(13,-5)}{J}
%
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeR{F}{G}{a}
\EdgeL{G}{I}{b}
\EdgeL{I}{J}{b}
\ChgEdgeLineStyle{dotted}
\ChgStateLineStyle{dotted}
\State[0]{(7,-3)}{H}
\EdgeL{G}{H}{a}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\VArcL[.6]{arcangle=40}{F}{J}{b}
\EdgeL{G}{H}{a}
\ArcL{I}{H}{a}
\RstEdgeLineStyle
%
\end{VCPicture}}
\end{center}
\caption{Les ensembles suffixes pour $m=ab^2+b$ (l'action est donnée par les quotients $(x^{-1})_{x\in \{a,b\}}$ de Eilenberg \cite{Ei}).}\label{pfQ}
\end{figure} 
%
En effet, l'élément $b+ab^2 \in S^*$ est un relateur 
avec le deuxième type d'ordre (graphe à droite de la figure \ref{pfQ}) ce qui 
n'est pas le cas avec le premier type (graphe à gauche de la figure \ref{pfQ}).

\subsection{Calcul de $\End_{\A}(M)$ et des idempotents (projecteurs)}

D'abord un petit exercice sur les projecteurs.

\begin{exo}\label{exoproj}
	Soit $V$ un \ev et $f\in \End(V)$.\\ 
1) Montrer que les conditions suivantes sont équivalentes\\
	i) $f^2=:f\circ f=f$ (on dit alors que $f$ est idempotent)\\
	ii) $V=Im(f)\oplus Ker(f)$ et $(\forall y\in Im(f))(f(y)=y)$\\
2) En indexant les propriétés comme suit :\\
\begin{tabular}{ccc}
A) $f^2:=f\circ f=f$ & B) $V=Im(f)\oplus Ker(f)$ & C) $(\forall y\in Im(f))(f(y)=y)$.
\end{tabular}

a) Trouver une application linéaire $V\mapsto V$ (on pourra la décrire sous forme de matrice) telle que 
(B) mais pas (C) ni (A).\\ 
b) Quels sont les liens logiques entre (A), (B) et (C) ?


3) On suppose maintenant que $V$ est muni d'une structure de $\Si$-module.\\ 
Montrer que, si $f\in\End_k(V)$ est idempotent (i.e. un projecteur), les propriétés suivantes sont équivalentes\\
i) $f$ est $\Si$-linéaire (voir \mref{morph_mod})\\
ii) $Im(f)$ et $Ker(f)$ sont stables par $\Si$ (i.e. des sous-modules de $V$). 

\ss
4) Dans cette question, on suppose que $\Si$ engendre un groupe fini d'actions de $V$ dans $V$ (i.e. $\mu(\Si)=G\subset \Aut(V)$ est fini).\\
Soit $W$ un sous-module de $V$ et $p\ :\ V\mapsto V$ un projecteur sur $W$.\\
a) Montrer que 
\begin{equation}
	f(v)=\frac{1}{|G|}\sum_{g\in G} g(p(g^{-1}(v))) 
\end{equation}
définit un projecteur $\Si$-linéaire d'image $W$.\\
b) Déduire de ce qui précède que tout sous-module de $V$ indécomposable est irréductible. 

\ss
5) Déduire de ce qui précède que, si $V$ est de dimension finie, il s'exprime comme somme 
\begin{equation}\label{dec_ind}
	V=V_1\oplus V_2\oplus\cdots \oplus V_r 
\end{equation}
de sous-modules indécomposables.      
\end{exo}

{\bf Commentaire}\pointir 
 La décomposition \mref{dec_ind} est unique à permutation et isomophisme près. En fait, on montre que \footnote{Admis ici, voir le théorème de Krull-Schmidt \mref{KrullSchmidt}.}, dans les conditions précédentes, si
\begin{equation}\label{dec_ind}
	V=V_1\oplus V_2\oplus\cdots \oplus V_r =W_1\oplus W_2\oplus\cdots \oplus W_s
\end{equation}
sont deux décomositions en indécomposables, alors $r=s$ et il existe une permutation $\tau$ (ici renommage des indices) telle que, pour tout $1\leq j\leq r$ $V_j\simeq W_{\tau(j)}$. 

\hfill$\diamondsuit$\\
\hspace{1cm}


Nous allons voir que les projecteurs sont des outils cruciaux pour décomposer les modules.
La section précédente nous a fourni un ensemble de relateurs de type particulier, 
ils sont de type 
\begin{equation}\label{pref}
sp-\sum_{q\in P}\alpha(s,p,q)q.\textrm{ pour } (s,p)\in S\times P\textrm{ tels que } sp\notin P
\end{equation} 

\smallskip
\noindent
La deuxième étape dans le processus de décomposition est le calcul des 
endomorphismes et projecteurs. On a vu dans la section 
précédente et d'après  le lemme  \ref{l1},  qu'il est possible de déterminer 
algorithmiquement un endomorphisme $\varphi$ dans la base 
$(s\cdot m)_{s\in P}$ de $\A\cdot m$. 
En effet, l'algorithme suffixe permet de calculer l'ensemble suffixe $P$ et 
l'ensemble des relateurs $R$. \`A chaque élément 
$x=\sum_{s\in P}\alpha_{s}s.m$, on peut associer un unique endomorphisme 
$\varphi_x\in \End_{k}(\A\cdot m)$ tel que, pour tout 
\begin{equation}\label{morph1}
	(\forall w\in P)(w\in P)
\end{equation}
Pour que $\varphi_x\in \End_{\A}(\A\cdot m)$ il faut et il suffit 
que $ann(m)\subset ann(x)$.\\
Inversement, à chaque morphisme 
$\varphi\in\End_{\A}(\A\cdot m)$, on peut associer un élément 
$m_{\varphi}$.  

\bs
\noindent
L'algorithme  suivant permet de construire l'endomorphisme 
$\varphi$. Il prend en entrée l'ensemble suffixe $P$, l'ensemble des 
relateurs $R$ du module et l'ensemble $S$. 
L'ordre du calcul des vecteurs $\varphi (s\cdot m)$ est donné suivant le 
rangement de $s$ dans l'ensemble $P$. Si $s=s_is'$, 
alors $\varphi (s' \cdot m)$ est déjà connu. 

\newpage
\noindent
\begin{tabular}{llllllllllllllllllllllllllllllllll}
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\hline
\end{tabular}
\begin{tabbing}
{\bf Algorithme} {\it cons\_$\varphi$}\\
\begin{tabular}{llllllllllllllllllllllllllllllllll}
\hline
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\end{tabular}\\
{\bf Entrée :}\quad\quad \= l'ensemble des transpositions $S$\\
                 \> l'ensemble suffixe $P$ \\
                 \> l'ensemble des relateurs $R$ \\
{\bf Sortie :} 	 \> le morphisme $\varphi$\\
{\bf Début}\\
{\it 1}.\,\,$Y:=S$ \\ 
{\it 2}.\,\,$\varphi(\varepsilon f):=
\sum_{s\in P}\alpha_{s,\varepsilon}s\cdot m$\\
{\it 3}.\,\,{\bf Tant que } $Y\neq \emptyset$  {\bf faire } \\
{\it 4}.\quad\quad retirer un mot $ss_i$ de $Y$\\
{\it 5}.\quad\quad {\bf Si} $ss_i\notin P$ {\bf alors} \\
{\it 6}.\>$Y:=Y-\{ss_i\}$\\
{\it 7}.\quad\quad {\bf Sinon} \\
{\it 8}.\>$\varphi(ss_i\cdot m ):=s\varphi(s_i\cdot m)$\\
        \>$Y:=(Y\cup Sss_i)-\{ss_i\}$\\
{\it 9}.\quad\quad {\bf Fin\_si}\\
{\it 10}.\,\,{\bf Fin\_faire}\\
{\it 11}.\,\,{\bf retourner} $(\varphi)$\\
{\bf Fin.}\\
\begin{tabular}{llllllllllllllllllllllllllllllllll}
\hline
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\
\end{tabular}
\end{tabbing}
L'algorithme ne considère que les éléments $ss_i$ qui sont dans 
l'ensemble suffixe $P$, les autres éléments, qui ne sont pas dans $P$ et 
qu'on retrouve forcément dans l'ensemble des relateurs $R$ seront traités
 à part pour qu'on puisse les manipuler afin de  vérifier le deuxième point du 
lemme \ref{l4}.
\begin{lemma}\label{l4}
Soit  $\varphi\in\End_{k}(\A\cdot m)$ et  $m_\varphi=\varphi(m)$. 
Alors la transformation linéaire $\varphi$ appartient à  
$\End_{\A}(\A\cdot m)$  
si et seulement si:

\smallskip
\noindent
i) pour tout  $s\in P$, on a $\varphi(s\cdot m)=s\cdot\varphi(m)$,\\
ii) pour tout $(s_i,s)\in S\times P$ tel que $s_is\notin P$, la différence 
$\left(s_is-\sum_{s'\in P} \alpha_{s_is,s'}s'\right)$ annule  $m_\varphi$.
\end{lemma}
Une fois qu'on a le morphisme $\varphi$, et d'après le lemme  \ref{l4}, pour 
trouver l'ensemble des projecteurs, on doit étudier la relation d'idempotence
\begin{align}
\varphi^2=\varphi\label{eq1}
\end{align}
et vérifier que 
\begin{align}
& \varphi (s\cdot m)  = s\cdot \varphi(m) \quad \quad \forall \,\, 
s\in P \label{eq2}\\
& r\cdot \varphi(m)         =0                 \quad \quad \forall \,\, 
r\in R\label{eq3}
\end{align}
De ces trois formules (\ref{eq1}), (\ref{eq2}) et (\ref{eq3}), on obtient 
un système de $n|P|^2+|P|$ équations en les inconnues 
$\alpha_{s,\varepsilon}$ pour tout $s\in P$.

\bigskip
\noindent
Toute solution non-triviale $\varphi$ donne une première décomposition 
$\A\cdot m=\A\cdot m_{\varphi}\oplus \A\cdot m_{1-\varphi}$. Ensuite, on 
réapplique l'algorithme sur $\A\cdot m_{\varphi}$ 
 et 
$\A\cdot m_{1-\varphi}$. À l'aide de réexécutions de l'algorithme, on obtient une somme directe de sous-modules 
indécomposables. Sinon, s'il n'existe aucune solution non-triviale, on déduit 
que le module $\A\cdot m$ ne peut pas être une somme directe de sous-modules.
\begin{theorem}
Soit $m\in M$. Une répétition finie de l'algorithme suffixe et 
$cons\_\varphi$  décide s'il existe une décomposition de $\A\cdot m$ en 
une somme directe de sous-modules indécomposables. 
Si aucune solution non-triviale ne peut être trouvée, le module $\A\cdot m$ 
est indécomposable.
\end{theorem} 
Dans la partie suivante, nous allons appliquer le processus de 
décomposition pour décomposer des modules définis sur différentes algèbres. 
Nous commençons par les  fonctions définies sur l'algèbre du groupe 
symétrique. Ensuite, des modules définis sur l'algèbre de Hecke. En effet, les
 fonctions booléennes jouent un rôle important en cryptographie et surtout dans
 les systèmes de chiffrement.
\begin{remark} 
La forme particulière des relateurs $R$ (\ref{pref}) donne un quotient 
$(k\l A\r;R)$ libre sur $k$ même si $k$ est un anneau.
\end{remark}
%
\section{Idempotents}

\subsection{Généralités}
Classes de Burnside, nombres idempotents, formule exponentielle.

\subsection{Décomposition}

\begin{exo}
	Soit $G_n=\langle g;g^n=1\rangle$ (le groupe cyclique d'ordre $n$).\\
0) (Warmup) Montrer que $G_n=\{g^k\}_{0\leq k<n}$ et que 
$$
g^p=g^q\Longleftrightarrow p-q \textrm{ est divisible par n }
$$
1) Pour $0\leq k<n$, et $\xi=e^{\frac{2i\pi}{n}}$ on pose 
\begin{equation}
	e_k=\frac{1}{n}\sum_{j=0}^{n-1} \xi^{-jk}g^j
\end{equation}
a) Montrer que $g.e_k=\xi^k e_k$ puis que 
\begin{equation}
	e_{k_1}e_{k_2}=\delta_{k_1,k_2}e_{k_1}
\end{equation}
b) Montrer que 
\begin{equation}
	\sum_{k=0}^{n-1}e_k=1_{G_n}
\end{equation}

2) (Sandwiches)\pointir\\
a) Montrer que 
\begin{equation}
	dim(e_{k_1}\C[G_n]e_{k_2})= 0\textrm{ si }k_1\not= k_2 \textrm{ et $1$ si } k_1= k_2 
\end{equation}
b) En déduire que si l'on pose $e_k g e_k=\mu(g)e_k$, l'application
\begin{equation}
g\ra 
\begin{pmatrix} \mu_1(g) & 0 & \cdots & 0\cr 0 & \mu_2(g) & \ddots & \vdots \cr
\vdots & \ddots & \ddots & 0 \cr 0 & \cdots &0 & \mu_n(g)
\end{pmatrix}	
\end{equation}
est une représentation injective (en théorie des représentations on dit fidèle).\\
4) Pour une groupe général (fini) $G$, on considère une FCIOM $(e_t)_{t\in T}$.\\
a (**) Montrer que 
\begin{equation}
	dim(e_s\C[G]e_t)\in\{0,1\}
\end{equation}
b) (**) Montrer que la relation $s\sim t$ définie par $dim(e_s\C[G]e_t)=1$ est une relation d'équivalence.\\ 
5) (**) Soit $B=T/\sim$ et $b\in B$. On range les éléments de $b$ en une suite $t_1,t_2\cdots t_l$, puis on choisit $E_{i,i+1}\in e_{t_i}\C[G]e_{t_{i+1}}$ non nul.\\
a) Montrer que l'on peut choisir, pour tout $0\leq i<l$, $E_{i+1,i}$ tel que $E_{i,i+1}E_{i+1,i}=e_{t_i}$ et que cela implique que $E_{i+1,i}E_{i,i+1}=e_{t_{i+1}}$.\\
b) On définit $E_{i,j}$ par 
\begin{eqnarray}
&&	E_{i,j}=E_{i,i+1}E_{i+1,i+2}\cdots E_{j-1,j}\textrm{ pour $i<j$ }\cr
&&	E_{i,j}=E_{i,i-1}E_{i-1,i-2}\cdots E_{j+1,j}\textrm{ pour $i>j$ }\cr
&& E_{i,i}=e_{t_i}
\end{eqnarray}
montrer que ces éléments sont des unités matricielles i.e. $E_{i,j_1}E_{j_2,k}=\delta_{j_1,j_2}E_{i,k}$.\\
c) Pour $0\leq i,j\leq l$ on définit $\rho_{i,j}(g)$ par $e_{t_i} g e_{t_j}=\rho_{i,j}(g) E_{i,j}$. Montrer que 
$\rho_b=(\rho_{i,j})_{0\leq i,j\leq l}$ définit une représentation matricielle de $G$.\\  
6) a) (**) Montrer que la représentation par blocs 
$\rho=(\rho_b)_{b\in B};\ \C[G]\mapsto \bigoplus_{b\in B}\mathcal{M}(l_b,\C)$ est fidèle.\\
b) (***) Montrer que $\rho$ est un isomorphisme. 
\end{exo}

\section{Application I : Cryptographie et fonctions booléennes}
%
\subsection{Définition}
La cryptographie est l'étude des  méthodes et techniques 
mathématiques liées aux aspects de la sécurité de l'information tels que la 
confidentialité, l'intégralité des données, l'authentification d'identités et 
l'authentification de l'originalité des données. C'est un ensemble de 
techniques qui fournit la sécurité de l'information. 
La cryptographie permet de stocker des informations sensibles ou de les 
transmettre à travers des réseaux non sûrs (comme Internet) de telle sorte 
qu'elles ne puissent être lues par personne à l'exception du destinataire 
convenu. Elle fait appel à l'algèbre linéaire, la théorie des groupes, la 
théorie combinatoire et la théorie des graphes. Différentes fonctions 
mathématiques de base sont importantes pour comprendre en détail les 
algorithmes de chiffrement. 
Les systèmes de chiffrement basés sur des fonctions linéaires, ou des fonctions
 affines, étant considérés comme faibles, la capacité à mesurer la 
non-linéarité est un moyen pour calculer la force d'un algorithme. 
La non-linéarité d'une fonction est la mesure du nombre de bits qui doivent 
changer dans la table de vérité d'une fonction booléenne pour s'approcher 
d'une fonction affine.  Une  fonction affine est une fonction booléenne 
linéaire f(x) = ax + b où l'addition peut être représentée par un OU-Exclusif 
et la multiplication par un ET. Les opérations OU-Exclusif et ET ensemble 
produisent le même résultat que les opérations somme et produit  "modulo 2".

\noindent
Par fonction booléenne, on entend toute fonction 
$\{0,1\}^n\rightarrow \{0,1\}$ ce qui, en langage informatique, est juste une 
fonction qui prend  en argument un mot de $n$ bits et qui retourne  une 
valeur logique VRAI ou FAUX. \`A toute fonction booléenne $f$ à $n$ variables, on peut associer 
canoniquement un graphe : son diagramme de décision binaire (BDD : Binary 
Decision Diagram) quasi-réduit. Cette technique est utilisée depuis longtemps 
dans la vérification des circuits.
%
\subsection{Les Diagrammes de Décision Binaire}

Les graphes de décision binaires (BDD) sont des graphes orientés 
sans circuit, basés sur la décomposition de Shannon des fonctions booléennes. 
Ils ont été introduits en 1978 par Akers \cite{A} pour représenter de façon 
compacte les fonctions booléennes. Puis en 1986, Bryant \cite{B1} propose les 
OBDD une représentation canonique des 
BDD ainsi que des algorithmes pour calculer efficament les opérations 
booléennes sur ces structures de données. 
%
\begin{figure}
\begin{center}
\SmallPicture\VCDraw{\begin{VCPicture}{(7,0)(8,9)}
\ChgEdgeLabelScale{0.8}
\State[x_1]{(8,8)}{A}
\State[x_2]{(4,6)}{B}
\State[x_2]{(12,6)}{C}
\State[x_3]{(2,4)}{D}
\State[x_3]{(6,4)}{E}
\State[x_3]{(10,4)}{F}
\State[x_3]{(14,4)}{G}
\FinalState[0]{(1,2)}{H}
\FinalState[0]{(3,2)}{I}
\FinalState[0]{(5,2)}{J}
\FinalState[0]{(7,2)}{K}
\FinalState[1]{(9,2)}{L}
\FinalState[1]{(11,2)}{M}
\FinalState[0]{(13,2)}{N}
\FinalState[0]{(15,2)}{O}
\EdgeR{A}{B}{0}
\EdgeL{A}{C}{1}
\EdgeR{B}{D}{}
\EdgeL{B}{E}{}
\EdgeR{C}{F}{}
\EdgeL{C}{G}{}
\EdgeR{D}{H}{}
\EdgeL{D}{I}{}
\EdgeR{E}{J}{}
\EdgeL{E}{K}{}
\EdgeR{F}{L}{}
\EdgeL{F}{M}{}
\EdgeR{G}{N}{}
\EdgeL{G}{O}{}
\end{VCPicture}}
\caption{Diagramme de Shannon de $f=x_1x_2+x_1$.}\label{ds}
\end{center}
\end{figure}
%
Soit la fonction booléenne $f:\{0,1\}^3\rightarrow \{0,1\}$ définie par 
$f(x_1,x_2,x_3)=x_1x_2+x_1$. Son diagramme de Shannon est donné dans la 
figure \ref{ds}. Après un certain nombre d'opérations de réduction sur ce 
diagramme, on obtient un BDD réduit. 
Le BDD correspondant à la fonction $f$ est donné dans la figure \ref{bdd}.
%
%\begin{center}
\begin{figure}
\begin{center}
\SmallPicture\VCDraw{\begin{VCPicture}{(9,2)(8,9)}
\ChgEdgeLabelScale{0.8}
\State[x_1]{(8,8)}{A}
\State[x_2]{(10,6)}{C}
\FinalState[0]{(7,4)}{D}
\FinalState[1]{(9,4)}{F}
\FinalState[0]{(11,4)}{G}
\EdgeR{A}{C}{}
\EdgeL{A}{D}{}
\EdgeR{C}{F}{}
\EdgeL{C}{G}{}
\end{VCPicture}}
\end{center}
\caption{Le BDD pour $f=x_1x_2+x_1$.}\label{bdd}
\end{figure}
%\end{center}
%
\section{Décomposition d'une fonction booléenne}

Nous étudions ici l'orbite d'une fonction booléenne $f\in\F{n}$ sous 
l'action de l'algèbre $\A_n= \mathbb Z_2[\SG_n]$ \cite{H} 
du groupe symétrique $\mathfrak S_n$ sur les variables 
dans le but de 
donner une décomposition de $f$ à l'aide de la théorie de minimisation.
Soit $\F{n}$ le $\A_n$-module à gauche des fonctions booléennes à $n$ 
variables $(x_1,\dotsc,x_n)$ et $f\in \F{n}$ une fonction booléenne.
 Considérons le sous-module $\A_n.f$. Il existe une décomposition du 
module $\A_n.f$ en une somme directe $\A_n.f=M_1\oplus\dotsm\oplus M_l$ de
sous-modules indécomposables $M_i$. D'après le théorème de Krull-Schmidt, 
cette décomposition est unique à isomorphisme près.
%
\begin{figure}
\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(5,-2)(12,8)}
%
\ChgStateLineColor{white}
\StateVar[1]{(8,8)}{A}
\StateVar[\sigma_1]{(5,5)}{B}
\StateVar[\sigma_2]{(11,5)}{C}
\StateVar[\sigma_2\sigma_1]{(5,2)}{D}
\StateVar[\sigma_1\sigma_2]{(11,2)}{E}
\StateVar[\sigma_1\sigma_2\sigma_1]{(8,-1)}{F}
\StateVar[0]{(16,8)}{G}
\StateVar[1]{(16,5)}{H}
\StateVar[2]{(16,2)}{I}
\StateVar[3]{(16,-1)}{J}
%
\EdgeR{A}{B}{\sigma_1}
\EdgeL{A}{C}{\sigma_2}
\EdgeR{B}{D}{\sigma_2}
\EdgeL{C}{E}{\sigma_1}
\EdgeL{D}{F}{\sigma_1}
\EdgeR{E}{F}{\sigma_2}
\ChgEdgeLineStyle{dotted}
\EdgeR{A}{G}{}
\EdgeR{C}{H}{}
\EdgeR{E}{I}{}
\EdgeR{F}{J}{}
%
\end{VCPicture}}
\end{center}
\caption{Le permutoèdre pour $n=3$.}
\label{prtr}
\end{figure}
%
\subsection{Algèbre du groupe symétrique}

L'algèbre $\A_n= \mathbb Z_2[\SG_n]$ agit par permutations 
de variables sur l'ensemble des fonctions booléennes 
$\F{n}$. Elle est engendrée par les  transpositions simples 
$S=(\sigma_1,\dotsc, \sigma_{n-1})$ où $\sigma_i$ est la 
transposition de 
$i$ et $i+1$ et peut être présentée par les relations suivantes dites de 
Moore-Coxeter \cite{H,DKL} :
% 
\begin{equation*}\left\{
\begin{array}{ll}
{\sigma_i}^2=1,\\
\sigma_i\sigma_j=\sigma_j\sigma_i&\text{si $|i-j|>1$,}\\
\sigma_i\sigma_{i+1}\sigma_i=\sigma_{i+1}\sigma_i\sigma_{i+1}.\\
\end{array}\right.
\end{equation*}
%
Toute permutation $\sigma\in \mathfrak S_n$ est un produit
 de transpositions élémentaires. 
La longueur d'une permutation est nulle si et seulement si cette 
permutation est égale à 1. La longueur d'une permutation est égale à 1 si et 
seulement si cette permutation est une transposition élémentaire. Enfin, la 
longueur de l'inverse d'une permutation est égale à la longueur de la 
permutation (voir figure \ref{prtr}) \cite{H}. 
L'algèbre $\A_n$ est une algèbre assoicative de type fini. 
Elle agit à gauche sur $\mathbb Z_2\l x_1,\dotsc,x_n\r $ par l'action de 
$\sigma_i$ définie sur les variables par :
%
\begin{equation*}\left\{
\begin{array}{ll}
\sigma_i x_i=x_{i+1},\\
\sigma_i x_{i+1}=x_i,\\
\sigma_i x_j=x_j&\text{si $j\not =i,i+1$.}\\
\end{array}\right .
\end{equation*}
%
On rappelle que $S=\{\sigma_1,\dotsc,\sigma_{n-1}\}$ est l'ensemble de ces  
transpositions simples,
$\F{n}$ un $\A_n$-module à gauche des fonctions booléennes à $n$ 
variables. Il s'agit d'un $\mathbb Z_2$ espace vectoriel de dimension finie 
et on considère les sous-modules monogènes c'est à 
dire engendré par un seul élément (i.e. $\A_n.f$). 

\begin{theorem}[Krull-Schmidt]\label{KrullSchmidt}
Soit $M$ un $\A_n$-module de dimension finie. Soient deux décompositions 
de $M$ en $\A_n$-sous-modules indécomposables  
$M=M_1\oplus \cdots \oplus M_r=N_1\oplus \cdots N_s$ alors $r=s$ et 
il existe une permutation $\tau\in \SG_r$ telle que 
$$
(\forall j\leq r)(M_j\simeq N_{\tau(j)}).
$$
\end{theorem}

Il existe donc une décomposition du module $\A_n.f$ en une somme directe  
$\A_n.f=M_1\oplus \cdots \oplus M_l$ de $\A_n$-sous-modules 
indécomposables, essentiellement unique d'après le théorème de 
Krull-Schmidt \mref{KrullSchmidt} (voir aussi \cite{CR}).\\ 
Le but de l'algorithme est donc de calculer une 
décomposition de $\A_n\cdot f$ par la connaissance de l'ensemble de 
projecteurs orthogonaux  
$\pi_i\in \End_{\A_n}(\A_n\cdot f)$ ($i=1,\dotsc ,l$) qui satisfont :
\begin{equation*}\left\{
\begin{array}{ll}
\pi_i\circ\pi_i =\pi_i,\\
\pi_i\circ\pi_j=0\quad\text{si $i\not =j$,}\\
\pi_1\oplus\dotsm\oplus\pi_l=1_{\End_{\A_n}(\A_n .f)}.\\
\end{array}\right .
\end{equation*}

\bigskip
\noindent
Ainsi, le module $\A_n\cdot f$ est  somme directe de sous-modules 
$\pi_i(\A_n\cdot f)=\A_n\pi_i(f)$ qui sont engendrés par un seul élément.  
Si $\pi_i$ est un tel projecteur, $\pi_i$ doit être $\A_n$-linéaire.
%

%
\begin{figure}
\begin{center}
\SmallPicture\VCDraw{
\begin{VCPicture}{(-2,2)(21.5,13)}
%
\StateVar[x_1x_2+x_1]{(1,12)}{A}
\StateVar[x_1x_2+x_2]{(1,10)}{B}
\StateVar[x_1x_3+x_3]{(1,8)}{C}
\StateVar[x_2x_3+x_3]{(1,6)}{D}
\StateVar[x_2x_3+x_2]{(1,4)}{E}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\LArcR[.5]{A}{B}{\sigma_1}
\LArcL[.5]{B}{C}{\sigma_2}
\LArcR[.5]{C}{D}{\sigma_1}
\LArcL[.5]{D}{E}{\sigma_2}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\LArcR[.5]{B}{A}{\sigma_1}
\LArcL[.5]{C}{B}{\sigma_2}
\LArcR[.5]{D}{C}{\sigma_1}
\LArcL[.5]{E}{D}{\sigma_2}
\VArcL[.9]{arcangle=80}{E}{A}{\sigma_1}
\VArcL[.9]{arcangle=80}{E}{B}{\sigma_1}
\VArcL[.9]{arcangle=80}{E}{C}{\sigma_1}
\VArcL[.9]{arcangle=80}{E}{D}{\sigma_1}
\VArcL[.9]{arcangle=80}{A}{B}{\sigma_2}
\VArcL[.9]{arcangle=80}{A}{C}{\sigma_2}
\VArcL[.9]{arcangle=80}{A}{D}{\sigma_2}
\VArcL[.9]{arcangle=80}{A}{E}{\sigma_2}
\LoopN{A}{\sigma_2}
\LoopS{E}{\sigma_1}
%
\RstEdgeLineStyle
%
\StateVar[x_1x_2+x_1]{(14.5,10)}{A}
\StateVar[x_1x_2+x_2]{(11.5,8)}{B}
\StateVar[x_1x_3+x_3]{(8,6)}{C}
\StateVar[x_1x_3+x_1]{(17.5,8)}{E}
\StateVar[x_2x_3+x_2]{(20.5,6)}{F}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\LArcR{A}{B}{\sigma_1}
\LArcL{B}{C}{\sigma_2}
\LArcL{A}{E}{\sigma_2}
\LArcR{E}{F}{\sigma_1}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\LArcR[.3]{B}{A}{\sigma_1}
\LArcL[.3]{E}{A}{\sigma_2}
\LArcR[.7]{F}{E}{\sigma_1,\sigma_2}
\VArcL[.6]{arcangle=100}{C}{A}{\sigma_1}
\LArcL[.7]{C}{B}{\sigma_1,\sigma_2}
\LArcR[.5]{C}{E}{\sigma_1}
\LArcR[.5]{C}{F}{\sigma_1}
\LArcL[.5]{F}{B}{\sigma_2}
\VArcL[.5]{arcangle=45}{F}{C}{\sigma_2}
\LoopS{C}{\sigma_1}
\LoopS[.75]{F}{\sigma_2}
%
\ChgEdgeArrowStyle{<-}
\VArcL[.4]{arcangle=115}{A}{F}{\sigma_2}
%
\end{VCPicture}}
\end{center}
\caption{L'ensemble suffixe et  relateurs pour $f=x_1x_2+x_1$.}
\label{pf}  
\end{figure}
%
%
\subsection{Exemples de décompositions}
On considère ici la fonction  booléenne $f=x_1x_2+x_1\in\F{3}$. L'ensemble 
des relateurs dépend du choix de l'ordre du parcours de l'arbre des suffixes. 
En effet, la figure \ref{pf} montre bien que l'ensemble des relateurs n'est pas
 le même si  on choisit l'ordre lexicographique gradué ou bien l'ordre 
lexicographique usuel. Dans notre cas, on considère l'ordre lexicographique 
gradué (graphe droite de la figure \ref{pf}). L'ensemble suffixe est 
\[
P=\{\varepsilon, \sigma_1,\sigma_2,\sigma_2\sigma_1,\sigma_1\sigma_2\}.
\] 
L'ensemble des relateurs est 
\[
R=\left \{
\begin{array}{l}
%\varepsilon\varepsilon   + \varepsilon,\, 
\sigma_1\sigma_1 + \varepsilon,\\
\sigma_2\sigma_2         + \varepsilon,\, \sigma_1\sigma_2\sigma_2 + 
\sigma_1,\, \sigma_2\sigma_1\sigma_1 + \sigma_2,\\
\sigma_1\sigma_2\sigma_1 + 
(\varepsilon+ \sigma_1+\sigma_2+\sigma_1\sigma_2+\sigma_2\sigma_1), \\
\sigma_2\sigma_1\sigma_2 + 
(\varepsilon+ \sigma_1+\sigma_2+\sigma_1\sigma_2+\sigma_2\sigma_1). \\
\end{array}\right \}.
\]
Soit $\varphi\in \End_k(\A_3.f)$ et $f_{\varphi}\in \A_3.f$ tel que :
\[
f_\varphi =\alpha_\varepsilon \varepsilon.f+ \alpha_{\sigma_1}\sigma_1.f+
 \alpha_{\sigma_2}\sigma_2.f+ \alpha_{\sigma_2\sigma_1}\sigma_2\sigma_1.f+
 \alpha_{\sigma_1\sigma_2}\sigma_1\sigma_2.f.
\] 
L'ensemble suffixe $P$ et l'ensemble des relateurs $R$ vont nous servir 
comme entrée dans  l'algorithme $cons\_\varphi$ pour construire la matrice 
$\varphi$. 

\noindent
Selon l'algorithme $cons\_\varphi$, la matrice $\varphi$ est la suivante :
%
\[
\varphi=
\begin{pmatrix}
\alpha_\varepsilon&\alpha_{\sigma_1}+\alpha_{\sigma_1\sigma_2}&
\alpha_{\sigma_2}+\alpha_{\sigma_2\sigma_1}&
\alpha_{\sigma_2}+\alpha_{\sigma_2\sigma_1}&
\alpha_{\sigma_1}+\alpha_{\sigma_1\sigma_2}\\
\alpha_{\sigma_1}&\alpha_\varepsilon+\alpha_{\sigma_1\sigma_2}&
\alpha_{\sigma_1\sigma_2}+\alpha_{\sigma_2\sigma_1}&
\alpha_{\sigma_2}&\alpha_{\sigma_1}+\alpha_{\sigma_2}\\
\alpha_{\sigma_2}&\alpha_{\sigma_1\sigma_2}+\alpha_{\sigma_2\sigma_1}&
\alpha_\varepsilon+\alpha_{\sigma_2\sigma_1}&
\alpha_{\sigma_1}+\alpha_{\sigma_2}&\alpha_{\sigma_1}\\
\alpha_{\sigma_1\sigma_2}&\alpha_{\sigma_1\sigma_2}&
\alpha_{\sigma_1}+\alpha_{\sigma_2\sigma_1}&
\alpha_\varepsilon+\alpha_{\sigma_2}&
\alpha_{\sigma_1}+\alpha_{\sigma_2\sigma_1}\\
\alpha_{\sigma_2\sigma_1}&\alpha_{\sigma_2}+\alpha_{\sigma_1\sigma_2}&
\alpha_{\sigma_2\sigma_1}&\alpha_{\sigma_2}+\alpha_{\sigma_1\sigma_2}&
\alpha_\varepsilon+\alpha_{\sigma_2}\\
\end{pmatrix}
\]
%
Une solution non-triviale du système donné par $\varphi^2=\varphi$,  
$\sigma\cdot \varphi(f)=\varphi(\sigma\cdot f)$ pour tout $\sigma\in P$ et 
$r\cdot \varphi(f)=0$ pour tout $r\in R$ est :
\[
f_{\varphi}=\sigma_2\sigma_1.f+\sigma_1\sigma_2.f
\]
et  
\[
f_{1+\varphi}=\varepsilon.f+\sigma_2\sigma_1.f+\sigma_1\sigma_2.f
\]
 C'est à 
dire \[
f_{\varphi}=x_1x_3+x_2+x_2x_3+x_3
\]
et  
\[
f_{1+\varphi}=x_1+x_1x_2+x_1x_3+x_2+x_2x_3+x_3
\]  
Ce qui nous donne $\A_3.f=\A_3.f_{\varphi}\oplus\A_3.f_{1+\varphi}$  et les 
décompositions complètes des modules $\A_3.f_\varphi$ et 
 $\A_3.f_{1+\varphi}$ sont données dans la figure \ref{f3}. 
%
\begin{figure}
\begin{center}
\SmallPicture\VCDraw{
\begin{VCPicture}{(0,-4)(21,8)}
%
\StateVar[x_1x_3+x_2+x_2x_3+x_3]{(11,7)}{A}
\StateVar[x_1+x_1x_3+x_2x_3+x_3]{(4,4)}{B}
\StateVar[x_1+x_1x_2+x_2+x_2x_3]{(11,1)}{C}
\StateVar[x_1x_2+x_2+x_2x_3+x_3]{(17,4)}{D}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\LArcR{A}{B}{\sigma_1}
\LArcR{B}{C}{\sigma_2}
\LArcL{A}{D}{\sigma_2}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\EdgeR[.7]{B}{A}{\sigma_1}
\EdgeL[.7]{D}{A}{\sigma_2,\sigma_1}
\EdgeR[.45]{C}{B}{\sigma_1,\sigma_2}
\EdgeL[.3]{C}{D}{\sigma_1}
\LArcL{D}{C}{\sigma_1}
%
\StateVar[x_1+x_1x_2+x_1x_3+x_2+x_2x_3+x_3]{(11,-3)}{E}
%
\LoopN{E}{\sigma_1,\sigma_2}
%
\end{VCPicture}}
\end{center}
\caption{Décomposition complète de $\A_3.f$.}\label{f3}
\end{figure}

\section{Application II : Module sur  $\mathfrak H^n_k(0)$}
\subsection{L'algèbre de Hecke}

L'algèbre de Hecke générique notée $\mathfrak H^n_k(q_1,q_2)$, qui peut être 
considérée comme une  déformation à deux paramètres  de l'algèbre du groupe 
symétrique, est l'algèbre sur l'anneau commutatif $k$ présentée par les 
générateurs $(T_i)_{1\leq i<n}$ et les relations 
%
\begin{equation*}\left\{
\begin{array}{ll}
T_iT_j=  T_jT_i &\text{si $|i-j|>1$,}\\
T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1},\\
(T_i-q_1)(T_i-q_2)=0.\\
\end{array}\right.
\end{equation*}
%
Les scalaires  $q_1$ et $q_2$ sont les paramètres de l'algèbre. 
L'entier strictement positif $n$ est son degré. 
L'algèbre $\mathfrak H^n_k(q_1,q_2)$ est de dimension $n!$ en tant que 
module sur $k$. 
Dans ce qui suit, on va s'intéresser à l'algèbre de Hecke à $q=0$  
sur $\mathbb Q$ que l'on notera $\mathfrak H^n_k(0)$. 

Elle est engendrée par la famille $(T_i)_{1\leq i <n}$ et les relations 
%
\begin{equation*}\left\{
\begin{array}{ll}
T_iT_j=T_jT_i &\text{si $|i-j|>1$,}\\
T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1},\\
T_i(T_i+1)=0.\\
\end{array}\right.
\end{equation*}
%
%
\begin{figure}
\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(5,-4)(12,8)}
%
\StateVar[abc]{(8,8)}{A}
\StateVar[bac]{(5,5)}{B}
\StateVar[acb]{(11,5)}{C}
\StateVar[bca]{(5,2)}{D}
\StateVar[cab]{(11,2)}{E}
\StateVar[cba]{(8,-1)}{F}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeL{A}{B}{T_1}
\EdgeR{A}{C}{T_2}
\EdgeR{B}{D}{T_2}
\EdgeL{C}{E}{T_1}
\EdgeL{D}{F}{T_1}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\EdgeR{E}{F}{T_2}
\LoopN[.5]{B}{T_1|-1}
\LoopN[.5]{C}{T_2|-1}
\LoopS[.5]{D}{T_2|-1}
\LoopS[.5]{E}{T_1|-1}
\LoopS[.5]{F}{\StackTwoLabels{\IOL{T_1}{-1}}{\IOL{T_2}{-1}}}
%
\end{VCPicture}}
\end{center}
\caption{Description de $\mathfrak H^n_k(0)\cdot abc$}
\label{f4}
\end{figure}
%

\bigskip
\noindent
L'algèbre de Hecke $\mathfrak H^n_k(0)$ agit à gauche sur 
$\mathbb Q\l a_1,\cdots,a_n\r$ comme suit :
%
\begin{equation*}\left\{
\begin{array}{ll}
T_i(\dotsc a(i)a(i+1)\dotsc) =\dotsc a(i+1)a(i)\dotsc 
                                         & \text{si $a(i)<a(i+1).$} \\
T_i(\dotsc a(i)a(i+1)\dotsc) = 0,        & \text{si $a(i)=a(i+1).$}  \\
T_i(\dotsc a(i)a(i+1)\dotsc) =-\dotsc a(i)a(i+1)\dotsc 
                                         & \text{si $a(i)>a(i+1).$} \\
\end{array} \right.
\end{equation*}
Où $a(i)$ est la lettre du mot argument à la place $i$.
%
\subsection{Exemples de décompositions}
Soit $m=abc \in \mathbb Q\l a,b,c\r$. Une description complète de l'action de
$T_i$ sur $\mathfrak H^3_k(0)\cdot m$ est donnée dans la figure \ref{f4}. 
En choisissant l'ordre lexicographique gradué  pour le parcours de l'arbre des 
suffixes, l'ensemble suffixe est 
\[
P=\{\varepsilon,T_1,T_2,T_1T_2,T_2T_1,T_1T_2T_1\}.
\] 
L'ensemble des relateurs est ici 
\[
R=\left \{
\begin{array}{l}
%\varepsilon\varepsilon   + \varepsilon,\, T^2_1+T_1,\\
T^2_2+T_2,\, T_1T^2_2+T_1T_2,\\
T_2T^2_1+T_2T_1,\, T_2T_1T_2-T_1T_2T_1\\
T_1T_2T^2_1+T_1T_2T_1, \, T_1T_2T_1T_2+T_1T_2T_1\\
\end{array}\right \}.
\]
Soit $\varphi\in\End_{\A}(\A\cdot m)$ et $m_{\varphi}\in \A\cdot m$ tel 
que :
\begin{align*}
m_{\varphi} & =\alpha_{\varepsilon}\varepsilon\cdot m+\alpha_{T_1}T_1\cdot m+
            \alpha_{T_2}T_2\cdot m+\alpha_{T_1T_2}T_1T_2\cdot m\\
            &+\alpha_{T_2T_1}T_2T_1\cdot m+\alpha_{T_1T_2T_1}T_1T_2T_1\cdot m
\end{align*}
L'algorithme suffixe nous a retourné l'ensemble suffixe $P$ et l'ensemble 
des relateurs $R$, on applique l'algorithme $cons\_\varphi$ qui va 
permettre de calculer la matrice $\varphi$ et l'ensemble des projecteurs. 
La matrice $\varphi$ est la suivante :
{\tiny 
\[
\varphi=
\begin{pmatrix}
\alpha{T_\varepsilon} & 0                            & 0    & 0 & 0 & 0 \\ 
\alpha_{T_1} & \alpha_{T_{\varepsilon}}-\alpha_{T_1} & 0    & 0 & 0 & 0 \\ 
\alpha_{T_2}    & 0 & \alpha_{T_{\varepsilon}}-\alpha_{T_2} & 0 & 0 & 0\\
\alpha_{T_1T_2} & 0 & \alpha_{T_1}-\alpha_{T_1T_2} & \alpha_{T_{\varepsilon}}
-\alpha_{T_1} & 0 & 0 \\
\alpha_{T_2T_1} & \alpha_{T_2}-\alpha_{T_2T_1} & 0 & 0 &
\alpha_{T_{\varepsilon}}-\alpha_{T_2} & 0 \\
\alpha_{T_1T_2T_1} & \alpha_{T_1T_2}-\alpha_{T_1T_2T_1} & 
\alpha_{T_2T_1}-\alpha_{T_1T_2T_1} & 
\alpha_{T_2}-\alpha_{T_1T_2} & 
\alpha_{T_1}-\alpha_{T_1T_2} & 
\alpha_{T_{\varepsilon}}\alpha_{T_1}-\alpha_{T_1T_2}\\
 &  &  & -\alpha_{T_2T_1} & 
-\alpha_{T_2T_1} & 
-\alpha_{T_1T_2}-\alpha_{T_2T_1}\\
 & & & +\alpha_{T_1T_2T_1} & +\alpha_{T_1T_2T_1} & +\alpha_{T_1T_2T_1}\\
\end{pmatrix}
\]}
Une solution non-triviale du système donné par $\varphi^2=\varphi$,  
$T\cdot \varphi(m)=\varphi(T\cdot m)$ pour tout $T\in P$ et 
$r\cdot \varphi(m)=0$ pour tout $r\in R$ est :
$m_{\varphi}=-T_1T_2T_1\cdot m$
et  
$m_{1-\varphi}=\varepsilon\cdot m+T_1T_2T_1\cdot m$, c'est à dire 
$m_{\varphi}=-cba$ et  $m_{1-\varphi}=abc+cba$. Ce qui nous donne une 
première décomposition $\mathfrak H^3_k(0)\cdot abc=-\mathfrak H^3_k(0)\cdot 
cba+\mathfrak H^3_k(0)\cdot (abc+cba)$ donnée dans la figure \ref{f5}.
%
\begin{figure}
\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(7,-2)(12,8)}
%
\StateVar[-cba]{(3,8)}{G}
\StateVar[abc+cba]{(12,8)}{A}
\StateVar[bac-cba]{(9,5)}{B}
\StateVar[acb-cba]{(15,5)}{C}
\StateVar[bca+cba]{(9,2)}{D}
\StateVar[cab+cba]{(15,2)}{E}
\ChgStateLineStyle{dotted}
\StateVar[0]{(12,-1)}{F}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeL{A}{B}{T_1}
\EdgeR{A}{C}{T_2}
\EdgeR{B}{D}{T_2}
\EdgeL{C}{E}{T_1}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\EdgeL{D}{F}{T_1}
\EdgeR{E}{F}{T_2}
\LoopN[.5]{B}{T_1|-1}
\LoopN[.5]{C}{T_2|-1}
\LoopS[.5]{D}{T_2|-1}
\LoopS[.5]{E}{T_1|-1}
\LoopS[.5]{G}{\StackTwoLabels{\IOL{T_1}{-1}}{\IOL{T_2}{-1}}}
%
\end{VCPicture}}
\end{center}
\caption{Action de $T_i$ sur $\mathfrak H^3_k(0)\cdot (-cba)$ et 
$\mathfrak H^3_k(0)\cdot (abc+cba)$.}
\label{f5}
\end{figure}
%
On applique maintenant l'algorithme sur le sous-module 
$\mathfrak H^3_k(0)\cdot m'$ avec $m'=(abc+cba)$ pour voir s'il est 
décomposable ou non. L'ensemble suffixe est 
\[
P=\{\varepsilon,T_1,T_2,T_1T_2,T_2T_1\}.
\]
L'ensemble des relateurs est 
\[
R=\left \{
\begin{array}{l}
%\varepsilon\varepsilon   + \varepsilon,\\ 
T_1T_2T_1,\, T_2T_1T_2,\\
T^2_1+T_1,\, T^2_2+T_2,\\
T_1T^2_2+T_1T_2,\, T_2T^2_1+T_2T_1\\
\end{array}\right \}.
\]
Soit $\varphi\in\End_{\A}(\A\cdot m')$ et $m'_{\varphi}\in \A\cdot m'$ 
tel que :
\begin{align*}
m'_{\varphi} & =\alpha_{\varepsilon}\varepsilon\cdot m'+\alpha_{T_1}T_1\cdot m'
+ \alpha_{T_2}T_2\cdot m'+\alpha_{T_1T_2}T_1T_2\cdot m'+\alpha_{T_2T_1}T_2T_1
\cdot m'.
\end{align*}
La matrice $m'_{\varphi}$ est la suivante :
\[
\varphi=
\begin{pmatrix}
\alpha{T_\varepsilon} & 0                            & 0    & 0 & 0 \\ 
\alpha_{T_1} & \alpha_{T_{\varepsilon}}-\alpha_{T_1} & 0    & 0 & 0 \\ 
\alpha_{T_2}    & 0 & \alpha_{T_{\varepsilon}}-\alpha_{T_2} & 0 & 0 \\
\alpha_{T_1T_2} & 0 & \alpha_{T_1}-\alpha_{T_1T_2} & \alpha_{T_{\varepsilon}}
-\alpha_{T_1} & 0\\
\alpha_{T_2T_1} & \alpha_{T_2}-\alpha_{T_2T_1} & 0 & 0 &
\alpha_{T_{\varepsilon}}-\alpha_{T_2}  \\
\end{pmatrix}
\]
%
\begin{figure}
\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(12,-3)(12,13)}
%
\StateVar[abc+cba+cab+acb+bac+bca]{(12,10)}{G}
\StateVar[-cab-acb-bac-bca]{(12,8)}{A}
\StateVar[bac-cba]{(8,4)}{B}
\StateVar[acb-cba]{(16,4)}{C}
\StateVar[bca+cba]{(8,0)}{D}
\ChgStateLineStyle{dotted}
\StateVar[0]{(12,-2)}{F}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeL{A}{B}{T_1}
\EdgeR{A}{C}{T_2}
\EdgeR{B}{D}{T_2}
\ChgEdgeLineStyle{dotted}
\ChgEdgeLineColor{blue}
\ChgEdgeLabelColor{blue}
\EdgeL{C}{B}{\IOL{T_1}{-1}}
\EdgeL{C}{D}{\IOL{T_1}{-1}}
\EdgeL{D}{F}{T_1}
\LoopN[.5]{B}{T_1|-1}
\LoopS[.5]{D}{T_2|-1}
\LoopS[.7]{C}{\StackTwoLabels{\IOL{T_1}{-1}}{\IOL{T_2}{-1}}}
\LoopN[.5]{G}{\StackTwoLabels{\IOL{T_1}{-1}}{\IOL{T_2}{-1}}}
\ChgEdgeArrowStyle{->}
\VArcR[.5]{arcangle=-45}{C}{A}{\IOL{T_1}{-1}}
%
\end{VCPicture}}
\end{center}
\caption{Action de $T_i$ sur $\mathfrak H^3_k(0)\cdot m'_{\varphi}$ et 
$\mathfrak H^3_k(0)\cdot m'_{1-\varphi}$.}
\label{f6}
\end{figure}
%
\noindent
Une solution non-triviale du système donné par $\varphi^2=\varphi$, 
$T\cdot \varphi (m')=\varphi (T\cdot m')$ pour tout $T\in P$
 et $r\cdot \varphi (m')=0$ pour tout $r\in R$ est 
$m'_{\varphi}=-T_1\cdot m'-T_2\cdot m'-T_1T_2\cdot m'-T_2T_1\cdot m'$ et 
$m'_{1-\varphi}=\varepsilon\cdot m'+T_1\cdot m'+T_2\cdot m'+T_1T_2\cdot m'+
T_2T_1\cdot m'$, c'est à dire $m'_{\varphi}=-cab-acb-bac-bca$ et 
$m'_{1-\varphi}=abc+cba+cab+acb+bac+bca$ 
%Le morphisme 
%$m'_{\varphi}=-cab-acb-bac-bca$ se décompose en $m''_{\varphi}=-bac+cba$ 
%et $m''_{1-\varphi}= -cab-acb-bca-cba$ 
et la description complète de 
$\mathfrak H^3_k(0)\cdot (abc+cba)$ est donnée dans la figure \ref{f6}. 
La décomposition complète du $\mathfrak H^3_k(0)$-module 
$\mathfrak H^3_k(0)\cdot abc$ est donnée dans la figure \ref{f7}.
%
\begin{figure}
\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(8,3)(11,8)}
%
\StateVar[\mathfrak H^3_k(0)\cdot abc]{(8,8)}{A}
\StateVar[\mathfrak H^3_k(0)\cdot m_{\varphi}]{(4,6)}{B}
\StateVar[\mathfrak H^3_k(0)\cdot m_{1-\varphi}]{(12,6)}{C}
\StateVar[\mathfrak H^3_k(0)\cdot m'_{\varphi}]{(8,4)}{D}
\StateVar[\mathfrak H^3_k(0)\cdot m'_{1-\varphi}]{(16,4)}{E}
%\StateVar[\mathfrak H^3_k(0)\cdot m''_{\varphi}]{(4,2)}{F}
%\StateVar[\mathfrak H^3_k(0)\cdot m''_{1-\varphi}]{(12,2)}{G}
\ChgEdgeLineColor{red}
\ChgEdgeLabelColor{red}
\EdgeL{A}{B}{}
\EdgeR{A}{C}{}
\EdgeR{C}{D}{}
\EdgeR{C}{E}{}
%\EdgeR{D}{F}{}
%\EdgeR{D}{G}{}
%
\end{VCPicture}}
\end{center}
\caption{Décomposition complète de $\mathfrak H^3_k(0)\cdot abc$.}
\label{f7}
\end{figure}
%
\section{Description du programme  DEC-MOD}
Nous allons manipuler maintenant notre algorithme de décomposition de 
module en MuPAD pour l'appliquer sur des modules sur l'algèbre du groupe 
symétrique ou sur l'algèbre de Hecke à $q=0$. Nous commençons par le cas des 
groupes symétriques. Pour cela, on doit définir le domaine des modules sur 
cette algèbre.

\begin{verbatim} 
>> F:=Dom::FreeModuleTable(Dom::IntegerMod(2),combinat::words)

      Dom::FreeModuleTable(Dom::IntegerMod(2), combinat::words)
\end{verbatim}
Soit $f:\{0,1\}^3\rightarrow \{0,1\}$ définie par 
$f(X_1,X_2,X_3)=X_1X_3+X_1$. On définit maintenant le module 
$\A_3\cdot f$ comme suit :
\begin{verbatim}

>> G:=F([1,0,1])+F([1,0,0])

                        B([1, 0, 1]) + B([1, 0, 0])
\end{verbatim}
Une fois qu'on a le module, on peut appliquer l'algorithme :
\begin{verbatim}

>> decomposition(3,G,2)

        {[x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0],

         [x1 = -1, x2 = 0, x3 = 0, x4 = 0, x5 = 0],

         [x1 = 0, x2 = 0, x3 = 0, x4 = -1, x5 = -1],

         [x1 = -1, x2 = 0, x3 = 0, x4 = -1, x5 = -1]}

\end{verbatim}
D'après l'ensemble des projecteurs, le module $\A_3\cdot f$  se décompose en 
$\A_3\cdot (X_2X_3+X_3)$ et $\A_3\cdot (X_1X_2+X_2)$. On applique le même 
algorithme sur les sous-modules 
$\A_3\cdot (X_2X_3+X_3)$ et $\A_3\cdot (X_1X_2+X_2)$, pour voir s'ils sont 
décomposables ou non :
\begin{verbatim}
>> G1:=F([0,1,1])+F([0,0,1])
                         
                         B([0, 1, 1]) + B([0, 0, 1])

>> G2:=G+G1

   B([1, 0, 1]) + B([1, 0, 0]) + B([0, 1, 1]) + B([0, 0, 1])

>> decomposition(3,G1,2)

       {[x1 = 0, x2 = 0, x3 = 0, x4 = 0], 

        [x1 = -1, x2 = 0, x3 = 0, x4 = 0]}

>> decomposition(3,G2,2)

                       {[x1 = 0], [x1 = -1]}

\end{verbatim}
Les deux sous-modules ne sont donc pas décomposables et une somme directe pour 
le module $\A_3\cdot f$ est 
\[
\A_3\cdot f=\A_3\cdot (X_2X_3+X_3)\oplus \A_3\cdot (X_1X_2+X_2)
\]
On définit maintenant le domaine des modules sur l'algèbre de Hecke à $q=0$
 $\mathfrak H^3_k(0)$.
\begin{verbatim}

>>F:=Dom::FreeModuleTable(Dom::Rational,combinat::integerVectors)

   Dom::FreeModuleTable(Dom::Rational, combinat::integerVectors)

\end{verbatim}
Ensuite, le module $\mathfrak H^3_k(0)\cdot abc$.
\begin{verbatim}

>> G:=F([1,2,3])

                          B([1, 2, 3])
\end{verbatim}
On applique maintenant l'algorithme pour voir si 
$\mathfrak H^3_k(0)\cdot abc$ est décomposable ou non.
\begin{verbatim}

  {[x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0],

   [x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = -1],

   [x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0],

   [x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 1],

   [x1 = 0, x2 = -1, x3 = -1, x4 = -1, x5 = -1, x6 = 0],

   [x1 = 0, x2 = -1, x3 = -1, x4 = -1, x5 = -1, x6 = -1],

   [x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 1, x6 = 0],

   [x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 1, x6 = 1]}

\end{verbatim}
D'après l'ensemble des projecteurs, et en choisissant le deuxième projecteur, 
le module se décompose en $\mathfrak H^3_k(0)\cdot (-cba)$ et 
$\mathfrak H^3_k(0)\cdot (abc+cba)$. On vérifie maitenant si le sous-module 
$\mathfrak H^3_k(0)\cdot (abc+cba)$ est décomposable ou non. 
\begin{verbatim}

>> G1:=F([1,2,3])+F([3,2,1])

                        B([1, 2, 3]) + B([3, 2, 1])

\end{verbatim}
\begin{verbatim}

  {[x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0],

   [x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 0],

   [x1 = 0, x2 = -1, x3 = -1, x4 = -1, x5 = -1],

   [x1 = 1, x2 = 1, x3 = 1, x4 = 1, x5 = 1]}

\end{verbatim}
Si on choisit le troisième projecteur, le sous-module 
$\mathfrak H^3_k(0)\cdot (abc+cba)$ se décompose en 
$\mathfrak H^3_k(0)\cdot (-bac-acb-bca-cab)$ et 
$\mathfrak H^3_k(0)\cdot (abc+cba+bac+acb+bca+cab)$ et une somme directe du 
module $\mathfrak H^3_k(0)\cdot abc$ est 
\begin{align*}
\mathfrak H^3_k(0)\cdot abc & =\mathfrak H^3_k(0)\cdot (-cba)\\
                         & \oplus \mathfrak H^3_k(0)\cdot (-bac-acb-bca-cab)\\
                         & \oplus \mathfrak H^3_k(0)\cdot 
                                         (abc+cba+bac+acb+bca+cab).
\end{align*}
On peut manipuler aussi la fonction suffixe qui calcule une base pour l'espace 
$\A\cdot m$ et un ensemble de relateurs. Nous allons l'appliquer pour le 
module $\mathfrak H^3_k(0)\cdot abc$. 
\begin{verbatim}
>> suffixe(3,G,1)

 [
  [[0], B([1, 2, 3])], 
  [[0, 1], B([2, 1, 3])], 
  [[0, 2], B([1, 3, 2])],
  [[0, 1, 2], B([2, 3, 1])], 
  [[0, 2, 1], B([3, 1, 2])],
  [[0, 1, 2, 1], B([3, 2, 1])]]


          table(
                      table(
          [0, 1, 2, 1, 2] =   [0, 1, 2, 1] = -1 ,
                            )
                      table(
          [0, 1, 2, 1, 1] =   [0, 1, 2, 1] = -1 ,
                            )
                      table(
          [0, 2, 1, 2] =   [0, 1, 2, 1] = 1 ,
                            )
                      table(
          [0, 2, 1, 1] =   [0, 2, 1] = -1 ,
                            )
                      table(
          [0, 1, 2, 2] =   [0, 1, 2] = -1 ,
                            )
                      table(
          [0, 2, 2] =   [0, 2] = -1 ,
                            )
                      table(
          [0, 1, 1] =   [0, 1] = -1 ,
                            )
                      table(
          [0] =   [0] = 1
                            )
          )

\end{verbatim}


\subsection{Cas des groupes finis : Caractères}

Dans ce qui suit les \ev sont supposés sur $k\ (=\R\textrm{ ou }\C)$ et les groupes sont supposés finis.

\bs
\begin{definition}
	Soit $G$ un groupe et $V$ un EV. On appelle représentation de $G$ dans $V$ une application $\rho\ :\ G\mapsto Aut(V)$ compatible avec la multiplication, c'est à dire que 
\begin{equation}
	(\forall g_1,g_2\in G)(\rho(g_1g_2)=\rho(g_1)\circ\rho(g_2))
\end{equation}
Avec cette donnée, $V$ est appelé $G$-module. L'image $\rho(g)[v]$ se note souvent $g.v$.
\end{definition}

\begin{exo}
Soit $G$, un groupe et $\rho_G$ une représentation de l'ensemble $G$ dans l'espace vectoriel $V$.\\
Montrer que les conditions suivantes sont équivalentes :\\
i) $\rho_G$ est une représentation du groupe $G$\\
ii) $\rho_G$ est une représentation du semigroupe $G$ et $\rho_G(1_G)=Id_V$.
\end{exo}

Selon le schema général, on dit qu'une application linéaire ($k$-linéaire) entre deux $G$-modules 
$\phi\ :\ V_1\mapsto V_2$ est $G$-linéaire si les actions de $G$ agissent comme des scalaires (c'est à dire permutent avec $\phi$ ou peuvent être ``sorties'' de $\phi$). Si $\phi$ est bijective (ou inversible) on dit que $V_1$ et $V_2$ sont isomorphes (c'est à dire ``ont même forme''). On dit qu'une représentation $V$ (de $G$) contient une autre (disons $W$), s'il y a un sous-module de $V$ qui est isomorphe à $W$. À cause de l'unicité des décompositions, on voit que la {\it signature} du $G$-module $V$ est l'ensemble des ``types'' de modules qu'il contient (avec leur multiplicités). Il nous faut d'abord étudier une représentation modèle, c'est à dire qui contient toutes les autres.   
  

\begin{exo} Pour le module de la figure \mref{exemple2}, écrire les matrices de transition. Montrer que ce module est irréductible.\\ 
Donner la fonction trace (i.e. $g\ra tr(\rho(g))$ (voir le paragraphe \mref{trace}).
\end{exo}

\subsubsection{Un modèle qui contient toutes les représentations : la représentation régulière}

\begin{exo}\label{idemp_orth} 
Soit $G$, un groupe fini. On considère la AAU $\A=\C[G]$ (sommes à coefficients complexes 
$\sum_{g\in G}\al_g g$) et les opérateurs $\gamma_h\ :\ \sum_{g\in G}\al_g g\ra \sum_{g\in G}\al_g h.g$ 
($=h.\sum_{g\in G}\al_g g$ dans $\A$).\\ 
1) a) Montrer que $g\mapsto \gamma_g$ est une représentation de $G$.\\
2) Soit 
\begin{equation}\label{decalg}
\C[G]=\oplus_{i=1..n} V_i	
\end{equation}
 une décomposition en modules (i.e. \sev stables pour l'action des $\gamma_g$, c'est à dire les multiplications à gauche) et $1_G=\sum_{i=1}^n e_i$ la décomposition de $1_G$ selon \mref{decalg}\footnote{On dit aussi résolution de l'unité.}.\\
a) Montrer que l'on a 
\begin{enumerate}[i)]
	\item $1_G=\sum_{i=1}^n e_i$
	\item $(\forall i\in [1..n])(e_ie_i=e_i)$
	\item $(\forall i,j\in [1..n])(i\not= j\Longrightarrow e_ie_j=e_je_i=0)$
\end{enumerate}
b) Inversement, montrer que, si une famille d'éléments de $\C[G]$ vérifie (ex \ref{idemp_orth}.2.a), on a \mref{decalg} avec $V_i=\C[G]e_i$. \\
\end{exo}

{\bf Commentaire}\pointir Une famille $(e_i)_{i=1..n}$ d'idempotents qui vérifie les conditions de l'exercice \mref{idemp_orth} est appelée FCIO,  {\it famille complète d'idempotents orthogonaux}. Si, de plus, les modules $\A e_i$ sont irréductibles, cette famille est appelée FCIOM, {\it famille complète d'idempotents orthogonaux minimaux}.
\hfill$\diamondsuit$\\
\hspace{1cm}

\begin{exo}
Utiliser l'exercice \mref{exoproj} pour montrer que, dans $\A=\C[G]$, on peut toujours construire une FCIOM.\\
\end{exo}

\begin{exo} (Cette version ``effective'' du théorème de Wedderburn est due à Marianne Flouret \cite{Fl})\\
1) a) Soient $e,f\in \A$ deux idempotents, montrer que la formule
\begin{equation}
\phi_{fae}(x)=xfae
\end{equation}
définit un élément de $\Hom_{G}(\A f,\A e)$.\\
b) Montrer que la correspondance $fae\ra \phi_{fae}(x)$, $f\A e\mapsto \Hom_{G}(\A f,\A e)$ est un isomorphisme d'\ev s.\\
c) En déduire que, si $\A e$ et $\A f$ sont irréductibles, $f\A e$ soit de dimension $0$ (si $\A e$ et $\A f$ ne sont pas du même type) soit de dimension $1$ (si $\A e$ et $\A f$ sont du même type).\\
2) Soit $(e_1^{(1)},\cdots e_{n_1}^{(1)}, e_1^{(2)},\cdots e_{n_2}^{(2)},  \cdots \cdots 
,e_1^{(k)},\cdots   e_{n_k}^{(k)})$ une FCIOM rangés selon les types des $\A e_i^{(j)}$. Pour chaque bloc $e_1^{(j)},\cdots   e_{n_j}^{(j)}$, et chaque $l\in [1..n_j-1]$ on prend un élément $e_l^{(j)}a_l^{(j)}e_{l+1}^{(j)}$ tel que $\not=0$ (on rappelle que pour deux idempotents $e,f$ de la liste, on a 
$$
dim(f\A e)=[e\textrm{ et } f\textrm{ sont de même type}])
$$
on construit ensuite les éléments $E_{l,l+1}^{(j)}=e_l^{(j)}a_l^{(j)}e_{l+1}^{(j)}$ puis, pour $1\leq l< m\leq n_j$ 
\begin{equation}
E_{l,m}^{(j)}=E_{l,l+1}^{(j)}E_{l+1,l+2}^{(j)}\cdots E_{m-1,m}^{(j)}
\end{equation}
ensuite on choisit $a_{n_j}^{(j)}$ de façon que $E_{n_j,1}^{(j)}=e_{n_j}^{(j)}a_{n_j}^{(j)}e_{1}^{(j)}$ vérifie $E_{1,n_j}^{(j)}E_{n_j,1}^{(j)}=e_{1}^{(j)}$ puis, pour $1\leq m\leq l\leq n_j$ 
\begin{equation}
E_{l,m}^{(j)}=E_{l,l+1}^{(j)}E_{l+1,l+2}^{(j)}\cdots 
E_{n_j-1,n_j}^{(j)}E_{n_j,1}^{(j)}E_{1,2}^{(j)}E_{2,3}^{(j)}\cdots  E_{m-1,m}^{(j)}
\end{equation}
a) Montrer que les $E_{l,m}^{(j)}$ forment un système d'unités matricielles c'est à dire que 
\begin{equation}
E_{a,b}^{(j)}E_{c,d}^{(j)}=[b=c]E_{a,d}^{(j)}	
\end{equation}
et que $E_{a,a}^{(j)}=e_a{(j)}$\\
b) Montrer que la famille $\big(E_{a,b}^{(j)}\big)_{1\leq j\leq k\top 1\leq a,b\leq n_j}$ est une base de $\C[G]$.
\end{exo}

\subsubsection{Construction d'une FCIOM pour le groupe symétrique}

Nous allons construire une FCIOM gràce à une algorithme extrêmement efficace donné par la définition d'un drapeau de polynômes, les GZ-polyn\^omes\footnote{Version simplifiée de la construction que l'on peut trouver dans la thèse d'\'Eric Laugerotte\cite{La}.}. Cette construction repose sur l'emboîtement des groupes symétriques 
\begin{equation}
	\SG_0\subset \SG_1\subset \SG_2\subset\cdots  \subset\SG_n\subset\SG_{n+1}\cdots   
\end{equation}


\begin{exo}\label{scal_inv} 
(Ici, $k=\R$ et $G$ est un groupe fini) Soit $V$, un $G$-module de dimension finie. On dit qu'un produit scalaire $\scal{.}{.}$ sur $V$ est invariant par $G$ si 
\begin{equation}
	(\forall g\in G)(\forall u,v\in V)(\scal{g.u}{g.v}=\scal{u}{v})
\end{equation}
1) Montrer que si $W\subset V$ est stable, il en est de même de $W^\perp$.\\
2) Reprendre l'exercice précédent avec $k=\C$ et un produit scalaire hermitien.\\
3) Montrer, d'une autre façon que dans l'exercice \mref{idemp_orth}, que la représentation régulière contient toutes les représentations.

On munit $\A=\C [G]$ de 
 
\begin{equation}\label{pscal}
\scal{\sum_{g\in G}\al\ g}{\sum_{g\in G}\be\ g}=	\sum_{g\in G}\bar\al\be. 
\end{equation}

3) a) Vérifier que \mref{pscal} définit bien un produit scalaire (hermitien) pour lequel les points de $G$ (i.e. les fonctions caractéristiques) forment une base orthogonale.\\
b) Montrer que  
\begin{equation}
	(\forall g\in G)(\forall\ u,v\in \A)(\scal{u}{v}=\scal{\gamma_g(u)}{\gamma_g(v)})
\end{equation}
(c'est à dire que ce produit scalaire est invariant, voir l'exercice \mref{scal_inv}).\\
c) En déduire qu'il existe une décomposition de type \mref{decalg} en sous-modules irréductibles (les idempotents correspondants seront dits minimaux).

{\small
4) a) Soit $U$ un $G$-module irréductible et $x$ une de ses vecteurs non nuls. Soit 
$$
ann(x)=\{h\in \C[G]\ |\ h.x=0\}.
$$ 
Montrer que $ann(x)^\perp$ est un sous module de $\C[G]$ (en tant que $G$-module à gauche) et que 
$U\simeq ann(x)^\perp$.\\
b) Soit $\C[G]=\oplus_{i=1}^n V_i$ une décomposition en sous-modules irréductibles. Montrer qu'il existe un indice $j\in [1..n]$ (et un seul) tel que
\begin{equation}\label{decalg}
\C[G]=(\oplus_{i=1..j-1} V_i)\oplus (ann(x)^\perp)\oplus (\oplus_{i=j+1..n} V_i)
\end{equation} 
c) En déduire que $\C[G]$ contient (au moins) une copie de chaque représentation irréductible de $G$.}

5) Ici $G=\SG_n$. On considère, dans $\C[G]$, les \'el\'ements 
de Jucys-Murphy $(x_m)_{2\leq m\leq n}$	(voir \cite{Ju} et \cite{Mu}) définis par 

\begin{eqnarray}
x_m&=&\sum_{i=1}^{m-1} \si_{(i,m)} \textrm{ où $\si_{(i,m)}$ est la transposition de $i$ et de $m$.}
\end{eqnarray}

a) Montrer les relations suivantes. 
a1) Si $i,j\in [2..n]$ tels que $i<j-1$,  
%
\begin{eqnarray}
\left [\si_i,x_j\right ]&=&0.\label{Tx}
\end{eqnarray}

a2) Si $i=j-1$, 
%
\begin{eqnarray}
\si_{j-1}x_j&=&1+x_{j-1}\si_{j-1}\label{Tx2}
\end{eqnarray}

a3) 
%
\begin{eqnarray}
x_j\si_{j-1}&=&1+\si_{j-1}x_{j-1}.\label{Tx3}
\end{eqnarray}

b) D\'eduire des relations \ref{Tx}, \ref{Tx2} et \ref{Tx3}, la relation de 
commutation 
%
\begin{eqnarray}
\left [x_i,x_j\right ]=0.
\end{eqnarray}
\end{exo}


 
\begin{figure}[h]
%
\vbox to 40mm{
\qline(4,0)(4,-4)
\qline(5,0)(5,-4)
\qline(6,-1)(6,-4)
\qline(7,-1)(7,-4)
\qline(8,-2)(8,-4)
\qline(9,-3)(9,-4)
%
\qline(4,0)(5,0)
\qline(4,-1)(7,-1)
\qline(4,-2)(8,-2)
\qline(4,-3)(9,-3)
\qline(4,-4)(9,-4)
}
%
\caption{Le diagramme de Ferrers de $(5,4,3,1)$.}
\label{f14}
\end{figure} 

Les modules irréductibles sur $\SG_n$ sont indexés par des diagrammes de Ferrers à $n$ cases.\\ 
Les polynômes qui servent à la construction d'une FCIOM sont calculés par rapport à un objet combinatoire que l'on nomme {\it tableau de Young}.\\

On d\'esigne par $t$ un {\em tableau} de Young
(voir \cite{FH}, \cite{Mc1} ou \cite{LS2}) de forme $\lambda$, 
un remplissage du diagramme de Ferrers de forme $\lambda$ 
par des lettres appartenant \`a un alphabet $\{a_1,a_2\ldots \}$, ordonn\'e par 
($a_1<a_2<\cdots $), tel que les mots 
lus de la gauche vers la droite sur les lignes  soient croissants et les mots 
lus sur les colonnes de bas en haut soient strictement croissants.  

Un tableau de Young est dit standard lorsqu'il ne comporte aucune répétition. 
Il est utile pour la suite, sans perte de g\'en\'eralit\'e, de prendre comme  
alphabet l'ensemble $[1..n]$ muni de l'ordre usuel sur les entiers. 
%
\begin{figure}[h]
%
\vbox to 40mm{
%\psgrid(0,0)(11,-6)
\qline(4,0)(4,-4)
\qline(5,0)(5,-4)
\qline(6,-1)(6,-4)
\qline(7,-1)(7,-4)
\qline(8,-2)(8,-4)
\qline(9,-3)(9,-4)
%
\qline(4,0)(5,0)
\qline(4,-1)(7,-1)
\qline(4,-2)(8,-2)
\qline(4,-3)(9,-3)
\qline(4,-4)(9,-4)
%
\rput(4.5,-0.5){\small{9}}
\rput(4.5,-1.5){\small{6}}
\rput(4.5,-2.5){\small{2}}
\rput(4.5,-3.5){\small{1}}
\rput(5.5,-1.5){\small{10}}
\rput(5.5,-2.5){\small{5}}
\rput(5.5,-3.5){\small{3}}
\rput(6.5,-1.5){\small{11}}
\rput(6.5,-2.5){\small{7}}
\rput(6.5,-3.5){\small{4}}
\rput(7.5,-2.5){\small{13}}
\rput(7.5,-3.5){\small{8}}
\rput(8.5,-3.5){\small{12}}
}
%
\caption{Un tableau de Young de forme $(5,4,3,1)$.}
\label{f16}
\end{figure}
 
Pr\'ecisons l'action des $x_m$ sur ${\cal H}^{n}_{\Q(q)}(q)$.  
%
\begin{figure}[h]
%
%
\vbox to 55mm{
%\psgrid(0,0)(11,-6)
\qline(4,-1)(4,-5)
\qline(5,-1)(5,-5)
\qline(6,-2)(6,-5)
\qline(7,-2)(7,-5)
\qline(8,-3)(8,-5)
\qline(9,-4)(9,-5)
%
\qline(4,-1)(5,-1)
\qline(4,-2)(7,-2)
\qline(4,-3)(8,-3)
\qline(4,-4)(9,-4)
\qline(4,-5)(9,-5)
%
\rput(4.5,-1.5){9}
\rput(4.5,-2.5){6}
\rput(4.5,-3.5){2}
\rput(4.5,-4.5){1}
\rput(5.5,-2.5){10}
\rput(5.5,-3.5){5}
\rput(5.5,-4.5){3}
\rput(6.5,-2.5){11}
\rput(6.5,-3.5){7}
\rput(6.5,-4.5){4}
\rput(7.5,-3.5){13}
\rput(7.5,-4.5){8}
\rput(8.5,-4.5){12}
%
\qline(3.5,-2.5)(5.5,-0.5)
\qline(3.5,-3.5)(5.5,-1.5)
\qline(3.5,-4.5)(6.5,-1.5)
\qline(3.5,-5.5)(7.5,-1.5)
\qline(4.5,-5.5)(7.5,-2.5)
\qline(5.5,-5.5)(8.5,-2.5)
\qline(6.5,-5.5)(8.5,-3.5)
\qline(7.5,-5.5)(9.5,-3.5)
%
\rput(5.7,-0.3){-3}
\rput(5.7,-1.3){-2}
\rput(6.7,-1.3){-1}
\rput(7.7,-1.3){0}
\rput(7.7,-2.3){1}
\rput(8.7,-2.3){2}
\rput(8.7,-3.3){3}
\rput(9.7,-3.3){4}
}
%
%
\caption{Les diagonales d'un tableau de Young.}
\label{f22}
\end{figure}

Les {\em GZ-polyn\^omes}, index\'es par les tableaux de Young et not\'es $GZ_t$, 
seront d\'efinis r\'ecursivement comme suit,   
%
\[
GZ_t=\left\{
\begin{array}{ll}
1&\mbox{si $t$ est de poids $1$,}\\
GZ_{t-n}\times\displaystyle\prod_{{\scriptsize t'-n=t-n}\atop{\scriptsize 
t'\not =t}}
\frac{\displaystyle X_n-\chi_{t'}(n)}{\displaystyle \chi_t(n)-
\chi_{t'}(n)}&\mbox{si $t$ est de poids $n$.}
\end{array}
\right .
\]
%
  

\begin{theorem}\label{gelf}
%
Posons $t\in\mbox{Tab}(n)$, $GZ_t\left (x_2,x_3,\ldots ,x_n\right )=g_t$. Alors $\left (g_t\right)_{t\in\mbox{\scriptsize Tab}(n)}$ est une FCIOM de $\C[\SG_n]$ (qui est d'ailleurs dans $\Q[\SG_n]$).    
%
\end{theorem}

%
\noindent
%
{\bf Preuve}\hspace{1mm} Soit $h_t$ l'\'evaluation du polyn\^ome $GZ_t$ en 
$\left (x_2,x_3,\ldots ,x_n\right )$. Quand $n=2$, les GZ-polyn\^omes sont les 
suivants, 
%
\[
\renewcommand{\arraystretch}{1.8}
\begin{array}{lll}
%
GZ_{(1,1)^c}&=&\frac{\displaystyle -1}{\displaystyle 2}\left (X_2-1\right ),\\
%
GZ_{(2)^c}&=&\frac{\displaystyle 1}{\displaystyle 2}\left (X_2+1\right ).\\
%
\end{array}
\]
% 
\`A l'aide de quelques calculs simples, on montre que 
\[
\begin{array}{lll}
%
\chi_{(1,1)^c}\left (h_{(1,1)^c}\right )&=&1,\\
%
\chi_{(2)^c}\left (h_{(1,1)^c}\right )&=&0,\\
%
\chi_{(1,1)^c}\left (h_{(2)^c}\right )&=&0,\\
%
\chi_{(2)^c}\left (h_{(2)^c}\right )&=&1.\\
%
\end{array}
\]
On suppose maintenant $n>2$. Pour tout tableau de Young $t\in\mbox{Tab}(n)$, 
on d\'eduit de la formule du polyn\^ome $GZ_t$ que, si $t_0\in\mbox{Tab}(n)$, 
%
\[
\chi_{t_0}\left (h_t\right )=
\chi_{t_0}\left (h_{t-n}\right )\chi_{t_0}\left (
\prod_{{\scriptsize t'-n=t-n}\atop{\scriptsize t'\not =t}}
\frac{\displaystyle x_n-\chi_{t'}(x_n)}{\displaystyle\chi_t(x_n)-\chi_{t'}(x_n)}
\right ).
\]
%
Comme $X_n$ n'intervient pas dans l'expression du polyn\^ome $GZ_{t-n}$, on a 
%
\[
\chi_{t_0}\left (h_{t-n}\right )=\chi_{t_0-n}\left (h_{t-n}\right ).
\]
% 
Par cons\'equent, 
%
\[
\chi_{t_0}\left (h_t\right )=
\chi_{t_0-n}\left (h_{t-n}\right )
\prod_{{\scriptsize t'-n=t-n}\atop{\scriptsize t'\not =t}}
\frac{\displaystyle \chi_{t_0}\left (x_n\right )-
\chi_{t'}(x_n)}{\displaystyle\chi_t(x_n)-\chi_{t'}(x_n)}
.
\]
%
Si $t_0=t$, 
%
$
\chi_t\left (h_t\right )=\chi_{t-n}\left (h_{t-n}\right )=1
$ 
%
par induction. Si $t_0\neq t$ et $t_0-n=t-n$, par construction on a  
%
$
\chi_{t_0}\left (h_t\right )=0.
$ 
%
Si $t_0\neq t$ et $t_0-n\neq t-n$, 
%
$
\chi_{t_0-n}\left (h_{t-n}\right )=0
$ 
%
par induction, et ainsi 
%
$
\chi_{t_0}\left (h_t\right )=0.
$ 
%
\hfill $\Box$

%
\bigskip
\noindent
%

Cette famille v\'erifie une relation dont 
l'importance sera mise en \'evidence lorsque l'on discutera de l'efficacit\'e du 
calcul. 


\begin{proposition}\label{formsom}
%
Les \'el\'ements de la FCIOM $\left (g_t\right )_{t\in\mbox{\scriptsize 
Tab}(n)}$ v\'erifient 
%
\begin{eqnarray}
g_t=\sum_{{t'\in\mbox{\scriptsize Tab}(n+1)}\atop{t'-
(n+1)=t}}g_{t'}.\label{formrec}
\end{eqnarray}
%
%
\end{proposition}

\noindent
{\bf Preuve}\hspace{1mm}  Soit  
%
$
s_t=\sum_{{t'\in\mbox{\scriptsize Tab}(n+1)}\atop{t'-(n+1)=t}}g_{t'}.
$ 
%
D'apr\`es le th\'eor\`eme \ref{gelf}, on a 
%
\begin{eqnarray*}
%
g_ts_t&=&g_t
\sum_{{\scriptsize t'\in\mbox{\scriptsize Tab}(n+1)}\atop{\scriptsize t'-
(n+1)=t}}g_t\prod_{{\scriptsize t"-(n+1)=t'-(n+1)}\atop{\scriptsize t"\not =t'}}
\frac{\displaystyle x_{n+1}-\chi_{t"}(x_{n+1})}{\displaystyle 
\chi_{t'}(x_{n+1})-\chi_{t"}(x_{n+1})}\\
%
&=&\sum_{{\scriptsize t'\in\mbox{\scriptsize Tab}(n+1)}\atop{\scriptsize t'-
(n+1)=t}}g_t\prod_{{\scriptsize t"-(n+1)=t'-(n+1)}\atop{\scriptsize t"\not =t'}}
\frac{\displaystyle x_{n+1}-\chi_{t"}(x_{n+1})}{\displaystyle 
\chi_{t'}(x_{n+1})-\chi_{t"}(x_{n+1})}\\
%
&=&s_t.
%
\end{eqnarray*}
%
De m\^eme, $g_{t'}s_t=0$ si $t'$ est un tableau de poids $n$ distinct de $t$. 
Cependant 
%
\begin{eqnarray}
\sum_{t\in\mbox{\scriptsize Tab}(n)}s_t=\sum_{t\in\mbox{\scriptsize 
Tab}(n+1)}g_t=1
\end{eqnarray}
% 
ce qui prouve que $g_t=s_t$.\hfill $\Box$

%
\bigskip
\noindent
%
Sans \'evaluer, les GZ-polyn\^omes satisfont deux importantes relations. 
%

\begin{proposition}
%
Les GZ-polyn\^omes v\'erifient 

\begin{eqnarray}
%
& &GZ_t=\sum_{{t'\in\mbox{\scriptsize Tab}(n+1)}\atop{t'-
(n+1)=t}}GZ_{t'},\label{rela1}\\
%
& &\sum_{t\in\mbox{\scriptsize Tab}(n)}GZ_t=1.\label{rela2}
%
\end{eqnarray}
%
\end{proposition}

\noindent
{\bf Preuve}\hspace{1mm} La relation (\ref{rela1}) est d\'eduite de la 
d\'efinition r\'ecursive des GZ-polyn\^omes et de la relation formelle 
\[
\sum_{i=1}^{m}\prod_{j\neq i}\frac{\displaystyle X-a_j}{\displaystyle a_i-a_j}=1
\]
qui est vraie pour toute famille $(a_1,a_2,\ldots ,a_m)$ de scalaires distincts. 
La relation (\ref{rela2}) est une application directe de (\ref{rela1}).\hfill 
$\Box$

%
\subsubsection{\'Etude rapide de la complecité du calcul}
%
On constate que les formules des GZ-polyn\^omes  sont moins ``complexes" que les 
formules des polyn\^omes DJ obtenues par l'interpolation de Lagrange. On peut 
fixer deux op\'erations \'el\'ementaires qui sont 
l'addition d'\'el\'ements de la forme $\sigma\in \SG_n$ et le produit d'un 
g\'en\'erateur $\si_i$ et de $\sigma$. Comme $T_{(i,m)}$ (transposition de $i$ et de $m$) 
se d\'ecompose en 
$\si_i\cdots \si_{m-2}\si_{m-1}\si_{m-2}\cdots \si_i$, le produit $x_m\sigma$ 
n\'ecessite au minimum $(m-1)m$ op\'erations \'el\'ementaires. La proposition 
suivante montre que les polyn\^omes $GZ_t$ sont minimaux en la variable $X_n$ 
qui est la plus co\^uteuse en calculs lors de l'\'evaluation en les $q$-
analogues de Jucys-Murphy. On note $\mbox{deg}_i(Q)$ le degr\'e du polyn\^ome 
$Q$ en $X_i$. 

\begin{proposition}\label{effic}
%
Si $Q_t\in k[X_i]_{1<i\leq n}$ v\'erifie    
%
$
Q_t\left (x_2,x_3,\ldots ,x_n\right )=g_t
$  
%
alors 
%
\begin{eqnarray}
\mbox{deg}_n(Q_t)\geq\mbox{deg}_n\left (GZ_t\right ).
\end{eqnarray}
%
De plus, si on a \'egalit\'e,  
%
\begin{eqnarray}
Q_t=\prod_{{t'-n=t-n}\atop {t'\neq t}}\frac{\displaystyle X_n-\chi_{t'}\left 
(x_n\right )}
{\displaystyle\chi_{t}\left (x_n\right )-\chi_{t'}\left (x_n\right )}\times 
Q_{t-n}+R\label{diveuc}
\end{eqnarray}
%
avec 
%
$
Q_{t-n}\in k[X_i]_{1<i\leq n-1}$,  $\mbox{deg}_n (R)<\mbox{deg}_n (Q_t)$ 
%
et 
%
\begin{eqnarray}
R\left (x_2,x_3,\ldots ,x_n\right )g_{t-n}=0.\label{Rgt}
\end{eqnarray} 
%
%
%
\end{proposition}

%
\noindent
%
{\bf Preuve}\hspace{1mm} On peut supposer que 
%
$
Q_t=\sum_{i=0}^{m}X_{n}^{i}Q_i
$ 
%
o\`u $Q_j\in k[X_i]_{1<i\leq n-1}$. Puisque l'\'evaluation de $Q_t$ en les 
\'el\'ements de Jucys-Murphy est $g_t$, on a 
%
\begin{eqnarray*}
%
\delta_{t\,t'}&=&\chi_{t'}\left (Q_t\left (x_2,x_3,\ldots ,x_n\right )\right )\\
&=&\sum_{i=0}^{m}\chi_{t'}^{i}\left (x_n\right )\chi_{t-n}\left (Q_i\left 
(x_2,x_3,\ldots ,x_{n-1}\right )\right )\\
&=&\chi_{t-n}\left (Q_{t}\left (x_2,x_3,\ldots ,x_{n-1},X_n\right )\right )\left 
(\chi_{t'}\left (x_n\right )\right )
%
\end{eqnarray*}
%
ce qui prouve que le polyn\^ome 
$\chi_{t-n}\left (Q_{t}\left (x_2,x_3,\ldots ,x_{n-1},X_n\right )\right )$ est 
un polyn\^ome d'interpolation $L$ correspondant aux \'equations 
%
\begin{eqnarray}
%
L\left (\chi_{t'}\left (x_n\right )\right )&=&\delta_{t\,t'}\label{finter}
%
\end{eqnarray}
%
dont le degr\'e en $X_n$, qui est $m$, est par cons\'equent n\'ecessairement 
sup\'erieur ou \'egal au nombre de tableaux de Young $t'\neq t$ tel que $t'-n=t-
n$ (le polyn\^ome $\chi_{t-n}\left (GZ_t\left (x_2,x_3,\ldots ,x_{n-1},X_n\right 
)\right )$ \'etant le polyn\^ome d'interpolation de Lagrange correspondant aux 
\'equations \ref{finter}). 

Enfin, l'\'egalit\'e \ref{diveuc} est obtenue en effectuant 
la division euclidienne de $Q_t$ par 
$\displaystyle\prod_{{t'-n=t-n}\atop {t'\neq t}}\frac{\displaystyle X_n-
\chi_{t'}\left (x_n\right )}{\displaystyle \chi_{t}\left (x_n\right )-
\chi_{t'}\left (x_n\right )}$ 
%
avec $\mbox{deg}_n(R)<\mbox{deg}_n\left (Q_t\right )$. Le fait que 
$\mbox{deg}_n\left (Q_t\right )=\mbox{deg}_n\left (GZ_t\right )$ montre que 
$Q_{t-n}$ est ind\'ependant de $X_n$, ce qui entra\^ine, par comparaison du 
terme dominant avec le polyn\^ome d'interpolation de Lagrange que 
%
\begin{eqnarray}
\chi_t\left (Q_{t-n}\left (x_2,x_3,\ldots ,x_{n-1}\right )\right )=1.
\label{eqg1}
\end{eqnarray}
%
En effet, si $t'$ est un tableau de Young distinct de $t$ mais tel que $t'-n=t-
n$, on a  
%
\begin{eqnarray*}
%
\chi_{t'}\left (R\left (x_2,x_3,\ldots ,x_{n-1},X_n\right )\right )
\left (\chi_{t'}\left (x_n\right )\right )&=&
\chi_{t'}\left (R\left (x_2,x_3,\ldots ,x_{n-1},x_n\right )\right )\\
&=&\chi_{t'}\left (Q_t\left (x_2,x_3,\ldots ,x_{n-1},x_n\right )\right )\\
&=&0.
%
\end{eqnarray*}
% 
Le polyn\^ome $\chi_{t'}\left (R\left (x_2,x_3,\ldots ,x_{n-1},X_n\right )\right 
)$ est  donc divisible par le polyn\^ome  
%
$
%
\prod_{{\scriptsize t'-n=t-n}\atop{\scriptsize t'\not =t}}
\left (X_n-\chi_{t'}(x_n)\right )
%
$ 
%
et ainsi  
%
\begin{eqnarray}
\chi_{t'}\left (R\left (x_2,x_3,\ldots ,x_{n-1},X_n\right )\right )=0
\end{eqnarray} 
%
vu la condition sur $\mbox{deg}_n(R)$. Comme (toujours pour $t-n=t'-n$) on a 
$\chi_t\equiv\chi_{t'}$ sur 
${\cal JM}^{n-1}_{k}$, on en d\'eduit la relation \ref{eqg1} mais cela  montre 
aussi la relation \ref{Rgt} en vertu des propositions \ref{bij} et 
\ref{formsom}. \hfill $\Box$

%
\bigskip
%
On attire l'attention sur l'efficacit\'e du calcul des idempotents $g_t$ par les 
GZ-polyn\^omes. Ainsi ce calcul  a une meilleure complexit\'e, en consid\'erant 
les op\'erations \'el\'ementaires mentionn\'ees pr\'ec\'edemment, que par les 
formules de {\sc R. Dipper} et {\sc G. James}. Pour tout tableau de 
Young $t$ de poids $n>1$,   
%
\[
\left\{
\begin{array}{ll}
\mbox{deg}_i\left (DJ_t\right )\geq\mbox{deg}_i\left (GZ_t\right )&\mbox{si 
$i=2$,}\\
\mbox{deg}_i\left (DJ_t\right )>\mbox{deg}_i\left (GZ_t\right )&\mbox{si 
$2<i\leq n$.}\\
\end{array}
\right .
\]
%
Si $i=2$, 
%
\[
\mbox{deg}_2\left (DJ_t\right )=
\frac{\displaystyle 1}{\displaystyle 2}\sum_{|\lambda |=n}n_\lambda\geq 
1=\mbox{deg}_2\left (GZ_t\right )
\]
%
avec l'\'egalit\'e quand $n=2$. Si $2<i\leq n$, on note $t_i$ le tableau de 
Young de poids $i$ obtenu en retirant de $t$ les cellules num\'erot\'ees par un 
nombre sup\'erieur \`a $i$. On trouve  
$\mbox{deg}_i\left (DJ_t\right )>\mbox{deg}_i\left (GZ_t\right )$ car 
%
\begin{eqnarray*}
%
\mbox{deg}_i\left (DJ_t\right )&=&\mbox{deg}_i\left (
\prod_{{\scriptstyle t'\in\mbox{\scriptsize Tab}(n)}\atop {\scriptstyle 
\chi_{t'}(i)\neq\chi_t(i)}}\frac{\displaystyle X_i-\chi_{t'}(x_i)}{\displaystyle 
\chi_t(x_i)-\chi_{t'}(x_i)}\right )\\
&=&\mbox{deg}_i\left (
\prod_{{\scriptstyle t'\in\mbox{\scriptsize Tab}(i)}\atop {\scriptstyle 
\chi_{t'}(i)\neq\chi_t(i)}}\frac{\displaystyle X_i-\chi_{t'}(x_i)}{\displaystyle 
\chi_t(x_i)-\chi_{t'}(x_i)}\right )\\
%
\end{eqnarray*}
%
et 
%
\[
%
\mbox{deg}_i\left (GZ_t\right )=\mbox{deg}_i\left (
\prod_{{\scriptstyle t'-i=t_i-i}\atop {\scriptstyle 
t'\neq t_i}}\frac{\displaystyle X_i-\chi_{t'}(x_i)}{\displaystyle \chi_t(x_i)-
\chi_{t'}(x_i)}\right ).
%
\]

\section{Traces}

\section{Liminaire}
Nous utiliserons plus tard le r\'esultat g\'en\'eral suivant~:

\begin{proposition}\label{proCent}
Soit $\mathcal{A}$ et $\mathcal{B}$ deux alg\`ebres semi-simples de dimensions finies. On 
suppose que $\mathcal{A}$ est une sous-alg\`ebre de $\mathcal{B}$ et on d\'enote par $\mathcal{C}$ 
le centralisateur de $\mathcal{A}$ dans $\mathcal{B}$. 

Si $V$ est un $\mathcal{A}$-module irr\'eductible et $W$ un $\mathcal{B}$-module irr\'eductible, alors 
$Hom_{\mathcal{A}}(V,\mbox{Res}_{\mathcal{A}}W)$ est un $\mathcal{C}$-module irr\'eductible.
\end{proposition}

Cette proposition est valide en caract\'eristique quelconque, mais nous ne l'appliquerons qu'au cas de 
deux alg\`ebres semi-simples sur $\mathbb{C}$.   

\section{Bases et alg\`ebres de Gelfand-Tsetlin}
Dans $\mathbb{C}\mathfrak{S}_n$, on d\'efinit pour $k=1,\ldots,n$, le $k^{\mbox{\scriptsize e}}$ \'el\'ement de 
Young-Jucys-Murphy (YJM) par~:
$$L_k := \sum_{1\leq m<k}(m,k),$$
o\`u $(m,k)$ d\'esigne la transposition \'echangeant $m$ et $k$.

\smallskip
\textbf{Exercice}. Les \'el\'ements de YJM commutent.

\smallskip
On d\'enote par $\mathcal{Z}_n$ le centre de $\mathbb{C}\mathfrak{S}_n$, et par $\mathcal{Z}_{m,n}$ le commutant de 
$\mathbb{C}\mathfrak{S}_m$ dans $\mathbb{C}\mathfrak{S}_n$, si $m\leq n$.

\smallskip
\textbf{Exercice}. Les sommes de $\mathfrak{S}_m$-classes de conjugaison dans $\mathfrak{S}_n$ forment un syst\`eme g\'en\'erateur de 
$\mathcal{Z}_{m,n}$.

\begin{proposition}\label{proZmn}
$\mathcal{Z}_{m,n} = \langle S'_m,\mathcal{Z}_n,L_{m+1},\ldots,L_n \rangle$.
\end{proposition}

On est maintenant en mesure de donner la r\`egle de branchement pour la tour d'alg\`ebres 
$$\mathbb{C}\mathfrak{S}_0\subset \mathbb{C}\mathfrak{S}_1 \subset \cdots \subset \mathbb{C}\mathfrak{S}_n\subset\mathbb{C}\mathfrak{S}_{n+1}\subset \cdots$$

\begin{theorem}\label{thmBraRul}
Soit $W$ un $\mathbb{C}\mathfrak{S}_{n+1}$-module irr\'eductible et $V$ un $\mathbb{C}\mathfrak{S}_{n}$-module irr\'eductible. Alors la multiplicit\'e de 
$V$ dans la d\'ecomposition de $\mbox{Res}_{\mathbb{C}\mathfrak{S}_n}W$ en somme directe de modules est 0 ou 1.
\end{theorem}

\textbf{D\'emonstration}. Soit $W$ un $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible. Il d\'ecoule de la proposition \ref{proZmn} que 
le centralisateur de $\mathbb{C}\mathfrak{S}_n$ dans $\mathbb{C}\mathfrak{S}_{n+1}$ est commutatif. Tous ses modules irr\'eductibles non triviaux 
sont donc de dimension 1. La proposition \ref{proCent} entra\^{\i}ne donc que la dimension de  
$Hom_{\mathbb{C}\mathfrak{S}_m}(W,\mbox{Res}_{\mathbb{C}\mathfrak{S}_n}V)$ est 0 ou 1.\hfill $\Box$

Il reste maintenant \`a d\'ecrire le graphe de branchement, d\'esign\'e (temporairement) par $\mathbb{B}$. On va d\'emontrer qu'il s'agit 
en r\'ealit\'e du graphe de Young $\mathbb{Y}$, 
c'est-\`a-dire du diagramme de Hasse du treillis des partitions (ou diagrammes de Young) ordonn\'ees par inclusion. 

\medskip
Soit $V$ un $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible. Soit $\langle\cdot,\cdot\rangle$ le produit int\'erieur $\mathfrak{S}_n$-invariant sur 
$V$ (ce produit est unique \`a un scalaire pr\`es). Le th\'eor\`eme \ref{thmBraRul} implique que la d\'ecomposition 
$$\mbox{Res}_{\mathbb{C}\mathfrak{S}_{n-1}}V = \bigoplus_{W\rightarrow V} W$$
(on somme sur tous les $\mathbb{C}\mathfrak{S}_n$-modules pour lesquels il existe un arc de $W$ vers $V$ dans le graphe de branchement) est 
canonique. En it\'erant le processus jusqu'\`a $\mathfrak{S}_0$, on obtient une d\'ecomposition canonique  
$$\mbox{Res}_{\mathbb{C}S_{0}}V = \bigoplus_{T} V_T$$
en sous-espaces de dimension 1 $V_T$, o\`u $T$ d\'ecrit l'ensemble des chemins $W_0 \rightarrow \cdots\rightarrow W_n=V$ dans le 
graphe de branchement. 

\smallskip
\textbf{Exercice}. $\mathbb{C}S_k\cdot V_T=W_k$, pour tout $k$, $0\leq k \leq n$. 

\smallskip
En choisissant un vecteur $v_T$ dans chaque $V_T$, on obtient une base $\{v_T\}$ appel\'ee {\em base de Gelfand-Tsetlin} 
(en abr\'eg\'e, base de GZ). Cette base est d\'etermin\'ee de fa\c{c}on unique (\`a des scalaires pr\`es). En outre, si $\varphi : V\rightarrow W$ 
est un isomorphisme de modules irr\'eductibles, alors $\varphi$ envoie une base de GZ sur une base de GZ. 

\smallskip
\textbf{Exercice}. Toute base de GZ est orthogonale pour le produit int\'erieur $\langle\cdot,\cdot\rangle$.

\smallskip
D'apr\`es le th\'eor\`eme de Wedderburn, $\mathbb{C}\mathfrak{S}_n$ se d\'ecompose en 
\begin{equation}
\mathbb{C}\mathfrak{S}_n = \bigoplus_V \mbox{End}_{\mathbb{C}}(V) \label{eqDecCSn}
\end{equation}
(on somme sur les classes d'\'equivalence de $\mathbb{C}\mathfrak{S}_n$-modules irr\'eductibles). Cette d\'ecomposition est canonique. Si on choisit 
une base de GZ dans chaque $V$. Relativement \`a ces bases, on a naturellement
\begin{equation}
\mathbb{C}\mathfrak{S}_n = \bigoplus_V M_{\mbox{\scriptsize{dim}}V}(\mathbb{C})  \label{eqDecCSnMat}.
\end{equation}

On d\'efinit la (sous-)alg\`ebre de Gelfand-Tsetlin $\mathcal{GZ}(n) \subset \mathbb{C}\mathfrak{S}_n$ constitu\'ee de tous les \'el\'ements de $\mathbb{C}\mathfrak{S}_n$ 
qui sont diagonaux pour toute base de GZ dans chaque $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible. Dans les termes de la d\'ecomposition \ref{eqDecCSnMat}, 
$\mathcal{GZ}(n)$ est constitu\'ee de toutes les matrices diagonales. On en d\'eduit~:

\begin{proposition}
$\mathcal{GZ}(n)$ est une sous-alg\`ebre commutative maximale de $\mathbb{C}\mathfrak{S}_n$. C'est \'egalement une alg\`ebre semi-simple.
\end{proposition}

\begin{proposition}
(i)~$\mathcal{GZ}(n) = \langle \mathcal{Z}_0,\mathcal{Z}_1,\ldots,\mathcal{Z}_n\rangle$~; 
(ii)~$\mathcal{GZ}(n) = \langle \mathcal{L}_1,\mathcal{L}_2,\ldots,\mathcal{L}_n\rangle$.
\end{proposition}

\textbf{D\'emonstration}. (i) Soit $e_V\in\mathcal{Z}_n$ l'idempotent central associ\'e au $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible $V$~; il agit comme l'identit\'e sur $V$, 
et comme 0 sur tout $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible non isomorphe \`a $V$ (relativement \`a la d\'ecomposition \ref{eqDecCSn}, $e_V$ est l'endomorphisme identit\'e 
sur la composante $V$ et l'endomorphisme nul sur les autres composantes). Si $T$ est un chemin $W_0\rightarrow W_1\rightarrow\cdots\rightarrow W_n=V$ dans 
$\mathbb{B}$, alors
$$e_{W_0}e_{W_1}\cdots e_{W_n} \in \mathcal{Z}_0\mathcal{Z}_1\cdots\mathcal{Z}_n$$
agit sur $V$ comme la projection sur $V_T$ suivant $\bigoplus_{S\neq T}$ et sur tout $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible $V'\not\cong V$, comme 0. La sous-alg\`ebre 
engendr\'ee par les centres $\mathcal{Z}_0,\mathcal{Z}_1,\ldots,\mathcal{Z}_n$ contient donc $\mathcal{GZ}(n)$. Or 
$\langle \mathcal{Z}_0,\mathcal{Z}_1,\ldots,\mathcal{Z}_n\rangle$ est commutative et $\mathcal{GZ}(n)$ est une sous-alg\`ebre commutative maximale de $\mathbb{C}\mathfrak{S}_n$, 
donc les deux sous-alg\`ebres co\"{\i}ncident. \\
(ii) \hfill $\Box$

On va maintenant faire jouer \`a $\mathcal{GZ}(n)$ le r\^ole d'une sous-alg\`ebre de Cartan. Comme $\mathcal{GZ}(n)$ est semi-simple, on peut d\'ecomposer 
tout $\mathbb{C}\mathfrak{S}_n$-module irr\'eductible $V$ en une somme directe d'espaces (simultan\'ement) propres pour les \'el\'ements de YJM $L_1,\ldots,L_n$. Si 
$\lambda=(\lambda_1,\ldots,\lambda_n)\in \mathbb{C}^n$ et si $V_{\lambda}$ d\'esigne l'espace (simultan\'ement) propre pour les $L_1,\ldots,L_n$ 
correspondant aux valeurs prores $\lambda_1,\ldots,\lambda_n$, alors on dit que $\lambda$ est un poids de $V$ et que $V_{\lambda}$ est l'epace de 
poids $\lambda$.

\medskip
Les vecteurs d'une base de GZ sont des poids (par d\'efinition). D'autre part, d'apr\`es la d\'ecomposition \ref{eqDecCSnMat}, $\mathcal{GZ}(n)$ est constitu\'ee de
toutes les matrices diagonales, donc les espaces de poids sont de dimension 1~; ce sont donc exactement les droites engendr\'ees par les \'el\'ements d'une base de 
GZ. On remarque aussi que si $\lambda$ est un poids d'un module irr\'eductible $V$, ce ne peut \^etre le poids d'aucun module irr\'eductible non isomorphe \`a $V$. On 
obtient ainsi, \`a travers les bases de Gelfand-Tsetlin, une bijection entre les poids (pour tous les groupes sym\'etriques) et tous les chemins d\'emarrant \`a la racine 
dans le graphe de branchement. On d\'esigne par $\lambda_T$ le poids associ\'e au chemin $T$ et par $T_{\lambda}$ un chemin associ\'e au poids $\lambda$~; on abr\`ege 
$v_{T_{\lambda}}$ en $v_{\lambda}$.

Un chemin $T$ se termine au sommet $V$ ssi le poids associ\'e $\lambda_T$ est un poids de $V$. Il est maintenant \'evident que pour d\'ecrire le graphe de branchement 
$\mathbb{B}$, il suffit de d\'ecrire les ensembles 
$$W(n) = \{\lambda\in\mathbb{C}^n \mid \lambda \mbox{ est un poids d'un }\mathbb{C}\mathfrak{S}_n\mbox{-module}\} \;\; (n\geq 0)$$
et la relation d'\'equivalence sur 
$$\lambda\approx\mu \Leftrightarrow \lambda \mbox{ et }\mu\mbox{ sont des poids du m\^eme }\mathbb{C}\mathfrak{S}_n\mbox{-module irr\'eductible}$$
En effet, on remarque que 
$$\mathbb{B} = \bigcup_{n\geq 0}(W(n)\slash\approx)$$
et que, pour toutes toutes $[\lambda]$ et $[\mu]$, respectivement classes d'\'equivalence de $\lambda\in W(n-1)$ et de $\mu\in W(n)$, on a 
$[\lambda]\rightarrow [\mu]$ dans $\mathbb{B}$ ssi il existe un poids $\nu=(nu_1,\ldots,nu_n)$ tel que $\nu\approx\mu$ et 
$\lambda=(\lambda_1,\ldots,\lambda_{n-1})$.

\smallskip
Anticipons un peu sur la suite~: les \'el\'ements de $W(n)\slash\approx)$ seront \'etiquet\'es par les partitions $\alpha\vdash n$ et ceux de $W(n)$ par les 
tableaux standard de forme $\alpha$~; deux tableaux seront \'equivalents ssi ils ont la m\^eme forme. Plus pr\'ecis\'ement, si $T$ est un tableau standard de 
forme $\alpha$, le poids associ\'e $\lambda$ peut \^etre reconstruit de la fa\c{c}on suivante~: $\lambda_i$ est le {\em contenu} de la case de $\alpha$ o\`u appara\^{\i}t 
$i$.

\section{Description des poids}
\subsection{Modules de l'alg\`ebre de Hecke affine d\'eg\'en\'er\'ee $\mathcal{H}_2$}
En notant $s_i$ la transposition \'el\'ementaire \'echangeant $i$ et $i+1$, on a les relations~:
$$s_iLi_i= L_{i+1}s_i-1, \;\; s_iL_j=L_js_i \;(j\neq i,i+1)$$
De la deuxi\`eme relation, on tire
\begin{proposition}
Soit $\lambda=(\lambda_1,\ldots,\lambda_n)\in W(n)$, et $1\leq k<n$. Alors $s_kv_{\lambda}$ est une combinaison lin\'eaire de vecteurs 
$v_{\mu}$ tels que $\mu_i=\lambda_i$ pour $i\neq k,k+1$.
\end{proposition}

Le r\^ole de $sl_2$ est jou\'e par les $\mathcal{B}_i:=\langle L_i,L_{i+1},s_i\rangle$. Chaque $\mathcal{B}_i$ est un quotient de l'alg\`ebre
$$\mathcal{h}_2 =\langle s,x,y \mid xy=yx, s^2=1, sx=ys-1\rangle.$$

\begin{proposition}
[... description des irreps de $\mathcal{h}_2$ ...].
\end{proposition}

\begin{corollary}
Soit 
\end{corollary}

De ce qui pr\'ec\`edeon tire~:

\begin{proposition}\label{proWn}
Soit $\lambda\in W(n)$. Alors~: \\
(i) $\lambda_1=0$~;\\
(ii) $\{lambda_i -1,\lambda_i+1\}\cap\{\lambda_1,\ldots,\lambda_{i-1}\}\neq\emptyset$ pour tout $i$, $2\leq i\leq n$~;\\
(iii) Si $\lambda_i=\lambda_j=a$ pour un certain couple $i<j$, alors 
$$\{a_1,a+1\}\subset\{\lambda_{i+1},\ldots,\lambda_{j-1}\}.$$
\end{proposition}

\subsection{Le graphe de Young est le graphe de branchement}

On rappelle que le graphe de Young $\mathbb{Y}$ est le graphe gradu\'e dont l'ensemble des sommets est l'ensemble $\mathcal{P}$ des partitions (repr\'esent\'ees par leur 
diagramme de Young), et dont les arcs relient tout diagramme de Young \`a ceux qui sont obtenus en ajoutant une case. La composante de rang $n$ du graphe 
est donc l'ensemble $\mathcal{P}(n)$ des partitions de poids $n$ (en particulier, la composante de rand 0 est constitu\'ee de l'unique diagramme vide $\emptyset$). 
Les chemins de $\emptyset$ \`a un sommet $\alpha$ dans $\mathbb{Y}$ sont en bijection avec les tableaux standard de forme $\alpha$. \`A tout tableau standard $T$ 
de forme $alpha$, correspondant au chemin $\emptyset=T_0,T_1,\ldots,T_n=\alpha$, on associe le vecteur de contenu cont($T$), aussi not\'e $\lambda_T$, d\'efini par
$$\lambda_T=(\mbox{cont}(T_1),\ldots,\mbox{cont}(T_n)) \in \mathbb{Z}^n$$
o\`u $\mbox{cont}(T_i)$ d\'esigne le contenu ({\em i.e.} le n$^{\mbox{\scriptsize o}}$ de la diagonale) de la case ajout\'ee \`a $T_{i-1}$ pour obtenir $T_i$.

\medskip
On pose $W'(n) := \{\lambda_T \mid T \mbox{ est un tableau standard dont la forme }\in\mathcal{P}(n)\}$. Il est facile de retrouver la forme $\alpha$ 
\`a partir du vecteur $\lambda_T$~: le nombre de cases dans la diagonale de n$^{\mbox{\scriptsize o}}$ $a$ du diagramme de Young $\alpha$ est le nombre de composantes de $\lambda_T$ 
\'egales \`a $a$. Ainsi deux $n$-uplets $\lambda,\mu\in W'(n)$ proviennent de tableaux de m\^eme forme ssi l'un est image de l'autre par une permutation, ce qu'on note 
$\lambda\sim \mu$.

\begin{lemma}
L'ensemble $W'(n)$ est exactement l'ensemble de tous les $n$-uplets $\lambda\in\mathbb{C}^n$ qui satisfont les propri\'et\'es (i)--(iii) de la proposition 
\ref{proWn}. On en d\'eduit $W(n)\subset W'(n)$.
\end{lemma}

Soit $\nu=(\nu_1,\ldots,\nu_n)\in\mathbb{C}^n$. Une {\em transposition admissible} pour $\nu$ est une transposition \'el\'ementaire $s_i\in \mathfrak{S}_n$ correspondant 
\`a un couple $\nu_i,\nu_{i+1}$ tel que $|\nu_i -\nu_{i+1}|\neq 1$. Si $\nu=\lambda_T$, une transposition admissible \'echange $i$ et $i+1$ s'ils ne se trouvent 
pas dans des diagonales adjacentes du tableau $T$. Naturellement, une transposition admissible tranforme un tableau standard en un tableau standard de m\^eme forme.

\smallskip
Soit $\alpha=(\alpha_1\geq\cdots\geq\alpha_k>0)\in\mathcal{P}(n)$. Le tableau canonique de forme $\alpha$, not\'e $T(\alpha)$, est obtenu en remplissant chaque 
ligne de gauche \`a droite, en commen\c{c}ant par la premi\`ere ligne.

\begin{lemma}
Soit $\alpha\in\mathcal{P}(n)$. Si $T$ est un tableau standard de forme $\alpha$, alors il existe une suite de transpositions admissibles qui transforme $T$ en 
$T(\alpha)$. En outre, on peut choisir les transpositions admissibles $s_{i_1},\ldots,s_{i_{\ell}}$ de telle sorte que $\ell=\ell(s_{i_1}\cdots s_{i_{\ell}})$.
\end{lemma}

\begin{lemma}
Si $\lambda\in W'(n)$ et s'il existe $\mu\in W(n)$ tel que $\lambda\sim \mu$, alors $\lambda\in W(n)$ et $\lambda\approx\mu$.
\end{lemma}

On touche enfin au but~:

\begin{theorem}
$W(n)=W'(n)$. En outre, $\lambda_T\approx\lambda_S$ $\Leftrightarrow$ les tableaux $T$ et $S$ on la m\^eme forme $\Leftrightarrow$ $\lambda_T\sim\lambda_S$. 
On en conclut que le graphe de branchement $\mathbb{B}$ est isomorphe au graphe de Young $\mathbb{Y}$.
\end{theorem}

\section{Formules de Murnaghan-Nakayama}

\newpage
\section{Annexe A: Automates}

\subsection{Description de la structure d'automate}

\subsubsection{Graphe pond\'er\'e}
L'\'el\'ement de base de ces graphes est la fl\^eche $A=q_1\stackrel{a|\al}{\ra} q_2$ avec 
$q_i\in Q,\ a\in \S,\ \al\in k$ o\`u $Q$ est un ensemble d'\'etats, $\S$ un alphabet et $k$, 
un semi-anneau\footnote{Nous verrons plus bas que les axiomes de la structure de semi-anneau 
sont contraints par la d\'efinition m\^eme du syst\`eme de transitions ainsi obtenu.}. 
Pour un tel objet, on d\'efinit, selon les conventions g\'en\'erales de la th\'eorie des graphes,
\begin{itemize}
\item $t(A):=q_1$ (``tail'': queue, source, origine) 
\item $h(A):=q_2$ (``head'' t\^ete, but, extr\'emit\'e)
\item $l(A):=a$ (``label'' \'etiquette)
\item $w(A):=\al$ (``weight'' poids).
\end{itemize}
Un {\it chemin} est une suite d'ar\^etes $c=A_1A_2\cdots A_n$ (c'est un mot en les ar\^etes et sa 
longueur est $n$) telle que $h(A_k)=t(A_{k+1})$ pour $1\leq k\leq n-1$
pour un tel chemin $t(c)=t(A_1),\ h(c)=h(A_n)$, $l(c)=l(A_1)l(A_2)\cdots l(A_n)$ (concat\'enation),
 $w(c)=w(A_1)w(A_2) \cdots w(A_n)$ (produit dans le semi-anneau). \\
Par exemple pour le chemin de longueur 3 suivant ($k=\N$), 
\begin{equation}
u=p\stackrel{a|2}{\ra} q \stackrel{b|3}{\ra} r \stackrel{c|5}{\ra} s
\end{equation}
on a $t(u)=p,\ h(u)=s,\ l(u)=abc,\ h(u)=30$.

\ss
Le poids d'un ensemble de chemins de m\^eme source, but et \'etiquette est la somme des poids 
des chemins  de cet ensemble. Ainsi, si 

\begin{equation}
 {\mathbf q1}\mhs {\stackrel{u|\al}{\ra}  \atop \stackrel{u|\be}{\ra}}\mhs {\mathbf q2}
\end{equation}

le poids de cet ensemble de chemins est $\al+\be$. On a donc que les poids se multiplient en s\'erie et 
s'aditionnent en parall\`ele. Les diagrammes suivants montrent la n\'ecessit\'e des axiomes de 
semi-anneau.

\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Diagramme 	& Identit\'e 	& Nom \\
\hline
\hline
$\ \ \ \stackrel{a|\al}{\ra}$ &&\\
$p  \stackrel{a|\be}{\ra} q$ & $\al+(\be+\ga)=(\al+\be)+\ga$ & Associativit\'e de $+$\\
$\ \ \ \stackrel{a|\ga}{\ra}$ &&\\
\hline
$p {\stackrel{a|\al}{\ra} \atop \stackrel{a|\be}{\ra}} q$ & $\al+\be=\be+\al$ & Commutativit\'e de $+$\\
\hline
$p {\stackrel{a|\al}{\ra} \atop \stackrel{a| 0}{\ra}} q$ & $\al+0=\al$ & \'El\'ement neutre (droite) de $+$\\
$p\stackrel{a|0}{\ } q \stackrel{b|\be}{\ra } r$ & $0+\be=\al$ & \'El\'ement neutre (gauche) de $+$\\
\hline
$p\stackrel{a|\al}{\ra} q \stackrel{b|\be}{\ra} r \stackrel{c|\ga}{\ra} s$ &
$\al(\be\ga)=(\al\be)\ga$ & Associativit\'e de $\times$\\
\hline
$p {\stackrel{a|\al}{\ra} \atop \stackrel{a|\be}{\ra}} q \stackrel{b|\ga}{\ra} r$ & $(\al+\be)\ga=\al\ga+\be\ga$ &
Distributivit\'e (droite) de $\times$ sur $+$\\
\hline
$p\stackrel{a|\al}{\ra} q {\stackrel{b|\be}{\ra} \atop \stackrel{b|\ga}{\ra}} r $ & $\al(\be+\ga)=\al\be+\al\ga$ &
Distributivit\'e (gauche) de $\times$ sur $+$\\
\hline
$p\stackrel{a|\al}{\ra} q \stackrel{b| 1_k}{\ra} r $ & $\al\times 1_k=\al$ & \'El\'ement neutre (droite) de $\times$\\
$p\stackrel{a|1_k}{\ra} q \stackrel{b|\be}{\ra} r $ & $1_k\times \be=\be$ & \'El\'ement neutre (gauche) de 
$\times$\\
\hline
\end{tabular}
\end{center}

\subsubsection{Structure et comportement des automates}

Un automate \`a poids ou pond\'er\'e (``automaton with weights'') est la donn\'ee de trois \'el\'ements 
vectoriels $(I,M,T)$:

\ss
$
\left\{ \
\begin{array}{ll}
\bullet & {\rm Un\ vecteur\ d'entr\acute ee\ } I\in k^{1\times Q}\\
\bullet & {\rm Une\ famille\ (index\acute ee\ \grave a\ A) \ de\ matrices\ de\ transition\ } M : 
A\rightarrow k^{Q\times Q}\\
\bullet & {\rm Un\ vecteur\ de\ sortie\ } T\in k^{Q\times 1}\\
\end{array}
\right. \ 
$

\ss
La donn\'ee des transitions ($M$) est \'equivalente \`a celle d'un graphe pond\'er\'e dont les sommets sont 
$Q$, l'alphabet $A$ et les poids sont pris dans $k$. De plus celle de $I$ (resp. $T$) correspond \`a la donn\'ee 
de fl\^eches rentrantes (resp. sortantes) marqu\'ees avec des poids. Dans tout ce processus, on peut ne 
pas indiquer les fl\^eches de poids nul.\\
Ce type d'automates g\'en\'eralise les automates (bool\'eens) de la th\'eorie des langages (que l'on obtient 
alors pour $k=\B$) est une machine qui prend un mot en entr\'ee et retourne un coefficient (dans $k$)  en 
sortie. Son comportement est donc une fonction ${\cal A}:\ A^*\ra k$ (que l'on peut noter, de mani\`ere 
\'equivalente, comme une s\'erie ${\cal A}=\sum_{w\in A^*}{\cal A}(w) w$).

\ss
{\bf Calcul du poids ${\cal A}(w)$}\pointir

\ss
On \'etend d'abord la fonction de transition $M$ \`a $A^*$ par 
\begin{equation}
M(\ep)=I_{Q\times Q},\ M(w)=M(a_1a_2\cdots a_n)=M(a_1)M(a_2\cdots M(a_n)
\end{equation}
o\`u $I_{Q\times Q}$ est la matrice identit\'e de format $Q\times Q$. Le calcul du poids d'un mot est 
alors, par d\'efinition,
\begin{equation}
{\cal A}(w) :=IM(w)T
\end{equation}
d'apr\`es la r\`egle de multiplication des matrices, on a bien que $IM(w)T$ est une matrice de format 
$1\times 1$ et donc un \'el\'ement de $k$. Le lien avec le graphe de l'automate est donn\'e par la 
proposition suivante : 
\begin{proposition}
Soit, pour deux \'etats $r,s$ et un mot $w\in A^*$
\begin{equation}\label{pchem}
{\cal A}^{r,s}(w):=I_r \left( \sum_{ \stackrel{ c,\ {\rm chemin}\ l(c)=w }{\overline{t(c)=r,\ h(c)=s}}  } weight(c) \right) 
 T_s
\end{equation}
alors 
\begin{equation}
{\cal A}(w)= \sum_{r,s\in Q}{\cal A}^{r,s}(w)
\end{equation}
\end{proposition}

Cette proposition a le sens intuitif suivant : \\
\begin{enumerate}
\item l'\'equation \mref{pchem} donne le poids calcul\'e comme au paragraphe pr\'ec\'edent 
\begin{itemize}
\item on fait le bilan parall\`ele (c'est \`a dire une somme) des poids des chemins qui joingnent $r$ \`a $s$
\end{itemize}
\item on multiplie (\`a gauche si c'est non commutatif) par le poids d'entr\'ee en $r$
\item on multiplie (\`a droite si c'est non commutatif) par le poids de sortie en $s$
\end{enumerate}

\subsubsection{Exemples de fonctions produites par des automates}

\begin{enumerate}
\item Longueur totale $\sum_{w\in A^*}|w|w$
\item Comptage des $a$, $\sum_{w\in A^*}|w|_a w$ et des $b$, $\sum_{w\in A^*}|w|_bw$
\item Produit des degr\'es partiels $\sum_{w\in A^*}|w|_a|w|_bw$
\item Autres produits $\sum_{w\in A^*}F_{|w|}|w|w$, $\sum_{w\in A^*}F_{|w|_a}|w|_bw$
\end{enumerate}

\subsection{Which rational calculus ?}

If $Q$ is a finite set, the space $k^{Q\times Q}$
 of square matrices with indices in $Q$ and coefficients in $k$ has a natural  semiring
structure  with  the usual operations (sum and  product). A
(right) star of $M\in k^{Q\times Q}$  (when it exists) is a solution of
the equation $MY + 1_{Q\times Q} = Y$ (where $ 1_{Q\times Q}$ is the
identity matrix).
Let $M\in k^{Q\times Q}$ be given by
\[M =\left (
\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{array} \right )
\]
where $a_{11}\in k^{Q_1\times Q_1}$,  $a_{12}\in k^{Q_1\times Q_2}$,
$a_{21}\in k^{Q_2\times Q_1}$ and $a_{22}\in k^{Q_2\times Q_2}$ such that
 $Q_1+Q_2=Q$.
Let $N\in k^{Q\times Q}$ given by
\[
N=\left (
\begin{array}{cc}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{array}
\right )
\]
with
\begin{align}
A_{11}&=   (a_{11}+ a_{12}{a_{22}}^{\ast}a_{21})^{\ast}\label{form1}\\
A_{12}&=  {a_{11}}^{\ast}a_{12}A_{22}\label{form2}\\
A_{21}&=  {a_{22}}^{\ast}a_{21}A_{11}\label{form3}\\
A_{22}&=  (a_{22}+ a_{21}{a_{11}}^{\ast}a_{12})^{\ast}\label{form4}
\end{align}

\begin{theorem}\label{t1}
If the right hand sides of formulas (\ref{form1}), (\ref{form2}), (\ref{form3})
and (\ref{form4}) are defined,  the matrix $M$ admits $N$  as a right star.
\end{theorem}

\bigskip
\noindent
{\bf Proof. }\hspace{1mm} Suppose, without loss of generality, that $Q=[1,n]_\N;\ n=p+q;\ Q_1=[1,p]_\N;\ Q_2=[p+1,p+q]_\N$. 
We have to show that $N$ is a solution of the equation
$My+1_{n\times n}=y$. By computation, one has
\begin{align*}
MN+1&=
\left (
\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{array} \right )
\left (
\begin{array}{cc}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{array} \right )+
\left (
\begin{array}{cc}
1_{p\times p} & 0_{p\times q} \\
0_{q\times p} & 1_{q\times q} \\
\end{array} \right )\\
\\
&=\left (
\begin{array}{ll}
a_{11}A_{11}+a_{12}A_{21}+1_{p\times p} & a_{11}A_{12}+a_{12}A_{22} \\
a_{21}A_{11}+a_{22}A_{21}   & a_{21}A_{12}+a_{22}A_{22}+1_{q\times q} \\
\end{array} \right )\\
\end{align*}
where $0_{p\times q}$ is the zero matrix in $k^{p\times q}$.
We verify the relations (\ref{form1}), (\ref{form2}), (\ref{form3})
and (\ref{form4}) by:
\begin{eqnarray*}
  a_{11}A_{11}+a_{12}A_{21}+1_{p\times p}& = &
a_{11}A_{11}+a_{12}a_{22}^{\ast}a_{21}A_{11}+1_{p\times p}=\\
 A_{11}(a_{11}+a_{12}{a_{22}}^{\ast}a_{21})+1_{p\times p} &=& A_{11}
\end{eqnarray*}
\begin{eqnarray*}
 a_{11}A_{12}+a_{12}A_{22} & =& a_{11}{a_{11}}^{\ast}a_{12}A_{22}+a_{12}
A_{22}=\\
(a_{11}{a_{11}}^{\ast}+1)a_{12}A_{22}&=& {a_{11}}^{\ast}a_{12}A_{22}=A_{12}
\end{eqnarray*}
\begin{eqnarray*}
a_{21}A_{11}+a_{22}A_{21}    & =&a_{21}A_{11}+a_{22}{a_{22}}^{\ast}a_{21}A_{11}=\\
(1+a_{22}{a_{22}}^{\ast})a_{21}A_{11}&=&{a_{22}}^{\ast}a_{21}A_{11}=A_{21}
\end{eqnarray*}
\begin{eqnarray*}
a_{21}A_{12}+a_{22}A_{22}+1_{q\times q}&=&a_{21}{a_{11}}^{\ast}a_{12}A_{22}
+a_{22}A_{22}+1_{q\times q}=\\
(a_{22}a_{21}{a_{11}}^{\ast}a{12})A_{22}+1_{q\times q}&=&A_{22}
\end{eqnarray*}
\mbox{ }\hfill$\square$

\bigskip
\noindent
\begin{remark}
i) In \cite{HY} and \cite{RR}, similar formulas are expressed for the computation
of the inverse of matrices when $k$ is a division ring (this can be extended
to the case of rings).\\
It must be emphasized that the converse of Theorem \mref{t1}, of course, does not hold as shows the example below 
(the coefficients are taken in a ring and here the star is unique). 
\begin{equation}
M=\begin{pmatrix} 1 & -1\cr 1 & -1 \end{pmatrix}\ \  M^*=\begin{pmatrix} 2 & -1\cr 1 & 0 \end{pmatrix}
\end{equation} 
However, if the formulas are defined at each step of the computation (see below for a formalization of this), it provides 
a recursive way to compute a star of a matrix.\\ 
ii) Similar formulas can be stated in the case of a left star. The matrix
$N$
is the left star of $M$ with
\begin{align}\label{blockstar}
A_{11}  &  =   (a_{11}+ a_{12}{a_{22}}^{\ast}a_{21})^{\ast}\cr
A_{12}  &  =  A_{11} a_{12}{a_{22}}^{\ast}\cr
A_{21}  &  =  A_{22}a_{21}{a_{11}}^{\ast}\cr
A_{22}  &  =  (a_{22}+ a_{21}{a_{11}}^{\ast}a_{12})^{\ast}
\end{align}
iii) When all their terms are defined, formulas above (as well as 
(\ref{form1}), (\ref{form2}), (\ref{form3}) and (\ref{form4}))
 are valid with matrices of any size with
any block partitionning. Matrices of even size are often, in practice, partitionned into
 square blocks but, for matrices with odd dimensions, the approach called
dynamic peeling  is applied. More specifically, let $ M\in
k^{n\times n}$ a matrix given by
\[M =\left (
\begin{array}{cc}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{array} \right )
\]
where $n\in 2\mathbb N +1$. The dynamic peeling \cite{HJJTT}
consists of cutting out the matrix in the following way:
 $a_{11}$ is a $(n-1)\times (n-1)$ matrix,
 $a_{12}$ is a $(n-1)\times 1$ matrix,
 $a_{21}$ is a $1\times (n-1)$ matrix and
 $a_{22}$ is a  scalar.
\end{remark}

%\input{schur_mmi2.tex}

\newpage
\begin{thebibliography}{99}
\subsection*{Références générales.}
%
\bibitem{A} {\sc E. Abe} Hopf algebras. Cambridge (1980).
%
\bibitem{BR} {\sc Berstel J. and Reutenauer C.}, {\it Rational series and their 
languages}, EATCS, 1988.
%
\bibitem{B-AlgIII} {\sc Bourbaki N.}, Alg\`ebre Ch. III. Hermann (1970) 
%
\bibitem{C} {\sc Cohen H.}, {\it A Course in Computational Algebraic Number 
Theory}. Springer (1993)
%
\bibitem{Ca} {\sc Cayley A.}, On certain results related to quaternions. 
Phil. Mag. {\bf 26}, 141-145 (1845).
%
\bibitem{CR}
\textsc{\sc Curtis C. W., Reiner I.}, 
\emph {Methods of representation theory.} 
Wiley Interscience, (1990). 
%
\bibitem{Da} {\sc Davenport J., Siret Y., Tournier E.}, {\it Calcul formel}, 
Masson (1986)
%
\bibitem{De} {\sc Demazure Michel}, Cours d'alg\`ebre : Divisibilit\'e, Primalit\'e, 
codes. Cassini (1997).
%
\bibitem{Ei} {\sc Eilenberg S.}, Automata, languages and machines, Acad. Press (1974).
%
\bibitem{GG} {\sc von zur Gathen J. and Gerahrd J.} Modern Computer Algebra. 
Cambridge (1999).
%
\bibitem{HY}
{\sc Heyting A.},
``Die Theorie der Linearen Gleichungen in einer Zahlenspezies mit
nichtkommutativer Multiplikation''.
{\it Math. Ann.} {\bf 98} (1927) 465-490.
%
\bibitem{FH}{{\sc W. Fulton} et {\sc J. Harris}, {\em Representation theory: a 
first course}, \rm Springer-Verlag, New-York, 1991.}
%
\bibitem{NQ}{\sc Naudin P., Quitt\'e C.}, {\it Algorithmique Alg\'ebrique} 
Masson (1992)
%
\bibitem{RR} \textsc{Richardson A. R.}, {\it Simultaneous Linear equations over a division ring}.
{\it Proc. Lond. Math. Soc.} {\bf 28} (1928) 395-420.
%
\bibitem{K1} \textsc{Knuth D.}, {\it The art of computer programming}, Tome I \& II.
Addison-Wesley (1981)
%
\bibitem{St} \textsc{Stanley R.}, {\it Enumerative Combinatorics Vol I and II}, Cambridge. 
%

\subsection*{Références spécialisées.}
\subsubsection*{Automates./Informatique.}
%
\bibitem{DC} \textsc{Champarnaud J.-M., Duchamp G.} :{\it 
Derivatives of rational expressions\\ and related theorems}, T.C.S. {\bf 313} 31 (2004).
%
\bibitem{D21} \textsc{Duchamp G., Reutenauer C.}, {\it Un crit\`ere de rationalit\'e 
provenant de la g\'eom\'etrie noncommutative} Invent. Math. {\bf 128} 613-622.
(1997).
%
\bibitem{DHKL} \textsc{Duchamp G., Hadj Kacem H. and Laugerotte E.}, 
{\it Algebraic elimination of $\epsilon$-transitions}, DMTCS, Volume 7 n° 1 (2005), pp. 51-70
%
\bibitem{Ei} {\sc Eilenberg S.}, Automata, languages and machines, Acad. Press (1974).
%
\bibitem{La} {\sc Laugerotte \'E.}, {\it Combinatoire et Calcul symbolique en Th\'eorie des 
Repr\'esentations}, Thèse de l'Université de Rouen (6 novembre 1997).  
%
\bibitem{Fl} \textsc{\sc Flouret M.}, 
\emph{Contribution à l'Algorithmique Noncommutative}, Thèse de l'Université de Rouen (19 janvier 1999).
%
\bibitem{FL} \textsc{\sc Flouret M., Laugerotte \'E.}, 
\emph{Noncommutative minimization algorithms.} 
Information Processing Letters {\bf 64}, 123-126 (1997).
%
\bibitem{HHK} \textsc{Hatem Hadj-Kacem}, 
{\it Contribution \`a la th\'eorie et aux applications des automates 
\`a multiplicit\'es}, Thèse de l'Université de Rouen (17/06/2005).
%
\bibitem{JGL} \textsc{Luque Jean-Gabriel}, 
{\it Mono\"\i des et automates admettant un produit de m\'elange}, 
Thèse de l'Université de Rouen (09/12/1999).
%
\bibitem{HJJTT} \textsc{Huss-Lederman S., Jacobson E.M., Johnson J.R., Tsao A., Turnbull T.},
``Implementation of Strassen's Algorithm for Matrix Multiplication''.
{\it Proceeding of the ACM/IEEE conference on supercomputing}
, Pittsburgh, Pennsylvania, USA (1996).
%
\bibitem{Iv} \textsc{Iverson Kenneth E.}, A programming Language. Wiley, 1962. 
%
\bibitem{S} \textsc{Sch\"utzenberger},
``On the  definition of a family of automata''.
{\it Inform. and Contr.} {\bf 4} (1961) 245-270.
%%% 
\subsubsection*{Cryptographie/Cryptologie.}
%
\bibitem{B1}
\textsc{\sc Bryant R. E.},
\emph{Graph-based algorithms for boolean function manipulation}. 
IEEE Transactions on Computers {\bf 35}, (1986).
%
\bibitem{BFCA05} {\sc Duchamp G. H. E., Hadj-Kacem H., Laugerotte E.}, 
{\it On the decomposition of boolean functions}, BFCA05, March 7-8, 2005.
%
\subsubsection*{Combinatoire Algébrique}
%
\bibitem{Fo} \textsc{Fomin S.} {\it Duality of graded graphs}, J. Alg. Comb. 3 (1994) 357-404
 "Schensted algorithms for dual graded graphs", J. Alg. Comb. 4 (1995), 5-45.
%
\bibitem{DKL}
\textsc{\sc Duchamp G., Krob D.,  Lascoux A., Leclerc B., Scharf T., 
 Thibon J.-Y.}, 
\emph{Euler-Poincar\'e characteristic and polynomial representations of 
Iwahori-Hecke algebras}. Pub. of the RIMS {\bf 31}, (1995).
%
\bibitem{H} \textsc{Humphreys J. E.},  
\emph{Reflection groups and Coxeter groups}. 
Cambridge University Press, (1990).
%
\bibitem{Jo} \textsc{Joyal A.}, {\it Une théorie combinatoire des séries formelles}, Adv. Math.42 (1981), 1-82.
%
\bibitem{Ju} \textsc{Jucys A. A.}, {\em Symmetric polynomials and the center of 
the symmetric group ring}, Reports on Mathematical physics, {\bf 5}, 107-112, 
1974. 
%
\bibitem{Mu} \textsc{Murphy G. E.}, {\em A new construction of Young's seminormal 
representation of the symmetric groups}, \rm Journal of Algebra, {\bf 69}, 287-
297, 1981.
%
\bibitem{Mu1} \textsc{Murphy G. E.}, {\em The idempotents of the symmetric group 
and Nakayma's conjecture}, \rm Journal of Algebra, {\bf 81}, 258-265, 1983.
%
\bibitem{OV} \textsc{Okounkov A.} et {\sc A. M. Vershik}, {\it Inductive 
construction of representation theory for symmetric groups}, Russian Math. 
Survey, {\bf 51}, Vol 2, 1996.
%
\bibitem{Mc1} \textsc{I. G. Macdonald}, {\it Symmetric functions and Hall 
polynomials}, Clarendon Press, Oxford, 1979.
%
\bibitem{LS2} \textsc{Lascoux A.} et \textsc{Sch\"utzenberger M. -P.}, {\it Le 
mono\"ide plaxique}, Quaderni della Ricerca Scientifica del CNR, Rome, 
1981.
%
\bibitem{To} \textsc{Touchard J.}, {\it Sur les cycles des permutations}, Acta Math. {\bf 70} (1939), 243-297.
%

\subsubsection*{Combinatoire et Physique.}
%
\bibitem{GOF10} \textsc{G. H. E. Duchamp, P. Blasiak, A. Horzela, K. A. Penson, A. I. Solomon}, {\it Feynman graphs and related Hopf algebras}, Journal of Physics, Volume 30, 2006: Conference Series, SSPCM'05, Myczkowce, Poland.\\
arXiv : {\tt cs.SC/0510041}
%
\bibitem{GOF4} \textsc{G. Duchamp, K.A. Penson, A.I. Solomon, A. Horzela and P. Blasiak}, {\it One-Parameter Groups and 
Combinatorial Physics},Proceedings of the Third International Workshop on Contemporary Problems in Mathematical Physics 
(COPROMAPH3), Porto-Novo (Benin), November 2003, J. Govaerts, M. N. Hounkonnou and A. Z. Msezane Eds., p. 436, 
World Scientific Publishing, Singapore (2004)\\
arXiv :  {\tt quant-ph/0401126} 
%
\bibitem{RU} \textsc{Ridell R.J., Uhlenbeck G.E.}, {\it On the theory of the virial development of the equation of state of monomatomic gases}, 
 J. Chem. Phys. {\bf 21} (1953), 2056-2064.
%
\end{thebibliography}
\end{document}

