Pour tout ensemble fini de cardinal , on note l'espace vectoriel de dimension des fonctions de vers . On note l'élément de qui est la fonction qui à associe 1 , et à tout autre élément de associe 0 . En particulier, tout élément de s'écrit de façon unique , pour une famille de coefficients - à savoir pour tout . Les vecteurs forment la base canonique de .
L'espace est muni d'un produit scalaire défini par
pour lequel la base est orthonormée. On note .
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 est .
Si et sont deux matrices de même largeur, la matrice est obtenue en plaçant toutes les lignes de au-dessus de toutes les lignes de .
Une relation binaire sur un ensemble est un sous-ensemble de . Pour toute relation binaire sur un ensemble , on notera si et seulement si ( ) est dans . On notera d'autre part la relation définie par si et seulement s'il existe un entier , et éléments de tels que . La relation est définie par si et seulement s'il existe un entier , et éléments de tels que .
La différence ensembliste est définie par . La différence symétrique est définie par .
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 vecteurs non nuls de , et supposons qu'ils sont orthogonaux deux à deux, c'est-à-dire pour tous . Pour tout vecteur de , montrer que
est orthogonal à tous les , et que de plus l'espace vectoriel engendré par est identique à celui engendré par .
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 est un tableau de lignes et colonnes, et que . L'élément est donc défini pour et . La jième colonne de sera vue comme un vecteur , et on supposera qu'en entrée de GS1, les vecteurs sont orthogonaux deux à deux.
Que calcule GS1 ?
Question 1.3. Montrer que le programme
pour de 1 à faire
remplace le tableau de vecteurs de par un tableau de vecteurs orthogonaux engendrant le même sous-espace vectoriel.
Montrer que la complexité de GS ( ), c'est-à-dire le nombre d'opérations élémentaires (affectations et opérations arithmétiques) effectuées par GS ( ), est en .
Question 1.4. Pour toute matrice de lignes et colonnes, en déduire qu'on peut calculer en opérations élémentaires.
Question 1.5. En considérant la transposée de , en déduire que l'on peut calculer en opérations élémentaires.
Question 1.6. En déduire un algorithme, fondé sur les algorithmes des questions précédentes, calculant dim en opérations élémentaires.
2 Complexes simpliciaux et homologie
On appelle complexe simplicial tout triplet ( ), où est un ensemble fini de sommets, est un ordre total sur , et est un ensemble de parties non vides de , vérifiant la condition :
( ) si et , alors .
On notera souvent le complexe simplicial ( ), par abus de notation. On notera si et seulement si et .
Les éléments de sont appelés les simplexes de . La dimension est par convention card . En particulier, la dimension de tout simplexe de la forme est 0 .
Pour tout , on note l'ensemble des simplexes de dimension de .
Fig. 1 - La représentation graphique d'un complexe simplicial
La relation dénote l'inclusion stricte entre simplexes : si et seulement si est strictement inclus dans ; on dit alors que est une face de . Par exemple, est une face de dimension 1 de . On dit que est une face directe de , et l'on note si et seulement si est une face de et .
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 , (les trois segments, de dimension 1), et (leurs faces) - les sommets sont représentés comme des points. Le diagramme de droite est la représentation du complexe simplicial ( ) avec , et où les simplexes sont les faces triangulaires (les simplexes de dimension 2) et , les segments (dimension 1) et , et tous leurs sous-ensembles non vides.
Pour tout simplexe de de dimension , avec , pour tout , on pose
où désigne la différence ensembliste. On appelle la face numéro de .
Question 2.1. Montrer l'égalité
pour tout simplexe de de dimension , et pour tous tels que .
Question 2.2. Étant donné un complexe simplicial , pour tout , on note l'espace vectoriel . (On rappelle que est l'ensemble des simplexes de dimension de .) Par extension, on notera l'espace vectoriel 0 réduit à un seul élément noté aussi 0 . On appelle tout vecteur de une chaîne de dimension .
On pose , pour tout , l'unique application linéaire telle que
si , et telle que si . Autrement dit, est l'application nulle et pour tout , pour tout vecteur de ,
On appelle l'opérateur bord. Montrer que est l'application nulle pour tout . En déduire que .
Question 2.3. Le sous-espace vectoriel de , est l'ensemble des cycles de dimension . Le sous-espace vectoriel de , est l'ensemble des bords de dimension . Par la question 2.2, est aussi un sous-espace vectoriel de ; autrement dit, tout bord est un cycle. On note l'orthogonal de dans est le -ième espace vectoriel d'homologie de .
La dimension de est appelé le -ième nombre de Betti de . D'autre part, la caractéristique d'Euler de est
Montrer le théorème d'Euler-Poincaré :
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 .
3 Calcul des nombres de Betti
Dans cette partie, on va concevoir des algorithmes pour calculer les nombres de Betti d'un complexe simplicial ( ). Pour ceci, on choisit une énumération des simplexes de dimension de , pour chaque ; on notera les simplexes de dimension de . On dit que le numéro de est est alors représenté à l'aide des données suivantes:
un entier supérieur ou égal à la dimension de tout simplexe de ;
un tableau , tel que est le nombre de simplexes de de dimension ;
un tableau face, tel que face est le numéro du simplexe , pour tous .
L'ordre sur est donné par . On notera que, pour tous et fixés, tous les face , sont des entiers distincts.
Par exemple, le complexe simplicial de droite de la figure 1 sera représenté par : ;
En numérotant les simplexes comme suit :
dimension 0 :
1
2
3
4
5
6
7
dimension 1 :
1
2
3
4
5
6
7
8
9
dimension 2 :
1
2
le tableau face est donné par :
face
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
1
2
0
4
8
1
3
7
2
2
6
Question 3.1. On identifie les opérateurs bord à leurs matrices, en choisissant pour tout sa base standard . On note la matrice transposée de . Montrer que
Question 3.2. En déduire, ainsi que de la partie 1, un algorithme prenant en entrée une représentation ( , face) d'un complexe simplicial , et un entier naturel , et retournant le nombre de Betti de . 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 ( ) un complexe simplicial, et soit un sous-ensemble non vide de qui n'est pas dans , mais dont tous les sous-ensembles stricts sont dans . On note que est un complexe simplicial.
Posons les nombres de Betti de ceux de . Soit l'opérateur bord de , et disons que crée un cycle dans (de dimension ) si et seulement si .
Montrer que, si crée un cycle dans , alors et pour tout ; et si ne crée pas de cycle dans , alors et pour tout .
Fig. 2 - Homotopie simple
Question 3.4. Soient et deux complexes simpliciaux. On dit que est obtenu à partir de en contractant une face de si et seulement s'il existe une face directe de telle que . (Un exemple est donné en figure 2.) Montrer que est un complexe simplicial, mais pas . Montrer que crée un cycle dans , et que ne crée pas de cycle dans . En déduire que et ont les mêmes nombres de Betti.
Question 3.5. On note la relation entre complexes simpliciaux définie par si et seulement s'il existe un nombre fini de complexes simpliciaux , tels que, pour tout de 1 à est obtenu à partir de en contractant une face, ou est obtenu à partir de en contractant une face. On dira alors que et 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 , on appelle champ de vecteurs discret sur toute relation binaire sur 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 , 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 tel que , autrement dit si et seulement s'il n'existe pas de simplexes tels que .
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 est un complexe simplicial fixé, et que est un champ de vecteurs discret acyclique sur .
Question 4.1. On appelle sous-complexe de tout sous-ensemble de qui est un complexe simplicial. Soit l'ensemble de tous les simplexes de dimension maximale de . On admettra que, étant acyclique, pour tout sous-complexe non vide de , il existe un simplexe dans tel qu'il n'y a pas de simplexe dans avec . On fixera un tel simplexe pour chaque sous-complexe non vide, et on le notera .
Dans l'exemple ci-dessus, on vérifie que contient juste les deux simplexes et . On peut constater sur le diagramme (4) que l'on peut choisir indifféremment l'un ou l'autre pour .
Un sous-complexe sera dit normal si et seulement s'il n'existe pas de simplexes tels que .
Soit un sous-complexe normal non vide de , et un simplexe tel que . Montrer que est aussi dans , que , et que est un sous-complexe normal de .
Question 4.2. Un simplexe de est dit critique si et seulement s'il n'existe pas de simplexe de tel que .
Soit un sous-complexe normal non vide de . Montrer que, si est critique, alors est un sous-complexe normal de .
Question 4.3. Pour tout sous-complexe normal de , on note le nombre de simplexes critiques de , et le -ième nombre de Betti de . Montrer que l'on a les inégalités de Morse :
pour tout , ainsi que l'égalité de Morse :
(Indication : supprimer dans le bon ordre des simplexes de , 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 , en déduire les inégalités de Morse faibles :
pour tout .
5 Évasivité
Soit ( ) un complexe simplicial fixé, , .
Le but de cette partie est d'examiner la possibilité d'écrire un programme prenant en entrée un sous-ensemble de et retournant Vrai si est un simplexe de , Faux sinon.
On se limite à des programmes qui procèdent uniquement en posant des questions de la forme "est-ce que ?" ( ), 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 pour .
Un reconnaisseur sera estimé efficace s'il peut décider si , pour tout , en posant strictement moins de questions. Pour chercher un reconnaisseur efficace pour , on va jouer sur l'ordre dans lequel il pose les questions.
On associera à chaque reconnaisseur une application qui à tout sous-ensemble de associe une permutation de , vérifiant la propriété : pour tout , si et alors pour tout .
La façon de construire l'application à partir de est la suivante. Supposons que, pour décider si pose comme première question "est-ce que ?", alors on pose . Ensuite, si pose comme deuxième question "est-ce que ?", alors on pose , et ainsi de suite. Intuitivement, 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 ième question, alors on aurait posé les mêmes premières questions pour reconnaître .
Dans la suite, on fixera un reconnaisseur . On note la famille de permutations vérifiant ( ) qui lui est associée.
On définit par si et seulement si et . (On rappelle que est le nombre de sommets de .) Comme précédemment, on définit par si et seulement si ou .
Question 5.1. Montrer que pour tout , il existe un unique tel que .
Question 5.2. Soit l'ensemble des suites finies ( ) d'entiers naturels. On appelle la longueur de la suite . La suite [] de longueur nulle est la suite vide. On définit la relation binaire par si et seulement s'il existe satisfaisant les conditions (a) et (b) :
(a) pour tout ;
(b) , ou bien et ;
Montrer que est un ordre strict, c'est-à-dire une relation irréflexive et transitive.
Question 5.3. Pour tout , on pose , où dénote la différence symétrique. On pose d'autre part la suite croissante des indices , tels que . (Par exemple, si , alors est .)
Montrer que implique . En déduire que est un champ de vecteur discret acyclique sur .
Question 5.4. Un sous-ensemble non vide de est évasif si et seulement si et , ou bien et .
Le reconnaisseur est inefficace si et seulement s'il existe un sous-ensemble évasif. Il est efficace sinon. L'idée est que est inefficace si et seulement s'il y a un simplexe non vide tel que, pour décider si est dans , on est obligé de poser toutes
les questions jusqu'à la dernière. Aucun reconnaisseur ne teste jamais l'appartenance de l'ensemble vide à ; ceci est dû au fait que l'ensemble vide n'est jamais dans , et justifie la définition.
Soient les nombres de Betti de .
Montrer le théorème de Kahn-Saks-Sturtevant : quel que soit le reconnaisseur pour , il y a au moins sous-ensembles évasifs pour . En déduire que ceci implique qu'il n'existe aucun reconnaisseur efficace pour dès que 2. On pourra utiliser la question 4.4.
Les complexes simpliciaux de la figure 1 ont-ils des reconnaisseurs efficaces?
ENS Informatique Fondamentale (Maths Info) MP PC 2004 - Version Web LaTeX | WikiPrépa | WikiPrépa
