Pour tout ensemble fini E de cardinal k, on note ℝ^E l'espace vectoriel de dimension k des fonctions de E vers ℝ. On note eˆ l'élément de ℝ^E qui est la fonction qui à e associe 1 , et à tout autre élément de E associe 0 . En particulier, tout élément a de ℝ^E s'écrit de façon unique ∑_(e ∈ E)a_e eˆ, pour une famille de coefficients (a_e)_(e ∈ E) - à savoir a_e = a(e) pour tout e ∈ E. Les vecteurs eˆ, e ∈ E forment la base canonique de ℝ^E.
L'espace ℝ^E est muni d'un produit scalaire défini par
pour lequel la base (eˆ)_(e ∈ E) est orthonormée. On note |v| = √(v ⋅ v).
On note 0 l'espace vectoriel de dimension 0 . Il est réduit à l'élément 0 .
On rappelle aussi que le rang d'une application linéaire f : ℝ^E → ℝ^F est dimImf = dimℝ^E − dimKerf = cardE − dimKerf.
Si A et B sont deux matrices de même largeur, la matrice [A/B] est obtenue en plaçant toutes les lignes de A au-dessus de toutes les lignes de B.
Une relation binaire sur un ensemble A est un sous-ensemble de A × A. Pour toute relation binaire → sur un ensemble A, on notera x → y si et seulement si ( x, y ) est dans →. On notera d'autre part → ^∗ la relation définie par x → ^∗ y si et seulement s'il existe un entier k ≥ 0, et k + 1 éléments x_0, x_1, x_2, …, x_k de A tels que x = x_0 → x_1 → x_2 → … → x_k = y. La relation → ^+est définie par x → ^+y si et seulement s'il existe un entier k ≥ 1, et k + 1 éléments x_0, x_1, x_2, …, x_k de A tels que x = x_0 → x_1 → x_2 → … → x_k = y.
La différence ensembliste ∖ est définie par A∖B = {x ∈ A|x ∉ B}. La différence symétrique Δ est définie par AΔB = (A∖B) ∪ (B∖A).
L'usage de la calculatrice est autorisé (et fondamentalement inutile). On pourra utiliser les résultats de questions précédentes même si on n'y a pas répondu.
1 Quelques calculs matriciels
Question 1.1. Soient v_1, …, v_(k − 1)k − 1 vecteurs non nuls de ℝ^m, et supposons qu'ils sont orthogonaux deux à deux, c'est-à-dire v_i ⋅ v_j = 0 pour tous i, j, 1 ≤ i < j < k. Pour tout vecteur v de ℝ^m, montrer que
est orthogonal à tous les v_i, 1 ≤ i < k, et que de plus l'espace vectoriel engendré par v_1, …, v_(k − 1), v^′ est identique à celui engendré par v_1, …, v_(k − 1), v.
Question 1.2. On considère le programme suivant:
$\operatorname{GS1}(A, m, n, k)$
pour $j$ de 1 à $k-1$ faire
$s:=0 ; x:=0 ;$
pour $i$ de 1 à $m$ faire
$s:=s+A[i, j] \times A[i, k] ; x:=x+A[i, j] \times A[i, j] ;$
si $x \neq 0$ alors pour $i$ de 1 à $m$ faire
$A[i, k]:=A[i, k]-s \times A[i, j] / x ;$
On supposera que A est un tableau de m lignes et n colonnes, et que 1 ≤ k ≤ n. L'élément A[i, j] est donc défini pour 1 ≤ i ≤ m et 1 ≤ j ≤ n. La jième colonne A[ −, j] de A sera vue comme un vecteur v_j, et on supposera qu'en entrée de GS1, les vecteurs v_1, …, v_(k − 1) sont orthogonaux deux à deux.
Que calcule GS1 (A, m, n, k) ?
Question 1.3. Montrer que le programme
GS(A, m, n)
pour k de 1 à n faire
GS1(A, m, n, k)
remplace le tableau A de n vecteurs de ℝ^m par un tableau de n vecteurs orthogonaux engendrant le même sous-espace vectoriel.
Montrer que la complexité de GS ( A, m, n ), c'est-à-dire le nombre d'opérations élémentaires (affectations et opérations arithmétiques) effectuées par GS ( A, m, n ), est en O(n^2 m).
Question 1.4. Pour toute matrice A de m lignes et n colonnes, en déduire qu'on peut calculer dimKerA en O(n^2 m) opérations élémentaires.
Question 1.5. En considérant la transposée A^t de A, en déduire que l'on peut calculer dimKerA en O(m^2 n) opérations élémentaires.
Question 1.6. En déduire un algorithme, fondé sur les algorithmes des questions précédentes, calculant dim KerA en O(min(m, n)^2 max(m, n)) opérations élémentaires.
2 Complexes simpliciaux et homologie
On appelle complexe simplicial tout triplet ( V, ≤, K ), où V est un ensemble fini de sommets, ≤ est un ordre total sur V, et K est un ensemble de parties non vides de V, vérifiant la condition :
( † ) si α ∈ K et β ⊂ α, β ≠ ∅, alors β ∈ K.
On notera souvent K le complexe simplicial ( V, ≤, K ), par abus de notation. On notera x < y si et seulement si x ≤ y et x ≠ y.
Les éléments α de K sont appelés les simplexes de K. La dimension dimα est par convention card α − 1. En particulier, la dimension de tout simplexe de la forme {x} est 0 .
Pour tout p ∈ ℕ, on note K_p l'ensemble des simplexes de dimension p de K.
Fig. 1 - La représentation graphique d'un complexe simplicial
La relation ⊏^+dénote l'inclusion stricte entre simplexes : x⊏^+y si et seulement si x est strictement inclus dans y; on dit alors que x est une face de y. Par exemple, {b, c} est une face de dimension 1 de {b, c, d}. On dit que x est une face directe de y, et l'on note x⊏y si et seulement si x est une face de y et dimx = dimy − 1.
Il est parfois utile de considérer une représentation graphique des complexes simpliciaux. Par exemple, le complexe simplicial de gauche de la figure 1 est formé des simplexes {u, v}, {u, w}, {v, w} (les trois segments, de dimension 1), et {u}, {v}, {w} (leurs faces) - les sommets sont représentés comme des points. Le diagramme de droite est la représentation du complexe simplicial ( V, ≤, K ) avec V = {a, b, c, d, e, f, g}, et où les simplexes sont les faces triangulaires (les simplexes de dimension 2) {b, c, d} et {d, e, f}, les segments (dimension 1) {a, b}, {c, e} et {e, g}, et tous leurs sous-ensembles non vides.
Pour tout simplexe α = {x_0, x_1, …, x_p} de K de dimension p, avec x_0 < x_1 < … < x_p, pour tout i, 0 ≤ i ≤ p, on pose
∂_p^i α = α∖{x_i}
où ∖ désigne la différence ensembliste. On appelle ∂_p^i α la face numéro i de α.
Question 2.1. Montrer l'égalité
∂_(p − 1)^i∂_p^j α = ∂_(p − 1)^(j − 1)∂_p^i α
pour tout simplexe α de K de dimension p ≥ 1, et pour tous i, j tels que 0 ≤ i < j ≤ p.
Question 2.2. Étant donné un complexe simplicial K, pour tout p ∈ ℕ, on note C_p l'espace vectoriel ℝ^(K_p). (On rappelle que K_p est l'ensemble des simplexes de dimension p de K.) Par extension, on notera C_(− 1) l'espace vectoriel 0 réduit à un seul élément noté aussi 0 . On appelle tout vecteur de C_p une chaîne de dimension p.
On pose d_p : C_p → C_(p − 1), pour tout p ≥ 0, l'unique application linéaire telle que
d_p(αˆ) = ∑_(i = 0)^p(− 1)^i∂_p^i αˆ
si p ≥ 1, et telle que d_p(α) = 0 si p = 0. Autrement dit, d_0 est l'application nulle et pour tout p ≥ 1, pour tout vecteur ∑_(α ∈ K_p)a_α αˆ de C_p,
On appelle d_p l'opérateur bord. Montrer que d_(p − 1) ∘ d_p est l'application nulle pour tout p ≥ 1. En déduire que Imd_p ⊂ Kerd_(p − 1).
Question 2.3. Le sous-espace vectoriel Z_p = Kerd_p de C_p, p ≥ 0, est l'ensemble des cycles de dimension p. Le sous-espace vectoriel B_p = Imd_(p + 1) de C_p, p ≥ 0, est l'ensemble des bords de dimension p. Par la question 2.2, B_p est aussi un sous-espace vectoriel de Z_p; autrement dit, tout bord est un cycle. On note H_p l'orthogonal de B_p dans Z_p.H_p est le p-ième espace vectoriel d'homologie de K.
La dimension β_p de H_p est appelé le p-ième nombre de Betti de K. D'autre part, la caractéristique d'Euler de K est
χ(K) = ∑_(p ∈ ℕ)(− 1)^p cardK_p
Montrer le théorème d'Euler-Poincaré :
χ(K) = ∑_(p ∈ ℕ)(− 1)^p β_p
Question 2.4. Calculer les nombres de Betti et la caractéristique d'Euler du complexe simplicial de gauche de la figure 1 , pour l'ordre u < v < w.
3 Calcul des nombres de Betti
Dans cette partie, on va concevoir des algorithmes pour calculer les nombres de Betti d'un complexe simplicial ( V, ≤, K ). Pour ceci, on choisit une énumération des simplexes de dimension p de K, pour chaque p ∈ ℕ; on notera α_1^((p)), …, α_(card K_p)^((p)) les simplexes de dimension p de K. On dit que le numéro de α_j^((p)) est j.K est alors représenté à l'aide des données suivantes:
un entier n supérieur ou égal à la dimension de tout simplexe de K;
un tableau c, tel que c[p] est le nombre de simplexes de K de dimension p, 0 ≤ p ≤ n;
un tableau face, tel que face [p, j, i] est le numéro du simplexe ∂_p^i α_j^((p)), pour tous 1 ≤ p ≤ n, 1 ≤ j ≤ c[p], 0 ≤ i ≤ p.
L'ordre ≤ sur V est donné par α_1^((0)) < α_2^((0)) < … < α_(c[0])^((0)). On notera que, pour tous p et j fixés, tous les face [p, j, i], 0 ≤ i ≤ p, sont des entiers distincts.
Par exemple, le complexe simplicial de droite de la figure 1 sera représenté par : − n = 2; − c[0] = 7, c[1] = 9, c[2] = 2;
En numérotant les simplexes comme suit :
dimension 0 :
1
2
3
4
5
6
7
{a}
{b}
{c}
{d}
{e}
{f}
{g}
dimension 1 :
1
2
3
4
5
6
7
8
9
{a, b}
{b, c}
{b, d}
{c, d}
{c, e}
{d, e}
{d, f}
{e, f}
{e, g}
dimension 2 :
1
2
{b, c, d}
{d, e, f}
le tableau face [p, j, i] est donné par :
face [1, j, i] =
i∖^j
1
2
3
4
5
6
7
8
9
0
2
3
4
4
5
5
6
6
7
1
1
2
2
3
3
4
4
5
5
face[2, j, i] =
i∖^j
1
2
0
4
8
1
3
7
2
2
6
Question 3.1. On identifie les opérateurs bord d_p : C_p → C_(p − 1) à leurs matrices, en choisissant pour tout C_q sa base standard αˆ_1^((q)), …, αˆ_(c[q])^((q)). On note d_p^t la matrice transposée de d_p. Montrer que
H_p = Ker[(d_(p + 1)^t)/(d_p)]
Question 3.2. En déduire, ainsi que de la partie 1, un algorithme prenant en entrée une représentation ( n, c, face) d'un complexe simplicial K, et un entier naturel p, et retournant le nombre de Betti β_p de K. En particulier, on demande d'écrire effectivement le programme construisant les matrices impliquées, dans le style des programmes donnés en question 1.2 et 1.3.
Combien d'opérations élémentaires nécessite cet algorithme?
Question 3.3. Soit ( V, ≤, K ) un complexe simplicial, et soit γ un sous-ensemble non vide de V qui n'est pas dans K, mais dont tous les sous-ensembles stricts sont dans K. On note que K ∪ {γ} est un complexe simplicial.
Posons (β_p)_(p ∈ ℕ) les nombres de Betti de K, (β_p^′)_(p ∈ ℕ) ceux de K^′ = K ∪ {γ}. Soit d_p^′ l'opérateur bord de K^′, et disons que γ crée un cycle dans K (de dimension p − 1 ) si et seulement si d_p^′(γˆ) ∈ Imd_p.
Montrer que, si γ crée un cycle dans K, alors β_p^′ = β_p + 1 et β_q^′ = β_q pour tout q ≠ p; et si γ ne crée pas de cycle dans K, alors p ≥ 1, β_(p − 1)^′ = β_(p − 1) − 1 et β_q^′ = β_q pour tout q ≠ p − 1.
Fig. 2 - Homotopie simple
Question 3.4. Soient K et K^′ deux complexes simpliciaux. On dit que K est obtenu à partir de K^′ en contractant une face β de K^′ si et seulement s'il existe une face directe α de β telle que K = K^′∖{α, β}. (Un exemple est donné en figure 2.) Montrer que K ∪ {α} est un complexe simplicial, mais pas K ∪ {β}. Montrer que α crée un cycle dans K, et que β ne crée pas de cycle dans K ∪ {α}. En déduire que K et K^′ ont les mêmes nombres de Betti.
Question 3.5. On note ≅ la relation entre complexes simpliciaux définie par K ≅ K^′ si et seulement s'il existe un nombre fini de complexes simpliciaux K_0 = K, K_1, …, K_(m − 1), K_m = K^′ tels que, pour tout i de 1 à m, K_i est obtenu à partir de K_(i − 1) en contractant une face, ou K_(i − 1) est obtenu à partir de K_i en contractant une face. On dira alors que K et K^′ sont simplement homotopes.
Que peut-on dire des nombres de Betti de deux complexes simpliciaux simplement homotopes? Quels sont les nombres de Betti, et la caractéristique d'Euler, du complexe simplicial de droite de la figure 1 ?
4 Champs de vecteurs discrets
Pour tout complexe simplicial K, on appelle champ de vecteurs discret sur K toute relation binaire ▹ sur K telle que :
(i) α▹β implique que α⊏β;
(ii) pour tout simplexe α, il existe au plus un simplexe β tel que α⋈β, où ⋈ est la relation définie par α⋈β si et seulement si α▹β ou β▹α.
On pourra vérifier que le complexe simplicial de la droite de la figure 1 a , par exemple, un champ de vecteurs discret défini par :
Si ▹ est un champ de vecteurs discret sur K, on définit la relation binaire → par α → β si et seulement si α▹β, ou bien α⊐β et β≯α. Dans l'exemple, la relation → est celle décrite dans le diagramme (3) ci-dessous, où l'on trouve une flèche de α vers β si et seulement si α → β. On observera que la flèche α → β monte si et seulement si α▹β; on a représenté ces flèches montantes en gras pour mieux les voir.
On dit que ▹, ou →, est acyclique si et seulement s'il n'existe pas de simplexe α_1 tel que α_1 → ^+α_1, autrement dit si et seulement s'il n'existe pas de simplexes α_1, …, α_k(k ≥ 1) tels que α_1 → α_2 → … → α_k → α_1.
On peut réarranger le diagramme (3) comme suit et ainsi constater de visu que le champ de vecteurs discret ▹ de l'exemple est acyclique:
Dans le reste de cette partie, on supposera que K est un complexe simplicial fixé, et que ▹ est un champ de vecteurs discret acyclique sur K.
Question 4.1. On appelle sous-complexe K^′ de K tout sous-ensemble de K qui est un complexe simplicial. Soit A^′ l'ensemble de tous les simplexes de dimension maximale de K^′. On admettra que, ▹ étant acyclique, pour tout sous-complexe K^′ non vide de K, il existe un simplexe α dans A^′ tel qu'il n'y a pas de simplexe γ dans A^′ avec γ → ^+α. On fixera un tel simplexe pour chaque sous-complexe K^′ non vide, et on le notera α_(max)(K^′).
Dans l'exemple ci-dessus, on vérifie que A^′ contient juste les deux simplexes {b, c, d} et {d, e, f}. On peut constater sur le diagramme (4) que l'on peut choisir indifféremment l'un ou l'autre pour α_(max)(K).
Un sous-complexe K^′ sera dit normal si et seulement s'il n'existe pas de simplexes α ∈ K^′, β ∉ K^′ tels que α⋈β.
Soit K^′ un sous-complexe normal non vide de K, α = α_(max)(K^′), et β un simplexe tel que α⋈β. Montrer que β est aussi dans K^′, que β▹α, et que K^′∖{α, β} est un sous-complexe normal de K.
Question 4.2. Un simplexe α de K est dit critique si et seulement s'il n'existe pas de simplexe β de K tel que α⋈β.
Soit K^′ un sous-complexe normal non vide de K, α = α_(max)(K^′). Montrer que, si α est critique, alors K^′∖{α} est un sous-complexe normal de K.
Question 4.3. Pour tout sous-complexe normal K^′ de K, on note c_p(K^′) le nombre de simplexes critiques de K^′, et β_p(K^′) le p-ième nombre de Betti de K^′. Montrer que l'on a les inégalités de Morse :
(Indication : supprimer dans le bon ordre des simplexes de K^′, en se fondant sur les questions précédentes. On pourra s'aider des résultats de la partie 3.)
Question 4.4. En appliquant le résultat précédent au cas K^′ = K^′, en déduire les inégalités de Morse faibles :
c_p(K) ≥ β_p(K)
pour tout p ∈ ℕ.
5 Évasivité
Soit ( V, ≤, K ) un complexe simplicial fixé, V = {v_1, v_2, …, v_n}, v_1 < v_2 < … < v_n, n ≥ 1.
Le but de cette partie est d'examiner la possibilité d'écrire un programme prenant en entrée un sous-ensemble α de V et retournant Vrai si α est un simplexe de K, Faux sinon.
On se limite à des programmes qui procèdent uniquement en posant des questions de la forme "est-ce que v_i ∈ α ?" ( 1 ≤ i ≤ n ), et selon la réponse, vrai ou faux, posera d'autre
questions, jusqu'à décider de retourner Vrai ou Faux. Un tel programme sera appelé un reconnaisseur Rec_K(α) pour K.
Un reconnaisseur sera estimé efficace s'il peut décider si α ∈ K, pour tout α ⊂ V, en posant strictement moins de n questions. Pour chercher un reconnaisseur efficace pour K, on va jouer sur l'ordre dans lequel il pose les questions.
On associera à chaque reconnaisseur REC_K une application qui à tout sous-ensemble α de V associe une permutation σ_α de {1, 2, …, n}, vérifiant la propriété : (‡) pour tout α ⊂ V, si v_(σ_α(k)) ∈ α et β = α∖{v_(σ_α(k))}(1 ≤ k ≤ n) alors σ_β(j) = σ_α(j) pour tout j, 1 ≤ j ≤ k.
La façon de construire l'application α ↦ σ_α à partir de REC_K est la suivante. Supposons que, pour décider si α ∈ K, Rec_K pose comme première question "est-ce que v_(i_1) ∈ α ?", alors on pose σ_α(1) = i_1. Ensuite, si Rec_K pose comme deuxième question "est-ce que v_(i_2) ∈ α ?", alors on pose σ_α(2) = i_2, et ainsi de suite. Intuitivement, ReD_K ne va pas poser deux fois la même question, ce qui fait de σ_α une permutation. La condition ( ‡ ) exprime que si l'on doit poser une série de questions pour reconnaître α, et si β ne diffère de α qu'à partir de la k ième question, alors on aurait posé les mêmes k premières questions pour reconnaître β.
Dans la suite, on fixera un reconnaisseur REC_K. On note σ_α la famille de permutations vérifiant ( ‡ ) qui lui est associée.
On définit ▹ par β▹α si et seulement si v_(σ_α(n)) ∈ α et β = α∖{v_(σ_α(n))}. (On rappelle que n est le nombre de sommets de K.) Comme précédemment, on définit ⋈ par α⋈β si et seulement si α▹β ou β▹α.
Question 5.1. Montrer que pour tout α ⊂ V, il existe un unique β ⊂ V tel que α⋈β.
Question 5.2. Soit S l'ensemble des suites finies [n_1, …, n_k] ( k ≥ 0 ) d'entiers naturels. On appelle k la longueur de la suite [n_1, …, n_k]. La suite [] de longueur nulle est la suite vide. On définit la relation binaire ≺surS par [n_1, …, n_k]≺[n_1^′, …, n_ℓ^′] si et seulement s'il existe j, 1 ≤ j ≤ k satisfaisant les conditions (a) et (b) :
(a) pour tout i, 1 ≤ i < j, n_i = n_i^′;
(b) ℓ = j − 1, ou bien ℓ ≥ j et n_j < n_j^′;
Montrer que ≺ est un ordre strict, c'est-à-dire une relation irréflexive et transitive.
Question 5.3. Pour tout α ⊂ V, on pose α˘ = αΔ{v_(σ_α)(n)}, où Δ dénote la différence symétrique. On pose d'autre part [ [α] ] la suite croissante des indices i, 1 ≤ i ≤ n, tels que v_(σ_α(i)) ∈ α. (Par exemple, si n = 3, α = {v_1, v_2}, σ_α = {1 ↦ 3, 2 ↦ 2, 3 ↦ 1}, alors [ [α] ] est [2, 3].)
Montrer que β → α implique [ [β˘] ]≺[ [α˘] ]. En déduire que ▹ est un champ de vecteur discret acyclique sur K.
Question 5.4. Un sous-ensemble α non vide de V est évasif si et seulement si α ∈ K et α˘ ∉ K ∪ {∅}, ou bien α ∉ K ∪ {∅} et α˘ ∈ K.
Le reconnaisseur Rec_K est inefficace si et seulement s'il existe un sous-ensemble α évasif. Il est efficace sinon. L'idée est que Rec_K est inefficace si et seulement s'il y a un simplexe α non vide tel que, pour décider si α est dans K, on est obligé de poser toutes
les questions jusqu'à la dernière. Aucun reconnaisseur ne teste jamais l'appartenance de l'ensemble vide à K; ceci est dû au fait que l'ensemble vide n'est jamais dans K, et justifie la définition.
Soient β_p les nombres de Betti de K.
Montrer le théorème de Kahn-Saks-Sturtevant : quel que soit le reconnaisseur Rec_K pour K, il y a au moins 2(∑_(p ∈ ℕ)β_p − 1) sous-ensembles évasifs pour Rec_K. En déduire que ceci implique qu'il n'existe aucun reconnaisseur efficace pour K dès que ∑_(p ∈ ℕ)β_p ≥ 2. On pourra utiliser la question 4.4.
Les complexes simpliciaux de la figure 1 ont-ils des reconnaisseurs efficaces?
Pas de description pour le moment
Commentaires• ENS Informatique Fondamentale (Maths Info) MP PC 2004
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
.jpg)