HEC, ESSEC 2023 Sujet 0Maths approfondies

Dans tout ce problème, \(n\) et \(p\) sont deux entiers naturels tels que \(n \geqslant 2\) et \(p \geqslant 1\).

Pour tout entier naturel non nul \(k\) :

• on identifie chaque élément de \(\mathbb{R}^{k}\) à la matrice colonne de ses coordonnées dans la base canonique,

• on identifie chaque endomorphisme de \(\mathbb{R}^{k}\) à sa matrice dans la base canonique,

• on rappelle que si \(X\) et \(Y\) sont deux éléments de \(\mathbb{R}^{k}\), le produit scalaire canonique de \(X\) et \(Y\) vaut \({}^t\!\, XY\) où \({}^t\!X\) désigne la transposée de \(X\).

On utilise les notations suivantes :

• \(\mathcal{S}_{n}\) désigne l’ensemble des matrices carrées d’ordre \(n\) symétriques réelles, et \(\mathcal{H}_{n}\) le sous-ensemble de \(\mathcal{S}_{n}\) formé des matrices dont tous les coefficients diagonaux sont nuls,

• \(U_{n}\) est le vecteur colonne de \(\mathbb{R}^{n}\) dont toutes les composantes valent 1 et \(H_{n}=\mathrm{I}_{n}-\frac{1}{n} \, U_{n} \,{}^t\!\, U_{n}\) où \(\mathrm{I}_{n}\) désigne la matrice identité d’ordre \(n\),

• Dans tout le problème, si \(A \in \mathcal{H}_{n}\) est d’élément générique \(a_{i, j}\), c’est-à-dire \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\), on notera : \[\forall i \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right], \ a_{i}=\frac{1}{n} \sum_{k=1}^{n} a_{i, k}=\frac{1}{n} \sum_{k=1}^{n} a_{k, i}\quad \text{et} \quad a=\frac{1}{n^{2}} \sum_{1 \leqslant i, j \leqslant n} a_{i, j}=\frac{1}{n} \sum_{i=1}^{n} a_{i}\]

• On dit qu’une matrice \(A \in \mathcal{H}_{n}\) d’élément générique \(a_{i, j}\) est une matrice euclidienne de type \((n, p)\), s’il existe \(n\) vecteurs \(X_{1}, \ldots, X_{n}\) de \(\mathbb{R}^{p}\) tels que : \[\forall(i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^{2}, \ a_{i, j}=\left\|X_{i}-X_{j}\right\|^{2}\]

  la norme étant la norme euclidienne canonique sur \(\mathbb{R}^{p}\),

• On dit alors que les vecteurs \(X_{1}, \ldots, X_{n}\) sont associés à \(A\) et réciproquement,

• On notera \(\mathcal{E}_{n, p}\) l’ensemble des matrices euclidiennes de type \((n, p)\) et \(\mathcal{E}_{n}\) la réunion des ensembles \(\mathcal{E}_{n, p}\) pour \(p \in \mathbb{N}^{*}\).

On admet que \(\operatorname{dim}\left(\mathcal{S}_{n}\right)=\frac{n \left( n+1 \right)}{2}\) et que si l’on note \(\mathcal{D}_{n}\) le sous-espace vectoriel de \(\mathcal{S}_{n}\) des matrices diagonales, \(\operatorname{dim}\left(\mathcal{D}_{n}\right)=n\).

L’objet du problème est d’établir une caractérisation des matrices euclidiennes qui sont utilisées en analyse de données.

Partie I - Une application linéaire de dans

1. 1. Montrer que \(\mathcal{H}_{n}\) est un sous-espace vectoriel de \(\mathcal{S}_{n}\) et que \(\mathcal{S}_{n}=\mathcal{H}_{n} \oplus \mathcal{D}_{n}\).

   2. En déduire la dimension de \(\mathcal{H}_{n}\).

2. 1. Soit \(X \in \mathbb{R}^{n}\). Montrer que \(\frac{1}{n} \, U_{n}\, {}^t\!\, U_{n} X\) est la projection orthogonale de \(X \operatorname{sur} \operatorname{Vect}\left(U_{n}\right)\), le sous-espace vectoriel de \(\mathbb{R}^{n}\) engendré par \(U_{n}\).

   2. En déduire que \(H_{n}\) est le projecteur orthogonal sur \(\left(\operatorname{Vect}\left(U_{n}\right)\right)^{\perp}\).

   3. \(H_{n}\) est-elle inversible? Quel est le rang de \(H_{n}\) ?

      On définit l’application \(\Phi\) de \(\mathcal{H}_{n}\) dans \(\mathcal{S}_{n}\) par : \(\forall A \in \mathcal{H}_{n}, \Phi(A)=-\frac{1}{2} H_{n} A H_{n}\).

3. Vérifier que \(\Phi\) est bien définie et qu’elle est linéaire.

4. Écrire une fonction Python Phi(A) qui retourne \(\Phi(A)\) lorsque le tableau numpy A représente la matrice \(A\).

   On supposera avoir importé numpy avec l’instruction import numpy as np.

   Que renvoie Phi(np.array([[0,2],[2,0]])) ?

5. 1. Quels sont les coefficients de la matrice \(H_{n}\) ?

   2. Soit \(A=\left(a_{i, j}\right)\) appartenant à \(\mathcal{H}_{n}\) et \(a_{i, j}^{\prime}\) l’élément générique de la matrice \(A H_{n}\). Établir pour tout \((i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^{2}\), l’égalité : \(a_{i, j}^{\prime}=a_{i, j}-a_{i}\).

   3. En déduire que \(b_{i, j}\), l’élément générique de \(\Phi(A)\), vérifie :

      \[\forall(i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^{2}, \ b_{i, j}=\frac{1}{2}\left(a_{i}+a_{j}-a_{i, j}-a\right)\]

   4. Un exemple. Calculer \(\Phi(A)\) si \(A= \begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 3 \\ 2 & 3 & 0 \end{pmatrix}\).

6. Soit \(A \in \mathrm{Ker}(\Phi)\) d’élément générique \(a_{i, j}\).

   1. Montrer que, pour tout \(i \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), \(a_{i}=\dfrac{a}{2}\).

   2. En déduire que \(a=0\) puis que \(A\) est la matrice nulle.

   3. Que peut-on en déduire pour \(\Phi\) ?

7. On considère l’ensemble \(\mathcal{K}_{n}\) des matrices \(M\) de \(\mathcal{S}_{n}\) telle que \(M U_{n}=0\).

   1. Montrer que \(\operatorname{Im}(\Phi) \subset \mathcal{K}_{n}\).

   2. Montrer que \(\mathcal{K}_{n}\) et \(\mathcal{D}_{n}\) sont en somme directe.

   3. En déduire que \(\operatorname{dim}\left(\mathcal{K}_{n}\right)=\dfrac{n \left( n-1 \right)}{2}\) et que \(\operatorname{Im}(\Phi)=\mathcal{K}_{n}\).

Partie II - Propriétés des matrices euclidiennes

Dans cette partie, \(A=\left(a_{i, j}\right)\) appartient à \(\mathcal{E}_{n, p}\) et est associée aux vecteurs \(X_{1}, \ldots, X_{n}\) appartenant à \(\mathbb{R}^{p}\).

On démontre dans cette partie que \(\Phi(A)\) ne possède que des valeurs propres positives parmi lesquelles se trouve 0.

8. Un exemple lorsque \(n=3\).

   \(A\) est la matrice associée aux vecteurs : \[X_{1}= {}^t\!\begin{pmatrix} 1 & 0 & 1 \end{pmatrix},\quad X_2 = {}^t\!\begin{pmatrix} 1 & 1& 0 \end{pmatrix} \quad \text{et} \quad X_3 = {}^t\!\begin{pmatrix} 1 & 1& 1 \end{pmatrix}\]

   Déterminer \(A\), \(\Phi(A)\), puis les valeurs propres de \(\Phi(A)\).

9. Un autre exemple dans le cas général. Dans cette question \(A\) a tous ses coefficients non diagonaux qui valent 1.

   1. En utilisant une base orthonormée de \(\mathbb{R}^{n}\), montrer que \(A\) appartient à \(\mathcal{E}_{n, n}\).

   2. Si \(b_{i, j}\) désigne l’élément générique de \(\Phi(A)\), montrer que : \[\forall (i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^{2}, \ b_{i, j}= \begin{cases} \hfill -\frac{1}{2 n} \hfill & \text {si } i \neq j \\ \hfill \frac{n-1}{2 n} \hfill & \text {si } i=j \end{cases}\]

   3. En déduire que \(\Phi(A)=\frac{1}{2} \,H_{n}\) puis que \(\operatorname{rg}(\Phi(A))=n-1\) et \(\operatorname{Sp}(\Phi(A))=\left\{0, \frac{1}{2}\right\}\).

10. Montrer que pour tout entier \(k \geqslant p\), \(A \in \mathcal{E}_{n, k}\).

11. 1. Montrer que pour tout vecteur \(Y \in \mathbb{R}^{p}\), les vecteurs \(X_{1}-Y, \ldots, X_{n}-Y\) sont aussi associés à \(A\).

    2. En déduire que l’on peut choisir les \(X_{i}\) de sorte qu’ils soient associés à \(A\) et vérifient : \[\sum_{i=1}^{n} X_{i}=0 \tag{1}\]

       On suppose dans la suite de cette partie que cette relation (1) est vérifiée.

    3. Exprimer \(a_{i, j}\) en fonction de \(\left\|X_{i}\right\|^{2},\left\|X_{j}\right\|^{2}\) et \({}^t\!X_{i} X_{j}\). En déduire que : \[a_{i}=\left\|X_{i}\right\|^{2}+\frac{1}{n} \sum_{j=1}^{n}\left\|X_{j}\right\|^{2}\] puis que : \[a=\frac{2}{n} \sum_{j=1}^{n}\left\|X_{j}\right\|^{2}\]

    4. On note \(b_{i, j}\) l’élément générique de \(\Phi(A)\). En utilisant la question 5.c), établir l’égalité : \[\forall(i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]^{2}, \ b_{i, j}={ }^{t} X_{i} X_{j}\]

       puis que, si l’on note \(X\) la matrice de \(\mathcal{M}_{p, n}(\mathbb{R})\) dont les colonnes sont \(X_{1}, \ldots, X_{n}\) : \(\Phi(A)= {}^t\!X X\).

    5. Montrer que \(\operatorname{rg}(\Phi(A))=\operatorname{rg}(X)\) et en déduire que \(\operatorname{rg}(\Phi(A)) \leqslant p\).

12. Montrer que les valeurs propres de \(\Phi(A)\) sont positives ou nulles et que 0 est une de ces valeurs propres.

Partie III - Caractérisation de Schönberg-Young-Householder
des matrices euclidiennes

On considère dans les questions 13 et 14 de cette partie \(A \in \mathcal{H}_{n}\).

On note alors \(G=\Phi(A)\), \(p=\operatorname{rg}(G)\) et on suppose que \(\operatorname{Sp}(G) \subset \mathbb{R}^{+}\) et \(p \neq 0\).

On démontre que sous ces hypothèses \(A\) est euclidienne. On établit ensuite une caractérisation des matrices euclidiennes.

13. 1. Montrer qu’il existe des réels strictement positifs \(\alpha_{1}, \ldots, \alpha_{p}\) et une matrice orthogonale \(P\) tels que \(G=P \Delta^2 \,{}^t\!P\) où \(\Delta\) est la matrice diagonale dont les \(p\) premiers éléments diagonaux sont \(\alpha_{1}, \ldots, \alpha_{p}\) et les autres coefficients sont nuls.

    2. Montrer que les \(n-p\) dernières lignes de \(\Delta \, {}^t\!P\) sont nulles.

    3. On considère \(X\) la matrice de \(\mathcal{M}_{p, n}(\mathbb{R})\) dont les lignes sont les \(p\) premières lignes de \(\Delta^{t} P\). Montrer que \(G={}^t\!X X\).

14. On note \(X_{j}\) la \(j\)-ème colonne de \(X\).

    1. Montrer que l’élément générique de \(G\) est \({}^t\!X_{i} X_{j}\).

    2. En utilisant que \(G U_{n}=0\), en déduire que \(\sum\limits_{j=1}^{n} X_{j}=0\).

    3. En conclure que \(A\) est la matrice euclidienne associée aux points \(X_{1}, \ldots, X_{n}\) et que \(A \in \mathcal{E}_{n, p}\).

15. 1. En utilisant les résultats de la partie II et ceux de cette partie, démontrer que l’on a, pour toute \(A \in \mathcal{H}_{n}\), l’équivalence suivante : \[A \in \mathcal{E}_{n} \Longleftrightarrow \operatorname{Sp}(\Phi(A)) \subset \mathbb{R}^{+}\]

       et que, si \(A \in \mathcal{E}_{n}\) n’est pas la matrice nulle, \(p=\operatorname{rg}(\Phi(A))\) est la valeur minimale de \(p\) pour laquelle on a \(A \in \mathcal{E}_{n, p}\).

    2. En déduire que \(\mathcal{E}_{n}=\mathcal{E}_{n, n-1}\).

    3. Application. En utilisant la matrice de la question 9 et le résultat précédent, montrer que dans \(\mathbb{R}^{n-1}\), il existe \(n\) vecteurs \(X_{1}, \ldots , X_{n}\) tels que \(\left\|X_{i}-X_{j}\right\|=1\) pour tout \(i \neq j\) mais pas \(n+1\) ou plus.

16. On importe la bibliothèque linalg de numpy en exécutant import numpy.linalg as al et on saisit une matrice A qui représente une matrice de \(\mathcal{H}_{n}\).

    Donner une commande Python comportant Phi(A) et la fonction al.eig qui vaut True lorsque A représente une matrice euclidienne et False sinon.

17. Soit \(M \in \mathcal{S}_{n}\). Montrer que \(\operatorname{Sp}(M) \subset \mathbb{R}^{+}\) si et seulement si pour tout élément \(X\) de \(\mathbb{R}^{n},\ {}^t\!X M X \geqslant 0\).

    En déduire que, pour toute \(A \in \mathcal{H}_{n}\) : \[A \in \mathcal{E}_{n} \Longleftrightarrow \forall X \in \mathbb{R}^{n}, \ {}^t\!X \Phi(A) X \geqslant 0\]

18. Dans cette question, on suppose comme dans la question 5.d) que \(A=\begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 3 \\ 2 & 3 & 0 \end{pmatrix}\) et on pose \(X=\begin{pmatrix} x \\ y \\ z \end{pmatrix}\).

    1. Montrer que \({ }^{t} X \Phi(A) X=\dfrac{1}{3}\left(x^{2}+2 y^{2}+3 z^{2}-2 x z-4 y z\right)\).

    2. En déduire que \(A\) est euclidienne.

Partie IV - Une condition nécessaire et une condition suffisante utilisant la trace

On établit dans cette partie une condition nécessaire et une condition suffisante, assez faciles à vérifier, pour qu’une matrice de \(\mathcal{H}_{n}\) soit euclidienne.

Pour toute matrice \(M \in \mathcal{S}_{n}\) semblable à une matrice diagonale dont les valeurs propres non nulles sont \(\lambda_{1} \geqslant \ldots \geqslant \lambda_{r}\) où \(r \geqslant 1\), on pose :

\[m=\frac{\operatorname{Tr}(M)}{r}=\frac{1}{r} \sum_{k=1}^{r} \lambda_{k} \quad \text{et} \quad s=\sqrt{\frac{\operatorname{Tr}\left(M^{2}\right)}{r}-m^{2}}\]

19. Soit \(M \in \mathcal{S}_{n}\). On pose \(\Lambda=\begin{pmatrix} \lambda_{1} \\ \vdots \\ \lambda_{r} \end{pmatrix}\) et on rappelle que \(U_{r}=\begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}\).

    1. Montrer que \(m=\dfrac{1}{r} \,{}^t\!\, U_{r} \Lambda\) puis que \(m^{2} \leqslant \dfrac{\operatorname{Tr}\left(M^{2}\right)}{r}\). En déduire que la définition de \(s\) est toujours possible.

    2. Montrer que \(s^{2}=\dfrac{1}{r} \,{}^t\!\Lambda H_{r} \Lambda\), où \(H_{r}=\mathrm{I}_{r}-\frac{1}{r} \, U_{r} {}^t\!\, U_{r}\).

    3. Soit \(Y \in \mathbb{R}^{r}\), montrer que :

       \[\left|{ }^{t} Y H_{r} \Lambda\right| \leqslant \sqrt{{ }^{t} Y H_{r} Y} \sqrt{{ }^{t} \Lambda H_{r} \Lambda}\]

       en déduire que :

       \[-s \sqrt{r} \sqrt{{ }^{t} Y H_{r} Y} \leq{ }^{t} Y H_{r} \Lambda \leqslant s \sqrt{r} \sqrt{{ }^{t} Y H_{r} Y}\]

    4. On suppose que \(Y\) est le \(r\)-ième vecteur de la base canonique de \(\mathbb{R}^{r}\).

       Montrer que \({ }^{t} Y H_{r} Y=\dfrac{r-1}{r}\) et \({ }^{t} Y H_{r} \Lambda=\lambda_{r}-m\).

       En déduire que :

       \[\lambda_{r} \geqslant m-s \sqrt{r-1}\]

    5. Montrer que \(: r^{2}\left(m-\lambda_{r}\right)^{2} \geqslant \sum\limits_{k=1}^{r}\left(\lambda_{k}-\lambda_{r}\right)^{2}\) et que \(\sum\limits_{k=1}^{r}\left(\lambda_{k}-\lambda_{r}\right)^{2}=r s^{2}+r\left(m-\lambda_{r}\right)^{2}\). En conclure que si \(r \geqslant 2\) :

       \[\lambda_{r} \leqslant m-\frac{s}{\sqrt{r-1}}\]

20. On suppose, dans cette question, que \(n \geqslant 3\) et l’on considère \(A \in \mathcal{H}_{n}\).

    On utilise les notations de la question précédente avec \(M=-H_{n} A H_{n}=2 \, \Phi(A)\), en supposant que le rang de \(M\), noté \(r\), est supérieur ou égal à 1.

    1. Montrer que \(m=\dfrac{1}{n r} \,{}^t\!\, U_{n} A U_{n}\) et que \(s^{2}=\dfrac{1}{r} \, \operatorname{Tr} (A^{2} )-\dfrac{2}{n r} \, {}^t\!\, U_{n} A^{2} U_{n}+ \left( r-1 \right)m^{2}\).

    2. Montrer que si \(A\) est euclidienne alors \(\dfrac{2}{n} \,{}^t\!\,U_{n} A^{2} U_{n} \geqslant \operatorname{Tr} (A^{2} )\).

    3. On rappelle que \(r \leqslant n-1\). Montrer que si l’on a \(m \geqslant 0\) et :

       \[\frac{2}{n} \,{}^t\!\, U_{n} A^{2} U_{n}-\frac{n-3}{n^{2}(n-2)}\left( {}^t\!\, U_{n} A U_{n}\right)^{2} \geqslant \operatorname{Tr} (A^{2} )\]

       alors \(A\) est euclidienne.

21. Exemples.

    1. On suppose dans cette question que \(n=3\) et \(A \in \mathcal{H}_{3}\).

       Montrer que \(A \in \mathcal{E}_{3}\) si et seulement si \(m \geqslant 0\) et \(\dfrac{2}{3} \,{}^t\!\, U_{3} A^{2} U_{3} \geqslant \operatorname{Tr} (A^{2} )\). En déduire pour quelles valeurs de \(a\), la matrice \(\begin{pmatrix} 0 & a & 1 \\ a & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\) est euclidienne.

    2. Montrer que la matrice de la question 9 satisfait la condition suffisante de la question 20.c).

22. Écrire une fonction Python CsEuclidienne(A) qui renvoie True si A, représentant une matrice de symétrique à élément diagonaux tous nuls, vérifie la condition suffisante de la question 20.c) et False sinon.