L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Soit un entier . On note ( ) la base canonique de ( est le vecteur ligne qui a toutes ses coordonnées nulles, sauf la -ème qui vaut 1 ). On pose aussi .

On considère , l'ensemble des matrices réelles de taille . Une sous-matrice dans , est obtenue en choisissant lignes et colonnes et tous les coefficients qui sont sur ces lignes et colonnes dans la matrice de départ. Par exemple

Une matrice carrée de est une matrice de permutation s'il existe une permutation de telle que et si . On notera cette matrice dans la suite. Ainsi, si . Attention, dans la suite du sujet, on sera souvent amené à faire des produits matriciels de la forme vecteur-ligne matrice.

On note . Si , on note le vecteur des coordonnées de triées dans l'ordre décroissant. Plus formellement, est le seul vecteur dans qui est de la forme pour une matrice de permutation . Par exemple, dans , si , alors .

On définit la relation de la façon suivante. Soient si

Par exemple, si et , alors ( ), et les sommes partielles vérifient:

ce qui implique .

Question 1.1. Vérifier que n'est pas une relation d'ordre sur mais en est une sur .
Question 1.2. Montrer que si et seulement si

Question 1.3. Montrer que si avec , alors .

Une matrice réelle carrée est une matrice doublement stochastique si toutes ses composantes sont positives et si les sommes sur les lignes et sur les colonnes valent toutes un:

Question 2.1. Soit une matrice doublement stochastique. Montrer que 1 est valeur propre de . Soient et deux matrices doublement stochastiques, montrer que est aussi doublement stochastique.

Question 2.2. Soit une matrice de . Montrer que si pour tout , alors est doublement stochastique (on regardera l'effet de sur les vecteurs e et ).

Question 2.3. Soit une matrice doublement stochastique. Soient tels que . Montrer qu'il existe une matrice doublement stochastique telle que . Montrer que .

Soit , et une matrice de permutation. Une ( )-transformation est une application linéaire de de la forme suivante: , avec la matrice , où est la matrice identité.

Question 2.4. Soit . Exprimer les coordonnées de en fonction de celles de lorsque est la matrice d'une transposition (c'est-à-dire une permutation qui échange seulement deux coordonnées).

Question 2.5. Soient avec et . Montrer qu'il existe une ( )transformation de la forme décrite en 2.4 telle que le vecteur vérifie et le cardinal de l'ensemble est strictement plus grand que le cardinal de .

Question 2.6. Soient . Déduire des questions précédentes que si et seulement si, il existe , matrice doublement stochastique, telle que .

Question 2.7. Écrire un programme Transf (dans un langage de haut niveau, comme par exemple celui employé à la question 3.6 ) qui construit une matrice répondant à la question 2.5.

Remarque: le programme Transf est la brique de base d'un programme qui construirait, pour tout couple , une matrice telle que . La construction d'un tel programme n'est pas demandée.

Question 2.8. Soit une matrice dans . Montrer que:

contient une sous-matrice nulle de taille avec .
(On pourra faire une récurrence sur pour le sens .)
Question 2.9. Montrer que si est une matrice doublement stochastique, alors il existe une permutation de telle que .

Soit . Montrer que si alors est de la forme , avec et doublement stochastique.

Question 2.10. (Théorème de Birkhoff) Soit une matrice doublement stochastique. Déduire des questions précédentes qu'il existe un nombre fini de matrices de permutations, et des réels positifs avec tels que . De plus, montrer que l'on peut choisir .

Question 2.11. En déduire la construction de l'ensemble des vecteurs tels que pour compléter la figure 1 (dans , en projection orthogonale à ( )) avec .

Un graphe fini est formé d'un ensemble fini de sommets et d'un ensemble de paires (ensembles à deux éléments) avec , appelées arêtes. Un graphe est souvent représenté par des points du plan pour les sommets et des liens entre sommets pour les arêtes. Une coloration des arêtes de avec couleurs est une application telle que les couleurs de deux arêtes et ayant un sommet en commun sont différentes:
. Un graphe est dit -coloriable si on peut colorier ses arêtes avec couleurs, en utilisant fois la couleur , pour . La figure 2 donne un exemple de coloration des arêtes d'un graphe avec 3 couleurs. Ce graphe est -coloriable (la couleur 1 est utilisée 3 fois, la couleur 2,3 fois et la couleur 3,2 fois).

Question 3.1. Soit un graphe -coloriable avec . Montrer que est aussi ( )-coloriable.

Question 3.2. Soit . Montrer que si avec , alors .

Question 3.3. En déduire que si est ( )-coloriable, alors est ( )coloriable dès que et . On pourra s'inspirer de la méthode utilisée pour la question 2.5.

Un tournoi est formé d'un ensemble fini de sommets et d'un ensemble de couples ( ). Pour deux sommets quelconques et avec , il y a toujours soit soit, , et pas les deux. De plus . Après numérotation des sommets du tournoi, , sa matrice d'incidence est une matrice de , avec

Figure 3: Tournoi à 4 sommets. Les couples sont représentés par les arcs .

Un tournoi peut représenter une compétition sportive dans laquelle équipes jouent toutes une fois les unes contre les autres. La présence du couple ( ) dans signifie que a gagné contre . Le score du sommet est le nombre de couples de la forme ( ). Avec
l'interprétation donnée précédemment, c'est le nombre de victoires de l'équipe . Le score du tournoi est le vecteur des scores de ses sommets: . La figure 3 montre un tournoi avec un score .

Question 3.4. Montrer qu'il existe un tournoi dont le score est ( ).
Question 3.5. Montrer que si est le score d'un tournoi, alors .

Pour la question qui suit, on considère un vecteur d'entiers positifs, tels que et aussi (triés dans l'ordre croissant). L'objet de la question est de proposer un algorithme qui construit un tournoi de score .
est une matrice initialisée à zéro: . La procédure Tri construit une matrice de permutation qui trie les premières coordonnées de dans l'ordre croissant et laisse les coordonnées inchangées. Par exemple, si et alors (les 4 premières coordonnées sont triées et le reste est inchangé). On considère l'algorithme suivant:
Tournoi ( )

Pour $i$ décroissant de $n$ à 1 faire \{
    Pour $j$ croissant de 1 à $s_{i}$ faire $\left\{M_{i j} \leftarrow 1 ;\right\}$
    Pour $j$ croissant de $s_{i}+1$ à $i-1$ faire $\left\{M_{j i} \leftarrow 1 ; s_{j} \leftarrow s_{j}-1 ;\right\}$
    $Q \leftarrow$ Tri $(s, i)$;
    $\left.s \leftarrow s Q ; M \leftarrow Q^{-1} M Q ;\right\}$

(une boucle croissante de à avec n'est pas exécutée)
Question 3.6. Soit le vecteur modifié par le premier passage dans la boucle sur . Montrer que . En déduire que l'algorithme Tournoi ( ) construit la matrice d'incidence d'un tournoi de score ( ), à une permutation près des indices.

Une fonction réelle est symétrique si pour toute matrice de permutation et tout .
Une fonction réelle est croissante (au sens usuel) si ( ) .
Une fonction réelle est Schur-croissante si . Elle est Schur-décroissante si - est Schur-croissante.
Soit une fonction réelle et . On définit , par .

Question 4.1. Montrer que si est Schur-croissante, alors est symétrique. Montrer que est Schur-croissante si et seulement si elle est symétrique et Schur-croissante en ses deux premiers arguments (autrement dit, est Schur-croissante pour tout , si ) (S'inspirer de la méthode utilisée à la question 2.6).

Question 4.2. Soit et . On définit par . Montrer que si est croissante au sens usuel et Schur-croissante et si est convexe, alors est Schur-croissante.

On considère un polygone à côtés ( ) inscrit dans un cercle de rayon 1 centré en (voir la figure 4 pour le cas ). On appelle les points de contact successifs du polygone avec le cercle (en choisissant le premier point arbitrairement, et en tournant dans le sens trigonométrique). On note l'angle (en radian) formé par les points si et par les points pour .
Question 4.3. Montrer que si le centre du cercle est à l'intérieur du polygone alors l'aire du polygone est une fonction Schur-décroissante des angles .
Question 4.4. Montrer que le polygone régulier a la plus grande aire parmi les polygones à côtés inscrits dans le cercle.

On considère maintenant les polygones à côtés ( ) circonscrits au cercle unité de centre (voir la figure 5 ). On appelle les points de contacts successifs, dans l'ordre trigonométrique, du polygone avec le cercle (qui sont maintenant les points de tangence au cercle), et l'angle formé par les points si et par les points pour . On note le polygone ainsi formé.

On note la longueur de la partie du cercle (centré en et de rayon ) qui reste dans le polygone (voir la figure 5). En particulier, , si .

Question 4.5. Montrer que, pour tout est une fonction Schur-croissante de dans .

Question 4.6. En déduire la forme d'un polygone , circonscrit au cercle unité, dont l'intérieur a le plus petit moment de rotation, défini par:

Qu'en est-il pour l'aire?