\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\graphicspath{ {./images/} }

\begin{document}
\section*{Conception : ESSEC BS - HEC Paris MATHÉMATIQUES APPLIQUÉES FILIÈRE ÉCONOMIQUE ET COMMERCIALE VOIE GÉNÉRALE}
Jeudi 23 avril 2026 de 14h à 18h

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.\\
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.\\
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.\\
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

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 \(A Y\) 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 :

\begin{itemize}
  \item[-] Pour tout \(X \in \mathcal{M}_{d, 1}(\mathbb{R})\), si \(\|X\|=0\) alors \(X=0\).
  \item[-] 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\|\).
  \item[-] Pour tous \(X \in \mathcal{M}_{d, 1}(\mathbb{R}), \lambda \in \mathbb{R},\|\lambda X\|=|\lambda|\|X\|\).
\end{itemize}

Si \(\mathcal{X}\) est un ensemble d'éléments de \(\left.\mathcal{M}_{n, 1}(\mathbb{R}), \varepsilon \in\right] 0,1\left[\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}\) :

\[
(1-\varepsilon)\|X\|^{2} \leqslant\|A X\|^{2} \leqslant(1+\varepsilon)\|X\|^{2}
\]

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

\begin{verbatim}
import numpy as np,numpy.random as rd
\end{verbatim}

Un aide-mémoire Python se trouve à la fin de l'énoncé.\\
Le mot "Fin" marque la fin de l'énoncé.

\section*{Préliminaire informatique}
\begin{itemize}
  \item[1.] a) Ecrire 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})\).
  \begin{itemize}
    \item[b)] On exécute les instructions suivantes :
\begin{verbatim}
X=np.array([1,0,1,1,1])
print(Norme(X));print(Norme((1/Norme(X))*X))
\end{verbatim}

Quel affichage obtient-on dans la console?
  \end{itemize}
  \item[2.] On exécute le script suivant :
\begin{verbatim}
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)
\end{verbatim}

et on obtient l'affichage :
\end{itemize}

\begin{itemize}
  \item[3.0] True
\end{itemize}

Expliquer ces résultats.

\begin{itemize}
  \item[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. Ecrire 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,
\begin{verbatim}
LX=[np.array([-1,3]),np.array([1,-2])];
print(EstIsom(np.array([[2,1],[0,1],[1,0]]),LX,0.2))
\end{verbatim}

quel affichage obtient-on dans la console? On justifiera sa réponse.
\end{itemize}

\section*{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}\) \(\operatorname{pour}(i, j) \in \llbracket 1, m \rrbracket \times \llbracket 1, n \rrbracket\).

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}}\left(\begin{array}{ccc}
G_{1,1}(\omega) & \ldots & G_{1, n}(\omega) \\
G_{2,1}(\omega) & \ldots & G_{2, n}(\omega) \\
\vdots & \vdots & \vdots \\
G_{m, 1}(\omega) & \ldots & G_{m, n}(\omega)
\end{array}\right)
\]

\begin{itemize}
  \item[4.] Ecrire 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.
  \item[-] 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 \llbracket 1, m \rrbracket\), on définit les variables aléatoires \(Y_{i}=\sum_{j=1}^{n} x_{j} G_{i, j}\) et \(Z\) la variable aléatoire \(\|M X\|^{2}\).
  \item[5.] Soit \(i \in \llbracket 1, m \rrbracket\).
  \begin{itemize}
    \item[a)] Soit \(j \in \llbracket 1, n \rrbracket\) tel que \(x_{j} \neq 0\). Quelle est la loi de \(x_{j} G_{i, j}\) ?
    \item[b)] En déduire la loi de \(Y_{i}\) et que \(\mathbb{E}\left(Y_{i}^{2}\right)=\|X\|^{2}=1\).
    \item[c)] Montrer que \(Z=\frac{1}{m} \sum_{i=1}^{m} Y_{i}^{2}\).
  \end{itemize}
  \item[-] Soit \(\varepsilon \in] 0,1[\) et \(\left.t \in] 0, \frac{1}{4}\right]\).
  \item[6.] a) Montrer que pour tout \(i \in \llbracket 1, m \rrbracket, \mathbb{E}\left(\mathrm{e}^{t Y_{i}^{2}}\right)\) existe et vaut \(\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{+\infty} \mathrm{e}^{-(1-2 t) \frac{x^{2}}{2}} d x\).
  \begin{itemize}
    \item[b)] En conclure que pour tout \(i \in \llbracket 1, m \rrbracket, \mathbb{E}\left(\mathrm{e}^{t Y_{i}^{2}}\right)=\frac{1}{\sqrt{1-2 t}}\).
  \end{itemize}
  \item[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}
\]
\end{itemize}

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[a)] Montrer que \(\mathbb{E}\left(\mathrm{e}^{t m Z}\right)\) existe et que \(\mathbb{P}(Z>(1+\varepsilon)) \leq \mathbb{P}(Z \geqslant(1+\varepsilon)) \leq \mathbb{E}\left(\mathrm{e}^{t m Z}\right) \mathrm{e}^{-t m(1+\varepsilon)}\).
    \item[b)] En déduire que \(\mathbb{P}(Z>(1+\varepsilon)) \leqslant\left(\frac{\mathrm{e}^{-t}}{\sqrt{1-2 t}}\right)^{m} \mathrm{e}^{-t m \varepsilon}\).
    \item[c)] Établir que \(-t-\frac{1}{2} \ln (1-2 t) \leqslant 2 t^{2}\) et en déduire que \(\mathbb{P}(Z>(1+\varepsilon)) \leqslant \mathrm{e}^{m\left(2 t^{2}-t \varepsilon\right)}\).
    \item[d)] En conclure que \(\mathbb{P}(Z>(1+\varepsilon)) \leqslant \mathrm{e}^{-m \frac{\varepsilon^{2}}{8}}\).
  \end{itemize}
  \item[8.] On montrerait de même que \(\mathbb{P}(Z<(1-\varepsilon)) \leqslant \mathrm{e}^{-m \frac{\varepsilon^{2}}{8}}\).\\
En déduire que \(\mathbb{P}([Z<(1-\varepsilon)] \cup[Z>(1+\varepsilon)]) \leqslant 2 \mathrm{e}^{-m \frac{\varepsilon^{2}}{8}}\).
  \item[-] Soit \(\mathcal{X}=\left\{X_{1}, \ldots, X_{r}\right\}\), un ensemble d'éléments de \(\mathcal{M}_{n, 1}(\mathbb{R})\), on note pour tout \(i \in \llbracket 1, r \rrbracket, B_{i}\) l'événement
\[
\left[(1-\varepsilon)\left\|X_{i}\right\|^{2} \leqslant\left\|M X_{i}\right\|^{2} \leqslant(1+\varepsilon)\left\|X_{i}\right\|^{2}\right]
\]
  \item[9.] a) Pour tout \(i \in \llbracket 1, r \rrbracket\) tel que \(X_{i} \neq 0\), on pose \(U_{i}=\frac{1}{\left\|X_{i}\right\|} X_{i}\).\\
Montrer que \(\left\|U_{i}\right\|=1\) et que \(B_{i}=\left[(1-\varepsilon) \leqslant\left\|M U_{i}\right\|^{2} \leqslant(1+\varepsilon)\right]\).
  \begin{itemize}
    \item[b)] 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 à \(2 r \mathrm{e}^{-m \frac{\varepsilon^{2}}{8}}\).
    \item[c)] On suppose que \(m>\frac{8 \ln (2 r)}{\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.
  \end{itemize}
  \item[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.
\end{itemize}

\section*{\(\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 :

\begin{itemize}
  \item[-] \(S(X)\) l'ensemble des indices \(i\) tels que \(x_{i} \neq 0\), appelé support de \(X\).
  \item[-] \(\langle X\rangle\) le nombre de composantes non nulles de \(X\) donc le cardinal de \(S(X)\).
  \item[-] Pour \(k \in \llbracket 0, n \rrbracket, \mathcal{C}_{k}\) l'ensemble des \(X \in \mathcal{M}_{n, 1}(\mathbb{R})\) tels que \(\langle X\rangle \leqslant k\).
  \item[-] Pour \(k \in \llbracket 0, n \rrbracket, \mathcal{T}_{k}\) l'ensemble des parties de \(\llbracket 1, n \rrbracket\) de cardinal \(k\) et pour tout \(T\) élément de \(\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\).
  \item[11.] Donner le cardinal de \(\mathcal{T}_{k}\) pour tout entier \(k \in \llbracket 0, n \rrbracket\).
  \item[12.] a) Déterminer \(\mathcal{C}_{0}\) et \(\mathcal{C}_{n}\).
  \begin{itemize}
    \item[-] Soit \(k \in \llbracket 1, n-1 \rrbracket\).
  \end{itemize}
\end{itemize}

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[b)] Soit \(T \in \mathcal{T}_{k}\), on pose \(T=\left\{i_{1}, \cdots, i_{k}\right\}\).\\
Montrer que \(\mathcal{Q}(T)\) est un sous-espace vectoriel de \(\mathcal{M}_{n, 1}(\mathbb{R})\) de dimension \(k\).
    \item[c)] Montrer que \(\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.
  \end{itemize}
  \item[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}\).
  \begin{itemize}
    \item[a)] Montrer que pour tout \(i \in \llbracket 1, n \rrbracket, 2\left|x_{i}\right|\left|y_{i}\right| \leqslant x_{i}^{2}+y_{i}^{2}\).
    \item[b)] En supposant que \(\|X\|=\|Y\|=1\), en déduire que \(\left|\sum_{i=1}^{n} x_{i} y_{i}\right| \leqslant 1\).
    \item[c)] En conclure dans le cas général que \(\left|\sum_{i=1}^{n} x_{i} y_{i}\right| \leqslant\|X\|\|Y\|\) puis que
\[
\left(\sum_{i=1}^{n} x_{i} y_{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?
  \end{itemize}
  \item[-] Soit \(A=\left(a_{i, j}\right) \in \mathcal{M}_{m, n}(\mathbb{R})\).
  \item[14.] a) Soit \(X \in \mathcal{M}_{n, 1}(\mathbb{R})\) de composantes \(x_{1}, . ., x_{n}\). Montrer que \(\|A X\|^{2}=\sum_{i=1}^{m}\left(\sum_{j=1}^{n} a_{i, j} x_{j}\right)^{2}\).
  \begin{itemize}
    \item[b)] En déduire que, pour tout \(X \in \mathcal{M}_{n, 1}(\mathbb{R}),\|A X\|^{2} \leqslant\left(\sum_{i=1}^{m} \sum_{j=1}^{n} a_{i, j}^{2}\right)\|X\|^{2}\).
  \end{itemize}
  \item[-] On pose \(\alpha=\sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} a_{i, j}^{2}}\).
  \item[15.] Montrer que pour tout \((X, Y) \in \mathcal{M}_{n, 1}(\mathbb{R})^{2}\) :
\[
\|A Y\|-\|A(X-Y)\| \leqslant\|A X\| \leqslant\|A Y\|+\|A(X-Y)\|
\]
  \item[-] On admet que pour tous \(k \in \llbracket 0, n \rrbracket, T \in \mathcal{T}_{k}\) et \(\left.\delta \in\right] 0,1\left[\right.\), il existe un sous-ensemble fini \(\mathcal{X}_{T, \delta}\) de \(\mathcal{Q}(T)\) tel que \(\# \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 \(\|X-Y\| \leqslant \frac{\delta}{4}\).
  \item[16.] Soit \(\delta \in] 0,1\left[\right.\). On définit la suite \(\left(u_{n}\right)_{n \in \mathbb{N}}\) par, \(u_{0}=\alpha-1\) et : \(\forall n \in \mathbb{N}, u_{n+1}=\frac{\delta}{4}\left(3+u_{n}\right)\). Montrer que \(\lim _{n \rightarrow+\infty} u_{n}=\frac{3 \delta}{4-\delta}\) et que \(\frac{3 \delta}{4-\delta} \leqslant \delta\).
  \item[-] Soit \(\left.k \in \llbracket 0, n \rrbracket, T \in \mathcal{T}_{k}, \varepsilon \in\right] 0,1[\) et \(\delta \in] 0,1\left[\right.\) tel que \(\varepsilon=2 \delta+\delta^{2}\).
  \item[17.] On suppose que \(A\) est une \(\left(\frac{\delta}{2}, \mathcal{X}_{T, \delta}\right)\)-isométrie .
  \begin{itemize}
    \item[a)] Montrer que pour tout \(Y \in \mathcal{X}_{T, \delta}\) de norme 1,
\[
1-\frac{\delta}{2} \leqslant \sqrt{1-\frac{\delta}{2}} \leqslant\|A Y\| \leqslant \sqrt{1+\frac{\delta}{2}} \leqslant 1+\frac{\delta}{2}
\]
  \end{itemize}
\end{itemize}

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[b)] En déduire que pour tout \(n \in \mathbb{N}^{*}\) et \(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 \frac{\delta}{4}\) et en utilisant la question 13, que :
\[
1-u_{n} \leqslant\|A X\| \leqslant 1+u_{n}
\]
    \item[c)] En conclure que pour tout \(X \in \mathcal{Q}(T)\) de norme 1 :
\[
1-\delta \leqslant\|A X\| \leqslant 1+\delta
\]
puis que \(\sqrt{1-\varepsilon} \leqslant\|A X\| \leqslant \sqrt{1+\varepsilon}\).
    \item[d)] En déduire que \(A\) est une \((\varepsilon, \mathcal{Q}(T))\)-isométrie.
  \end{itemize}
  \item[-] On suppose que \(k \in \llbracket 1, n \rrbracket\).
  \item[18.] En déduire que,\\
la probabilité que \(M\) ne soit pas une \((\varepsilon, \mathcal{Q}(T))\)-isométrie est inférieure à \(2\left(\frac{12}{\delta}\right)^{k} \mathrm{e}^{-m \frac{\delta^{2}}{32}}\), puis que la probabilité que \(M\) ne soit pas une \(\left(\varepsilon, \mathcal{C}_{k}\right)\)-isométrie est inférieure à \(2\binom{n}{k}\left(\frac{12}{\delta}\right)^{k} \mathrm{e}^{-m \frac{\delta^{2}}{32}}\).
  \item[19.] a) Montrer que \(\binom{n}{k} \leqslant \frac{n^{k}}{k!}\).
  \begin{itemize}
    \item[b)] En utilisant la somme d'une série, établir que \(e^{k} \geqslant 2 \frac{k^{k}}{k!}\). En déduire que \(2\binom{n}{k} \leqslant\left(\frac{\mathrm{e} n}{k}\right)^{k}\).
    \item[c)] On pose \(a=\frac{m}{k}\) et \(b=\frac{n}{k}\) et on suppose que \(a>32 \frac{\ln \left(\frac{12 b \mathrm{e}}{\delta}\right)}{\delta^{2}}\). Montrer qu'il existe une matrice \(A \in \mathcal{M}_{m, n}(\mathbb{R})\) qui est une \(\left(\varepsilon, \mathcal{C}_{k}\right)\)-isométrie.
  \end{itemize}
\end{itemize}

\section*{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 \(\sum_{i=1}^{n}\left|x_{i}\right|=\sum_{i \in S(X)}\left|x_{i}\right|\).\\
Soit \(k \in \llbracket 1, n \rrbracket\). Dans cette partie on montre qu'étant donné \(A Y\) 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 \(\left(\varepsilon, \mathcal{C}_{2 k}\right)\)-isométrie ou une \(\left(\varepsilon, \mathcal{C}_{3 k}\right)\)-isométrie.

\begin{itemize}
  \item[20.] Quelques propriétés utiles pour la suite - Soit \(r \in \mathbb{N}^{*}\).
  \begin{itemize}
    \item[a)] Montrer que pour tout \((X, Y) \in\left(\mathcal{M}_{n, 1}(\mathbb{R})\right)^{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}),\left|\sum_{i=1}^{r} X_{i}\right| \leqslant \sum_{i=1}^{r}\left|X_{i}\right|\).
    \item[b)] Montrer que si \(X_{1}, \ldots, X_{r}\), éléments de \(\mathcal{M}_{n, 1}(\mathbb{R})\), sont à supports deux à deux disjoints alors \(\left|\sum_{i=1}^{r} X_{i}\right|=\sum_{i=1}^{r}\left|X_{i}\right|\).
    \item[c)] En utilisant l'inégalité de la question 13, montrer que si \(X \in \mathcal{C}_{k}\),
\[
\|X\| \leqslant|X| \leqslant \sqrt{k}\|X\|
\]
  \end{itemize}
\end{itemize}

\begin{itemize}
  \item[21.] Soit \(A \in \mathcal{M}_{m, n}(\mathbb{R})\) une \(\left(\varepsilon, \mathcal{C}_{k}\right)\)-isométrie avec \(\left.\varepsilon \in\right] 0,1[\).
  \begin{itemize}
    \item[a)] Montrer que pour tout \(X \in \mathcal{C}_{k}\), si \(A X=0\) alors \(X=0\).
    \item[b)] En déduire que \(\operatorname{rg}(A) \geqslant k\).
  \end{itemize}
\end{itemize}

\section*{- Première caractérisation}
\begin{itemize}
  \item[22.] On suppose dans cette question que \(k \leqslant \frac{n}{2}\) et que \(A \in \mathcal{M}_{m, n}(\mathbb{R})\) est une \(\left(\varepsilon, \mathcal{C}_{2 k}\right)\)-isométrie.
  \begin{itemize}
    \item[a)] Soit \((X, Y) \in \mathcal{C}_{k}^{2}\) tels que \(A X=A Y\).\\
Justifier que \(X-Y \in \mathcal{C}_{2 k}\) et en déduire que \(X=Y\).
    \item[b)] Soit \(Y \in \mathcal{C}_{k}\), on pose \(B=A Y\). Montrer que \(Y\) est l'unique solution de l'équation \(A X=B\) qui minimise \(\langle X\rangle\).
  \end{itemize}
  \item[-] Deuxième caractérisation\\
On suppose désormais que \(k \leqslant \frac{n}{3}\) et que \(A \in \mathcal{M}_{m, n}(\mathbb{R})\) est une \(\left(\varepsilon, \mathcal{C}_{3 k}\right)\)-isométrie avec \(\varepsilon<\frac{1}{3}\).\\
On considère \(Y \in \mathcal{C}_{k}\), on pose \(A Y=B\). Soit \(X\) appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R})\) tel que \(A X=B\) et \(|X| \leqslant|Y|\). On pose \(Z=Y-X\).\\
On note \(S\) le support de \(Y\) et \(\bar{S}\) l'ensemble des indices des composantes de \(Y\) qui sont nulles.\\
Si \(I\) est un sous-ensemble non vide de \(\llbracket 1, n \rrbracket\), 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=\left(\begin{array}{r}1 \\ -1 \\ 0 \\ 2 \\ -1\end{array}\right)\) alors \(Z_{I}=\left(\begin{array}{l}1 \\ 0 \\ 0 \\ 2 \\ 0\end{array}\right)\).
  \item[23.] On suppose dans cette question que \(\langle Z\rangle \leqslant 3 k\). Montrer que \(Z=0\).
  \item[-] On suppose dans la suite de cette partie que \(3 k+1 \leqslant\langle Z\rangle\).
  \item[24.] a) Montrer que \(Y-Z_{\bar{S}}=X+Z_{S}\) et que \(\left|Y-Z_{\bar{S}}\right|=|Y|+\left|Z_{\bar{S}}\right|\).
  \begin{itemize}
    \item[b)] En déduire que \(\left|Z_{S}\right| \geqslant\left|Z_{\bar{S}}\right|\).
    \item[c)] Montrer que \(\left\|Z_{S}\right\| \geqslant \frac{1}{\sqrt{k}}\left|Z_{S}\right| \geqslant \frac{1}{\sqrt{k}}\left|Z_{\bar{S}}\right|\).
  \end{itemize}
  \item[-] On pose \(r=\left\lfloor\frac{\left\langle Z_{\bar{S}}\right\rangle}{2 k}\right\rfloor\).\\
On écrit \(\bar{S}\) sous la forme de la réunion disjointe \(T_{1} \cup \ldots \cup T_{r+1}\), avec pour tout \(i \in \llbracket 1, r \rrbracket\), les valeurs absolues des composantes non nulles de \(Z_{T_{i}}\) qui sont supérieures à toutes celles de \(Z_{T_{i+1}}\) et \(\left\langle Z_{T_{i}}\right\rangle=2 k\).\\
On a donc en particulier \(Z_{\bar{S}}=\sum_{i=1}^{r+1} Z_{T_{i}}\) et \(\left\langle Z_{T_{r+1}}\right\rangle<2 k\).\\
Pour \(i \in \llbracket 1, r \rrbracket\), on note \(\alpha_{i}\) la plus petite valeur absolue obtenue à partir des composantes non nulle de \(Z_{T_{i}}\).
  \item[25.] a) Soit \(i \in \llbracket 1, r \rrbracket\). Montrer que \(\left|Z_{T_{i}}\right| \geqslant \sqrt{2 k} \sqrt{2 k \alpha_{i}^{2}} \geqslant \sqrt{2 k}\left\|Z_{T_{i+1}}\right\|\).
  \begin{itemize}
    \item[b)] En déduire que \(\left\|Z_{S}\right\| \geqslant \sqrt{2} \sum_{i=2}^{r+1}\left\|Z_{T_{i}}\right\|\).
  \end{itemize}
  \item[26.] a) Montrer que :
\[
\|A Z\| \geqslant\left\|A Z_{S \cup T_{1}}\right\|-\left\|\sum_{i=2}^{r+1} A Z_{T_{i}}\right\| \geqslant \sqrt{1-\varepsilon}\left\|Z_{S \cup T_{1}}\right\|-\sqrt{1+\varepsilon} \sum_{i=2}^{r+1}\left\|Z_{T_{i}}\right\|
\]
\end{itemize}

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[b)] En déduire que \(\|A Z\| \geqslant\left(\sqrt{1-\varepsilon}-\frac{\sqrt{1+\varepsilon}}{\sqrt{2}}\right)\left\|Z_{S}\right\|\).
    \item[c)] En conclure que \(Z_{S}=0\) puis que \(X=Y\).
  \end{itemize}
  \item[27.] En déduire que \(Y\) est l'unique solution de l'équation \(A X=B\) qui minimise \(|X|\).
\end{itemize}

\section*{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\\[0pt]
[] Créer une liste vide\\
L.append(a) Ajoute l'élément a à la fin de la liste L\\
len(L) Renvoie le nombre d'éléments de la liste L\\
Module mathématique numpy de Python

\begin{verbatim}
import numpy as np
    np.array(L) Transforme la liste L en vecteur ou matrice numpy
np.zeros([n,m]) Crée la matrice nulle de taille n x m
    np.zeros(n) Crée le vecteur nul de taille n
np.ones([n,m]) Crée la matrice de taille \( n x m \ton\) dont tous les coefficients valent 1
    np.ones(n) Crée le vecteur de taille n dont tous les coefficients valent 1
        np.sum(M) Renvoie la somme de tous les éléments de M, matrice ou vecteur
    np.dot(M,X) Renvoie le produit matriciel de la matrice M par le vecteur X
    np.shape(M) Renvoie dans un couple le format de la matrice \( M
    np.sqrt(x) Renvoie 5x, 5i x 2
        np.log(x) Renvoie ln(x) si x> 0
\end{verbatim}

Sous module random de numpy pour la simulation probabiliste

\begin{verbatim}
import numpy.random as rd
\end{verbatim}

\begin{center}
\includegraphics[max width=\textwidth, alt={}]{8932c756-2a55-48b0-9cf2-7d610db8c759-09_34_1388_1497_336}
\end{center}

\begin{verbatim}
        aléatoires indépendantes qui suivent la loi normale N (m, d 2)
\end{verbatim}

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, elles renvoient un seul coefficient suivant les mêmes contraintes.

Fin


\end{document}