HEC-ESSEC 2026Maths appliquées

Le sujet se situe dans le cadre de la théorie de l’acquisition comprimée (compressed sensing) qui s’est développée depuis 2005.

Soit \(n,m\) des entiers tels que \(n>m\geqslant 1\), \(m\) bien plus petit que \(n\).

Dans le sujet, on s’intéresse au problème qui consiste à, étant donnés \(AY\) et \(A\in \mathcal{M}_{m,n}(\mathbb{R})\), \(Y\in \mathcal{M}_{n,1}(\mathbb{R})\) étant inconnu mais ayant peu de composantes non nulles, être en mesure de déterminer \(Y\) lorsque \(A\) vérifie une hypothèse que l’on précisera.

Pour tout \(d\) entier naturel non nul et \(X\in \mathcal{M}_{d,1}(\mathbb{R})\), de coefficients \(x_1,\ldots,x_d\), on pose \[\|X\|=\sqrt{\sum_{k=1}^d x_k^2}\]

On admet que l’on a défini une norme sur \(\mathcal{M}_{d,1}(\mathbb{R})\), ce qui sous-entend en particulier que :

• pour tout \(X\in \mathcal{M}_{d,1}(\mathbb{R})\), si \(\|X\|=0\), alors \(X=0\) ;

• pour tous \(X\in \mathcal{M}_{d,1}(\mathbb{R})\), \(Y\in \mathcal{M}_{d,1}(\mathbb{R})\), \[\|X\|-\|Y\|\leqslant \|X+Y\|\leqslant \|X\|+\|Y\| ;\]

• pour tous \(X\in \mathcal{M}_{d,1}(\mathbb{R})\), \(\lambda\in \mathbb{R}\), \[\|\lambda X\|=|\lambda|\|X\|.\]

Si \(\mathcal{X}\) est un ensemble d’éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\), \(\varepsilon\in \left] 0,1 \right[\) et \(A\in \mathcal{M}_{m,n}(\mathbb{R})\), on dit que \(A\) est une \((\varepsilon,\mathcal{X})\)-isométrie si pour tout \(X\in \mathcal{X}\) : \[\left( 1-\varepsilon \right) \|X\|^2\leqslant \|AX\|^2\leqslant \left( 1+\varepsilon \right) \|X\|^2\]

Pour les scripts et fonctions Python, on supposera que les instructions suivantes ont été exécutées :

import numpy as np, numpy.random as rd

Un aide-mémoire Python se trouve à la fin de l’énoncé.

Le mot « Fin » marque la fin de l’énoncé.

Préliminaire informatique

1. 1. Écrire une fonction Norme(X) qui renvoie \(\|X\|\) si le vecteur numpy X représente le vecteur colonne \(X\) de \(\mathcal{M}_{n,1}(\mathbb{R})\).

   2. On exécute les instructions suivantes :

      X = np.array([1,0,1,1,1])
      print(Norme(X)); print(Norme((1/Norme(X))*X))

      Quel affichage obtient-on dans la console ?

2. On exécute le script suivant :

   A = np.array([[2,1],[0,1],[1,0]]); X = np.array([1,-1])
   eps = 0.6
   print(Norme(np.dot(A,X))**2)
   print(1-eps <= Norme(np.dot(A,X))**2/Norme(X)**2 <= 1+eps)

   et on obtient l’affichage :

   3.0
   True

   Expliquer ces résultats.

3. On suppose que \(\mathcal{X}\), un ensemble d’éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\), est représenté par la liste finie LX de vecteurs numpy, la matrice \(A\) par le tableau numpy A et \(\varepsilon\) par eps. Écrire une fonction EstIsom(A,LX,eps) qui renvoie True si \(A\) est une \((\varepsilon,\mathcal{X})\)-isométrie et False sinon.

   En exécutant le script :

   LX = [np.array([-1,3]), np.array([1,-2])]
   print(EstIsom(np.array([[2,1],[0,1],[1,0]]), LX, 0.2))

   quel affichage obtient-on dans la console ? On justifiera sa réponse.

Le lemme de Johnson-Lindenstrauss

On considère \((\Omega,\mathcal{A},\mathbb{P})\) un espace probabilisé sur lequel sont définies les variables aléatoires \(G_{i,j}\) pour \((i,j)\in \left[\!\left[1,m\right]\!\right]\times \left[\!\left[1,n\right]\!\right]\).

Ces variables sont indépendantes et toutes de loi normale \(\mathcal{N}(0,1)\). On définit les matrices aléatoires \(M(\omega)\), pour tout \(\omega\in \Omega\), par : \[M(\omega)=\frac{1}{\sqrt{m}} \begin{pmatrix} G_{1,1}(\omega)&\cdots&G_{1,n}(\omega)\\ G_{2,1}(\omega)&\cdots&G_{2,n}(\omega)\\ \vdots&\vdots&\vdots\\ G_{m,1}(\omega)&\cdots&G_{m,n}(\omega) \end{pmatrix}\]

4. Écrire une expression Python qui réalise une simulation d’une telle matrice \(M\) si \(m\) et \(n\) sont donnés et représentés par les variables m et n.

• Soit \(X\) un élément de \(\mathcal{M}_{n,1}(\mathbb{R})\), de composantes \(x_1,\ldots,x_n\), tel que \(\|X\|=1\).

  Pour tout \(i\in \left[\!\left[1,m\right]\!\right]\), on définit les variables aléatoires \(\displaystyle Y_i=\sum_{j=1}^n x_jG_{i,j}\) et \(Z\) la variable aléatoire \(\|MX\|^2\).

5. Soit \(i\in \left[\!\left[1,m\right]\!\right]\).

   1. Soit \(j\in \left[\!\left[1,n\right]\!\right]\) tel que \(x_j\neq 0\). Quelle est la loi de \(x_jG_{i,j}\) ?

   2. En déduire la loi de \(Y_i\) et que \(\mathbb{E}(Y_i^2)=\|X\|^2=1\).

   3. Montrer que \(\displaystyle Z=\frac{1}{m}\sum_{i=1}^m Y_i^2\).

Soit \(\varepsilon\in \left] 0,1 \right[\) et \(t\in \left]0,\frac14\right[\).

6. 1. Montrer que pour tout \(i\in \left[\!\left[1,m\right]\!\right]\), \(\mathbb{E}(\mathrm{e}^{tY_i^2})\) existe et vaut \(\displaystyle \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{+\infty}\mathrm{e}^{-(1-2t)\frac{z^2}{2}}\,\mathrm{d}z\).

   2. En conclure que pour tout \(i\in \left[\!\left[1,m\right]\!\right]\), \(\displaystyle \mathbb{E}(\mathrm{e}^{tY_i^2})=\frac{1}{\sqrt{1-2t}}\).

7. On rappelle l’inégalité de Markov : si \(U\) est une variable aléatoire à valeurs positives admettant une espérance et \(a>0\) un réel, alors \[\mathbb{P}(U\geqslant a)\leqslant \frac{\mathbb{E}(U)}{a}\]

   1. Montrer que \(\mathbb{E}(\mathrm{e}^{tmZ})\) existe et que \(\mathbb{P}(Z>1+\varepsilon)\leqslant \mathbb{P}(Z\geqslant 1+\varepsilon) \leqslant \mathbb{E}(\mathrm{e}^{tmZ}) \, \mathrm{e}^{-tm(1+\varepsilon)}\)

   2. En déduire que \(\displaystyle \mathbb{P}(Z>1+\varepsilon)\leqslant \left(\frac{\mathrm{e}^{-t}}{\sqrt{1-2t}}\right)^m\mathrm{e}^{-tm\varepsilon}\)

   3. Établir que \(\displaystyle -t-\frac12\ln(1-2t)\leqslant 2t^2\) et en déduire que \(\displaystyle \mathbb{P}(Z>1+\varepsilon)\leqslant \mathrm{e}^{m(2t^2-t\varepsilon)}\)

   4. En conclure que \(\displaystyle \mathbb{P}(Z>1+\varepsilon)\leqslant \mathrm{e}^{-m\frac{\varepsilon^2}{8}}\)

8. On montrerait de même que \(\displaystyle \mathbb{P}(Z<1-\varepsilon)\leqslant \mathrm{e}^{-m\frac{\varepsilon^2}{8}}\)

   En déduire que \(\displaystyle \mathbb{P}([ Z<1-\varepsilon ] \cup [ Z>1+\varepsilon ] \leqslant 2\mathrm{e}^{-m\frac{\varepsilon^2}{8}}\)

• Soit \(\mathcal{X}=\{X_1,\ldots,X_r\}\) un ensemble d’éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\). On note, pour tout \(i\in \left[\!\left[1,r\right]\!\right]\), \(B_i\) l’événement \[\left[ \left( 1-\varepsilon \right) \|X_i\|^2\leqslant \|MX_i\|^2\leqslant \left( 1+\varepsilon \right) \|X_i\|^2\right]\]

9. 1. Pour tout \(i\in \left[\!\left[1,r\right]\!\right]\) tel que \(X_i\neq 0\), on pose \(\displaystyle U_i=\frac{1}{\|X_i\|}X_i\).

      Montrer que \(\|U_i\|=1\) et que \(B_i=\left[(1-\varepsilon)\leqslant \|MU_i\|^2\leqslant (1+\varepsilon)\right].\)

   2. On admet que la probabilité d’une réunion finie d’événements est inférieure à la somme des probabilités de ces événements.

      En déduire que la probabilité de l’événement « \(M\) n’est pas une \((\varepsilon,\mathcal{X})\)-isométrie » est inférieure à \(2r \, \mathrm{e}^{-m\frac{\varepsilon^2}{8}}.\)

   3. On suppose que \(\displaystyle m>\frac{8\ln(2r)}{\varepsilon^2}.\)

      En conclure qu’il existe une matrice \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) qui est une \((\varepsilon,\mathcal{X})\)-isométrie.

10. On suppose que \(\mathcal{X}\), un ensemble d’éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\), est représenté par la liste finie LX de vecteurs colonnes numpy. Écrire une fonction Isom(LX,m,eps) qui renvoie une matrice à \(m\) lignes et \(n\) colonnes qui est une \((\varepsilon,\mathcal{X})\)-isométrie.

\(\varepsilon\)-isométries pour les ensembles sporadiques de \(\mathcal{M}_{n,1}(\mathbb{R})\)

On conserve les notations de la partie précédente.

On rappelle que si \(E\) est un ensemble comportant un nombre fini d’éléments, son nombre d’éléments s’appelle son cardinal et se note \(\#E\).

Soit \(X\in \mathcal{M}_{n,1}(\mathbb{R})\), de composantes \(x_1,\ldots,x_n\). On note :

• \(S(X)\) l’ensemble des indices \(i\) tels que \(x_i\neq 0\), appelé support de \(X\) ;

• \(\langle X\rangle\) le nombre de composantes non nulles de \(X\), donc le cardinal de \(S(X)\) ;

• pour \(k\in \left[\!\left[0,n\right]\!\right]\), \(\mathcal{C}_k\) l’ensemble des \(X\in \mathcal{M}_{n,1}(\mathbb{R})\) tels que \(\langle X\rangle\leqslant k\) ;

• pour \(k\in \left[\!\left[0,n\right]\!\right]\), \(\mathcal{T}_k\) l’ensemble des parties de \(\left[\!\left[1,n\right]\!\right]\) de cardinal \(k\) et, pour tout \(T\in \mathcal{T}_k\), \(\mathcal{Q}(T)\) l’ensemble des éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\) dont le support est inclus dans \(T\).

11. Donner le cardinal de \(\mathcal{T}_k\) pour tout entier \(k\in \left[\!\left[0,n\right]\!\right]\).

12. 1. Déterminer \(\mathcal{C}_0\) et \(\mathcal{C}_n\).

       \(\blacktriangleright\) Soit \(k\in \left[\!\left[1,n-1\right]\!\right]\).

    2. Soit \(T\in \mathcal{T}_k\). On pose \(T=\{i_1,\ldots,i_k\}\).

       Montrer que \(\mathcal{Q}(T)\) est un sous-espace vectoriel de \(\mathcal{M}_{n,1}(\mathbb{R})\) de dimension \(k\).

    3. Montrer que \(\displaystyle \mathcal{C}_k=\bigcup_{T\in \mathcal{T}_k}\mathcal{Q}(T).\) \(\mathcal{C}_k\) est-il un sous-espace vectoriel de \(\mathcal{M}_{n,1}(\mathbb{R})\) ? Justifier la réponse.

13. Inégalité de Cauchy-Schwarz. Soit \(X\) et \(Y\) deux éléments non nuls de \(\mathcal{M}_{n,1}(\mathbb{R})\) de coefficients \(x_1,\ldots,x_n\) et \(y_1,\ldots,y_n\).

    1. Montrer que pour tout \(i\in \left[\!\left[1,n\right]\!\right]\), \(2|x_i||y_i|\leqslant x_i^2+y_i^2.\)

    2. En supposant que \(\|X\|=\|Y\|=1\), en déduire que \(\displaystyle \left|\sum_{i=1}^n x_iy_i\right|\leqslant 1.\)

    3. En conclure dans le cas général que \(\displaystyle \left|\sum_{i=1}^n x_iy_i\right|\leqslant \|X\|\|Y\|\) puis que \[\left(\sum_{i=1}^n x_iy_i\right)^2\leqslant \left(\sum_{i=1}^n x_i^2\right)\left(\sum_{i=1}^n y_i^2\right)\]

       L’inégalité reste-t-elle vraie si l’un des deux vecteurs \(X\) ou \(Y\) est nul ?

• Soit \(A=(a_{i,j})\in \mathcal{M}_{m,n}(\mathbb{R})\).

14. 1. Soit \(X\in \mathcal{M}_{n,1}(\mathbb{R})\) de composantes \(x_1,\ldots,x_n\). Montrer que \(\displaystyle \|AX\|^2=\sum_{i=1}^m\left(\sum_{j=1}^n a_{i,j}x_j\right)^2.\)

    2. En déduire que, pour tout \(X\in \mathcal{M}_{n,1}(\mathbb{R})\), \(\displaystyle \|AX\|^2\leqslant \left(\sum_{i=1}^m\sum_{j=1}^n a_{i,j}^2\right)\|X\|^2.\)

• On pose \(\displaystyle \alpha=\sqrt{\sum_{i=1}^m\sum_{j=1}^n a_{i,j}^2}.\)

15. Montrer que pour tout \((X,Y)\in \mathcal{M}_{n,1}(\mathbb{R})^2\) : \[\|AY\|-\|A(X-Y)\|\leqslant \|AX\|\leqslant \|AY\|+\|A(X-Y)\|\]

• On admet que pour tous \(k\in \left[\!\left[0,n\right]\!\right]\), \(T\in \mathcal{T}_k\) et \(\delta\in \left]0,1 \right]\), il existe un sous-ensemble fini \(\mathcal{X}_{T,\delta}\) de \(\mathcal{Q}(T)\) tel que \(\displaystyle \#\mathcal{X}_{T,\delta}\leqslant \left(\frac{12}{\delta}\right)^k\) et, pour tout \(X\in \mathcal{Q}(T)\) de norme \(1\), il existe \(Y\in \mathcal{X}_{T,\delta}\) de norme \(1\) tel que \(\displaystyle \|X-Y\|\leqslant \frac{\delta}{4}.\)

16. Soit \(\delta\in \left] 0,1 \right]\). On définit la suite \((u_n)_{n\in \mathbb{N}}\) par \(u_0=\alpha-1\) et : \(\displaystyle \forall n\in \mathbb{N},\ u_{n+1}=\frac{\delta}{4} \left( 3+u_n \right).\)

    Montrer que \(\displaystyle \lim_{n\to +\infty}u_n=\frac{3\delta}{4-\delta}\) et que \(\displaystyle \frac{3\delta}{4-\delta}\leqslant \delta.\)

• Soit \(k\in \left[\!\left[0,n\right]\!\right]\), \(T\in \mathcal{T}_k\), \(\varepsilon\in \left] 0,1 \right[\) et \(\delta\in \left] 0,1 \right[\) tels que \(\varepsilon=2\delta+\delta^2.\)

17. On suppose que \(A\) est une \(\displaystyle \left(\frac{\delta}{2},\mathcal{X}_{T,\delta}\right)\)-isométrie.

    1. Montrer que pour tout \(Y\in \mathcal{X}_{T,\delta}\) de norme \(1\), \[1-\frac{\delta}{2}\leqslant \sqrt{1-\frac{\delta}{2}}\leqslant \|AY\|\leqslant \sqrt{1+\frac{\delta}{2}}\leqslant 1+\frac{\delta}{2}\]

    2. En déduire que pour tout \(n\in \mathbb{N}^*\) et tout \(X\in \mathcal{Q}(T)\) de norme \(1\), en considérant \(Y\in \mathcal{X}_{T,\delta}\) de norme \(1\) tel que \(\|X-Y\|\leqslant \dfrac{\delta}{4}\) et en utilisant la question 15, on a \[1-u_n\leqslant \|AX\|\leqslant 1+u_n\]

    3. En conclure que pour tout \(X\in \mathcal{Q}(T)\) de norme \(1\), \[1-\delta\leqslant \|AX\|\leqslant 1+\delta\] puis que \(\sqrt{1-\varepsilon}\leqslant \|AX\|\leqslant \sqrt{1+\varepsilon}.\)

    4. En déduire que \(A\) est une \((\varepsilon,\mathcal{Q}(T))\)-isométrie.

• On suppose que \(k\in \left[\!\left[1,n\right]\!\right]\).

18. En déduire que

    • la probabilité que \(M\) ne soit pas une \((\varepsilon,\mathcal{Q}(T))\)-isométrie est inférieure à \(\displaystyle 2\left(\frac{12}{\delta}\right)^k \mathrm{e}^{-m\frac{\delta^2}{32}},\)

    • puis que la probabilité que \(M\) ne soit pas une \((\varepsilon,\mathcal{C}_k)\)-isométrie est inférieure à \(\displaystyle 2\binom{n}{k}\left(\frac{12}{\delta}\right)^k \mathrm{e}^{-m\frac{\delta^2}{32}}.\)

19. 1. Montrer que \(\displaystyle \binom{n}{k}\leqslant \frac{n^k}{k!}.\)

    2. En utilisant la somme d’une série, établir que \(\displaystyle \mathrm{e}^k\geqslant 2 \, \frac{k^k}{k!}.\)

       En déduire que \(\displaystyle 2\binom{n}{k}\leqslant \left(\frac{\mathrm{e}n}{k}\right)^k.\)

    3. On pose \(\displaystyle a=\frac{m}{k}\) et \(\displaystyle b=\frac{n}{k}\) et on suppose que \(\displaystyle a>32 \, \frac{\ln\left(\frac{12b\mathrm{e}}{\delta}\right)}{\delta^2}.\) Montrer qu’il existe une matrice \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) qui est une \((\varepsilon,\mathcal{C}_k)\)-isométrie.

L’acquisition comprimée

On conserve les notations de la partie précédente.

Soit \(X\in \mathcal{M}_{n,1}(\mathbb{R})\), de composantes \(x_1,\ldots,x_n\). On note \(|X|\) la somme \(\displaystyle \sum_{i=1}^n |x_i|=\sum_{i\in S(X)}|x_i|.\)

Soit \(k\in \left[\!\left[1,n\right]\!\right]\). Dans cette partie, on montre qu’étant donné \(AY\), où \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) est donnée et \(Y\in \mathcal{C}_k\) inconnu, on peut caractériser \(Y\) par une propriété vérifiée par \(\langle Y\rangle\) ou \(|Y|\) dans la mesure où \(A\) est une \((\varepsilon,\mathcal{C}_{2k})\)-isométrie ou une \((\varepsilon,\mathcal{C}_{3k})\)-isométrie.

20. Quelques propriétés utiles pour la suite. Soit \(r\in \mathbb{N}^*\).

    1. Montrer que pour tout \((X,Y)\in \mathcal{M}_{n,1}(\mathbb{R})^2\), \(|X+Y|\leqslant |X|+|Y|.\)

       En déduire que si \(X_1,\ldots,X_r\) sont des éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\), \(\displaystyle \left|\sum_{i=1}^r X_i\right|\leqslant \sum_{i=1}^r |X_i|.\)

    2. Montrer que si \(X_1,\ldots,X_r\), éléments de \(\mathcal{M}_{n,1}(\mathbb{R})\), sont à supports deux à deux disjoints, alors \(\displaystyle \left|\sum_{i=1}^r X_i\right|=\sum_{i=1}^r |X_i|.\)

    3. En utilisant l’inégalité de la question 13, montrer que si \(X\in \mathcal{C}_k\), \[\|X\|\leqslant |X|\leqslant \sqrt{k} \, \|X\|\]

21. Soit \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) une \((\varepsilon,\mathcal{C}_k)\)-isométrie avec \(\varepsilon\in \left] 0,1 \right[\).

    1. Montrer que pour tout \(X\in \mathcal{C}_k\), si \(AX=0\), alors \(X=0\).

    2. En déduire que \(\operatorname{rg}(A)\geqslant k\).

• Première caractérisation

22. On suppose dans cette question que \(k\leqslant \dfrac{n}{2}\) et que \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) est une \((\varepsilon,\mathcal{C}_{2k})\)-isométrie.

    1. Soit \((X,Y)\in \mathcal{C}_k^2\) tels que \(AX=AY\).

       Justifier que \(X-Y\in \mathcal{C}_{2k}\) et en déduire que \(X=Y\).

    2. Soit \(Y\in \mathcal{C}_k\). On pose \(B=AY\). Montrer que \(Y\) est l’unique solution de l’équation \(AX=B\) qui minimise \(\langle X\rangle\).

• Deuxième caractérisation

  On suppose désormais que \(k\leqslant \dfrac{n}{3}\) et que \(A\in \mathcal{M}_{m,n}(\mathbb{R})\) est une \((\varepsilon,\mathcal{C}_{3k})\)-isométrie avec \(\varepsilon<\dfrac13\).

  On considère \(Y\in \mathcal{C}_k\). On pose \(AY=B\). Soit \(X\) appartenant à \(\mathcal{M}_{n,1}(\mathbb{R})\) tel que \(AX=B\) et \(|X|\leqslant |Y|\). On pose \(Z=Y-X\).

  On note \(S\) le support de \(Y\) et \(\overline{S}\) l’ensemble des indices des composantes de \(Y\) qui sont nulles.

  Si \(I\) est un sous-ensemble non vide de \(\left[\!\left[1,n\right]\!\right]\), on note \(Z_I\) l’élément de \(\mathcal{M}_{n,1}(\mathbb{R})\) obtenu à partir de \(Z\) en donnant la valeur \(0\) aux composantes dont l’indice n’appartient pas à \(I\).

  Par exemple, si \(n=5\), \(I=\{1,3,4\}\) et \(Z=\begin{pmatrix}1\\ -1\\ 0\\ 2\\ -1\end{pmatrix},\) alors \(Z_I=\begin{pmatrix}1\\ 0\\ 0\\ 2\\ 0\end{pmatrix}.\)

23. On suppose dans cette question que \(\langle Z\rangle\leqslant 3k\). Montrer que \(Z=0\).

• On suppose dans la suite de cette partie que \(3k+1\leqslant \langle Z\rangle\).

24. 1. Montrer que \(Y-Z_{\overline{S}}=X+Z_S\) et que \(|Y-Z_{\overline{S}}|=|Y|+|Z_{\overline{S}}|.\)

    2. En déduire que \(|Z_S|\geqslant |Z_{\overline{S}}|.\)

    3. Montrer que \(\displaystyle \|Z_S\|\geqslant \frac{1}{\sqrt{k}} \, |Z_S|\geqslant \frac{1}{\sqrt{k}} \, |Z_{\overline{S}}|.\)

• On pose \(\displaystyle r=\left\lfloor \frac{\langle Z_{\overline{S}}\rangle}{2k}\right\rfloor.\)

  On écrit \(\overline{S}\) sous la forme de la réunion disjointe \(T_1\cup \cdots \cup T_{r+1}\), avec pour tout \(i\in \left[\!\left[1,r\right]\!\right]\), les valeurs absolues des composantes non nulles de \(Z_{T_i}\) qui sont supérieures à toutes celles de \(Z_{T_{i+1}}\) et \(\langle Z_{T_i}\rangle=2k\).

  On a donc en particulier \(\displaystyle Z_{\overline{S}}=\sum_{i=1}^{r+1} Z_{T_i}\) et \(\langle Z_{T_{r+1}}\rangle<2k.\)

  Pour \(i\in \left[\!\left[1,r\right]\!\right]\), on note \(\alpha_i\) la plus petite valeur absolue obtenue à partir des composantes non nulles de \(Z_{T_i}\).

25. 1. Soit \(i\in \left[\!\left[1,r\right]\!\right]\). Montrer que \(|Z_{T_i}|\geqslant \sqrt{2k}\sqrt{2k\alpha_i^2}\geqslant \sqrt{2k} \, \|Z_{T_{i+1}}\|.\)

    2. En déduire que \(\displaystyle \|Z_S\|\geqslant \sqrt{2}\sum_{i=2}^{r+1} \, \|Z_{T_i}\|.\)

26. 1. Montrer que \[\|AZ\|\geqslant \|AZ_{S\cup T_1}\|-\left\|\sum_{i=2}^{r+1}AZ_{T_i}\right\| \geqslant \sqrt{1-\varepsilon} \, \|Z_{S\cup T_1}\|-\sqrt{1+\varepsilon} \, \sum_{i=2}^{r+1}\|Z_{T_i}\|.\]

    2. En déduire que \(\displaystyle \|AZ\|\geqslant \left(\sqrt{1-\varepsilon}-\frac{\sqrt{1+\varepsilon}}{\sqrt{2}}\right)\|Z_S\|.\)

    3. En conclure que \(Z_S=0\), puis que \(X=Y\).

27. En déduire que \(Y\) est l’unique solution de l’équation \(AX=B\) qui minimise \(|X|\).

Aide-mémoire

Toutes les fonctions et instructions présentées ne sont pas utiles et il est possible d’utiliser d’autres fonctions ou instructions absentes de cet aide-mémoire.

Listes

Module mathématique numpy de Python

import numpy as np

Sous-module random de numpy pour la simulation probabiliste

import numpy.random as rd

Si le paramètre [r,s] est remplacé par r, cette fonction renvoie une réalisation d’un vecteur de longueur \(r\) correspondant à la loi en question, et si ce paramètre est omis, elle renvoie un seul coefficient suivant les mêmes contraintes.

Fin