\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}

\begin{document}
Concepteur: ESSEC\\
CODE EPREUVE :\\
281\\
CONCOURS D'ADMISSION DE 2006\\
ESSECM1\_S

\section*{Option scientifique}
\section*{MATHEMATIQUES I}
Lundi 15 mai 2006 de 8h à 12h

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté 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.\\
Ils ne doivent faire usage d'aucun document ; 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.

Dans tout ce problème, la lettre \(n\) désigne un entier supérieur ou égal à 2 et on note \(\llbracket 1, n \rrbracket\) l'ensemble \(\{1,2, \ldots, n\}\).\\
On rappelle qu'une permutation de \(\llbracket 1, n \rrbracket\) est une bijection de \(\llbracket 1, n \rrbracket\) sur lui-même.\\
Par ailleurs, on note :

\begin{itemize}
  \item \(\mathfrak{S}_{n}\) l'ensemble des permutations de \(\llbracket 1, n \rrbracket\);
  \item \(\quad \mathrm{M}_{n}(\mathbb{R})\) l'espace vectoriel des matrices carrées d'ordre \(n\) à coefficients réels ;
  \item \(\mathrm{M}_{p, q}(\mathbb{R})\) l'espace vectoriel des matrices à \(p\) lignes, \(q\) colonnes à coefficients réels ;
  \item \(m_{i, j}\) l'élément générique d'une matrice \(M\), c'est-à-dire le réel situé à l'intersection de la \(i^{\text {ème }}\) ligne et de la \(j^{\text {ème }}\) colonne de \(M\);
  \item \({ }^{t} M\) la transposée d'une matrice \(M\).
\end{itemize}

Lorsque \(\sigma\) appartient à \(\mathfrak{S}_{n}\), on appelle matrice de la permutation \(\sigma\) la matrice de \(\mathrm{M}_{n}(\mathbb{R})\) notée \(P_{\sigma}\) dont le terme générique \(p_{i, j}\) vérifie : \(\forall(i, j) \in \llbracket 1, n \rrbracket^{2} \quad p_{i, j}=1\) si \(\sigma(i)=j\) et \(p_{i, j}=0\) sinon.\\
Par exemple, pour \(n=3\) et \(\sigma \in \mathcal{S}_{3}\) définie par \(\sigma(1)=2, \sigma(2)=3, \sigma(3)=1, P_{\sigma}=\left(\begin{array}{lll}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{array}\right)\).

On s'intéresse dans un premier temps à l'ensemble \(E_{n}\) des matrices \(M\) appartenant à \(\mathrm{M}_{n}(\mathbb{R})\) vérifiant la propriété suivante : \(\forall i \in \llbracket 1, n \rrbracket, \forall j \in \llbracket 1, n \rrbracket \quad \sum_{k=1}^{n} m_{i, k}=\sum_{k=1}^{n} m_{k, j}\).\\
Dans ce cas, leur valeur commune sera notée \(\omega(M)\).

\section*{PARTIE I : Etude de l'ensemble \(\boldsymbol{E}_{\boldsymbol{n}}\)}
On note \(J\) la matrice d'ordre \(n\) dont tous les coefficients sont égaux à 1 c'est-à-dire égale à \(\left(\begin{array}{ccc}1 & \ldots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1\end{array}\right)\) et \(U\) la matrice colonne à \(n\) lignes égale à \(\left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)\).

\begin{enumerate}
  \item Généralités.\\
a) Montrer que \(E_{n}\) est un sous espace vectoriel de \(\mathrm{M}_{n}(\mathbb{R})\) et que l'application \(\omega: E_{n} \rightarrow \mathbb{R} \quad M \mapsto \omega(M)\) en est une forme linéaire.\\
b) Lorsque \(M \in \mathrm{M}_{n}(\mathbb{R})\), établir que : \(M \in E_{n}\) si et seulement si \(U\) est vecteur propre commun à \(M\) et \({ }^{t} M\) associé à une même valeur propre.\\
c) Vérifier que \(E_{n}\) est stable pour le produit matriciel et préciser \(\omega(M N)\) en fonction de \(\omega(M)\) et \(\omega(N)\) lorsque \(M\) et \(N\) appartiennent à \(E_{n}\).
  \item Dimension de \(E_{n}\).\\
a) Montrer que le noyau de \(\omega\) et la droite vectorielle engendrée par \(J\) sont supplémentaires dans \(E_{n}\).\\
b) Pour \((r, s) \in \llbracket 2, n \rrbracket^{2}\), on note \(A_{r, s}\) la matrice de \(E_{n}\) dont tous les éléments sont nuls sauf les quatre éléments : \(a_{1,1}, a_{r, s}, a_{1, s}, a_{r, 1}\) qui sont tels que : \(a_{1,1}=a_{r, s}=1\) et \(a_{1, s}=a_{r, 1}=-1\). Montrer que la famille \(\left(A_{r, s}\right)_{(r, s) \in \llbracket 2, n \rrbracket^{2}}\) est libre puis qu'elle est génératrice du noyau de \(\omega\). En déduire la dimension de \(E_{n}\).
  \item Une famille génératrice de \(E_{n}\).\\
a) Établir que pour toute permutation \(\sigma\) de \(\llbracket 1, n \rrbracket\), la matrice \(P_{\sigma}\) appartient à \(E_{n}\) et que les matrices \(P_{\sigma}\) sont les seules matrices \(M\) de \(E_{n}\) telles que \(\omega(M)=1\) n'admettant qu'un seul élément non nul par ligne et par colonne.\\
b) Écrire la matrice \(P_{\sigma}\) correspondant à la permutation \(\sigma\) de \(\mathfrak{S}_{n}\) définie par :
\end{enumerate}

\[
\forall k \in \llbracket 1, n-1 \rrbracket \quad \sigma(k)=k+1 \quad \text { et } \quad \sigma(n)=1
\]

Préciser les matrices : \(\left(P_{\sigma}\right)^{2},\left(P_{\sigma}\right)^{3}, \ldots,\left(P_{\sigma}\right)^{n}\).\\
c) Exprimer \(J\) comme combinaison linéaire de matrices de permutations . Faire de même avec chaque matrice du type \(A_{r, s}\) quand \((r, s) \in \llbracket 2, n \rrbracket^{2}\) : on pourra se limiter aux matrices \(A_{2,2}\) et \(A_{3,2}\) (si \(n \geq 3\) ) et donner une décomposition explicite de ces deux matrices en combinaison linéaire de matrices de permutations.\\
d) Prouver qu'il existe \((n-1)^{2}+1\) permutations \(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{(n-1)^{2}+1}\) de \(\llbracket 1, n \rrbracket\) telles que\\
\(\left(P_{\sigma_{1}}, P_{\sigma_{2}}, \cdots, P_{\sigma_{(n-1)^{2}+1}}\right)\) soit une base de \(E_{n}\).\\
Que représente la somme des composantes d'une matrice \(M\) de \(E_{n}\) relativement à cette base ?

\section*{Les deux parties suivantes du problème sont indépendantes de la partie I}
On s'intéresse dans toute la suite du problème à l'ensemble des matrices \(M\) de \(E_{n}\) dont tous les éléments \(m_{i, j}\) sont positifs ou nuls. On note \(E_{n}{ }^{+}\)cet ensemble.

\section*{PARTIE II: Etude de l'ensemble \(\boldsymbol{E}_{\boldsymbol{n}}^{\boldsymbol{+}}\)}
\begin{enumerate}
  \item Montrer que \(E_{n}^{+}\)est stable pour le produit matriciel et que pour toute famille ( \(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{p}\) ) de permutations de \(\llbracket 1, n \rrbracket\) et toute famille \(\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{p}\right)\) de réels positifs ou nuls \(\sum_{k=1}^{p} \alpha_{k} P_{\sigma_{k}} \in E_{n}^{+}\)
\end{enumerate}

\section*{Dans cette partie, on admettra que:}
\[
\forall M \in E_{n}^{+} \backslash\{0\} \quad \exists \sigma \in \mathfrak{S}_{n} \quad \text { telle que } \quad m_{1, \sigma(1)} m_{2 \sigma(2)}, m_{n, \sigma(n)}>0
\]

\begin{enumerate}
  \setcounter{enumi}{1}
  \item a) On suppose que \(\sigma\) est une telle permutation associée à \(M \in E_{n}^{+} \backslash\{0\}\) et on désigne par
\end{enumerate}

\[
c=\min \left\{m_{1, \sigma(1)}, m_{2, \sigma(2)}, \ldots, m_{n, \sigma(n)}\right\} . \text { Montrer que : } M-c P_{\sigma} \in E_{n}^{+}
\]

b) En déduire que pour toute matrice \(M\) de \(E_{n}^{+} \backslash\{0\}\), il existe \(p \in \mathbb{N}^{*}, p\) permutations \(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{p}\) de \(\llbracket 1, n \rrbracket\) et \(p\) réels \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{p}\) strictement positifs tels que : \(M=\sum_{k=1}^{p} \alpha_{k} P_{\sigma_{k}}\)\\
c) Montrer qu'une matrice de \(E_{n}^{+}\)possédant au moins \(n^{2}-n+1\) termes nuls est nulle ; en déduire que : \(1 \leqslant p \leqslant n^{2}-n+1\).\\
d) Exemple : lorsque \(M=\left(\begin{array}{lll}3 & 1 & 2 \\ 3 & 1 & 2 \\ 0 & 4 & 2\end{array}\right)\), exprimer \(M\) comme combinaison linéaire à scalaires strictement positifs de matrices de permutations de \(\llbracket 1,3 \rrbracket\).\\
3) Une application : L'espace vectoriel \(\mathbb{R}^{n}\) est muni de sa structure euclidienne canonique et on note \(\langle x \mid y\rangle\) le produit scalaire de deux vecteurs \(x\) et \(y\) de \(\mathbb{R}^{n}\)\\
On désigne par \(\left(u_{1}, u_{2}, \ldots ., u_{n}\right)\) et \(\left(v_{1}, v_{2}, \ldots, v_{n}\right)\) deux bases orthonormales de \(\mathbb{R}^{n}{ }_{. .}\)\\
a) Vérifier que la matrice \(M_{u, v}=\left(\left\langle v_{i} \mid u_{j}\right\rangle^{2}\right)\) appartient à \(E_{n}^{+}\)et donner la valeur de \(\omega\left(M_{u, v}\right)\). Lorsque \(\sigma\) est une permutation de \(\llbracket 1, n \rrbracket\), préciser \(M_{u, v}\) dans le cas où \(\left(v_{1}, v_{2}, \ldots, v_{n}\right)=\left(u_{\sigma(1)}, u_{\sigma(2)}, \ldots, u_{\sigma(n)}\right)\).\\
b) On introduit l'endomorphisme symétrique \(s\) de \(\mathbb{R}^{n}\) dont \(\left(u_{1}, u_{2}, \ldots, u_{n}\right)\) est une base orthonormale de diagonalisation et de valeurs propres respectivement associées \(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\).\\
On note \(\Lambda\) la matrice colonne \(\left(\begin{array}{c}\lambda_{1} \\ \vdots \\ \lambda_{n}\end{array}\right)\).

Montrer l'égalité matricielle : \(\left(\begin{array}{c}\left\langle s\left(v_{1}\right) \mid v_{1}\right\rangle \\ \vdots \\ \left\langle s\left(v_{n}\right) \mid v_{n}\right\rangle\end{array}\right)=M_{u, v} \Lambda\).\\
c) En utilisant la question II 2) b), établir que pour toute forme linéaire \(f\) de \(\mathrm{M}_{n, 1}(\mathbb{R})\), il existe deux permutations \(\sigma\) et \(\sigma^{\prime}\) de \(\llbracket 1, n \rrbracket\) vérifiant : \(f\left(P_{\sigma} \Lambda\right) \leqslant f\left(M_{u, v} \Lambda\right) \leqslant f\left(P_{\sigma^{\prime}} \Lambda\right)\).\\
d) On suppose que : \(\lambda_{1} \leqslant \lambda_{2} \leqslant \ldots \leqslant \lambda_{n}\) et \(r \in \llbracket 1, n \rrbracket\).

Trouver une forme linéaire \(f\) permettant d'en déduire les inégalités :

\[
\sum_{k=1}^{r} \lambda_{k} \leqslant \sum_{k=1}^{r}\left\langle s\left(v_{k}\right) \mid v_{k}\right\rangle \leqslant \sum_{k=1}^{r} \lambda_{n-r+k}
\]

Que représente le terme \(\left\langle s\left(v_{k}\right) \mid v_{k}\right\rangle\) dans la matrice de \(s\) relativement à la base \(\left(v_{1}, v_{2}, \ldots, v_{n}\right)\) et pouvez- vous donner une interprétation matricielle des inégalités obtenues ci- dessus ?

\section*{PARTIE III}
L'objet de cette dernière partie est la justification du résultat admis dans la partie II 1). Lorsque \((p, q) \in \llbracket 1, n \rrbracket^{2}\), on appelle sous-matrice de type \((p, q)\) de la matrice \(M\) appartenant à \(\mathrm{M}_{n}(\mathbb{R})\) toute matrice extraite de \(M\) en supprimant de \(M n-p\) lignes et \(n-q\) colonnes.

\begin{enumerate}
  \item Lorsque \(\sigma\) est une permutation de \(\llbracket 1, n \rrbracket\) et \(M\) un élément de \(\mathrm{M}_{n}(\mathbb{R})\), expliciter le terme générique des matrices \(P_{\sigma} M\) et \(M P_{\sigma^{-1}}\). Comment obtient-on ces deux matrices à partir de \(M\) ?
  \item On suppose que \(M\) appartient à \(\mathrm{M}_{n}(\mathbb{R})\) et qu'elle contient une sous-matrice nulle de type ( \(p, q\) ).\\
a) Montrer que : \(\exists \sigma, \sigma^{\prime}\) deux permutations de \(\llbracket 1, n \rrbracket\) telles que \(P_{\sigma} M P_{\sigma^{\prime}}=\left(\begin{array}{l|l}X & 0 \\ \hline Z & Y\end{array}\right)\) avec
\end{enumerate}

\[
X \in \mathrm{M}_{p, n-q}(\mathbb{R}), Z \in \mathrm{M}_{n-p, n-q}(\mathbb{R}) \text { et } Y \in \mathrm{M}_{n-p, q}(\mathbb{R})
\]

b) En déduire que si \(M\) appartient à \(E_{n}^{+} \backslash\{0\}\), on a \(p+q \leqslant n\).\\
3) On désire établir la propriété \(\left(\mathcal{P}_{n}\right)\) suivante : si \(M\) appartient à \(\mathrm{M}_{n}(\mathbb{R})\) et vérifie l'hypothèse \(\left(\mathcal{H}_{n}\right): \forall \sigma \in \mathfrak{S}_{n} \quad m_{1, \sigma(1)} m_{2, \sigma(2)} \ldots m_{n, \sigma(n)}=0\), alors \(M\) contient au moins une sous- matrice nulle de type ( \(p, q\) ) avec \(p+q=n+1\).\\
a) Le vérifier pour \(n=2\).\\
b) n étant supérieur ou égal à 3 , on suppose que la propriété \(\left(\mathcal{P}_{k}\right)\) est vérifiée pour tout \(k \in \llbracket 2, n-1 \rrbracket\). On désigne par \(M\) une matrice appartenant à \(\mathrm{M}_{n}(\mathbb{R})\) et vérifiant ( \(\mathcal{H}_{n}\) ).

\begin{itemize}
  \item Établir que \(M\) contient une sous-matrice de type \((n-1, n-1)\) vérifiant \(\left(\mathcal{H}_{n-1}\right)\).
  \item En déduire que : \(\exists \tau, \tau^{\prime} \in \mathfrak{S}_{n}, \exists p, q / p+q=n\) tels que \(P_{\tau} M P_{\tau^{\prime}}=\left(\begin{array}{l|l}X & 0 \\ \hline Z & Y\end{array}\right)\) avec
\end{itemize}

\[
X \in \mathrm{M}_{p}(\mathbb{R}), Z \in \mathrm{M}_{q, p}(\mathbb{R}) \text { et } Y \in \mathrm{M}_{q}(\mathbb{R}) .
\]

\begin{itemize}
  \item Montrer que \(X\) vérifie \(\left(\mathcal{H}_{p}\right)\) ou \(Y\) vérifie \(\left(\mathcal{H}_{q}\right)\).
  \item En déduire alors que \(M\) contient une sous-matrice nulle de type ( \(p^{\prime}, q^{\prime}\) ) telle que \(p^{\prime}+q^{\prime}=n+1\) et conclure.
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{3}
  \item Montrer alors, à l'aide de 2) b) que : \(\forall M \in E_{n}^{+} \backslash\{0\} \quad \exists \sigma \in \mathfrak{S}_{n}\) telle que \(m_{1, \sigma(1)} m_{2, \sigma(2)} \ldots m_{n, \sigma(n)}>0\).
\end{enumerate}

\end{document}