l'ensemble des permutations de l'ensemble des entiers compris entre 1 et , c'est-à-dire des applications de vers lui-même qui sont bijectives. C'est un ensemble fini ayant éléments et qui forme un groupe pour la loi de composition o, appelé groupe symétrique d'ordre .
. Il est muni du produit scalaire défini par ainsi que de la norme associée définie par .
. Il est muni du produit scalaire défini par ainsi que de la norme associée définie par .
la matrice unité de .
l'ensemble des matrices orthogonales de . On rappelle que c'est un groupe pour le produit matriciel appelé groupe orthogonal d'ordre .
.
On définit également les points suivants.
Pour tous , on définit le segment .
Une partie de est dite convexe lorsque pour tous , on a .
Si est convexe, est dit extrémal (dans ) si l'égalité avec et dans implique .
Ce problème a pour objectif d'étudier des propriétés de certains sous-ensembles de et d'en donner quelques illustrations géométriques. Il est constitué de cinq parties, largement indépendantes entre elles.

I Étude de l'ensemble

Dans toute cette partie, on s'intéresse à l'ensemble défini par

- Donner une condition nécessaire et suffisante sur

pour que la matrice

appartienne à

.
I.

, que dire de ses valeurs propres réelles ?

Calculer le spectre de

et en déduire que

n'appartient pas à

Montrer que

est convexe.
I.D - Soit

. On note

ses vecteurs colonnes.

Montrer que

. En déduire une expression de

à l'aide des coefficients de

- Montrer alors que

contient la boule unité fermée de

.
On pourra utiliser l'inégalité de Cauchy-Schwarz.
I.

- Montrer que

est contenu dans la boule fermée de centre 0 et de rayon

. Montrer de plus que cette inclusion est stricte dans le cas

.
I.

- Soit

symétrique (vérifiant

). Montrer que

si et seulement si toutes ses valeurs propres sont dans

.
I.H - Soit

. Montrer que

si et seulement si toutes les valeurs propres de

sont dans

II Matrices de permutation

II.A - Cas

L'ensemble

des permutations de

contient 6 éléments. On note (

) la base canonique de

.
II.A.1) Sachant qu'une application

est déterminée par la donnée du triplet (

), expliciter les 6 applications de

.
II.A.2) Justifier que

est diagonalisable dans

et préciser ses valeurs propres complexes.
II.A.3) Justifier que

. En déduire l'existence de

telle que

. Combien existe-t-il de matrices

telles que

?
II.A.4) Soit

Le segment

est-il contenu dans

Les ensembles

sont-ils égaux ?
II.A.5) Déterminer la dimension du sous-espace vectoriel (réel) de

engendré par l'ensemble

II.B - Cas général

II.B.1) On note (

) la base canonique de

. Pour tout

, on note

l'unique matrice de

telle que pour tout

.
Préciser les coefficients de

et justifier que

.
II.

- Une matrice de la forme

est dite matrice de permutation et on note

l'ensemble des matrices de permutations de

.
Montrer que l'application

du groupe (

) dans le groupe multiplicatif

est injective et que, pour tout

.
On en déduit que

est un sous-groupe de

, fini de cardinal

.
II.C.1) Pour tout

, montrer que

est fini. En déduire l'existence de

tel que

III Matrices magiques

Une matrice

dans

est dite magique s'il existe un réel

tel que pour tout

, on ait :

On note

l'ensemble des matrices magiques de

.
On note encore

.
Soient également

la droite de

engendrée par

(l'ensemble des vecteurs colonnes de

dont la somme des coordonnées vaut 0 ).
III.

- Montrer que les matrices de permutations sont magiques, c'est-à-dire que

.
III. B - Montrer que les sous espaces

sont supplémentaires dans

.
III.

- Soit

.
III.C.1) Montrer que

est magique si et seulement s'il existe un réel

tel que

.
III.C.2) Montrer que

est magique si et seulement si

laisse stable

.
III.C.3) Montrer que

est un sous-espace vectoriel de

stable pour le produit matriciel.
III.C.4) Montrer que

est une application linéaire, vérifiant

pour tous

.
III.C.5) Soit

magique et inversible. Montrer que

est magique et calculer

.
III.D - Déterminer

.
III.

- Montrer que pour tout

, on a

et que

est stable pour le produit matriciel.
III.

- Déterminer le centre de

c'est-à-dire :

On pourra utiliser les matrices de permutation élémentaire

avec

, associée à la permutation de

qui échange

et laisse invariant les autres éléments.
III.

- Déterminer un supplémentaire de

dans

III.H - Matrices super-magiques

Une matrice

à coefficients dans

de taille

est dite super-magique s'il existe un nombre

tel que les sommes des coefficients sur les lignes, sur les colonnes et sur les deux diagonales soient toutes égales à

.
III.H.1) Exprimer les conditions précédentes en fonction des

(coefficient de

à la

-ème ligne et

-ème colonne).
III.H.2) On choisit

. Déterminer une base de l'espace vectoriel des matrices super-magiques de

IV Matrices bistochastiques

Une matrice

est dite bistochastique si

est magique (

), tous les coefficients de

sont positifs et

. Ainsi si

on doit avoir :

.
On note

l'ensemble des matrices bistochastiques de

.
IV.

- Montrer que les matrices de permutation sont bistochastiques, c'est-à-dire que

.
IV.B - Les matrices bistochastiques sont-elles toujours inversibles?
IV.C - Montrer que

est stable pour le produit matriciel.

- Montrer que

IV.E - Exemple 1

IV.E.1) Pour tout

, on note

Justifier qu'une telle matrice

est diagonalisable et préciser ses valeurs propres.
IV.E.2) Déterminer

tel que

soit une matrice orthogonale.
IV.E.3) Déterminer le sous-espace vectoriel de

engendré par

IV.F - Exemple 2

Pour tout

, on note

.
IV.F.1) Justifier qu'une telle matrice est diagonalisable et préciser ses valeurs propres.
IV.F.2) Existe-t-il

tel que

soit une matrice orthogonale ?

IV.G - Exemple 3

IV.G.1) Soit

Montrer que

est la réunion de deux cercles de

(muni de son produit scalaire canonique) dont on précisera les centres et rayons.
IV.G.2) Soient

tels que

Préciser dans quels cas

V Points extrémaux de

- Les sous-ensembles suivants de

sont-ils convexes :

V. - Matrices de permutations

V.B.1) Décomposer la matrice

comme combinaison linéaire, à coefficients positifs et de somme 1, de matrices de permutations. Y a-t-il unicité de cette décomposition?
V.B.2) Montrer que les matrices de permutation sont des points extrémaux de

- On peut en fait établir la réciproque et le théorème (de Birkhoff) : «Les points extrémaux de

sont exactement les matrices de permutations

»

.
On souhaite juste ici établir ce résultat dans le cas simple

.
En supposant que

dans

, avec

est un point extrémal, justifier que

est une matrice de permutation.