Connectez-vous pour consulter le corrigé.
Problème inverse pour les matrices de distance euclidienne
Durée de l’épreuve : 3 heures. L’usage de la calculatrice et de tout dispositif électronique est interdit.
Sujet du Concours commun Mines-Ponts 2024, propriété du GIP CCMP, reproduit avec son autorisation.
Soit \(n\) un entier supérieur ou égal à 1.
On note \((x,y)\) (resp. \(X^TY\)) le produit scalaire euclidien usuel de deux vecteurs \(x\) et \(y\) de \(\mathbb{R}^n\) (resp. \(X\) et \(Y\) de \(\mathcal{M}_{n,1}(\mathbb{R})\) identifié canoniquement à \(\mathbb{R}^n\)) et \(\left\| x \right\|\) la norme de \(x\) (resp. \(\left\| X \right\|\) la norme de \(X\)) associée au produit scalaire.
Etant donnés deux points \(P\) et \(P'\) de \(\mathbb{R}^n\), on note \(d(P,P')\) la distance entre \(P\) et \(P'\) associée à la norme euclidienne usuelle : \[d(P,P')=\left\| \overrightarrow{OP}-\overrightarrow{OP'} \right\|\] où \(O\) est le point origine.
Un endomorphisme symétrique \(f\) de \(\mathbb{R}^n\) est dit positif si \[\forall x\in\mathbb{R}^n,\ (x,f(x))\geqslant0\] Une matrice symétrique \(A\) de \(\mathcal{M}_n(\mathbb{R})\) est dite positive si \[\forall X\in\mathcal{M}_{n,1}(\mathbb{R}),\ X^TAX\geqslant0\]
Soit \(\mathcal{B}\) une base orthonormée de \(\mathbb{R}^n\). Un endormorphisme symétrique \(f\) de \(\mathbb{R}^n\) est positif si, et seulement si, sa matrice (symétrique) dans \(\mathcal{B}\) est positive.
On appelle matrice de distance euclidienne (on notera MDE pour abréger) une matrice carrée \(D=(d_{i,j})\) d’ordre \(n\) telle qu’il existe un entier naturel non nul \(m\) et des points \(A_1\), ... \(A_n\) de \(\mathbb{R}^m\) tels que pour tout \((i,j)\in\{1,...,n\}^2\) on a : \[d_{i,j}=d(A_i,A_j)^2\]
On se propose dans ce sujet d’apporter une réponse partielle au problème consistant à déterminer, étant donnés des réels \(\lambda_1\), ..., \(\lambda_n\), une MDE de spectre \((\lambda_1,...,\lambda_n)\).
On admet sans démonstration dans ce sujet que des endomorphismes symétriques de \(\mathbb{R}^n\) sont positifs si et seulement si leur spectre est inclus dans \(\left[0,+\infty\right[\).
On appelle matrice de Hadamard d’ordre \(n\) toute matrice \(H\) carrée d’ordre \(n\) dont tous les coefficients sont égaux à 1 ou à \(-1\) et telle que \(\frac{1}{\sqrt{n}}H\) soit orthogonale.
Donner des exemples de matrices de Hadamard d’ordre 1 et 2.
Montrer que si \(H\) est une matrice de Hadamard alors toute matrice obtenue en multipliant une ligne ou une colonne de \(H\) par \(-1\) ou en échangeant deux lignes ou deux colonnes de \(H\) est encore une matrice de Hadamard.
Montrer que si \(H\) est une matrice de Hadamard d’ordre \(n\) alors il existe une matrice de Hadamard d’ordre \(n\) dont les coefficients de la première ligne sont tous égaux à 1. En déduire que si \(n\geqslant2\) alors \(n\) est pair.
Montrer que si \(H\) est une matrice de Hadamard d’ordre \(n\) supérieur ou égal à 4, alors \(n\) est multiple de 4. On pourra commencer par montrer que l’on peut supposer la première ligne de \(H\) uniquement composée de 1 et sa deuxième ligne composée de \(n/2\) coefficients égaux à 1 puis \(n/2\) coefficients égaux à \(-1\).
Soit \(f\) un endomorphisme symétrique de \(\mathbb{R}^n\). On note \(\lambda_1\leqslant...\leqslant\lambda_n\) les valeurs propres classées par ordre croissant de \(f\). Pour \(k\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), on introduit l’ensemble \(\pi_k\) des sous-espaces vectoriels de \(\mathbb{R}^n\) de dimension \(k\). On admettra ici que les min et max considérés existent bien (cela découle de la continuité des expressions considérés).
Justifier l’existence d’une base \((e_1,...,e_n)\) orthonormée de \(\mathbb{R}^n\) formée de vecteurs propres de \(f\), le vecteur \(e_i\) étant associé à \(\lambda_i\) pour tout \(i\in\{1,...,n\}\). On garde par la suite cette base.
Soit \(k\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) et \(S_k\) un sous-espace vectoriel de \(\mathbb{R}^n\) de dimension \(k\). On pose \(T_k=\mathrm{Vect}(e_k,...,e_n)\).
Justifier que \(S_k\cap T_k\neq\{0\}\).
En considérant \(x\in S_k\cap T_k\), justifier que : \[\max_{x\in S_k,\left\| x \right\|=1}(x,f(x))\geqslant\lambda_k\]
Soit \(k\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\). A l’aide de \(S=\mathrm{Vect}(e_1,...,e_k)\in\pi_k\), montrer l’égalité : \[\lambda_k=\min_{S\in\pi_k}\left(\max_{x\in S,\left\| x \right\|=1}(x,f(x))\right)\] C’est le théorème de Courant-Fischer. On aura également besoin par la suite du résultat de factorisation suivant :
Soit \(M\) une matrice symétrique de \(\mathcal{M}_n(\mathbb{R})\). Montrer que si \(M\) est positive, alors il existe \(B\in\mathcal{M}_n(\mathbb{R})\) telle que \(M=B^T.B\). En déduire que si \(M\) n’est plus supposée positive, mais admet une unique valeur propre strictement positive \(\lambda\) d’espace propre de dimension 1 et de vecteur propre unitaire \(u\), alors il existe \(B\in\mathcal{M}_n(\mathbb{R})\) telle que \(M=\lambda u.u^T-B^T.B\).
On note \(\mathbf{e}\) la matrice de \(\mathcal{M}_{n,1}(\mathbb{R})\) dont tous les coefficients sont égaux à 1. On note \(\Delta_n\) l’ensemble des MDE d’ordre \(n\) et \(\Omega_n\) l’ensemble des matrices \(M\) symétriques positives d’ordre \(n\) telles que \(M.\mathbf{e}=0\). On note enfin \(P\) la matrice d’ordre \(n\) définie par \[P=I_n-\frac{1}{n}\mathbf{e}.\mathbf{e}^T\] On note \(T\) l’application de \(\Delta_n\) dans \(\mathcal{M}_n(\mathbb{R})\) qui à \(D\) associe \[T(D)=-\frac{1}{2}PDP\] et \(K\) l’application de \(\Omega_n\) dans \(\mathcal{M}_n(\mathbb{R})\) qui à une matrice \(A\) associe \[K(A)=\mathbf{e}.\mathbf{a}^T+\mathbf{a}.\mathbf{e}^T-2A\] où \(\mathbf{a}\) est la matrice colonne de \(\mathcal{M}_{n,1}(\mathbb{R})\) dont les coefficients sont les coefficients diagonaux de \(A\).
Montrer que \(P\) est symétrique et que l’endomorphisme de \(\mathbb{R}^n\) canoniquement associé est une projection orthogonale sur \(\mathrm{Vect}(\mathbf{e})^\perp\).
Soit \(D\in\Delta_n\). Soient \(A_1\), ... , \(A_n\) des points dont la matrice \(D\) est la matrice de distance euclidienne. On note \(x_i\) les vecteurs coordonnées des \(A_i\). Soit \(M_A\) la matrice dont les colonnes sont les \(x_i\) et \(C\) la colonne formée des \(\left\| x_i \right\|^2\). Ecrire \(D\) comme combinaison linéaire de \(C\mathbf{e}^T\), \(\mathbf{e}C^T\) et \(M_A^T.M_A\). En déduire que pour toute matrice \(D\) de \(\Delta_n\) on a \(T(D)\in\Omega_n\).
Montrer que pour toute matrice \(A\) de \(\Omega_n\) on a \(K(A)\in\Delta_n\).
Montrer que les applications \(T:\Delta_n\to\Omega_n\) et \(K:\Omega_n\to\Delta_n\) vérifient : \[T\circ K=\operatorname{Id}_{\Omega_n}\] On peut montrer (mais ce n’est pas demandé) que l’on a également \(K\circ T=\operatorname{Id}_{\Delta_n}\) et que ces deux applications sont bijections réciproques l’une de l’autre.
Montrer qu’une matrice symétrique \(D\) d’ordre \(n\) à coefficients positifs ou nuls et de diagonale nulle est MDE si et seulement si \(-\frac{1}{2}PDP\) est positive.
Montrer que toute matrice symétrique à coefficients positifs, non nulle et de diagonale nulle, ayant une unique valeur propre strictement positive d’espace propre de dimension 1 et de vecteur propre \(\mathbf{e}\) est MDE.
On conserve ici les notations de la partie précédente.
Préciser la somme \(\displaystyle\sum_{i=1}^n\lambda_i\) des valeurs propres d’une MDE d’ordre \(n\).
Soit \(D\) une MDE d’ordre \(n\) non nulle. Montrer que pour tout \(x\in\mathrm{Vect}(\mathbf{e})^\perp\), on a \[x^TDx\leqslant0\]
Soit \(D\) une MDE d’ordre \(n\) non nulle. Soient \(\lambda_1\), ... ,\(\lambda_n\) ses valeurs propres, ordonnées dans l’ordre croissant. Montrer \[\lambda_{n-1}\leqslant0\] et en déduire que \(D\) a exactement une valeur propre strictement positive.
Soit \(H\) une matrice de Hadamard d’ordre \(n\) et de première ligne constante égale à 1. Soient \(\lambda_1\) , ..., \(\lambda_n\) des réels tels que \[\lambda_1>0\geqslant\lambda_2\geqslant...\geqslant\lambda_n\] et \[\sum_{i=1}^n\lambda_i=0\] On note \(U\) la matrice \(\frac{1}{\sqrt{n}}H\) et \(\Lambda\) la matrice diagonale dont les coefficients diagonaux sont les \(\lambda_i\). On note enfin \(D=U^T\Lambda U\).
Montrer que \(D\) est symétrique, à coefficients positifs et à diagonale nulle, et a pour valeurs propres \(\lambda_1\), ..., \(\lambda_n\), avec \(\lambda_1\) d’espace propre de dimension 1.
Montrer que \(D\) est MDE.
Donner une matrice de distance euclidienne d’ordre 4 telle que son spectre soit \(\{5,-1,-2,-2\}\).
Remarquons pour finir que la portée de ce résultat est à nuancer, car outre les conditions sur les ordres possibles pour les matrices de Hadamard, on ne sait même pas s’il existe de telles matrices pour tout ordre multiple de 4 ! D’autre part, il existe évidemment des matrices de distance euclidienne d’ordre impair...
Fin du problème
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Un problème d'algèbre linéaire euclidienne : matrices de Hadamard, théorème spectral et caractérisation des matrices de distance euclidienne par leur spectre, avec une construction explicite.
Accessible et bien construit.