2024-Mines-Pc2-corrigé

Mines-Ponts — PC — 2024 — Mathématiques II

Problème inverse pour les matrices de distance euclidienne

Notations et rappels

Soit {n\geq1}. On utilise le produit scalaire euclidien usuel {(x,y)=x^Ty} et la norme associée. La distance entre deux points de vecteurs coordonnées {x,y} est {\|x-y\|}.

Un endomorphisme symétrique {f} est positif lorsque {(x,f(x))\geq0} pour tout {x} ; une matrice symétrique {A} est positive lorsque {x^TAx\geq0} pour tout {x}. Ces propriétés correspondent dans une base orthonormée.

Une matrice de distance euclidienne, abrégée MDE, est une matrice {D=(d_{ij})} d’ordre {n} pour laquelle il existe {m\geq1} et des points {A_1,\ldots,A_n\in\mathbb R^m} tels que {d_{ij}=d(A_i,A_j)^2}.

On cherche à construire une MDE de spectre prescrit. On admet qu’un endomorphisme symétrique est positif si et seulement si toutes ses valeurs propres sont positives ou nulles.

1 — Matrices de Hadamard

Une matrice de Hadamard d’ordre {n} a tous ses coefficients dans {\{-1,1\}} et {H/\sqrt n} est orthogonale.

1. Donner des exemples de matrices de Hadamard d’ordres {1} et {2}.
2. Montrer que multiplier une ligne ou une colonne d’une matrice de Hadamard par {-1}, ou échanger deux lignes ou deux colonnes, donne encore une matrice de Hadamard.
3. Montrer qu’on peut obtenir une matrice de Hadamard d’ordre {n} dont la première ligne ne contient que des {1}. En déduire que {n} est pair si {n\geq2}.
4. Montrer que si une matrice de Hadamard est d’ordre {n\geq4}, alors {4} divise {n}. On pourra normaliser la première ligne et regrouper les {n/2} coefficients {1} de la deuxième ligne.

2 — Quelques résultats sur les endomorphismes symétriques

Soit {f} symétrique sur {\mathbb R^n}, de valeurs propres ordonnées {\lambda_1\leq\cdots\leq\lambda_n}. Pour {1\leq k\leq n}, on note {\pi_k} l’ensemble des sous-espaces de dimension {k}. L’existence des extrema considérés est admise.

5. Justifier l’existence d’une base orthonormée {(e_1,\ldots,e_n)} telle que {f(e_i)=\lambda_i e_i}. On conserve cette base.
6. Pour un sous-espace {S_k} de dimension {k}, poser {T_k=\operatorname{Vect}(e_k,\ldots,e_n)}. Justifier {S_k\cap T_k\ne\{0\}}.
7. En considérant un vecteur de {S_k\cap T_k}, montrer que {\max_{x\in S_k,\ \|x\|=1}(x,f(x))\geq\lambda_k.}
8. À l’aide de {S=\operatorname{Vect}(e_1,\ldots,e_k)}, montrer la formule de Courant–Fischer : {\lambda_k=\min_{S\in\pi_k}\left(\max_{x\in S,\ \|x\|=1}(x,f(x))\right).}
9. Si {M} est symétrique positive, montrer qu’il existe {B\in\mathcal M_n(\mathbb R)} telle que {M=B^TB}.

En déduire que si {M} est symétrique et possède une seule valeur propre strictement positive {\lambda}, d’espace propre de dimension {1} engendré par un vecteur unitaire {u}, alors {M=\lambda uu^T-B^TB} pour une certaine matrice {B}.

3 — Caractérisation des MDE

On note {e=(1,\ldots,1)^T}, {\Delta_n} l’ensemble des MDE d’ordre {n}, et {\Omega_n} l’ensemble des matrices symétriques positives {A} telles que {Ae=0}.
On pose {P=I_n-\frac1n ee^T,\quad T(D)=-\frac12PDP.}Pour {A\in\Omega_n}, si {a=(A_{11},\ldots,A_{nn})^T}, on définit {K(A)=ea^T+ae^T-2A.}

10. Montrer que {P} est symétrique et représente la projection orthogonale sur {\operatorname{Vect}(e)^\perp}.
11. Soit {D\in\Delta_n}, réalisée par des points {A_i} de vecteurs coordonnées {x_i}. Soient {M_A} la matrice de colonnes {x_i} et {C=(\|x_i\|^2)_i}. Exprimer {D} en fonction de {Ce^T}, {eC^T} et {M_A^TM_A}, puis montrer {T(D)\in\Omega_n}.
12. Montrer que {K(A)\in\Delta_n} pour tout {A\in\Omega_n}.
13. Montrer que {T\circ K=\operatorname{Id}_{\Omega_n}}.

L’énoncé indique également, sans en demander la preuve, que {K\circ T=\operatorname{Id}_{\Delta_n}} et que {T} et {K} sont des bijections réciproques.

14. Montrer qu’une matrice symétrique {D} à coefficients positifs ou nuls et de diagonale nulle est MDE si et seulement si {-\tfrac12PDP} est positive.
15. Montrer qu’une matrice symétrique non nulle, à coefficients positifs ou nuls et de diagonale nulle, ayant une seule valeur propre strictement positive d’espace propre de dimension {1} engendré par {e}, est MDE.

4 — Spectre des MDE

On conserve les notations précédentes.

16. Préciser la somme des valeurs propres d’une MDE d’ordre {n}.
17. Pour une MDE {D} non nulle, montrer que {x^TDx\leq0} pour tout {x\in e^\perp}.
18. Pour une MDE non nulle de valeurs propres {\lambda_1\leq\cdots\leq\lambda_n}, montrer que {\lambda_{n-1}\leq0}, puis qu’elle possède exactement une valeur propre strictement positive.

5 — Problème inverse pour les MDE

Soit {H} une matrice de Hadamard d’ordre {n}, dont la première ligne est constante égale à {1}. On se donne {\lambda_1>0\geq\lambda_2\geq\cdots\geq\lambda_n,\quad\sum_{i=1}^n\lambda_i=0.}On pose {U=H/\sqrt n}, {\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)} et {D=U^T\Lambda U}.

19. Montrer que {D} est symétrique, à coefficients positifs et de diagonale nulle, de valeurs propres {\lambda_1,\ldots,\lambda_n}, avec {\dim E_{\lambda_1}(D)=1}.
20. Montrer que {D} est une MDE.
21. Donner une MDE d’ordre {4} de spectre {\{5,-1,-2,-2\}}.

L’énoncé conclut en soulignant les limites de cette construction : elle suppose l’existence d’une matrice de Hadamard de l’ordre considéré. Il rappelle qu’à la date du sujet, leur existence pour tout ordre multiple de {4} n’est pas établie, tandis qu’il existe aussi des MDE d’ordre impair.