AnnalesÉcoles d'ingénieurs

X-ENS PC 2018 — Maths

Matrices à coefficients $\pm 1$ : déséquilibre maximal par changements de signes · 5 pages

Pour $A \in \mathcal{M}_n(\{-1, 1\})$ , le sujet étudie $M(A)$ , maximum de ${}^t\!XAY$ sur $X, Y \in \{-1, 1\}^n$ , et $M(n)$ , minimum de $M(A)$ . Après des cas particuliers ( $n^2$ est atteint exactement pour les matrices de rang 1), il établit l'inégalité de Hoeffding et en déduit par une méthode probabiliste que $M(n) \leqslant 2\sqrt{\ln 2}\, n^{3/2}$ , puis minore $M(n)$ par l'espérance de $g_A(Z)$ pour $Z$ uniforme, équivalente à $C n^{3/2}$ grâce à la formule de Stirling. Il démontre Stirling par une étude d'intégrales et majore enfin la plus petite valeur positive $m(A)$ par $\sqrt{2n \ln(2n)}$ .

Le sujet, partie par partie

Notations et Partie I — Cas particuliers p. 1–2

Calcul matriciel · Applications linéaires et rang · Dénombrement et combinatoire · Arithmétique des entiers — matrices à coefficients $\pm 1$ , matrice de rang 1, argument de parité, changement de signe de lignes et colonnes, problème de Gale-Berlekamp

Partie II — Majoration par la méthode probabiliste p. 3

Inégalités de concentration · Matrices et graphes aléatoires · Conditionnement et indépendance · Espaces probabilisés — inégalité de Hoeffding, matrice aléatoire de signes, méthode probabiliste, borne de la réunion, variables uniformes sur $\{-1, 1\}$

Partie III — Un minorant de $M(n)$ p. 3–4

Coefficients binomiaux · Espérance, variance, moments · Formule de Stirling · Équivalents et comparaison — méthode probabiliste, coefficients binomiaux, espérance de $|S_n|$ , formule de Stirling, minorant asymptotique

Partie IV — Une démonstration de la formule de Stirling p. 4–5

Formule de Stirling · Méthode de Laplace et phase stationnaire · Intégrales généralisées et intégrabilité · Convergence dominée · Fonctions Gamma et Bêta · Calcul différentiel · Fonctions spéciales — formule de Stirling, intégrale de Gauss, intégrales $x^n e^{-x}$ , convergence dominée, étude d'une fonction de deux variables

Partie V — Le minimum positif $m(A)$ p. 5

Inégalités de concentration · Espaces probabilisés · Calcul matriciel — inégalité de Hoeffding, méthode probabiliste, plus petite valeur positive, vecteurs de signes