Notes du cours de “Calcul Symbolique, Fonctions Symétriques et Spéciales” MMI 2006-2007. (Version provisoire)

G. H. E. Duchamp & Christophe Tollu & Frédéric Toumazet^{∗}

04-06-2007 19:22

Table des matières

0 Préambule 2

1 Introduction 3

2 Graphes et structures de transition 3

2.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Chaînes de Markov à une matrice . . . . . . . . . . . . . . . . . . . . 7 2.1.2 Plusieurs matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Coûts et poids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Décomposition 7 3.1 Cadre général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Décomposition automatique de modules . . . . . . . . . . . . . . . . . . . . . 10 3.3 Calcul de l’ensemble suffixe . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Calcul de End_{A}(M) et des idempotents (projecteurs) . . . . . . . . . . . . . . 13

4 Idempotents 16 4.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Décomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5 Application I : Cryptographie et fonctions booléennes 17 5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Les Diagrammes de Décision Binaire . . . . . . . . . . . . . . . . . . . . . . 18

6 Décomposition d’une fonction booléenne 18 6.1 Algèbre du groupe symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.2 Exemples de décompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7 Application II : Module sur ℌ_{k}^{n}(0) 21

∗ Prière de nous signaler les erreurs.

7.1 L’algèbre de Hecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 7.2 Exemples de décompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

8 Description du programme DEC-MOD 25

8.1 Cas des groupes finis : Caractères . . . . . . . . . . . . . . . . . . . . . . . . . 28

8.1.1 Un modèle qui contient toutes les représentations : la représentation

régulière . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 8.1.2 Construction d’une FCIOM pour le groupe symétrique . . . . . . . . . 30 8.1.3 Étude rapide de la complecité du calcul . . . . . . . . . . . . . . . . . 34

9 Traces 36

10 Liminaire 36

11 Bases et algèbres de Gelfand-Tsetlin 36

12 Description des poids 38 12.1 Modules de l’algèbre de Hecke affine dégénérée H_{2} . . . . . . . . . . . . . . . 38 12.2 Le graphe de Young est le graphe de branchement . . . . . . . . . . . . . . . . 39

13 Formules de Murnaghan-Nakayama 40

14 Annexe A: Automates 41

14.1 Description de la structure d’automate . . . . . . . . . . . . . . . . . . . . . . 41 14.1.1 Graphe pondéré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 14.1.2 Structure et comportement des automates . . . . . . . . . . . . . . . . 42 14.1.3 Exemples de fonctions produites par des automates . . . . . . . . . . . 43

14.2 Which rational calculus? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

0 Préambule

Ce cours est commun aux étudiants originaires des filières Informatique et Mathématique. Il est conçu de façon à permettre aux étudiants des deux sensibliltés

– d’acquérir des élements de culture générale scientifique n’auraient pas été acquis pendant leur parcours (comme les liens entre algèbre, combinatoire, analyse et géométrie)

– d’unifier les disciplines classiques et certains thèmes innovants Les illustrations seront faites en Maple et Mupad, mais le contenu de l’enseignement est, bien entendu, indépendant du langage. Le poly correspond à un programme maximal. Seule une partie de celui-ci sera traitée cette année (cette partie sera délimitée pendant le Forum). Les exercices qui sont là pour aider à la compréhension du cours. II se peut que vous ne compreniez pas certains énoncés, dans ce cas choisissez que les questions que vous êtes capables d’aborder ... et contactez-nous rapidement pour le décodage du reste.

Les parties en petits caract^{}ères sont des suppléments et ne sont pas obligatoires.

1 Introduction

Le cours qui suit est un mélange entre Mathématiques et Informatique. En particulier toutes les notions seront \underline{effectives} et \underline{implémentables}. Le cours débute par une description assez large et plutôt théorique, mais nous verrons très tôt

– des exemples complètement dévissés

– une implémentation et des programmes La première partie décrit les liens entre les notions suivantes

Théorie des représentations : k corps, Σ structuré Automates : k semi-anneau, Σ alphabet Actions

Fig. 1 – Les différents domaines de ce cours.

2 Graphes et structures de transition

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

a|w  q_{1}  q_{2}

i) q_{1},q_{2} ∈ Q Q est un ensemble (fini ou infini d’états) ii) a est le symbole qui agit iii) α ∈ k est un coefficient. L’ensemble (k) des coefficients est muni de deux lois +,×,

\underline{associatives}, + est \underline{commutative} et × soit \underline{distributive} (à droite et à gauche) sur +.

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

• α(f) = q_{1}, source ou origine de f

• β(f) = q_{2}, but ou extrémité de f

• λ(f) = a, étiquette de f

• weight(f), poids, coût ou coefficient de transition de f On appelle \underline{chemin} toute suite finie c = f_{1}f_{2} ⋯ f_{n} de flêches telle que (∀j < n)(β(f_{j}) = α(f_{j+1})). On étend aussitôt les notions précédentes aux chemins par (avec c = f_{1}f_{2} ⋯ f_{n})

\begin{matrix}• α(c) = α(f_{1}), source ou origine de c \\ • β(c) = β(f_{n}), but ou extrémité de c \\ • λ(c) = λ(f_{1})λ(f_{2}) ⋯ λ(f_{n}) (concaténation dans Σ^{∗}), étiquette de c \\ • weight(c) = weight(f_{1})weight(f_{2}) ⋯ weight(f_{n}) (produit dans k), poids de c. \end{matrix} \} (1)

Lorsque l’on a deux chemins c_{1} = f_{1}f_{2} ⋯ f_{n_{1}} et c_{2} = f_{n_{1}+1}f_{n_{1}+2} ⋯ f_{n} \underline{consécutifs} (c’est à dire que β(c_{1}) = α(c_{2})), on définit leur concaténation c_{1}c_{2} par f_{1}f_{2} ⋯ f_{n_{1}}f_{n_{1}+1}f_{n_{1}+2} ⋯ f_{n}. On vérifie facilement que les formules (1) 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ême source, but et étiquette 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 α + β.

q_{1}  q_{r} u|α u|β

On a donc que les poids se multiplient en série et s’aditionnent en parallèle. Les diagrammes suivants montrent la nécessité des propriétés exigées pour + et ×.

Diagramme  Identité  Nom

→^{a|α}

p →^{a|β} q  α + (β + γ) = (α + β) + γ Associativité de +

→^{a|γ}

p →^{a|α} ; →^{a|β}q  α + β = β + α  Commutativité de +
p →^{a|α} q →^{b|β} r →^{c|γ} s α(βγ) = (αβ)γ  Associativité de ×
p →^{a|α} ; →^{a|β}q →^{b|γ} r  (α + β)γ = αγ + βγ  Distributivité (droite) de × sur +
p →^{a|α} q →^{b|β} ; →^{b|γ}r  α(β + γ) = αβ + αγ  Distributivité (gauche) de × sur +

Remarque 2.1 i) La plupart du temps on a des éléments neutres pour + et ×. S’il n’y sont pas, on peut montrer qu’il est possible de les rajouter^{1}. ii) Les règles “multiplier” en série et “ajouter” en parallèle sont - aussi - celles des probabilités.

1. en langage académique cette opértion se nomme l’“adjonction”.

Exercice 2.2 On considère l’automate probabiliste de la figure (2).

a) Déterminer la fonction génératrice de probabilité

∑_{n≥0} p_{n}z^{n}  (2)

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 (2). b) Déterminer la fonction {P,F }^{∗} ↦ ℝ déterminée par l’automate ci-dessous (les charges d’entrée et de sortie sont p_{e},p_{s}).

1  2  3  4 p_{e} P |(0.5) F |(0.5) F |(0.5) P |(0.5) F |(0.5) P |(0.5) p_{s}

Fig. 2 – Un automate proposé par les étudiants

Correction de l’exercice (2.2) 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_{e}M^{n}[1,4]p_{s}. Par suite, la SG de probabilité est

∑_{n≥0} p_{n}z^{n} = ∑_{n≥0} p_{e}M^{n}[1,4]p_{s}z^{n} = p_{e}p_{s}(∑_{n≥0} M^{n}z^{n})[1,4] = p_{e}p_{s}(1 − zM)^{−1}[1,4] (3)

ceci se calcule avec la programme ci-dessous.

   > with(linalg):
   Warning, the protected names norm and trace have been redefined and
   unprotected
   > Mp:=matrix(4,4,[0,1/2,0,0,0,1/2,0,0,0,1/2,0,0,0,0,0,0]);

Mp := [ \begin{matrix}0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ]

   > Mf:=matrix(4,4,[1/2,0,0,0,0,0,1/2,0,0,0,0,1/2,0,0,0,0]);

Mf := [ \begin{matrix}\frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 \end{matrix} ]

> M:=matadd(Mp,Mf);

M := [ \begin{matrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 \end{matrix} ]

> I4:=matrix(4,4,(i,j)->if i=j then 1 else 0 fi);

I4 := [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ]

> M2:=matadd(I4,M,1,-z);

M2 := [ \begin{matrix}1 − \frac{z}{2} & −\frac{z}{2} & 0 & 0 \\ 0 & 1 − \frac{z}{2} & −\frac{z}{2} & 0 \\ 0 & −\frac{z}{2} & 1 & −\frac{z}{2} \\ 0 & 0 & 0 & 1 \end{matrix} ]

> inverse(M2)[1,4];

\frac{z^{3}}{(−2 + z) (−4 + 2 z + z^{2})}

finalement, la série cherchée est

\frac{t^{3}p_{e}p_{s}}{(2 − t)(4 − 2t − t^{2})} = p_{e}p_{s}(\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} + ⋯) (4)

b) La série cherchée se calcule selon le même principe, il s’agit de remplacer ∑_{n≥0} M^{n}z^{n} (= (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 (73).

2.1 Applications

2.1.1 Chaînes de Markov à une matrice

2.1.2 Plusieurs matrices

2.2 Coûts et poids

3 Décomposition

3.1 Cadre général

Un graphe pondéré détermine une \underline{structure de transition} qui est équivalente à la donnée d’une application Σ ↦ End(V). Cela revientà se donner une famille de matrices {M_{α}}_{α∈Σ} ou d’opérateurs {φ_{α}}_{α∈Σ} qui agissent sur un espace vectoriel V, soit une application^{2} μ : Σ ↦ End(V). Les opérateurs φ_{α} sont souvent appelés \underline{actions} de Σ sur V. Une telle structure est appelée \underline{représentation linéaire} de l’ensemble Σ et V s’appelle alors un Σ-module. 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 μ (on demande en général que μ soit un morphisme).

Définition 3.1 Soit (μ_{α})_{α∈Σ} une famille d’opérateurs agissant sur un espace vectoriel V.

i) On dit que qu’un sous-espace W ⊂ V est

• \underline{stable} si (∀α ∈ Σ)(μ_{α}(W) ⊂ W)

• \underline{irréductible} si pour tout sous-espace stable (0) ⊂ W_{1} ⊂ W, on a W_{1} = (0) ou W_{1} = W.

ii) Si V = ⊕_{i∈I}V_{i} et que les V_{i} sont stables on dit que V = ⊕_{i∈I}V_{i} est une décomposition de V. iii) Soient deux Σ-modules U et V. On dit qu’une application linéaire φ : U ↦ V est Σlinéaire si elle commute avec tous les μ_{α} soit

(∀α ∈ Σ)(∀v ∈ U)(φ ∘ μ_{α}(v) = μ_{α} ∘ φ(v)).  (5)

On dit aussi que φ est un morphisme de Σ-modules. On note Hom_{Σ}(U,V) l’ensemble des applications Σ-linéaires U ↦ V (resp. End_{Σ}(U) si U = V.

Remarque 3.2 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 (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}). 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 ↦ V se note Hom_{k}(U,V).

Exercice 3.3 (Généralités) Soit X un ensemble. Pour n,k ∈ ℕ, la classe de Burnside B(n,k) est l’ensemble des applications f : X ↦ X telles que f^{n} = f^{n+k} où f^{n} est la suite d’applications définies par

f^{0} = Id_{X} ; f^{n+1} = f ∘ f^{n}  (6)

2. On rappelle que End(V) désigne l’espace des applications linéaires V ↦ V.

Remarque. — C’est la “puissance compositionnelle” définie, pour n > 0 par f^{n} = \underbrace{f ∘ f ⋯ ∘ f}_{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-espace vectoriel et p, un projecteur de V.

a) Montrer que V = ker(p) ⊕ im(p) = V_{0} ⊕ V_{1}

b) Ici Σ = {p} Montrer que

End_{Σ}(V) = {f ∈ End(V)|f(V_{0}) ⊂ V_{0}, f(V_{1}) ⊂ f(V_{1})}  (7)

2) a) On suppose que 1/2 ∈ k. Soit s une symétrie de V. Montrer que

p_{(1)} = \frac{1}{2}(s + Id) et p_{(−1)} = \frac{1}{2}(s − Id)  (8)

sont des projecteurs.

b) On pose Σ_{1} = {s} ; Σ_{2} = {p_{(−1)},p_{(1)}}. Montrer que End_{Σ_{1}}(V) = End_{Σ_{2}}(V).

c) À l’aide de (1.b) et (2.b), caractériser End_{Σ_{1}}(V).

À 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 μ en une application

μ̄ : Σ^{∗} ↦ End(V)

qui transforme la concaténation en composition. Là, selon que les actions sont notées à droite ou à gauche on aura

μ̄(uv) = μ̄(u) ∘ μ̄(v) ou bien μ̄(uv) = μ̄(v) ∘ μ̄(u).  (9)

Ceci nous amèneà la structure minimale pour “préparer les actions”, c’est la notion de représentation d’un semigroupe^{3}.

Définition 3.4 Soit (G,∗) un semigroupe et (μ_{α})_{α∈G} une représentation de G dans V. On dit que μ est une représentation “à gauche” si

(∀u,v ∈ G)(μ_{α∗β} = μ_{α} ∘ μ_{β})  (10)

et “à droite” si

(∀u,v ∈ G)(μ_{α∗β} = μ_{β} ∘ μ_{α}).  (11)

Note 3.5 Cette définition est conditionnée par le déplacement des parenthèses en effet, si l’on note q.α (resp. α.q) pour μ_{α}(q) dans le cas d’une représentation à droite (resp. à gauche), on a (q.α).β = q.(α ∗ β) (resp. α.(β.q) = (α ∗ β).q).

Exemple 3.6 Nous considérons le groupe symétrique 𝔖_{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 σ_{1} = [213] et σ_{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.

3. Un semigroupe est un ensemble muni d’une loi associative.

e_{1}  e_{2}  e_{3} σ_{1} σ_{2} σ_{2} σ_{1}
Fig. 3 – Le 𝔖_{3}-module k^{3}.

Décomposition en sous-modules irréductibles. — 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 ⟨(x,y,z)|(x′,y′,z′)⟩ = xx′ + yy′ + zz′ (ici k = ℝ, pour ℂ prendre le premier vecteur conjugué) est invariant par 𝔖_{3} (voir exercice (8.7)). Par suite, le plan (e_{123})^{⊥} (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 (4).

e_{1} − e_{2}  e_{2} − e_{3} σ_{1}|1 σ_{1}| − 1,σ_{2}|1 σ_{2}|1 σ_{2}| − 1,σ_{1}|1

Fig. 4 – Un sous-module du 𝔖_{3}-module k^{3}.

Exercice 3.7 Montrer que le module de la figure 4 est irréductible.

Exercice 3.8 Décomposition de la repésentation régulière gauche de 𝔖_{3} dans ℝ[𝔖_{3}].. — Dans tout l’exercice, G = 𝔖_{3}. Les données sont les suivantes :

• l’espace est celui des fonctions G ↦ ℝ, notées comme des sommes f := ∑_{h∈G} f(h)h. Cet espace est noté ℝ[G].

• les éléments de G sont notés comme des listes et celui qui est à gauche agit par valeurs sur celui qui est à droite.

G = 𝔖_{3} = {[123],[132],[213],[231],[312],[321]}
g_{1}.g_{2} = [g_{1}[g_{2}[1]],g_{1}[g_{2}[2]],g_{1}[g_{2}[3]]]  (12)

• G agit sur les fonctions par linéarité soit

g.(∑_{h∈G} f(h)h) = ∑_{h∈G} f(h)g.h  (13)

Remarque. — On définit de même l’action à droite (mais nous n’en aurons besoin que plus tard) par

(∑_{h∈G} f(h)h).g = ∑_{h∈G} f(h)h.g  (14)

1) Montrer que, pour tout g ∈ G, l’application ρ(g) : ℝ[G] ↦ ℝ[G] est linéaire.

2) Montrer que c’est bien une représentation du groupe G au sens où

(∀g_{1},g_{2} ∈ G)(ρ(g_{1}.g_{2}) = ρ(g_{1}) ∘ ρ(g_{2}))  (15)

(il suffit de montrer l’égalité des images sur une base).

3) Montrer que les droites

D_{1} = ℝ(∑_{g∈G} g) ; D_{−1} = ℝ(∑_{g∈G}(−1)^{inv(g)}g)  (16)

sont invariantes par ρ.

4) Soit w_{1} = [123] − [213] + [132] − [231]. Décrire le module W_{1} engendré par w_{1} sous l’action de ρ.

5) a) Calculer w_{2} = w_{1}.[213]. Soit W_{2} le module engendré par w_{2}, montrer que l’on a

ℝ[G] = W_{1} ⊕ W_{2} ⊕ D_{1} ⊕ D_{−1} = W_{1} ⊕ W_{2} ⊕ W_{3} ⊕ W_{4}  (17)

b) Soit 1_{ℝ[G]} = e_{1} +e_{2} +e_{3} +e_{4}, la décomposition de 1_{ℝ[G]} selon la somme directe (17). Montrer que

i) (∀i,j ∈ [1..4])(e_{i}e_{j} = δ_{ij}e_{i}) = δ_{ij}e_{j})  ii) ℝ[G]e_{i} = W_{i}

Commentaire. — 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 famille d’idempotents orthogonaux. Si, de plus, 1 = ∑_{i} e_{i}, on dit que la famille est complète. Et si, de plus, tous les W_{i} = Ae_{i} sont irréductibles, on dit que c’est une Famille Complète d’Idempotents Orthogonaux Minimaux (FCIOM). On verra qu’une telle famille est l’outil de décomposition de ℂ[G] comme somme d’algèbres de matrices.

♢

3.2 Décomposition automatique de modules

Cet algorithme est l’œuvre de Schützenberger [2, ?, 28, 20]. En effet, il fut inventé pour l’optimisation des automates à multiplicités [2]. Un automate à multiplicités dans k est défini par la donnée d’un quintuplet (Σ,Q,I,T,F) [2] où

• Σ est l’alphabet (de commande)

• Q est l’ensemble fini des états

• I ⊂ Q est l’ensemble des états initiaux

• F ⊂ Q est l’ensemble des états finaux

• T ⊂ Q × A × k × Q contient les arcs orientés reliant les états entre eux.

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 \underline{représentation linéaire} (λ,μ,γ) de l’automate.

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 Σ-module engendré par un seul vecteur (dit \underline{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.

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 (λ,μ,γ) à multiplicités dans un corps (commutatif ou non) k (dû à Schützenberger), est la construction d’un ensemble préfixe^{4} P tel que l’orbite λμ(P) soit une base de λμ(k⟨⟨A⟩⟩) [2, ?, 28]. Ce même processus permet aussi d’obtenir un certificat cert(M) vérifiant si un Σmodule M engendré par une seul vecteur est décomposable ou non. 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.

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 (3.4), une deuxième extension aux combinaisons linéaires de mots (les polynômes non commutatifs k⟨Σ⟩) est nécessaire. Nous présentons l’algorithme dans le cadre général d’une algèbre d’opérateurs (associative) sur un espace vectoriel de dimension finie V. Il peut être compris avec A = k⟨Σ⟩.

Définition 3.9 Un espace vectoriel 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) → xy, bilinéaire A × A ↦ A. L’algèbre est dite \underline{commutative}, \underline{associative}, \underline{unitaire} si la produit l’est. Dans la suite, une algèbre associative, avec unité (unitaire) sera désignée par AAU. 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·m, ayant pour générateur m ∈ 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 ann(m) = {a ∈ A : a·m = 0} l’ensemble des annulateurs de m. C’est un idéal à gauche de A.

3.3 Calcul de l’ensemble suffixe

On commence par construire une partie suffixe P ⊂ S^{∗} tel que P · m soit une base de A · m.

Soit E := {(s_{i},s) ∈ S × P | s_{i}s ∉ P }. Pour (s_{i},s) ∈ E, on a :

s_{i}s.m = ∑_{s′∈P} α_{s_{i}s,s′}s′.m  (18)

4. suffixe si le actions sont à gauche.

et les différences R := {s_{i}s − ∑_{s′∈P} α_{s_{i}s,s′}s′}_{(s_{i},s)∈E} forment un ensemble complet de générateurs de ann(m). Donc, la première étape du processus de décomposition est le calcul d’un ensemble suffixe P ⊂ 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·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 · m) parmi les projecteurs de End_{k}(A · m).

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 ∈ M et retourne en sortie l’ensemble suffixe P et l’ensemble des relateurs R.

Algorithme suffixe

Entrée : l’ensemble S

un générateur m ∈ M

Sortie : un ensemble suffixe P ⊂ S^{∗}

un ensemble des relateurs R

Début

1. (P,Y,R) := (∅,{ε},∅)

2. Tant que Y ≠ ∅ faire

3. retirer un mot y de Y

4. Si y · m ∉ span(p · m : p ∈ P) alors

5. (P,Y) := (P ∪ {y},(Y − {y}) ∪ yS)

6. Sinon

7. Il existe une relation y.m = ∑_{p∈P} α_{p}p · m (P,Y,R) := (P,(Y − {y}),R ∪ {y − ∑_{p∈P} α_{p}p})

8. Fin si

9. Fin faire

10. retourner (P,R) Fin.

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 = {ε}. Ensuite, si y ∈ Y ⊆ S^{∗} est accepté, tous les suffixes de y sont dans P. Soit |s| la longueur du mot s ∈ S^{∗}. Puisque l’espace A·m est de dimension finie, il existe un entier positif l tel que :

span(s · m : s ∈ S^{∗})=span(s · m : s ∈ S^{∗} et |s| < l).

On a P ⊆ {s ∈ S^{∗} : |s| < l} et Y ⊆ {s ∈ S^{∗} : |s| < l + 1}. L’ensemble devient vide durant l’algorithme et alors l’algorithme se termine. Lemme 3.10 L’ensemble P · m = {s · m : s ∈ P } est une base de l’espace A · m. Preuve Soit C = SP − P le code suffixe complet associé à l’ensemble P [2]. On a la décomposition S^{∗} = P ⊔ S^{∗}CP du monoïde libre. Si s_{i}s ∈ C, il existe un relateur s_{i}s −

ab^{2} + b

b^{2} ε

b

a b b

0

a a b

ab^{2} + b

b^{2}

b

ε

a b b

0

a b a a

Fig. 5 – Les ensembles suffixes pour m = ab^{2} + b (l’action est donnée par les quotients (x^{−1})_{x∈{a,b}} de Eilenberg [20]).

∑_{s′∈P} α_{s′}s′ ∈ R. Soit maintenant s_{i} ∈ S et s_{i}s ∈ CS^{∗}S. on a alors par induction :

s_{i}s · m = ∑_{s′∈P} α_{s′}s_{i}s′ · m

= ∑_{s_{i}s′∈P} α_{s′}s_{i}s′ · m + ∑_{s_{i}s∉P} ∑_{s′′∈P} α_{s′}β_{s_{i}s′}^{s′′}s′′ · m.

Et donc s_{i}s · m ∈ span(s · m : s ∈ P). □

D’après le lemme 3.10, l’algorithme suffixe calcule une description complète de l’espace A · m. On remarque que l’ensemble des relateurs dépend du choix du mot y ∈ Y. Soit m = ab^{2} + b ∈ ℚ⟨a,b⟩. Les actions étant données par les formules de décalage (quotients de Eilenberg [20]). La figure 5 donne l’ensemble suffixe et l’ensemble des relateurs de 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. En effet, l’élément b + ab^{2} ∈ S^{∗} est un relateur avec le deuxième type d’ordre (graphe à droite de la figure 5) ce qui n’est pas le cas avec le premier type (graphe à gauche de la figure 5).

3.4 Calcul de End_{A}(M) et des idempotents (projecteurs)

D’abord un petit exercice sur les projecteurs.

Exercice 3.11 Soit V un espace vectoriel et f ∈ End(V).

1) Montrer que les conditions suivantes sont équivalentes

i) f^{2} =: f ∘ f = f (on dit alors que f est idempotent) ii) V = Im(f) ⊕ Ker(f) et (∀y ∈ Im(f))(f(y) = y)

2) En indexant les propriétés comme suit :

A) f^{2} := f ∘ f = f B) V = Im(f) ⊕ Ker(f) C) (∀y ∈ Im(f))(f(y) = y).

a) Trouver une application linéaire V ↦ 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 Σ-module. Montrer que, si f ∈ End_{k}(V) est idempotent (i.e. un projecteur), les propriétés suivantes sont équivalentes

i) f est Σ-linéaire (voir (3.1)) ii) Im(f) et Ker(f) sont stables par Σ (i.e. des sous-modules de V).

4) Dans cette question, on suppose que Σ engendre un groupe fini d’actions de V dans V (i.e. μ(Σ) = G ⊂ Aut(V) est fini). Soit W un sous-module de V et p : V ↦ V un projecteur sur W.

a) Montrer que

f(v) = \frac{1}{|G|} ∑_{g∈G} g(p(g^{−1}(v)))  (19)

définit un projecteur Σ-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.

5) Déduire de ce qui précède que, si V est de dimension finie, il s’exprime comme somme

V = V_{1} ⊕ V_{2} ⊕ ⋯ ⊕ V_{r}  (20)

de sous-modules indécomposables.

Commentaire. — La décomposition (21) est unique à permutation et isomophisme près. En fait, on montre que^{5}, dans les conditions précédentes, si

V = V_{1} ⊕ V_{2} ⊕ ⋯ ⊕ V_{r} = W_{1} ⊕ W_{2} ⊕ ⋯ ⊕ W_{s}  (21)

sont deux décomositions en indécomposables, alors r = s et il existe une permutation τ (ici renommage des indices) telle que, pour tout 1 ≤ j ≤ r V_{j} ≃ W_{τ(j)}.

♢

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

sp − ∑_{q∈P} α(s,p,q)q. pour (s,p) ∈ S × P tels que sp ∉ P  (22)

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 3.10, qu’il est possible de déterminer algorithmiquement un endomorphisme φ dans la base (s · m)_{s∈P} de A · m. En effet, l’algorithme suffixe permet de calculer l’ensemble suffixe P et l’ensemble des relateurs R. À chaque élément x = ∑_{s∈P} α_{s}s.m, on peut associer un unique endomorphisme φ_{x} ∈ End_{k}(A · m) tel que, pour tout

(∀w ∈ P)(w ∈ P)  (23)

Pour que φ_{x} ∈ End_{A}(A · m) il faut et il suffit que ann(m) ⊂ ann(x). Inversement, à chaque morphisme φ ∈ End_{A}(A · m), on peut associer un élément m_{φ}.

L’algorithme suivant permet de construire l’endomorphisme φ. 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 φ(s · m) est donné suivant le rangement de s dans l’ensemble P. Si s = s_{i}s′, alors φ(s′ · m) est déjà connu.

5. Admis ici, voir le théorème de Krull-Schmidt (6.1).

Algorithme cons φ

Entrée : l’ensemble des transpositions S l’ensemble suffixe P l’ensemble des relateurs R

Sortie : le morphisme φ Début

1. Y := S

2. φ(εf) := ∑_{s∈P} α_{s,ε}s · m

3. Tant que Y ≠ ∅ faire

4. retirer un mot ss_{i} de Y

5. Si ss_{i} ∉ P alors

6. Y := Y − {ss_{i}}

7. Sinon

8. φ(ss_{i} · m) := sφ(s_{i} · m)

Y := (Y ∪ Sss_{i}) − {ss_{i}}

9. Fin si

10. Fin faire

11. retourner (φ) Fin.

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 3.12. Lemme 3.12 Soit φ ∈ End_{k}(A · m) et m_{φ} = φ(m). Alors la transformation linéaire φ appartient à End_{A}(A · m) si et seulement si:

i) pour tout s ∈ P, on a φ(s · m) = s · φ(m), ii) pour tout (s_{i},s) ∈ S × P tel que s_{i}s ∉ P, la différence (s_{i}s − ∑_{s′∈P} α_{s_{i}s,s′}s′) annule m_{φ}. Une fois qu’on a le morphisme φ, et d’après le lemme 3.12, pour trouver l’ensemble des projecteurs, on doit étudier la relation d’idempotence

φ^{2} = φ  (24)

et vérifier que

φ(s · m) = s · φ(m)  ∀ s ∈ P  (25)
r · φ(m) = 0  ∀ r ∈ R  (26)

De ces trois formules (24), (25) et (26), on obtient un système de n|P |^{2} + |P | équations en les inconnues α_{s,ε} pour tout s ∈ P.

Toute solution non-triviale φ donne une première décomposition A · m = A · m_{φ} ⊕ A · m_{1−φ}. Ensuite, on réapplique l’algorithme sur A · m_{φ} et A · m_{1−φ}. À 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 · m ne peut pas être une somme directe de sous-modules. Théorème 3.13 Soit m ∈ M. Une répétition finie de l’algorithme suffixe et cons φ décide s’il existe une décomposition de A · m en une somme directe de sous-modules indécomposables. Si aucune solution non-triviale ne peut être trouvée, le module A · m est indécomposable. 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. Remarque 3.14 La forme particulière des relateurs R (22) donne un quotient (k⟨A⟩; R) libre sur k même si k est un anneau.

4 Idempotents

4.1 Généralités

Classes de Burnside, nombres idempotents, formule exponentielle.

4.2 Décomposition

Exercice 4.1 Soit G_{n} = ⟨g; g^{n} = 1⟩ (le groupe cyclique d’ordre n).

0) (Warmup) Montrer que G_{n} = {g^{k}}_{0≤k<n} et que

g^{p} = g^{q} ⟺ p − q est divisible par n

1) Pour 0 ≤ k < n, et ξ = e^{\frac{2iπ}{n}} on pose

e_{k} = \frac{1}{n} ∑_{j=0}^{n−1} ξ^{−jk}g^{j}  (27)

a) Montrer que g.e_{k} = ξ^{k}e_{k} puis que

e_{k_{1}}e_{k_{2}} = δ_{k_{1},k_{2}}e_{k_{1}}  (28)

b) Montrer que

∑_{k=0}^{n−1} e_{k} = 1_{G_{n}}  (29)

2) (Sandwiches). —

a) Montrer que

dim(e_{k_{1}}ℂ[G_{n}]e_{k_{2}}) = 0 si k_{1} ≠ k_{2} et 1 si k_{1} = k_{2}  (30)

b) En déduire que si l’on pose e_{k}ge_{k} = μ(g)e_{k}, l’application

g → (\begin{matrix}μ_{1}(g) & 0 & ⋯ & 0 \\ 0 & μ_{2}(g) & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & ⋯ & 0 & μ_{n}(g) \end{matrix})  (31)

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∈T}. a (**) Montrer que

dim(e_{s}ℂ[G]e_{t}) ∈ {0,1}  (32)

b) (**) Montrer que la relation s ∼ t définie par dim(e_{s}ℂ[G]e_{t}) = 1 est une relation d’équivalence.

5) (**) Soit B = T/ ∼ et b ∈ B. On range les éléments de b en une suite t_{1},t_{2} ⋯ t_{l}, puis on choisit E_{i,i+1} ∈ e_{t_{i}}ℂ[G]e_{t_{i+1}} non nul.

a) Montrer que l’on peut choisir, pour tout 0 ≤ 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

E_{i,j} = E_{i,i+1}E_{i+1,i+2} ⋯ E_{j−1,j} pour i < j
E_{i,j} = E_{i,i−1}E_{i−1,i−2} ⋯ E_{j+1,j} pour i > j
E_{i,i} = e_{t_{i}}  (33)

montrer que ces éléments sont des unités matricielles i.e. E_{i,j_{1}}E_{j_{2},k} = δ_{j_{1},j_{2}}E_{i,k}.

c) Pour 0 ≤ i,j ≤ l on définit ρ_{i,j}(g) par e_{t_{i}}ge_{t_{j}} = ρ_{i,j}(g)E_{i,j}. Montrer que ρ_{b} = (ρ_{i,j})_{0≤i,j≤l} définit une représentation matricielle de G.

6) a) (**) Montrer que la représentation par blocs ρ = (ρ_{b})_{b∈B}; ℂ[G] ↦ ⨁_{b∈B} M(l_{b},ℂ) est fidèle.

b) (***) Montrer que ρ est un isomorphisme.

5 Application I : Cryptographie et fonctions booléennes

5.1 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”. Par fonction booléenne, on entend toute fonction {0,1}^{n} → {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. À 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.

x_{1} x_{2}  x_{2} x_{3}  x_{3}  x_{3}  x_{3} 0  0  0  0  1  1  0  0 01
Fig. 6 – Diagramme de Shannon de f = x_{1}x_{2} + x_{1}.

0 x_{1} 1 x_{2} 0
Fig. 7 – Le BDD pour f = x_{1}x_{2} + x_{1}.

5.2 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 [1] pour représenter de façon compacte les fonctions booléennes. Puis en 1986, Bryant [29] 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. Soit la fonction booléenne f : {0,1}^{3} → {0,1} définie par f(x_{1},x_{2},x_{3}) = x_{1}x_{2} + x_{1}. Son diagramme de Shannon est donné dans la figure 6. 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 7.

6 Décomposition d’une fonction booléenne

Nous étudions ici l’orbite d’une fonction booléenne f ∈ 𝔽n sous l’action de l’algèbre A_{n} = ℤ_{2}[𝔖_{n}] [33] du groupe symétrique 𝔖_{n} sur les variables dans le but de donner une décomposition de f à l’aide de la théorie de minimisation. Soit 𝔽n le A_{n}-module à gauche des fonctions booléennes à n variables (x_{1}, …,x_{n}) et f ∈ 𝔽n une fonction booléenne. Considérons le sousmodule A_{n}.f. Il existe une décomposition du module A_{n}.f en une somme directe A_{n}.f = M_{1} ⊕ ⋯ ⊕ 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.

σ_{1} σ_{2}

σ_{2}σ_{1} σ_{1}σ_{2}

σ_{1}σ_{2}σ_{1} 0

1

2

3

σ_{1} σ_{2} σ_{2} σ_{1} σ_{1} σ_{2}

Fig. 8 – Le permutoèdre pour n = 3.

6.1 Algèbre du groupe symétrique

L’algèbre A_{n} = ℤ_{2}[𝔖_{n}] agit par permutations de variables sur l’ensemble des fonctions booléennes 𝔽n. Elle est engendrée par les transpositions simples S = (σ_{1}, …,σ_{n−1}) où σ_{i} est la transposition de i et i + 1 et peut être présentée par les relations suivantes dites de Moore-Coxeter [33, 32] :

\{ \begin{matrix}σ_{i}^{2} = 1, \\ σ_{i}σ_{j} = σ_{j}σ_{i} & si |i − j| > 1, \\ σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1}. \end{matrix}

Toute permutation σ ∈ 𝔖_{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 8) [33]. L’algèbre A_{n} est une algèbre assoicative de type fini. Elle agit à gauche sur ℤ_{2}⟨x_{1}, …,x_{n}⟩ par l’action de σ_{i} définie sur les variables par :

\{ \begin{matrix}σ_{i}x_{i} = x_{i+1}, \\ σ_{i}x_{i+1} = x_{i}, \\ σ_{i}x_{j} = x_{j} & si j ≠ i,i + 1. \end{matrix}

On rappelle que S = {σ_{1}, …,σ_{n−1}} est l’ensemble de ces transpositions simples, 𝔽n un A_{n}- module à gauche des fonctions booléennes à n variables. Il s’agit d’un ℤ_{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).

Théorème 6.1 (Krull-Schmidt) 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} ⊕ ⋯ ⊕ M_{r} = N_{1} ⊕ ⋯ N_{s} alors r = s et il existe une permutation τ ∈ 𝔖_{r} telle que

(∀j ≤ r)(M_{j} ≃ N_{τ(j)}).

Il existe donc une décomposition du module A_{n}.f en une somme directe A_{n}.f = M_{1}⊕⋯⊕M_{l} de A_{n}-sous-modules indécomposables, essentiellement unique d’après le théorème de Krull-Schmidt (6.1) (voir aussi [6]). x_{1}x_{2} + x_{1}

x_{1}x_{2} + x_{2}

x_{1}x_{3} + x_{3}

x_{2}x_{3} + x_{3}

x_{2}x_{3} + x_{2}

σ_{1} σ_{2} σ_{1} σ_{2} σ_{1} σ_{2} σ_{1} σ_{2} σ_{1} σ_{1} σ_{1} σ_{1} σ_{2} σ_{2} σ_{2} σ_{2} σ_{2} σ_{1}

x_{1}x_{2} + x_{1}

x_{1}x_{2} + x_{2}

x_{1}x_{3} + x_{3}

x_{1}x_{3} + x_{1}

x_{2}x_{3} + x_{2}

σ_{1} σ_{2} σ_{2} σ_{1} σ_{1} σ_{2} σ_{1},σ_{2} σ_{1} σ_{1},σ_{2} σ_{1} σ_{1} σ_{2} σ_{2} σ_{1} σ_{2} σ_{2}

Fig. 9 – L’ensemble suffixe et relateurs pour f = x_{1}x_{2} + x_{1}.

Le but de l’algorithme est donc de calculer une décomposition de A_{n} · f par la connaissance de l’ensemble de projecteurs orthogonaux π_{i} ∈ End_{A_{n}}(A_{n} · f) (i = 1, …,l) qui satisfont :

\{ \begin{matrix}π_{i} ∘ π_{i} = π_{i}, \\ π_{i} ∘ π_{j} = 0 si i ≠ j, \\ π_{1} ⊕ ⋯ ⊕ π_{l} = 1_{End_{An}(A_{n}.f)}. \end{matrix}

Ainsi, le module A_{n} · f est somme directe de sous-modules π_{i}(A_{n} · f) = A_{n}π_{i}(f) qui sont engendrés par un seul élément. Si π_{i} est un tel projecteur, π_{i} doit être A_{n}-linéaire.

6.2 Exemples de décompositions

On considère ici la fonction booléenne f = x_{1}x_{2} + x_{1} ∈ 𝔽3. L’ensemble des relateurs dépend du choix de l’ordre du parcours de l’arbre des suffixes. En effet, la figure 9 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 9). L’ensemble suffixe est

P = {ε,σ_{1},σ_{2},σ_{2}σ_{1},σ_{1}σ_{2}}.

L’ensemble des relateurs est

R = \{ \begin{matrix}σ_{1}σ_{1} + ε, \\ σ_{2}σ_{2} + ε, σ_{1}σ_{2}σ_{2} + σ_{1}, σ_{2}σ_{1}σ_{1} + σ_{2}, \\ σ_{1}σ_{2}σ_{1} + (ε + σ_{1} + σ_{2} + σ_{1}σ_{2} + σ_{2}σ_{1}), \\ σ_{2}σ_{1}σ_{2} + (ε + σ_{1} + σ_{2} + σ_{1}σ_{2} + σ_{2}σ_{1}). \end{matrix} \} .

Soit φ ∈ End_{k}(A_{3}.f) et f_{φ} ∈ A_{3}.f tel que :

f_{φ} = α_{ε}ε.f + α_{σ_{1}}σ_{1}.f + α_{σ_{2}}σ_{2}.f + α_{σ_{2}σ_{1}}σ_{2}σ_{1}.f + α_{σ_{1}σ_{2}}σ_{1}σ_{2}.f.

L’ensemble suffixe P et l’ensemble des relateurs R vont nous servir comme entrée dans l’algorithme cons φ pour construire la matrice φ.

x_{1}x_{3} + x_{2} + x_{2}x_{3} + x_{3}

x_{1} + x_{1}x_{3} + x_{2}x_{3} + x_{3}

x_{1} + x_{1}x_{2} + x_{2} + x_{2}x_{3}

x_{1}x_{2} + x_{2} + x_{2}x_{3} + x_{3}

σ_{1} σ_{2} σ_{2} σ_{1} σ_{2},σ_{1} σ_{1},σ_{2} σ_{1} σ_{1}

x_{1} + x_{1}x_{2} + x_{1}x_{3} + x_{2} + x_{2}x_{3} + x_{3}

σ_{1},σ_{2}

Fig. 10 – Décomposition complète de A_{3}.f.

Selon l’algorithme cons φ, la matrice φ est la suivante :

φ = (\begin{matrix}α_{ε} & α_{σ_{1}} + α_{σ_{1}σ_{2}} & α_{σ_{2}} + α_{σ_{2}σ_{1}} & α_{σ_{2}} + α_{σ_{2}σ_{1}} & α_{σ_{1}} + α_{σ_{1}σ_{2}} \\ α_{σ_{1}} & α_{ε} + α_{σ_{1}σ_{2}} & α_{σ_{1}σ_{2}} + α_{σ_{2}σ_{1}} & α_{σ_{2}} & α_{σ_{1}} + α_{σ_{2}} \\ α_{σ_{2}} & α_{σ_{1}σ_{2}} + α_{σ_{2}σ_{1}} & α_{ε} + α_{σ_{2}σ_{1}} & α_{σ_{1}} + α_{σ_{2}} & α_{σ_{1}} \\ α_{σ_{1}σ_{2}} & α_{σ_{1}σ_{2}} & α_{σ_{1}} + α_{σ_{2}σ_{1}} & α_{ε} + α_{σ_{2}} & α_{σ_{1}} + α_{σ_{2}σ_{1}} \\ α_{σ_{2}σ_{1}} & α_{σ_{2}} + α_{σ_{1}σ_{2}} & α_{σ_{2}σ_{1}} & α_{σ_{2}} + α_{σ_{1}σ_{2}} & α_{ε} + α_{σ_{2}} \end{matrix} )

Une solution non-triviale du système donné par φ^{2} = φ, σ · φ(f) = φ(σ · f) pour tout σ ∈ P et r · φ(f) = 0 pour tout r ∈ R est :

f_{φ} = σ_{2}σ_{1}.f + σ_{1}σ_{2}.f

et

f_{1+φ} = ε.f + σ_{2}σ_{1}.f + σ_{1}σ_{2}.f

C’est à dire

f_{φ} = x_{1}x_{3} + x_{2} + x_{2}x_{3} + x_{3}

et

f_{1+φ} = x_{1} + x_{1}x_{2} + x_{1}x_{3} + x_{2} + x_{2}x_{3} + x_{3}

Ce qui nous donne A_{3}.f = A_{3}.f_{φ} ⊕ A_{3}.f_{1+φ} et les décompositions complètes des modules A_{3}.f_{φ} et A_{3}.f_{1+φ} sont données dans la figure 10.

7 Application II : Module sur ℌ_{k}^{n}(0)

7.1 L’algèbre de Hecke

L’algèbre de Hecke générique notée ℌ_{k}^{n}(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≤i<n} et les relations

\{ \begin{matrix}T_{i}T_{j} = T_{j}T_{i} & si |i − j| > 1, \\ T_{i}T_{i+1}T_{i} = T_{i+1}T_{i}T_{i+1}, \\ (T_{i} − q_{1})(T_{i} − q_{2}) = 0. \end{matrix}

abc

bac acb

bca cab

cba

T_{1} T_{2} T_{2} T_{1} T_{1} T_{2} T_{1}| − 1 T_{2}| − 1 T_{2}| − 1 T_{1}| − 1 \begin{matrix}T_{1} |−1 \\ T_{2} |−1 \end{matrix}

Fig. 11 – Description de ℌ_{k}^{n}(0) · abc

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 ℌ_{k}^{n}(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 ℚ que l’on notera ℌ_{k}^{n}(0). Elle est engendrée par la famille (T_{i})_{1≤i<n} et les relations

\{ \begin{matrix}T_{i}T_{j} = T_{j}T_{i} & si |i − j| > 1, \\ T_{i}T_{i+1}T_{i} = T_{i+1}T_{i}T_{i+1}, \\ T_{i}(T_{i} + 1) = 0. \end{matrix}

L’algèbre de Hecke ℌ_{k}^{n}(0) agit à gauche sur ℚ⟨a_{1}, ⋯,a_{n}⟩ comme suit :

\{ \begin{matrix}T_{i}(… a(i)a(i + 1) …) = … a(i + 1)a(i) … & si a(i) < a(i + 1). \\ T_{i}(… a(i)a(i + 1) …) = 0, & si a(i) = a(i + 1). \\ T_{i}(… a(i)a(i + 1) …) = − … a(i)a(i + 1) … & si a(i) > a(i + 1). \end{matrix}

Où a(i) est la lettre du mot argument à la place i.

7.2 Exemples de décompositions

Soit m = abc ∈ ℚ⟨a,b,c⟩. Une description complète de l’action de T_{i} sur ℌ_{k}^{3}(0) · m est donnée dans la figure 11. En choisissant l’ordre lexicographique gradué pour le parcours de l’arbre des suffixes, l’ensemble suffixe est

P = {ε,T_{1},T_{2},T_{1}T_{2},T_{2}T_{1},T_{1}T_{2}T_{1}}.

L’ensemble des relateurs est ici

R = \{ \begin{matrix}T_{2}^{2} + T_{2}, T_{1}T_{2}^{2} + T_{1}T_{2}, \\ T_{2}T_{1}^{2} + T_{2}T_{1}, T_{2}T_{1}T_{2} − T_{1}T_{2}T_{1} \\ T_{1}T_{2}T_{1}^{2} + T_{1}T_{2}T_{1}, T_{1}T_{2}T_{1}T_{2} + T_{1}T_{2}T_{1} \end{matrix} \} .

−cba abc + cba

bac − cba acb − cba

bca + cba cab + cba

0

T_{1} T_{2} T_{2} T_{1} T_{1} T_{2} T_{1}| − 1 T_{2}| − 1 T_{2}| − 1 T_{1}| − 1 \begin{matrix}T_{1} |−1 \\ T_{2} |−1 \end{matrix}

Fig. 12 – Action de T_{i} sur ℌ_{k}^{3}(0) · (−cba) et ℌ_{k}^{3}(0) · (abc + cba).

Soit φ ∈ End_{A}(A · m) et m_{φ} ∈ A · m tel que :

m_{φ} = α_{ε}ε · m + α_{T_{1}}T_{1} · m + α_{T_{2}}T_{2} · m + α_{T_{1}T_{2}}T_{1}T_{2} · m
+ α_{T_{2}T_{1}}T_{2}T_{1} · m + α_{T_{1}T_{2}T_{1}}T_{1}T_{2}T_{1} · m

L’algorithme suffixe nous a retourné l’ensemble suffixe P et l’ensemble des relateurs R, on applique l’algorithme cons φ qui va permettre de calculer la matrice φ et l’ensemble des projecteurs. La matrice φ est la suivante :

φ = (\begin{matrix}αT_{ε} & 0 & 0 & 0 & 0 & 0 \\ α_{T1} & α_{Tε} − α_{T1} & 0 & 0 & 0 & 0 \\ α_{T2} & 0 & α_{Tε} − α_{T2} & 0 & 0 & 0 \\ α_{T1T2} & 0 & α_{T1} − α_{T1T2} & α_{Tε} − α_{T1} & 0 & 0 \\ α_{T2T1} & α_{T2} − α_{T2T1} & 0 & 0 & α_{Tε} − α_{T2} & 0 \\ α_{T1T2T1} & α_{T1T2} − α_{T1T2T1} & α_{T2T1} − α_{T1T2T1} & α_{T2} − α_{T1T2} & α_{T1} − α_{T1T2} & α_{Tε} α_{T1} − α_{T1T2} \\ & & & −α_{T2T1} & −α_{T2T1} & −α_{T1T2} − α_{T2T1} \\ & & & +α_{T1T2T1} & +α_{T1T2T1} & +α_{T1T2T1} \end{matrix} )

Une solution non-triviale du système donné par φ^{2} = φ, T · φ(m) = φ(T · m) pour tout T ∈ P et r · φ(m) = 0 pour tout r ∈ R est : m_{φ} = −T_{1}T_{2}T_{1} · m et m_{1−φ} = ε · m + T_{1}T_{2}T_{1} · m, c’est à dire m_{φ} = −cba et m_{1−φ} = abc + cba. Ce qui nous donne une première décomposition ℌ_{k}^{3}(0) · abc = −ℌ_{k}^{3}(0) · cba + ℌ_{k}^{3}(0) · (abc + cba) donnée dans la figure 12. On applique maintenant l’algorithme sur le sous-module ℌ_{k}^{3}(0) · m′ avec m′ = (abc + cba) pour voir s’il est décomposable ou non. L’ensemble suffixe est

P = {ε,T_{1},T_{2},T_{1}T_{2},T_{2}T_{1}}.

L’ensemble des relateurs est

R = \{ \begin{matrix}T_{1}T_{2}T_{1}, T_{2}T_{1}T_{2}, \\ T_{1}^{2} + T_{1}, T_{2}^{2} + T_{2}, \\ T_{1}T_{2}^{2} + T_{1}T_{2}, T_{2}T_{1}^{2} + T_{2}T_{1} \end{matrix} \} .

Soit φ ∈ End_{A}(A · m′) et m′_{φ} ∈ A · m′ tel que :

m′_{φ} = α_{ε}ε · m′ + α_{T_{1}}T_{1} · m′ + α_{T_{2}}T_{2} · m′ + α_{T_{1}T_{2}}T_{1}T_{2} · m′ + α_{T_{2}T_{1}}T_{2}T_{1} · m′.

abc + cba + cab + acb + bac + bca

−cab − acb − bac − bca

bac − cba acb − cba

bca + cba

0

T_{1} T_{2} T_{2} T_{1} |−1 T_{1} |−1 T_{1} T_{1}| − 1 T_{2}| − 1 \begin{matrix}T_{1} |−1 \\ T_{2} |−1 \end{matrix} \begin{matrix}T_{1} |−1 \\ T_{2} |−1 \end{matrix} T_{1} |−1

Fig. 13 – Action de T_{i} sur ℌ_{k}^{3}(0) · m′_{φ} et ℌ_{k}^{3}(0) · m′_{1−φ}.

ℌ_{k}^{3}(0) · abc ℌ_{k}^{3}(0) · m_{φ}  ℌ_{k}^{3}(0) · m_{1−φ} ℌ_{k}^{3}(0) · m′_{φ}  ℌ_{k}^{3}(0) · m′_{1−φ}

Fig. 14 – Décomposition complète de ℌ_{k}^{3}(0) · abc.

La matrice m′_{φ} est la suivante :

φ = (\begin{matrix}αT_{ε} & 0 & 0 & 0 & 0 \\ α_{T_{1}} & α_{T_{ε}} − α_{T_{1}} & 0 & 0 & 0 \\ α_{T_{2}} & 0 & α_{T_{ε}} − α_{T_{2}} & 0 & 0 \\ α_{T_{1}T_{2}} & 0 & α_{T_{1}} − α_{T_{1}T_{2}} & α_{T_{ε}} − α_{T_{1}} & 0 \\ α_{T_{2}T_{1}} & α_{T_{2}} − α_{T_{2}T_{1}} & 0 & 0 & α_{T_{ε}} − α_{T_{2}} \end{matrix} )

Une solution non-triviale du système donné par φ^{2} = φ, T · φ(m′) = φ(T · m′) pour tout T ∈ P et r · φ(m′) = 0 pour tout r ∈ R est m′_{φ} = −T_{1} · m′ − T_{2} · m′ − T_{1}T_{2} · m′ − T_{2}T_{1} · m′ et m′_{1−φ} = ε·m′+T_{1}·m′+T_{2}·m′+T_{1}T_{2}·m′+T_{2}T_{1}·m′, c’est à dire m′_{φ} = −cab−acb−bac−bca et m′_{1−φ} = abc+cba+cab+acb+bac+bca et la description complète de ℌ_{k}^{3}(0)·(abc+cba) est donnée dans la figure 13. La décomposition complète du ℌ_{k}^{3}(0)-module ℌ_{k}^{3}(0) · abc est donnée dans la figure 14.

8 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.

>> F:=Dom::FreeModuleTable(Dom::IntegerMod(2),combinat::words)
       Dom::FreeModuleTable(Dom::IntegerMod(2), combinat::words)

Soit f : {0,1}^{3} → {0,1} définie par f(X_{1},X_{2},X_{3}) = X_{1}X_{3} + X_{1}. On définit maintenant le module A_{3} · f comme suit :

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

Une fois qu’on a le module, on peut appliquer l’algorithme :

>> 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]}

D’après l’ensemble des projecteurs, le module A_{3} · f se décompose en A_{3} · (X_{2}X_{3} + X_{3}) et A_{3} · (X_{1}X_{2} + X_{2}). On applique le même algorithme sur les sous-modules A_{3} · (X_{2}X_{3} + X_{3}) et A_{3} · (X_{1}X_{2} + X_{2}), pour voir s’ils sont décomposables ou non :

>> 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]}

Les deux sous-modules ne sont donc pas décomposables et une somme directe pour le module A_{3} · f est

A_{3} · f = A_{3} · (X_{2}X_{3} + X_{3}) ⊕ A_{3} · (X_{1}X_{2} + X_{2})

On définit maintenant le domaine des modules sur l’algèbre de Hecke à q = 0 ℌ_{k}^{3}(0).

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

Ensuite, le module ℌ_{k}^{3}(0) · abc.

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

On applique maintenant l’algorithme pour voir si ℌ_{k}^{3}(0) · abc est décomposable ou non.

  {[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]}

D’après l’ensemble des projecteurs, et en choisissant le deuxième projecteur, le module se décompose en ℌ_{k}^{3}(0) · (−cba) et ℌ_{k}^{3}(0) · (abc + cba). On vérifie maitenant si le sous-module ℌ_{k}^{3}(0) · (abc + cba) est décomposable ou non.

>> G1:=F([1,2,3])+F([3,2,1])
                           B([1, 2, 3]) + B([3, 2, 1])
  {[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]}

Si on choisit le troisième projecteur, le sous-module ℌ_{k}^{3}(0) · (abc + cba) se décompose en ℌ_{k}^{3}(0) · (−bac − acb − bca − cab) et ℌ_{k}^{3}(0) · (abc + cba + bac + acb + bca + cab) et une somme directe du module ℌ_{k}^{3}(0) · abc est

ℌ_{k}^{3}(0) · abc = ℌ_{k}^{3}(0) · (−cba)
⊕ ℌ_{k}^{3}(0) · (−bac − acb − bca − cab)
⊕ ℌ_{k}^{3}(0) · (abc + cba + bac + acb + bca + cab).

On peut manipuler aussi la fonction suffixe qui calcule une base pour l’espace A · m et un ensemble de relateurs. Nous allons l’appliquer pour le module ℌ_{k}^{3}(0) · abc.

>> 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
                                )
           )

8.1 Cas des groupes finis : Caractères

Dans ce qui suit les espace vectoriel sont supposés sur k (= ℝ ou ℂ) et les groupes sont supposés finis.

Définition 8.1 Soit G un groupe et V un EV. On appelle représentation de G dans V une application ρ : G ↦ Aut(V) compatible avec la multiplication, c’est à dire que

(∀g_{1},g_{2} ∈ G)(ρ(g_{1}g_{2}) = ρ(g_{1}) ∘ ρ(g_{2}))  (34)

Avec cette donnée, V est appelé G-module. L’image ρ(g)[v] se note souvent g.v.

Exercice 8.2 Soit G, un groupe et ρ_{G} une représentation de l’ensemble G dans l’espace vectoriel V. Montrer que les conditions suivantes sont équivalentes :

i) ρ_{G} est une représentation du groupe G ii) ρ_{G} est une représentation du semigroupe G et ρ_{G}(1_{G}) = Id_{V}.

Selon le schema général, on dit qu’une application linéaire (k-linéaire) entre deux G-modules ϕ : V_{1} ↦ V_{2} est G-linéaire si les actions de G agissent comme des scalaires (c’est à dire permutent avec ϕ ou peuvent être “sorties” de ϕ). Si ϕ 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 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.

Exercice 8.3 Pour le module de la figure (4), écrire les matrices de transition. Montrer que ce module est irréductible. Donner la fonction trace (i.e. g → tr(ρ(g)) (voir le paragraphe (??)).

8.1.1 Un modèle qui contient toutes les représentations : la représentation régulière

Exercice 8.4 Soit G, un groupe fini. On considère la AAU A = ℂ[G] (sommes à coefficients complexes ∑_{g∈G} α_{g}g) et les opérateurs γ_{h} : ∑_{g∈G} α_{g}g → ∑_{g∈G} α_{g}h.g (= h. ∑_{g∈G} α_{g}g dans A).

1) a) Montrer que g ↦ γ_{g} est une représentation de G.

2) Soit

ℂ[G] = ⊕_{i=1..n}V_{i}  (35)

une décomposition en modules (i.e. sous espace vectoriel stables pour l’action des γ_{g}, c’est à dire les multiplications à gauche) et 1_{G} = ∑_{i=1}^{n} e_{i} la décomposition de 1_{G} selon (44)^{6}.

a) Montrer que l’on a

i) 1_{G} = ∑_{i=1}^{n} e_{i} ii) (∀i ∈ [1..n])(e_{i}e_{i} = e_{i}) iii) (∀i,j ∈ [1..n])(i ≠ j ⟹ e_{i}e_{j} = e_{j}e_{i} = 0)

b) Inversement, montrer que, si une famille d’éléments de ℂ[G] vérifie (ex 8.4.2.a), on a (44) avec V_{i} = ℂ[G]e_{i}.

Commentaire. — Une famille (e_{i})_{i=1..n} d’idempotents qui vérifie les conditions de l’exercice (8.4) est appelée FCIO, famille complète d’idempotents orthogonaux. Si, de plus, les modules Ae_{i} sont irréductibles, cette famille est appelée FCIOM, famille complète d’idempotents orthogonaux minimaux. ♢

Exercice 8.5 Utiliser l’exercice (3.11) pour montrer que, dans A = ℂ[G], on peut toujours construire une FCIOM.

Exercice 8.6 (Cette version “effective” du théorème de Wedderburn est due à Marianne Flouret [22])

1) a) Soient e,f ∈ A deux idempotents, montrer que la formule

ϕ_{fae}(x) = xfae  (36)

définit un élément de Hom_{G}(Af,Ae).

b) Montrer que la correspondance fae → ϕ_{fae}(x), fAe ↦ Hom_{G}(Af,Ae) est un isomorphisme d’espace vectoriel s.

c) En déduire que, si Ae et Af sont irréductibles, fAe soit de dimension 0 (si Ae et Af ne sont pas du même type) soit de dimension 1 (si Ae et Af sont du même type).

2) Soit (e_{1}^{(1)}, ⋯ e_{n_{1}}^{(1)},e_{1}^{(2)}, ⋯ e_{n_{2}}^{(2)}, · · · · · · ,e_{1}^{(k)}, ⋯ e_{n_{k}}^{(k)}) une FCIOM rangés selon les types des Ae_{i}^{(j)}. Pour chaque bloc e_{1}^{(j)}, ⋯ e_{n_{j}}^{(j)}, et chaque l ∈ [1..n_{j} − 1] on prend un élément e_{l}^{(j)}a_{l}^{(j)}e_{l+1}^{(j)} tel que ≠ 0 (on rappelle que pour deux idempotents e,f de la liste, on a

dim(fAe) = [e et f 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 ≤ l < m ≤ n_{j}

E_{l,m}^{(j)} = E_{l,l+1}^{(j)}E_{l+1,l+2}^{(j)} ⋯ E_{m−1,m}^{(j)}  (37)

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 ≤ m ≤ l ≤ n_{j}

E_{l,m}^{(j)} = E_{l,l+1}^{(j)}E_{l+1,l+2}^{(j)} ⋯ E_{n_{j}−1,n_{j}}^{(j)}E_{n_{j},1}^{(j)}E_{1,2}^{(j)}E_{2,3}^{(j)} ⋯ E_{m−1,m}^{(j)}  (38)

6. On dit aussi résolution de l’unité.

a) Montrer que les E_{l,m}^{(j)} forment un système d’unités matricielles c’est à dire que

E_{a,b}^{(j)}E_{c,d}^{(j)} = [b = c]E_{a,d}^{(j)}  (39)

et que E_{a,a}^{(j)} = e_{a}(j)

b) Montrer que la famille (E_{a,b}^{(j)})_{1≤j≤k⊤1≤a,b≤n_{j}} est une base de ℂ[G].

8.1.2 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ômes^{7}. Cette construction repose sur l’emboîtement des groupes symétriques

𝔖_{0} ⊂ 𝔖_{1} ⊂ 𝔖_{2} ⊂ ⋯ ⊂ 𝔖_{n} ⊂ 𝔖_{n+1} ⋯  (40)

Exercice 8.7 (Ici, k = ℝ et G est un groupe fini) Soit V, un G-module de dimension finie. On dit qu’un produit scalaire ⟨.|.⟩ sur V est invariant par G si

(∀g ∈ G)(∀u,v ∈ V)(⟨g.u|g.v⟩ = ⟨u|v⟩)  (41)

1) Montrer que si W ⊂ V est stable, il en est de même de W^{⊥}.

2) Reprendre l’exercice précédent avec k = ℂ et un produit scalaire hermitien.

3) Montrer, d’une autre façon que dans l’exercice (8.4), que la représentation régulière contient toutes les représentations. On munit A = ℂ[G] de

⟨∑_{g∈G} α g| ∑_{g∈G} β g⟩ = ∑_{g∈G} ᾱβ.  (42)

3) a) Vérifier que (42) 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

(∀g ∈ G)(∀ u,v ∈ A)(⟨u|v⟩ = ⟨γ_{g}(u)|γ_{g}(v)⟩)  (43)

(c’est à dire que ce produit scalaire est invariant, voir l’exercice (8.7)).

c) En déduire qu’il existe une décomposition de type (44) en sous-modules irréductibles (les idempotents correspondants seront dits minimaux).

4) a) Soit U un G-module irréductible et x une de ses vecteurs non nuls. Soit

ann(x) = {h ∈ ℂ[G] | h.x = 0}.

Montrer que ann(x)^{⊥} est un sous module de ℂ[G] (en tant que G-module à gauche) et que U ≃ ann(x)^{⊥}.

b) Soit ℂ[G] = ⊕_{i=1}^{n}V_{i} une décomposition en sous-modules irréductibles. Montrer qu’il existe un indice j ∈ [1..n] (et un seul) tel que

ℂ[G] = (⊕_{i=1..j−1}V_{i}) ⊕ (ann(x)^{⊥}) ⊕ (⊕_{i=j+1..n}V_{i})  (44)

c) En déduire que ℂ[G] contient (au moins) une copie de chaque représentation irréductible de G.

5) Ici G = 𝔖_{n}. On considère, dans ℂ[G], les éléments de Jucys-Murphy (x_{m})_{2≤m≤n} (voir [35] et [36]) définis par

7. Version simplifiée de la construction que l’on peut trouver dans la thèse d’Éric Laugerotte[21].

x_{m} = ∑_{i=1}^{m−1} σ_{(i,m)} où σ_{(i,m)} est la transposition de i et de m.  (45)

a) Montrer les relations suivantes. a1) Si i,j ∈ [2..n] tels que i < j − 1,

[σ_{i},x_{j}] = 0.  (46)

a2) Si i = j − 1,

σ_{j−1}x_{j} = 1 + x_{j−1}σ_{j−1}  (47)

a3)

x_{j}σ_{j−1} = 1 + σ_{j−1}x_{j−1}.  (48)

b) Déduire des relations 46, 47 et 48, la relation de commutation

[x_{i},x_{j}] = 0.  (49)

Fig. 15 – Le diagramme de Ferrers de (5,4,3,1).

Les modules irréductibles sur 𝔖_{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 tableau de Young.

On désigne par t un tableau de Young (voir [12], [39] ou [40]) de forme λ, un remplissage du diagramme de Ferrers de forme λ par des lettres appartenant à un alphabet {a_{1},a_{2} …}, ordonné par (a_{1} < a_{2} < ⋯), 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énéralité, de prendre comme alphabet l’ensemble [1..n] muni de l’ordre usuel sur les entiers. Précisons l’action des x_{m} sur H_{ℚ(q)}^{n}(q). Les GZ-polynômes, indexés par les tableaux de Young et notés GZ_{t}, seront définis récursivement comme suit,

GZ_{t} = \{ \begin{matrix}1 & si t est de poids 1, \\ GZ_{t−n} × ∏_{{t′−n=t−n \atop t′≠t}} \frac{X_{n} − χ_{t′}(n)}{χ_{t}(n) − χ_{t′}(n)} & si t est de poids n. \end{matrix}

Théorème 8.8 Posons t ∈ Tab(n), GZ_{t} (x_{2},x_{3}, …,x_{n}) = g_{t}. Alors (g_{t})_{t∈Tab(n)} est une FCIOM de ℂ[𝔖_{n}] (qui est d’ailleurs dans ℚ[𝔖_{n}]).

9 6 2 1  10 5 3  11 7 4  13 8  12

Fig. 16 – Un tableau de Young de forme (5,4,3,1).

9 6 2 1 10 5 3 11 7 4 13 8 12 -3 -2 -1 0 1 2 3 4

Fig. 17 – Les diagonales d’un tableau de Young.

Preuve Soit h_{t} l’évaluation du polynôme GZ_{t} en (x_{2},x_{3}, …,x_{n}). Quand n = 2, les GZpolynômes sont les suivants,

\begin{aligned}GZ_{(1,1)^{c}} & = & \frac{−1}{2} (X_{2} − 1) , \\ GZ_{(2)^{c}} & = & \frac{1}{2} (X_{2} + 1) . \end{aligned}

À l’aide de quelques calculs simples, on montre que

\begin{aligned}χ_{(1,1)^{c}} (h_{(1,1)^{c}}) & = & 1, \\ χ_{(2)^{c}} (h_{(1,1)^{c}}) & = & 0, \\ χ_{(1,1)^{c}} (h_{(2)^{c}}) & = & 0, \\ χ_{(2)^{c}} (h_{(2)^{c}}) & = & 1. \end{aligned}

On suppose maintenant n > 2. Pour tout tableau de Young t ∈ Tab(n), on déduit de la formule du polynôme GZ_{t} que, si t_{0} ∈ Tab(n),

χ_{t_{0}} (h_{t}) = χ_{t_{0}} (h_{t−n}) χ_{t_{0}} ( ∏_{{t′−n=t−n \atop t′≠t}} \frac{x_{n} − χ_{t′}(x_{n})}{χ_{t}(x_{n}) − χ_{t′}(x_{n})}) .

Comme X_{n} n’intervient pas dans l’expression du polynôme GZ_{t−n}, on a

χ_{t_{0}} (h_{t−n}) = χ_{t_{0}−n} (h_{t−n}) .

Par conséquent,

χ_{t_{0}} (h_{t}) = χ_{t_{0}−n} (h_{t−n}) ∏_{{t′−n=t−n \atop t′≠t}} \frac{χ_{t_{0}} (x_{n}) − χ_{t′}(x_{n})}{χ_{t}(x_{n}) − χ_{t′}(x_{n})}.

Si t_{0} = t, χ_{t} (h_{t}) = χ_{t−n} (h_{t−n}) = 1 par induction. Si t_{0} ≠ t et t_{0} − n = t − n, par construction on a χ_{t_{0}} (h_{t}) = 0. Si t_{0} ≠ t et t_{0} − n ≠ t − n, χ_{t_{0}−n} (h_{t−n}) = 0 par induction, et ainsi χ_{t_{0}} (h_{t}) = 0. △

Cette famille vérifie une relation dont l’importance sera mise en évidence lorsque l’on discutera de l’efficacité du calcul.

Proposition 8.9 Les éléments de la FCIOM (g_{t})_{t∈Tab(n)} vérifient

g_{t} = ∑_{{t′∈Tab(n+1) \atop t′−(n+1)=t}} g_{t′}.  (50)

Preuve Soit s_{t} = ∑_{{t′∈Tab(n+1) \atop t′−(n+1)=t}} g_{t′}. D’après le théorème 8.8, on a

g_{t}s_{t} = g_{t} ∑_{{t′∈Tab(n+1) \atop t′−(n+1)=t}} g_{t} ∏_{{t”−(n+1)=t′−(n+1) \atop t”≠t′}} \frac{x_{n+1} − χ_{t”}(x_{n+1})}{χ_{t′}(x_{n+1}) − χ_{t”}(x_{n+1})}

= ∑_{{t′∈Tab(n+1) \atop t′−(n+1)=t}} g_{t} ∏_{{t”−(n+1)=t′−(n+1) \atop t”≠t′}} \frac{x_{n+1} − χ_{t”}(x_{n+1})}{χ_{t′}(x_{n+1}) − χ_{t”}(x_{n+1})}
= s_{t}.

De même, g_{t′}s_{t} = 0 si t′ est un tableau de poids n distinct de t. Cependant

∑_{t∈Tab(n)} s_{t} = ∑_{t∈Tab(n+1)} g_{t} = 1  (51)

ce qui prouve que g_{t} = s_{t}. △

Sans évaluer, les GZ-polynômes satisfont deux importantes relations.

Proposition 8.10 Les GZ-polynômes vérifient

GZ_{t} = ∑_{{t′∈Tab(n+1) \atop t′−(n+1)=t}} GZ_{t′},  (52)

∑_{t∈Tab(n)} GZ_{t} = 1.  (53)

Preuve La relation (52) est déduite de la définition récursive des GZ-polynômes et de la relation formelle

∑_{i=1}^{m} ∏_{j≠i} \frac{X − a_{j}}{a_{i} − a_{j}} = 1

qui est vraie pour toute famille (a_{1},a_{2}, …,a_{m}) de scalaires distincts. La relation (53) est une application directe de (52). △ 8.1.3 Étude rapide de la complecité du calcul

On constate que les formules des GZ-polynômes sont moins “complexes” que les formules des polynômes DJ obtenues par l’interpolation de Lagrange. On peut fixer deux opérations élémentaires qui sont l’addition d’éléments de la forme σ ∈ 𝔖_{n} et le produit d’un générateur σ_{i} et de σ. Comme T_{(i,m)} (transposition de i et de m) se décompose en σ_{i} ⋯ σ_{m−2}σ_{m−1}σ_{m−2} ⋯ σ_{i}, le produit x_{m}σ nécessite au minimum (m − 1)m opérations élémentaires. La proposition suivante montre que les polynômes GZ_{t} sont minimaux en la variable X_{n} qui est la plus coûteuse en calculs lors de l’évaluation en les q- analogues de Jucys-Murphy. On note deg_{i}(Q) le degré du polynôme Q en X_{i}.

Proposition 8.11 Si Q_{t} ∈ k[X_{i}]_{1<i≤n} vérifie Q_{t} (x_{2},x_{3}, …,x_{n}) = g_{t} alors

deg_{n}(Q_{t}) ≥ deg_{n} (GZ_{t}) .  (54)

De plus, si on a égalité,

Q_{t} = ∏_{{t′−n=t−n \atop t′≠t}} \frac{X_{n} − χ_{t′} (x_{n})}{χ_{t} (x_{n}) − χ_{t′} (x_{n})} × Q_{t−n} + R  (55)

avec Q_{t−n} ∈ k[X_{i}]_{1<i≤n−1}, deg_{n}(R) < deg_{n}(Q_{t}) et

R (x_{2},x_{3}, …,x_{n}) g_{t−n} = 0.  (56)

Preuve On peut supposer que Q_{t} = ∑_{i=0}^{m} X_{n}^{i}Q_{i} où Q_{j} ∈ k[X_{i}]_{1<i≤n−1}. Puisque l’évaluation de Q_{t} en les éléments de Jucys-Murphy est g_{t}, on a

δ_{t t′} = χ_{t′} (Q_{t} (x_{2},x_{3}, …,x_{n}))
= ∑_{i=0}^{m} χ_{t′}^{i} (x_{n}) χ_{t−n} (Q_{i} (x_{2},x_{3}, …,x_{n−1}))
= χ_{t−n} (Q_{t} (x_{2},x_{3}, …,x_{n−1},X_{n})) (χ_{t′} (x_{n}))

ce qui prouve que le polynôme χ_{t−n} (Q_{t} (x_{2},x_{3}, …,x_{n−1},X_{n})) est un polynôme d’interpolation L correspondant aux équations

L (χ_{t′} (x_{n})) = δ_{t t′}  (57)

dont le degré en X_{n}, qui est m, est par conséquent nécessairement supérieur ou égal au nombre de tableaux de Young t′ ≠ t tel que t′−n = t−n (le polynôme χ_{t−n} (GZ_{t} (x_{2},x_{3}, …,x_{n−1},X_{n})) étant le polynôme d’interpolation de Lagrange correspondant aux équations 57).

Enfin, l’égalité 55 est obtenue en effectuant la division euclidienne de Q_{t} par ∏_{{t′−n=t−n \atop t′≠t}} \frac{X_{n} − χ_{t′} (x_{n})}{χ_{t} (x_{n}) − χ_{t′} (x_{n})}

avec deg_{n}(R) < deg_{n} (Q_{t}). Le fait que deg_{n} (Q_{t}) = deg_{n} (GZ_{t}) montre que Q_{t−n} est indépendant de X_{n}, ce qui entraîne, par comparaison du terme dominant avec le polynôme d’interpolation de Lagrange que

χ_{t} (Q_{t−n} (x_{2},x_{3}, …,x_{n−1})) = 1.  (58)

En effet, si t′ est un tableau de Young distinct de t mais tel que t′ − n = t − n, on a

χ_{t′} (R (x_{2},x_{3}, …,x_{n−1},X_{n})) (χ_{t′} (x_{n})) = χ_{t′} (R (x_{2},x_{3}, …,x_{n−1},x_{n}))
= χ_{t′} (Q_{t} (x_{2},x_{3}, …,x_{n−1},x_{n}))
= 0.

Le polynôme χ_{t′} (R (x_{2},x_{3}, …,x_{n−1},X_{n})) est donc divisible par le polynôme ∏_{{t′−n=t−n \atop t′≠t}} (X_{n} − χ_{t′}(x_{n})) et ainsi

χ_{t′} (R (x_{2},x_{3}, …,x_{n−1},X_{n})) = 0  (59)

vu la condition sur deg_{n}(R). Comme (toujours pour t − n = t′ − n) on a χ_{t} ≡ χ_{t′} sur J M_{k}^{n−1}, on en déduit la relation 58 mais cela montre aussi la relation 56 en vertu des propositions ?? et 8.9. △

On attire l’attention sur l’efficacité du calcul des idempotents g_{t} par les GZ-polynômes. Ainsi ce calcul a une meilleure complexité, en considérant les opérations élémentaires mentionnées précédemment, que par les formules de R. Dipper et G. James. Pour tout tableau de Young t de poids n > 1,

\{ \begin{matrix}deg_{i} (DJ_{t}) ≥ deg_{i} (GZ_{t}) & si i = 2, \\ deg_{i} (DJ_{t}) > deg_{i} (GZ_{t}) & si 2 < i ≤ n. \end{matrix}

Si i = 2,

deg_{2} (DJ_{t}) = \frac{1}{2} ∑_{|λ|=n} n_{λ} ≥ 1 = deg_{2} (GZ_{t})

avec l’égalité quand n = 2. Si 2 < i ≤ n, on note t_{i} le tableau de Young de poids i obtenu en retirant de t les cellules numérotées par un nombre supérieur à i. On trouve deg_{i} (DJ_{t}) > deg_{i} (GZ_{t}) car

deg_{i} (DJ_{t}) = deg_{i} ( ∏_{{t′∈Tab(n) \atop χ_{t′}(i)≠χ_{t}(i)}} \frac{X_{i} − χ_{t′}(x_{i})}{χ_{t}(x_{i}) − χ_{t′}(x_{i})})

= deg_{i} ( ∏_{{t′∈Tab(i) \atop χ_{t′}(i)≠χ_{t}(i)}} \frac{X_{i} − χ_{t′}(x_{i})}{χ_{t}(x_{i}) − χ_{t′}(x_{i})})

et

deg_{i} (GZ_{t}) = deg_{i} ( ∏_{{t′−i=t_{i}−i \atop t′≠t_{i}}} \frac{X_{i} − χ_{t′}(x_{i})}{χ_{t}(x_{i}) − χ_{t′}(x_{i})}) .

9 Traces

10 Liminaire

Nous utiliserons plus tard le résultat général suivant :

Proposition 10.1 Soit A et B deux algèbres semi-simples de dimensions finies. On suppose que A est une sous-algèbre de B et on dénote par C le centralisateur de A dans B. Si V est un A-module irréductible et W un B-module irréductible, alors Hom_{A}(V,Res_{A}W) est un C-module irréductible.

Cette proposition est valide en caractéristique quelconque, mais nous ne l’appliquerons qu’au cas de deux algèbres semi-simples sur ℂ.

11 Bases et algèbres de Gelfand-Tsetlin

Dans ℂ𝔖_{n}, on définit pour k = 1, …,n, le k^{e} élément de Young-Jucys-Murphy (YJM) par :

L_{k} := ∑_{1≤m<k}(m,k),

où (m,k) désigne la transposition échangeant m et k. Exercice. Les éléments de YJM commutent. On dénote par Z_{n} le centre de ℂ𝔖_{n}, et par Z_{m,n} le commutant de ℂ𝔖_{m} dans ℂ𝔖_{n}, si m ≤ n. Exercice. Les sommes de 𝔖_{m}-classes de conjugaison dans 𝔖_{n} forment un système générateur de Z_{m,n}.

Proposition 11.1 Z_{m,n} = ⟨S′_{m},Z_{n},L_{m+1}, …,L_{n}⟩.

On est maintenant en mesure de donner la règle de branchement pour la tour d’algèbres

ℂ𝔖_{0} ⊂ ℂ𝔖_{1} ⊂ ⋯ ⊂ ℂ𝔖_{n} ⊂ ℂ𝔖_{n+1} ⊂ ⋯

Théorème 11.2 Soit W un ℂ𝔖_{n+1}-module irréductible et V un ℂ𝔖_{n}-module irréductible. Alors la multiplicité de V dans la décomposition de Res_{ℂ𝔖_{n}}W en somme directe de modules est 0 ou 1.

Démonstration. Soit W un ℂ𝔖_{n}-module irréductible. Il découle de la proposition 11.1 que le centralisateur de ℂ𝔖_{n} dans ℂ𝔖_{n+1} est commutatif. Tous ses modules irréductibles non triviaux sont donc de dimension 1. La proposition 10.1 entraîne donc que la dimension de Hom_{ℂ𝔖_{m}}(W,Res_{ℂ𝔖_{n}}V) est 0 ou 1. △ Il reste maintenant à décrire le graphe de branchement, désigné (temporairement) par 𝔹. On va démontrer qu’il s’agit en réalité du graphe de Young 𝕐, c’est-à-dire du diagramme de Hasse du treillis des partitions (ou diagrammes de Young) ordonnées par inclusion.

Soit V un ℂ𝔖_{n}-module irréductible. Soit ⟨·,·⟩ le produit intérieur 𝔖_{n}-invariant sur V (ce produit est unique à un scalaire près). Le théorème 11.2 implique que la décomposition

Res_{ℂ𝔖_{n−1}}V = ⨁_{W →V} W

(on somme sur tous les ℂ𝔖_{n}-modules pour lesquels il existe un arc de W vers V dans le graphe de branchement) est canonique. En itérant le processus jusqu’à 𝔖_{0}, on obtient une décomposition canonique

Res_{ℂS_{0}}V = ⨁_{T} V_{T}

en sous-espaces de dimension 1 V_{T}, où T décrit l’ensemble des chemins W_{0} → ⋯ → W_{n} = V dans le graphe de branchement. Exercice. ℂS_{k} · V_{T} = W_{k}, pour tout k, 0 ≤ k ≤ n. En choisissant un vecteur v_{T} dans chaque V_{T}, on obtient une base {v_{T} } appelée base de Gelfand-Tsetlin (en abrégé, base de GZ). Cette base est déterminée de façon unique (à des scalaires près). En outre, si φ : V → W est un isomorphisme de modules irréductibles, alors φ envoie une base de GZ sur une base de GZ. Exercice. Toute base de GZ est orthogonale pour le produit intérieur ⟨·,·⟩. D’après le théorème de Wedderburn, ℂ𝔖_{n} se décompose en

ℂ𝔖_{n} = ⨁_{V} End_{ℂ}(V)  (60)

(on somme sur les classes d’équivalence de ℂ𝔖_{n}-modules irréductibles). Cette décomposition est canonique. Si on choisit une base de GZ dans chaque V. Relativement à ces bases, on a naturellement

ℂ𝔖_{n} = ⨁_{V} M_{dimV} (ℂ).  (61)

On définit la (sous-)algèbre de Gelfand-Tsetlin GZ(n) ⊂ ℂ𝔖_{n} constituée de tous les éléments de ℂ𝔖_{n} qui sont diagonaux pour toute base de GZ dans chaque ℂ𝔖_{n}-module irréductible. Dans les termes de la décomposition 61, GZ(n) est constituée de toutes les matrices diagonales. On en déduit :

Proposition 11.3 GZ(n) est une sous-algèbre commutative maximale de ℂ𝔖_{n}. C’estégalement une algèbre semi-simple.

Proposition 11.4 (i) GZ(n) = ⟨Z_{0},Z_{1}, …,Z_{n}⟩; (ii) GZ(n) = ⟨L_{1},L_{2}, …,L_{n}⟩.

Démonstration. (i) Soit e_{V} ∈ Z_{n} l’idempotent central associé au ℂ𝔖_{n}-module irréductible V ; il agit comme l’identité sur V, et comme 0 sur tout ℂ𝔖_{n}-module irréductible non isomorphe à V (relativement à la décomposition 60, e_{V} est l’endomorphisme identité sur la composante V et l’endomorphisme nul sur les autres composantes). Si T est un chemin W_{0} → W_{1} → ⋯ → W_{n} = V dans 𝔹, alors

e_{W_{0}}e_{W_{1}} ⋯ e_{W_{n}} ∈ Z_{0}Z_{1} ⋯ Z_{n}

agit sur V comme la projection sur V_{T} suivant ⨁_{S≠T} et sur tout ℂ𝔖_{n}-module irréductible V′ ≅ V, comme 0. La sous-algèbre engendrée par les centres Z_{0},Z_{1}, …,Z_{n} contient donc GZ(n). Or ⟨Z_{0},Z_{1}, …,Z_{n}⟩ est commutative et GZ(n) est une sous-algèbre commutative maximale de ℂ𝔖_{n}, donc les deux sous-algèbres coïncident. (ii) △ On va maintenant faire jouer à GZ(n) le rôle d’une sous-algèbre de Cartan. Comme GZ(n) est semi-simple, on peut décomposer tout ℂ𝔖_{n}-module irréductible V en une somme directe d’espaces (simultanément) propres pour les éléments de YJM L_{1}, …,L_{n}. Si λ = (λ_{1}, …,λ_{n}) ∈ ℂ^{n} et si V_{λ} désigne l’espace (simultanément) propre pour les L_{1}, …,L_{n} correspondant aux valeurs prores λ_{1}, …,λ_{n}, alors on dit que λ est un poids de V et que V_{λ} est l’epace de poids λ.

Les vecteurs d’une base de GZ sont des poids (par définition). D’autre part, d’après la décomposition 61, GZ(n) est constituée de toutes les matrices diagonales, donc les espaces de poids sont de dimension 1 ; ce sont donc exactement les droites engendrées par les éléments d’une base de GZ. On remarque aussi que si λ est un poids d’un module irréductible V, ce ne peut être le poids d’aucun module irréductible non isomorphe à V. On obtient ainsi, à travers les bases de Gelfand-Tsetlin, une bijection entre les poids (pour tous les groupes symétriques) et tous les chemins démarrant à la racine dans le graphe de branchement. On désigne par λ_{T} le poids associé au chemin T et par T_{λ} un chemin associé au poids λ; on abrège v_{T_{λ}} en v_{λ}. Un chemin T se termine au sommet V ssi le poids associé λ_{T} est un poids de V. Il est maintenant évident que pour décrire le graphe de branchement 𝔹, il suffit de décrire les ensembles

W (n) = {λ ∈ ℂ^{n} | λ est un poids d’un ℂ𝔖_{n}-module} (n ≥ 0)

et la relation d’équivalence sur

λ ≈ μ ⇔ λ et μ sont des poids du même ℂ𝔖_{n}-module irréductible

En effet, on remarque que

𝔹 = ⋃_{n≥0}(W (n)/ ≈)

et que, pour toutes toutes [λ] et [μ], respectivement classes d’équivalence de λ ∈ W (n − 1) et de μ ∈ W (n), on a [λ] → [μ] dans 𝔹 ssi il existe un poids ν = (nu_{1}, …,nu_{n}) tel que ν ≈ μ et λ = (λ_{1}, …,λ_{n−1}). Anticipons un peu sur la suite : les éléments de W (n)/ ≈) seront étiquetés par les partitions α ⊢ n et ceux de W (n) par les tableaux standard de forme α; deux tableaux seront équivalents ssi ils ont la même forme. Plus précisément, si T est un tableau standard de forme α, le poids associé λ peut être reconstruit de la façon suivante : λ_{i} est le contenu de la case de α où apparaît i.

12 Description des poids

12.1 Modules de l’algèbre de Hecke affine dégénérée H_{2}

En notant s_{i} la transposition élémentaire échangeant i et i + 1, on a les relations :

s_{i}Li_{i} = L_{i+1}s_{i} − 1, s_{i}L_{j} = L_{j}s_{i} (j ≠ i,i + 1)

De la deuxième relation, on tire Proposition 12.1 Soit λ = (λ_{1}, …,λ_{n}) ∈ W (n), et 1 ≤ k < n. Alors s_{k}v_{λ} est une combinaison linéaire de vecteurs v_{μ} tels que μ_{i} = λ_{i} pour i ≠ k,k + 1. Le rôle de sl_{2} est joué par les B_{i} := ⟨L_{i},L_{i+1},s_{i}⟩. Chaque B_{i} est un quotient de l’algèbre

⟨_{2} = ⟨s,x,y | xy = yx,s^{2} = 1,sx = ys − 1⟩.

Proposition 12.2 (... description des irreps de ⟨_{2} ...) .

Corollaire 12.3 Soit

De ce qui précèdeon tire :

Proposition 12.4 Soit λ ∈ W (n). Alors :

(i) λ_{1} = 0 ; (ii) {lambda_{i} − 1,λ_{i} + 1} ∩ {λ_{1}, …,λ_{i−1}} ≠ ∅ pour tout i, 2 ≤ i ≤ n; (iii) Si λ_{i} = λ_{j} = a pour un certain couple i < j, alors

{a_{1},a + 1} ⊂ {λ_{i+1}, …,λ_{j−1}}.

12.2 Le graphe de Young est le graphe de branchement

On rappelle que le graphe de Young 𝕐 est le graphe gradué dont l’ensemble des sommets est l’ensemble P des partitions (représentées par leur diagramme de Young), et dont les arcs relient tout diagramme de Young à ceux qui sont obtenus en ajoutant une case. La composante de rang n du graphe est donc l’ensemble P(n) des partitions de poids n (en particulier, la composante de rand 0 est constituée de l’unique diagramme vide ∅). Les chemins de ∅ à un sommet α dans 𝕐 sont en bijection avec les tableaux standard de forme α. À tout tableau standard T de forme alpha, correspondant au chemin ∅ = T_{0},T_{1}, …,T_{n} = α, on associe le vecteur de contenu cont(T), aussi noté λ_{T}, défini par

λ_{T} = (cont(T_{1}), …,cont(T_{n})) ∈ ℤ^{n}

où cont(T_{i}) désigne le contenu (i.e. le n^{o} de la diagonale) de la case ajoutée à T_{i−1} pour obtenir T_{i}.

On pose W′(n) := {λ_{T} | T est un tableau standard dont la forme ∈ P(n)}. Il est facile de retrouver la forme α à partir du vecteur λ_{T} : le nombre de cases dans la diagonale de n^{o} a du diagramme de Young α est le nombre de composantes de λ_{T} égales à a. Ainsi deux n-uplets λ,μ ∈ W′(n) proviennent de tableaux de même forme ssi l’un est image de l’autre par une permutation, ce qu’on note λ ∼ μ.

Lemme 12.5 L’ensemble W′(n) est exactement l’ensemble de tous les n-uplets λ ∈ ℂ^{n} qui satisfont les propriétés (i)–(iii) de la proposition 12.4. On en déduit W (n) ⊂ W′(n).

Soit ν = (ν_{1}, …,ν_{n}) ∈ ℂ^{n}. Une transposition admissible pour ν est une transpositionélémentaire s_{i} ∈ 𝔖_{n} correspondant à un couple ν_{i},ν_{i+1} tel que |ν_{i} − ν_{i+1}| ≠ 1. Si ν = λ_{T}, une transposition admissible échange 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ême forme. Soit α = (α_{1} ≥ ⋯ ≥ α_{k} > 0) ∈ P(n). Le tableau canonique de forme α, noté T (α), est obtenu en remplissant chaque ligne de gauche à droite, en commençant par la première ligne.

Lemme 12.6 Soit α ∈ P(n). Si T est un tableau standard de forme α, alors il existe une suite de transpositions admissibles qui transforme T en T (α). En outre, on peut choisir les transpositions admissibles s_{i_{1}}, …,s_{i_{ℓ}} de telle sorte que ℓ = ℓ(s_{i_{1}} ⋯ s_{i_{ℓ}}).

Lemme 12.7 Si λ ∈ W′(n) et s’il existe μ ∈ W (n) tel que λ ∼ μ, alors λ ∈ W (n) et λ ≈ μ.

On touche enfin au but :

Théorème 12.8 W (n) = W′(n). En outre, λ_{T} ≈ λ_{S} ⇔ les tableaux T et S on la même forme ⇔ λ_{T} ∼ λ_{S}. On en conclut que le graphe de branchement 𝔹 est isomorphe au graphe de Young 𝕐.

13 Formules de Murnaghan-Nakayama 14 Annexe A: Automates

14.1 Description de la structure d’automate

14.1.1 Graphe pondéré

L’élément de base de ces graphes est la flêche A = q_{1} →^{a|α} q_{2} avec q_{i} ∈ Q, a ∈ §, α ∈ k où Q est un ensemble d’états, § un alphabet et k, un semi-anneau^{8}. Pour un tel objet, on définit, selon les conventions générales de la théorie des graphes,

• t(A) := q_{1} (“tail”: queue, source, origine)

• h(A) := q_{2} (“head” tête, but, extrémité)

• l(A) := a (“label” étiquette)

• w(A) := α (“weight” poids). Un chemin est une suite d’arêtes c = A_{1}A_{2} ⋯ A_{n} (c’est un mot en les arêtes et sa longueur est n) telle que h(A_{k}) = t(A_{k+1}) pour 1 ≤ k ≤ n − 1 pour un tel chemin t(c) = t(A_{1}), h(c) = h(A_{n}), l(c) = l(A_{1})l(A_{2}) ⋯ l(A_{n}) (concaténation), w(c) = w(A_{1})w(A_{2}) ⋯ w(A_{n}) (produit dans le semi-anneau). Par exemple pour le chemin de longueur 3 suivant (k = ℕ),

u = p →^{a|2} q →^{b|3} r →^{c|5} s  (62)

on a t(u) = p, h(u) = s, l(u) = abc, h(u) = 30. Le poids d’un ensemble de chemins de même source, but et étiquette est la somme des poids des chemins de cet ensemble. Ainsi, si

q1  →^{u|α} ; →^{u|β}  q2  (63)

le poids de cet ensemble de chemins est α + β. On a donc que les poids se multiplient en série et s’aditionnent en parallèle. Les diagrammes suivants montrent la nécessité des axiomes de semi-anneau.

8. Nous verrons plus bas que les axiomes de la structure de semi-anneau sont contraints par la définition même du système de transitions ainsi obtenu.

Diagramme  Identité  Nom

→^{a|α}

p →^{a|β} q  α + (β + γ) = (α + β) + γ Associativité de +

→^{a|γ}

p →^{a|α} ; →^{a|β}q  α + β = β + α  Commutativité de +
p →^{a|α} ; →^{a|0}q  α + 0 = α  Élément neutre (droite) de +
p ^{a|0} q →^{b|β} r  0 + β = α  Élément neutre (gauche) de +
p →^{a|α} q →^{b|β} r →^{c|γ} s α(βγ) = (αβ)γ  Associativité de ×
p →^{a|α} ; →^{a|β}q →^{b|γ} r  (α + β)γ = αγ + βγ  Distributivité (droite) de × sur +
p →^{a|α} q →^{b|β} ; →^{b|γ}r  α(β + γ) = αβ + αγ  Distributivité (gauche) de × sur +
p →^{a|α} q →^{b|1_{k}} r  α × 1_{k} = α  Élément neutre (droite) de ×
p →^{a|1_{k}} q →^{b|β} r  1_{k} × β = β  Élément neutre (gauche) de ×

14.1.2 Structure et comportement des automates

Un automate à poids ou pondéré (“automaton with weights”) est la donnée de trois éléments vectoriels (I,M,T):

• Un vecteur d′entrée I ∈ k^{1×Q}
• Une famille (indexée à A) de matrices de transition M : A → k^{Q×Q}
• Un vecteur de sortie T ∈ k^{Q×1}

La donnée des transitions (M) est équivalente à celle d’un graphe pondéré dont les sommets sont Q, l’alphabet A et les poids sont pris dans k. De plus celle de I (resp. T) correspond à la donnée de flêches rentrantes (resp. sortantes) marquées avec des poids. Dans tout ce processus, on peut ne pas indiquer les flêches de poids nul. Ce type d’automates généralise les automates (booléens) de la théorie des langages (que l’on obtient alors pour k = 𝔹) est une machine qui prend un mot en entrée et retourne un coefficient (dans k) en sortie. Son comportement est donc une fonction A : A^{∗} → k (que l’on peut noter, de manière équivalente, comme une série A = ∑_{w∈A^{∗}} A(w)w). Calcul du poids A(w). — On étend d’abord la fonction de transition M à A^{∗} par

M(ϵ) = I_{Q×Q}, M(w) = M(a_{1}a_{2} ⋯ a_{n}) = M(a_{1})M(a_{2} ⋯ M(a_{n})  (64)

où I_{Q×Q} est la matrice identité de format Q × Q. Le calcul du poids d’un mot est alors, par définition,

A(w) := IM(w)T  (65)

d’après la règle de multiplication des matrices, on a bien que IM(w)T est une matrice de format 1 × 1 et donc un élément de k. Le lien avec le graphe de l’automate est donné par la proposition suivante : Proposition 14.1 Soit, pour deux états r,s et un mot w ∈ A^{∗}

A^{r,s}(w) := I_{r} ( ∑_{\overline{t(c)=r, h(c)=s}^{c, chemin l(c)=w}} weight(c)) T_{s}  (66)

alors

A(w) = ∑_{r,s∈Q} A^{r,s}(w)  (67)

Cette proposition a le sens intuitif suivant :

1. l’équation (66) donne le poids calculé comme au paragraphe précédent

• on fait le bilan parallèle (c’està dire une somme) des poids des chemins qui joingnent

r à s

2. on multiplie (à gauche si c’est non commutatif) par le poids d’entrée en r

3. on multiplie (à droite si c’est non commutatif) par le poids de sortie en s

14.1.3 Exemples de fonctions produites par des automates

1. Longueur totale ∑_{w∈A^{∗}} |w|w

2. Comptage des a, ∑_{w∈A^{∗}} |w|_{a}w et des b, ∑_{w∈A^{∗}} |w|_{b}w

3. Produit des degrés partiels ∑_{w∈A^{∗}} |w|_{a}|w|_{b}w

4. Autres produits ∑_{w∈A^{∗}} F_{|w|}|w|w, ∑_{w∈A^{∗}} F_{|w|_{a}}|w|_{b}w

14.2 Which rational calculus?

If Q is a finite set, the space k^{Q×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 ∈ k^{Q×Q} (when it exists) is a solution of the equation MY + 1_{Q×Q} = Y (where 1_{Q×Q} is the identity matrix). Let M ∈ k^{Q×Q} be given by

M = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )

where a_{11} ∈ k^{Q_{1}×Q_{1}}, a_{12} ∈ k^{Q_{1}×Q_{2}}, a_{21} ∈ k^{Q_{2}×Q_{1}} and a_{22} ∈ k^{Q_{2}×Q_{2}} such that Q_{1} + Q_{2} = Q. Let N ∈ k^{Q×Q} given by

N = ( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} )

with

A_{11} = (a_{11} + a_{12}a_{22}^{∗}a_{21})^{∗}  (68)
A_{12} = a_{11}^{∗}a_{12}A_{22}  (69)
A_{21} = a_{22}^{∗}a_{21}A_{11}  (70)
A_{22} = (a_{22} + a_{21}a_{11}^{∗}a_{12})^{∗}  (71)

Théorème 14.2 If the right hand sides of formulas (68), (69), (70) and (71) are defined, the matrix M admits N as a right star.

Proof. Suppose, without loss of generality, that Q = [1,n]_{ℕ}; n = p + q; Q_{1} = [1,p]_{ℕ}; Q_{2} = [p + 1,p + q]_{ℕ}. We have to show that N is a solution of the equation My + 1_{n×n} = y. By computation, one has

MN + 1 = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) ( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} ) + ( \begin{matrix}1_{p×p} & 0_{p×q} \\ 0_{q×p} & 1_{q×q} \end{matrix} )

= ( \begin{matrix}a_{11}A_{11} + a_{12}A_{21} + 1_{p×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×q} \end{matrix} )

where 0_{p×q} is the zero matrix in k^{p×q}. We verify the relations (68), (69), (70) and (71) by:

a_{11}A_{11} + a_{12}A_{21} + 1_{p×p} = a_{11}A_{11} + a_{12}a_{22}^{∗}a_{21}A_{11} + 1_{p×p} =
A_{11}(a_{11} + a_{12}a_{22}^{∗}a_{21}) + 1_{p×p} = A_{11}

a_{11}A_{12} + a_{12}A_{22} = a_{11}a_{11}^{∗}a_{12}A_{22} + a_{12}A_{22} =
(a_{11}a_{11}^{∗} + 1)a_{12}A_{22} = a_{11}^{∗}a_{12}A_{22} = A_{12}

a_{21}A_{11} + a_{22}A_{21} = a_{21}A_{11} + a_{22}a_{22}^{∗}a_{21}A_{11} =
(1 + a_{22}a_{22}^{∗})a_{21}A_{11} = a_{22}^{∗}a_{21}A_{11} = A_{21}

a_{21}A_{12} + a_{22}A_{22} + 1_{q×q} = a_{21}a_{11}^{∗}a_{12}A_{22} + a_{22}A_{22} + 1_{q×q} =
(a_{22}a_{21}a_{11}^{∗}a12)A_{22} + 1_{q×q} = A_{22}

□

Remarque 14.3 i) In [11] and [14], 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 (14.2), of course, does not hold as shows the example below (the coefficients are taken in a ring and here the star is unique).

M = (\begin{matrix}1 & −1 \\ 1 & −1 \end{matrix}) M^{∗} = (\begin{matrix}2 & −1 \\ 1 & 0 \end{matrix})  (72)

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

A_{11} = (a_{11} + a_{12}a_{22}^{∗}a_{21})^{∗}
A_{12} = A_{11}a_{12}a_{22}^{∗}
A_{21} = A_{22}a_{21}a_{11}^{∗}
A_{22} = (a_{22} + a_{21}a_{11}^{∗}a_{12})^{∗}  (73)

iii) When all their terms are defined, formulas above (as well as (68), (69), (70) and (71)) 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 ∈ k^{n×n} a matrix given by

M = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )

where n ∈ 2ℕ + 1. The dynamic peeling [26] consists of cutting out the matrix in the following way: a_{11} is a (n − 1) × (n − 1) matrix, a_{12} is a (n − 1) × 1 matrix, a_{21} is a 1 × (n − 1) matrix and a_{22} is a scalar.

Références

Références générales.

[1] E. Abe Hopf algebras. Cambridge (1980).

[2] Berstel J. and Reutenauer C., Rational series and their languages, EATCS, 1988.

[3] Bourbaki N., Algèbre Ch. III. Hermann (1970)

[4] Cohen H., A Course in Computational Algebraic Number Theory. Springer (1993)

[5] Cayley A., On certain results related to quaternions. Phil. Mag. 26, 141-145 (1845).

[6] Curtis C. W., Reiner I., Methods of representation theory. Wiley Interscience, (1990).

[7] Davenport J., Siret Y., Tournier E., Calcul formel, Masson (1986)

[8] Demazure Michel, Cours d’algèbre : Divisibilité, Primalité, codes. Cassini (1997).

[9] Eilenberg S., Automata, languages and machines, Acad. Press (1974).

[10] von zur Gathen J. and Gerahrd J. Modern Computer Algebra. Cambridge (1999).

[11] Heyting A., “Die Theorie der Linearen Gleichungen in einer Zahlenspezies mit nichtkommutativer Multiplikation”. Math. Ann. 98 (1927) 465-490.

[12] W. Fulton et J. Harris, Representation theory: a first course, Springer-Verlag, New-York, 1991.

[13] Naudin P., Quitté C., Algorithmique Algébrique Masson (1992)

[14] Richardson A. R., Simultaneous Linear equations over a division ring. Proc. Lond. Math. Soc. 28 (1928) 395-420.

[15] Knuth D., The art of computer programming, Tome I & II. Addison-Wesley (1981)

[16] Stanley R., Enumerative Combinatorics Vol I and II, Cambridge.

Références spécialisées.

Automates./Informatique.

[17] Champarnaud J.-M., Duchamp G. :Derivatives of rational expressions and related theorems, T.C.S. 313 31 (2004).

[18] Duchamp G., Reutenauer C., Un critère de rationalité provenant de la géométrie noncommutative Invent. Math. 128 613-622. (1997).

[19] Duchamp G., Hadj Kacem H. and Laugerotte E., Algebraic elimination of ϵtransitions, DMTCS, Volume 7 n^{∘} 1 (2005), pp. 51-70

[20] Eilenberg S., Automata, languages and machines, Acad. Press (1974).

[21] Laugerotte É., Combinatoire et Calcul symbolique en Théorie des Représentations, Thèse de l’Université de Rouen (6 novembre 1997).

[22] Flouret M., Contribution à l’Algorithmique Noncommutative, Thèse de l’Université de Rouen (19 janvier 1999).

[23] Flouret M., Laugerotte É., Noncommutative minimization algorithms. Information Processing Letters 64, 123-126 (1997).

[24] Hatem Hadj-Kacem, Contribution à la théorie et aux applications des automates à multiplicités, Thèse de l’Université de Rouen (17/06/2005).

[25] Luque Jean-Gabriel, Monoïdes et automates admettant un produit de mélange, Thèse de l’Université de Rouen (09/12/1999).

[26] Huss-Lederman S., Jacobson E.M., Johnson J.R., Tsao A., Turnbull T., “Implementation of Strassen’s Algorithm for Matrix Multiplication”. Proceeding of the ACM/IEEE conference on supercomputing , Pittsburgh, Pennsylvania, USA (1996).

[27] Iverson Kenneth E., A programming Language. Wiley, 1962.

[28] Schützenberger, “On the definition of a family of automata”. Inform. and Contr. 4 (1961) 245-270.

Cryptographie/Cryptologie.

[29] Bryant R. E., Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, (1986).

[30] Duchamp G. H. E., Hadj-Kacem H., Laugerotte E., On the decomposition of boolean functions, BFCA05, March 7-8, 2005.

Combinatoire Algébrique

[31] Fomin S. Duality of graded graphs, J. Alg. Comb. 3 (1994) 357-404 ”Schensted algorithms for dual graded graphs”, J. Alg. Comb. 4 (1995), 5-45.

[32] Duchamp G., Krob D., Lascoux A., Leclerc B., Scharf T., Thibon J.-Y., Euler-Poincaré characteristic and polynomial representations of Iwahori-Hecke algebras. Pub. of the RIMS 31, (1995).

[33] Humphreys J. E., Reflection groups and Coxeter groups. Cambridge University Press, (1990).

[34] Joyal A., Une théorie combinatoire des séries formelles, Adv. Math.42 (1981), 1-82.

[35] Jucys A. A., Symmetric polynomials and the center of the symmetric group ring, Reports on Mathematical physics, 5, 107-112, 1974.

[36] Murphy G. E., A new construction of Young’s seminormal representation of the symmetric groups, Journal of Algebra, 69, 287- 297, 1981.

[37] Murphy G. E., The idempotents of the symmetric group and Nakayma’s conjecture, Journal of Algebra, 81, 258-265, 1983.

[38] Okounkov A. et A. M. Vershik, Inductive construction of representation theory for symmetric groups, Russian Math. Survey, 51, Vol 2, 1996.

[39] I. G. Macdonald, Symmetric functions and Hall polynomials, Clarendon Press, Oxford, 1979.

[40] Lascoux A. et Schützenberger M. -P., Le monoïde plaxique, Quaderni della Ricerca Scientifica del CNR, Rome, 1981.

[41] Touchard J., Sur les cycles des permutations, Acta Math. 70 (1939), 243-297.

Combinatoire et Physique.

[42] G. H. E. Duchamp, P. Blasiak, A. Horzela, K. A. Penson, A. I. Solomon, Feynman graphs and related Hopf algebras, Journal of Physics, Volume 30, 2006: Conference Series, SSPCM’05, Myczkowce, Poland.

arXiv : cs.SC/0510041

[43] G. Duchamp, K.A. Penson, A.I. Solomon, A. Horzela and P. Blasiak, 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 : quant-ph/0401126

[44] Ridell R.J., Uhlenbeck G.E., On the theory of the virial development of the equation of state of monomatomic gases, J. Chem. Phys. 21 (1953), 2056-2064.