BCE Maths appliquées HEC/ESSEC ECG 2026Sujet, corrigé et rapport du jury

Conception : ESSEC BS - HEC Paris MATHÉMATIQUES APPLIQUÉES FILIÈRE ÉCONOMIQUE ET COMMERCIALE VOIE GÉNÉRALE

• -Pour tout X ∈ M_(d, 1)(ℝ), si ‖X‖ = 0 alors X = 0.
• -Pour tous X ∈ M_(d, 1)(ℝ), Y ∈ M_(d, 1)(ℝ), ‖X‖ − ‖Y‖ ⩽ ‖X + Y‖ ⩽ ‖X‖ + ‖Y‖.
• -Pour tous X ∈ M_(d, 1)(ℝ), λ ∈ ℝ, ‖λX‖ = |λ|‖X‖.

import numpy as np,numpy.random as rd

Préliminaire informatique

• 1.a) Ecrire une fonction Norme (X) qui renvoie ‖X‖ si le vecteur numpy X représente le vecteur colonne X de M_(n, 1)(ℝ).
  • b)
    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.0True

• 3.
  On suppose que X, un ensemble d'éléments de M_(n, 1)(ℝ), est représenté par la liste finie LX de vecteurs numpy, la matrice A par le tableau numpy A et ε par eps. Ecrire une fonction EstIsom(A,LX,eps) qui renvoie True si A est une ( ε, 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

• 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.
• -Soit X un élément de M_(n, 1)(ℝ) de composantes x_1, …, x_n tel que ‖X‖ = 1.
  Pour tout i ∈ [ [1, m] ], on définit les variables aléatoires Y_i = ∑_(j = 1)^n x_j G_(i, j) et Z la variable aléatoire ‖MX‖^2.
• 5.Soit i ∈ [ [1, m] ].
  • a)Soit j ∈ [ [1, n] ] tel que x_j ≠ 0. Quelle est la loi de x_j G_(i, j) ?
  • b)En déduire la loi de Y_i et que 𝔼(Y_i^2) = ‖X‖^2 = 1.
  • c)Montrer que Z = 1/m∑_(i = 1)^m Y_i^2.
• -Soit ε ∈ ]0, 1[ et t ∈ ]0, 1/4].
• 6.a) Montrer que pour tout i ∈ [ [1, m] ], 𝔼(e^(tY_i^2)) existe et vaut 1/(√(2π))∫_(− ∞)^(+ ∞)e^(− (1 − 2t)(x^2)/2)dx.
  • b)En conclure que pour tout i ∈ [ [1, m] ], 𝔼(e^(tY_i^2)) = 1/(√(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
  ℙ(U ⩾ a) ⩽ (𝔼(U))/a

• • a)Montrer que 𝔼(e^(tmZ)) existe et que ℙ(Z > (1 + ε)) ≤ ℙ(Z ⩾ (1 + ε)) ≤ 𝔼(e^(tmZ))e^(− tm(1 + ε)).
  • b)En déduire que ℙ(Z > (1 + ε)) ⩽ ((e^(− t))/(√(1 − 2t)))^m e^(− tmε).
  • c)Établir que − t − 1/2ln(1 − 2t) ⩽ 2t^2 et en déduire que ℙ(Z > (1 + ε)) ⩽ e^(m(2t^2 − tε)).
  • d)En conclure que ℙ(Z > (1 + ε)) ⩽ e^(− m(ε^2)/8).
• 8.On montrerait de même que ℙ(Z < (1 − ε)) ⩽ e^(− m(ε^2)/8).
  En déduire que ℙ([Z < (1 − ε)] ∪ [Z > (1 + ε)]) ⩽ 2e^(− m(ε^2)/8).
• -Soit X = {X_1, …, X_r}, un ensemble d'éléments de M_(n, 1)(ℝ), on note pour tout i ∈ [ [1, r] ], B_i l'événement
  [(1 − ε)‖X_i‖^2 ⩽ ‖MX_i‖^2 ⩽ (1 + ε)‖X_i‖^2]
• 9.a) Pour tout i ∈ [ [1, r] ] tel que X_i ≠ 0, on pose U_i = 1/(‖X_i‖)X_i.
  Montrer que ‖U_i‖ = 1 et que B_i = [(1 − ε) ⩽ ‖MU_i‖^2 ⩽ (1 + ε)].
  • 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 (ε, X)-isométrie, est inférieure à 2re^(− m(ε^2)/8).
  • c)On suppose que m > (8ln(2r))/(ε^2). En conclure qu'il existe une matrice A ∈ M_(m, n)(ℝ) qui est une (ε, X)-isométrie.
• 10.On suppose que X, un ensemble d'éléments de M_(n, 1)(ℝ), 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 (ε, X)-isométrie.

ε-isométries pour les ensembles sporadiques de M_(n, 1)(ℝ)

• - S(X) l'ensemble des indices i tels que x_i ≠ 0, appelé support de X.
• - ⟨X⟩ le nombre de composantes non nulles de X donc le cardinal de S(X).
• -Pour k ∈ [ [0, n] ], C_k l'ensemble des X ∈ M_(n, 1)(ℝ) tels que ⟨X⟩ ⩽ k.
• -Pour k ∈ [ [0, n] ], T_k l'ensemble des parties de [ [1, n] ] de cardinal k et pour tout T élément de T_k, Q(T) l'ensemble des éléments de M_(n, 1)(ℝ) dont le support est inclus dans T.
• 11.Donner le cardinal de T_k pour tout entier k ∈ [ [0, n] ].
• 12.a) Déterminer C_0 et C_n.
  • -Soit k ∈ [ [1, n − 1] ].

• • b)Soit T ∈ T_k, on pose T = {i_1, ⋯, i_k}.
    Montrer que Q(T) est un sous-espace vectoriel de M_(n, 1)(ℝ) de dimension k.
  • c)Montrer que C_k = ⋃_(T ∈ T_k)Q(T).
    C_k est-il un sous-espace vectoriel de M_(n, 1)(ℝ) ? Justifier la réponse.
• 13.Inégalité de Cauchy-Schwarz - Soit X et Y deux éléments non nuls de M_(n, 1)(ℝ) de coefficients x_1, …, x_n et y_1, …, y_n.
  • a)Montrer que pour tout i ∈ [ [1, n] ], 2|x_i||y_i| ⩽ x_i^2 + y_i^2.
  • b)En supposant que ‖X‖ = ‖Y‖ = 1, en déduire que |∑_(i = 1)^n x_i y_i| ⩽ 1.
  • c)En conclure dans le cas général que |∑_(i = 1)^n x_i y_i| ⩽ ‖X‖‖Y‖ puis que
    (∑_(i = 1)^n x_i y_i)^2 ⩽ (∑_(i = 1)^n x_i^2)(∑_(i = 1)^n y_i^2)
    L'inégalité reste-t-elle vraie si l'un des deux vecteurs X ou Y est nul?
• -Soit A = (a_(i, j)) ∈ M_(m, n)(ℝ).
• 14.a) Soit X ∈ M_(n, 1)(ℝ) de composantes x_1, .., x_n. Montrer que ‖AX‖^2 = ∑_(i = 1)^m(∑_(j = 1)^n a_(i, j)x_j)^2.
  • b)En déduire que, pour tout X ∈ M_(n, 1)(ℝ), ‖AX‖^2 ⩽ (∑_(i = 1)^m∑_(j = 1)^n a_(i, j)^2)‖X‖^2.
• -On pose α = √(∑_(i = 1)^m∑_(j = 1)^n a_(i, j)^2).
• 15.Montrer que pour tout (X, Y) ∈ M_(n, 1)(ℝ)^2 :
  ‖AY‖ − ‖A(X − Y)‖ ⩽ ‖AX‖ ⩽ ‖AY‖ + ‖A(X − Y)‖
• -On admet que pour tous k ∈ [ [0, n] ], T ∈ T_k et δ ∈ ]0, 1[, il existe un sous-ensemble fini X_(T, δ) de Q(T) tel que #X_(T, δ) ⩽ ((12)/δ)^k et pour tout X ∈ Q(T) de norme 1, il existe Y ∈ X_(T, δ) de norme 1 tel que ‖X − Y‖ ⩽ δ/4.
• 16.Soit δ ∈ ]0, 1[. On définit la suite (u_n)_(n ∈ ℕ) par, u_0 = α − 1 et : ∀n ∈ ℕ, u_(n + 1) = δ/4(3 + u_n). Montrer que lim_(n → + ∞)u_n = (3δ)/(4 − δ) et que (3δ)/(4 − δ) ⩽ δ.
• -Soit k ∈ [ [0, n] ], T ∈ T_k, ε ∈ ]0, 1[ et δ ∈ ]0, 1[ tel que ε = 2δ + δ^2.
• 17.On suppose que A est une (δ/2, X_(T, δ))-isométrie .
  • a)Montrer que pour tout Y ∈ X_(T, δ) de norme 1,
    1 − δ/2 ⩽ √(1 − δ/2) ⩽ ‖AY‖ ⩽ √(1 + δ/2) ⩽ 1 + δ/2

• • b)En déduire que pour tout n ∈ ℕ^∗ et X ∈ Q(T) de norme 1, en considérant Y ∈ X_(T, δ) de norme 1 tel que ‖X − Y‖ ⩽ δ/4 et en utilisant la question 13, que :
    1 − u_n ⩽ ‖AX‖ ⩽ 1 + u_n
  • c)En conclure que pour tout X ∈ Q(T) de norme 1 :
    1 − δ ⩽ ‖AX‖ ⩽ 1 + δ
    puis que √(1 − ε) ⩽ ‖AX‖ ⩽ √(1 + ε).
  • d)En déduire que A est une (ε, Q(T))-isométrie.
• -On suppose que k ∈ [ [1, n] ].
• 18.En déduire que,
  la probabilité que M ne soit pas une (ε, Q(T))-isométrie est inférieure à 2((12)/δ)^k e^(− m(δ^2)/(32)), puis que la probabilité que M ne soit pas une (ε, C_k)-isométrie est inférieure à 2(n/k)((12)/δ)^k e^(− m(δ^2)/(32)).
• 19.a) Montrer que (n/k) ⩽ (n^k)/(k!).
  • b)En utilisant la somme d'une série, établir que e^k ⩾ 2(k^k)/(k!). En déduire que 2(n/k) ⩽ ((en)/k)^k.
  • c)On pose a = m/k et b = n/k et on suppose que a > 32(ln((12be)/δ))/(δ^2). Montrer qu'il existe une matrice A ∈ M_(m, n)(ℝ) qui est une (ε, C_k)-isométrie.

L'acquisition comprimée

• 20.Quelques propriétés utiles pour la suite - Soit r ∈ ℕ^∗.
  • a)Montrer que pour tout (X, Y) ∈ (M_(n, 1)(ℝ))^2, |X + Y| ⩽ |X| + |Y|. En déduire que si X_1, …, X_r sont des éléments de M_(n, 1)(ℝ), |∑_(i = 1)^r X_i| ⩽ ∑_(i = 1)^r|X_i|.
  • b)Montrer que si X_1, …, X_r, éléments de M_(n, 1)(ℝ), sont à supports deux à deux disjoints alors |∑_(i = 1)^r X_i| = ∑_(i = 1)^r|X_i|.
  • c)En utilisant l'inégalité de la question 13, montrer que si X ∈ C_k,
    ‖X‖ ⩽ |X| ⩽ √k‖X‖

• 21.Soit A ∈ M_(m, n)(ℝ) une (ε, C_k)-isométrie avec ε ∈ ]0, 1[.
  • a)Montrer que pour tout X ∈ C_k, si AX = 0 alors X = 0.
  • b)En déduire que rg(A) ⩾ k.

- Première caractérisation

• 22.On suppose dans cette question que k ⩽ n/2 et que A ∈ M_(m, n)(ℝ) est une (ε, C_(2k))-isométrie.
  • a)Soit (X, Y) ∈ C_k^2 tels que AX = AY.
    Justifier que X − Y ∈ C_(2k) et en déduire que X = Y.
  • b)Soit Y ∈ C_k, on pose B = AY. Montrer que Y est l'unique solution de l'équation AX = B qui minimise ⟨X⟩.
• -Deuxième caractérisation
  On suppose désormais que k ⩽ n/3 et que A ∈ M_(m, n)(ℝ) est une (ε, C_(3k))-isométrie avec ε < 1/3.
  On considère Y ∈ C_k, on pose AY = B. Soit X appartenant à M_(n, 1)(ℝ) tel que AX = B et |X| ⩽ |Y|. On pose Z = Y − X.
  On note S le support de Y et S¯ l'ensemble des indices des composantes de Y qui sont nulles.
  Si I est un sous-ensemble non vide de [ [1, n] ], on note Z_I l'élément de M_(n, 1)(ℝ) 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 = (1; − 1; 0; 2; − 1) alors Z_I = (1; 0; 0; 2; 0).
• 23.On suppose dans cette question que ⟨Z⟩ ⩽ 3k. Montrer que Z = 0.
• -On suppose dans la suite de cette partie que 3k + 1 ⩽ ⟨Z⟩.
• 24.a) Montrer que Y − Z_(S¯) = X + Z_S et que |Y − Z_(S¯)| = |Y| + |Z_(S¯)|.
  • b)En déduire que |Z_S| ⩾ |Z_(S¯)|.
  • c)Montrer que ‖Z_S‖ ⩾ 1/(√k)|Z_S| ⩾ 1/(√k)|Z_(S¯)|.
• -On pose r = ⌊(⟨Z_(S¯)⟩)/(2k)⌋.
  On écrit S¯ sous la forme de la réunion disjointe T_1 ∪ … ∪ T_(r + 1), avec pour tout i ∈ [ [1, r] ], les valeurs absolues des composantes non nulles de Z_(T_i) qui sont supérieures à toutes celles de Z_(T_(i + 1)) et ⟨Z_(T_i)⟩ = 2k.
  On a donc en particulier Z_(S¯) = ∑_(i = 1)^(r + 1)Z_(T_i) et ⟨Z_(T_(r + 1))⟩ < 2k.
  Pour i ∈ [ [1, r] ], on note α_i la plus petite valeur absolue obtenue à partir des composantes non nulle de Z_(T_i).
• 25.a) Soit i ∈ [ [1, r] ]. Montrer que |Z_(T_i)| ⩾ √(2k)√(2kα_i^2) ⩾ √(2k)‖Z_(T_(i + 1))‖.
  • b)En déduire que ‖Z_S‖ ⩾ √2∑_(i = 2)^(r + 1)‖Z_(T_i)‖.
• 26.a) Montrer que :
  ‖AZ‖ ⩾ ‖AZ_(S ∪ T_1)‖ − ‖∑_(i = 2)^(r + 1)AZ_(T_i)‖ ⩾ √(1 − ε)‖Z_(S ∪ T_1)‖ − √(1 + ε)∑_(i = 2)^(r + 1)‖Z_(T_i)‖