\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}
\section*{MATHÉMATIQUES 2 APPLIQUÉES}
\section*{FILIÈRE ÉCONOMIQUE ET COMMERCIALE VOIE GÉNÉRALE}
Jeudi 25 avril 2024, de 14 h. à 18 h.

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.

On s'intéresse dans ce problème à l'énergie d'un graphe qui est définie à partir de l'énergie de sa matrice d'adjacence.

L'énergie d'un graphe a été introduite en 1978 par Ivan Gutman. Ce n'est qu'à partir des années 2000 que des recherches approfondies sur cette notion ont été entreprises.

Aujourd'hui plus de deux articles par semaine sont publiés sur l'énergie des graphes avec de nombreuses applications dans divers domaines scientifiques.

Les parties 2 et 3 sont indépendantes et un bref aide-mémoire Python se trouve en page 6.

Dans tout le problème \(n\) est un entier supérieur ou égal à 2 .\\
On rappelle que la notation \(\sum_{1 \leqslant i, j \leqslant n}\) est analogue à la notation \(\sum_{(i, j) \in[1, n]^{2}}\).

\section*{Partie 1 - Énergie et trace d'une matrice}
\begin{enumerate}
  \item Soit \(A\) une matrice carrée symétrique appartenant à \(\mathcal{M}_{n}(\mathbb{R})\). Justifier l'existence d'une matrice carrée inversible \(P\) appartenant à \(\mathcal{M}_{n}(\mathbb{R})\) telle que \(P^{-1} A P\) soit une matrice diagonale. Que peut-on dire des éléments diagonaux de \(P^{-1} A P\) ?
\end{enumerate}

\begin{itemize}
  \item En notant \(\lambda_{1}, \ldots, \lambda_{n}\) les éléments diagonaux de \(P^{-1} A P\), on pose alors \(\mathcal{E}(A)=\sum_{k=1}^{n}\left|\lambda_{k}\right|\), on nomme ce réel positif l'énergie de \(A\).\\
On admet que cette somme ne dépend pas du choix de \(P\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{1}
  \item Montrer que \(\mathcal{E}(A)=3\) si \(A=\left(\begin{array}{ccc}1 & -1 & -1 \\ -1 & 0 & 0 \\ -1 & 0 & 0\end{array}\right)\).
  \item Ecrire une fonction Python energie(A) qui renvoie l'énergie de la matrice symétrique représentée par le tableau numpy A .
\end{enumerate}

\begin{itemize}
  \item Si \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\) est une matrice carrée appartenant à \(\mathcal{M}_{n}(\mathbb{R})\), on définit la trace de A, notée \(\operatorname{tr}(A)\) par :
\end{itemize}

\[
\operatorname{tr}(A)=\sum_{i=1}^{n} a_{i, i}
\]

\begin{enumerate}
  \setcounter{enumi}{3}
  \item Notons \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\) et \(B=\left(b_{i, j}\right)_{1 \leqslant i, j \leqslant n}\).\\
a) Montrer que \(: \operatorname{tr}(A B)=\sum_{i=1}^{n}\left(\sum_{j=1}^{n} a_{i, j} b_{j, i}\right)=\sum_{1 \leqslant i, j \leqslant n} a_{i, j} b_{j, i}\).\\
b) En déduire que : \(\operatorname{tr}(A B)=\operatorname{tr}(B A)\) et \(\operatorname{tr}\left({ }^{t} A A\right)=\sum_{1 \leqslant i, j \leqslant n} a_{j, i}^{2}\).
\end{enumerate}

Que peut-on dire de \(A\) si \(\operatorname{tr}\left({ }^{t} A A\right)=0\) ?\\
c) Si \(A\) et \(B\) sont semblables, montrer que \(\operatorname{tr}(A)=\operatorname{tr}(B)\).\\
5. Dans cette question \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\) est symétrique et on utilise les notations de la question 1.\\
a) Montrer que \(|\operatorname{tr}(A)| \leqslant \mathcal{E}(A)\).\\
b) Justifier que \(\operatorname{tr}\left(A^{2}\right)=\sum_{k=1}^{n} \lambda_{k}^{2}\).\\
6. Dans la console Python, on obtient :

\begin{verbatim}
>>> energie(3*np.eye(3)-np.ones([3,3]))
6.0
\end{verbatim}

a) Déterminer quelle est la matrice \(A\) associée au tableau \(3 *\) np. eye \((3,3)\)-np. ones \(([3,3])\).\\
b) En calculant \(\operatorname{tr}(A), \operatorname{tr}\left(A^{2}\right)\) et en déterminant une valeur propre évidente de \(A\), expliciter son spectre et retrouver son énergie.

\section*{Partie 2 - Produit de Kronecker \(2 \times n\) de matrices symétriques}
\begin{itemize}
  \item Soit \(U=\left(\begin{array}{ll}u & v \\ v & w\end{array}\right)\) une matrice carrée appartenant à \(\mathcal{M}_{2}(\mathbb{R})\) symétrique et \(A\) une matrice carrée appartenant à \(\mathcal{M}_{n}(\mathbb{R})\) symétrique.\\
On définit \(U * A\) la matrice carrée appartenant à \(\mathcal{M}_{2 n}(\mathbb{R})\) que l'on peut naturellement représenter ainsi \(\left(\begin{array}{cc}u A & v A \\ v A & w A\end{array}\right)\) (écriture par blocs).
  \item Par exemple, si \(U=\left(\begin{array}{ll}2 & 1 \\ 1 & 0\end{array}\right)\) et \(A=\left(\begin{array}{lll}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{array}\right)\), alors \(U * A=\left(\begin{array}{cc}2 A & A \\ A & 0_{3}\end{array}\right)\) par blocs, d'où \(U * A=\left(\begin{array}{cccccc}0 & 2 & 2 & 0 & 1 & 1 \\ 2 & 0 & 0 & 1 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0\end{array}\right)\) (03 désigne la matrice nulle de \(\mathcal{M}_{3}(\mathbb{R})\) ).
  \item Si \(X\) est une matrice colonne appartenant à \(\mathcal{M}_{2 n, 1}(\mathbb{R}), X=\left(\begin{array}{c}x_{1} \\ \vdots \\ x_{2 n}\end{array}\right)\), on écrira \(X=\binom{X_{1}}{X_{2}}\) avec \(X_{1}=\left(\begin{array}{c}x_{1} \\ \vdots \\ x_{n}\end{array}\right)\) et \(X_{2}=\left(\begin{array}{c}x_{n+1} \\ \vdots \\ x_{2 n}\end{array}\right)\).\\
On admet qu'alors la matrice colonne \((U * A) X\) de \(\mathcal{M}_{2 n, 1}(\mathbb{R})\) est égale à \(\binom{u A X_{1}+v A X_{2}}{v A X_{1}+w A X_{2}}\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{6}
  \item a) Écrire une fonction Python \(\operatorname{prod} 2 \mathrm{~K}(\mathrm{u}, \mathrm{v}, \mathrm{w}, \mathrm{A})\) qui étant donné \(U=\left(\begin{array}{ll}u & v \\ v & w\end{array}\right)\) et \(A\), représentée par un tableau numpy, renvoie \(U * A\) sous la forme d'un tableau numpy.\\
b) Compléter le code suivant s'affichant dans la console Python:
\end{enumerate}

\begin{verbatim}
>>> prod2K(...,-1,...,...)
array([[-2., 1., 2., -1.],
    [ 1., -2., -1., 2.],
    [ 2., -1., -4., 2.],
    [-1., 2., 2., -4.]])
\end{verbatim}

\begin{enumerate}
  \setcounter{enumi}{7}
  \item Soit \(\binom{a}{b}\) un vecteur propre de \(U\) pour la valeur propre \(\lambda\) et \(X\) un vecteur propre de \(A\) pour \(\mu\). On pose \(Y=\binom{a X}{b X}\).\\
a) Établir l'égalité : \((U * A) Y=\mu\binom{(u a+v b) X}{(v a+w b) X}\).\\
b) Montrer que \(Y\) est un vecteur propre de \(U * A\) et préciser pour quelle valeur propre.
  \item a) Justifier l'existence d'une base \(\left(\binom{a}{b},\binom{c}{d}\right)\) de \(\mathcal{M}_{2,1}(\mathbb{R})\) et de \(\left(X_{1}, \ldots, X_{n}\right)\) une base de \(\mathcal{M}_{n, 1}(\mathbb{R})\), formée de vecteurs propres de \(U\) et \(A\) respectivement.
\end{enumerate}

\begin{itemize}
  \item On note \(\gamma_{1}\) et \(\gamma_{2}\) les valeurs propres associées à \(\binom{a}{b}\) et \(\binom{c}{d}\) respectivement et \(\mu_{1}, \ldots, \mu_{n}\) celles associées à \(X_{1}, \ldots, X_{n}\) respectivement.\\
On pose, pour tout \(i \in \llbracket 1, n \rrbracket, Y_{i}=\binom{a X_{i}}{b X_{i}}\) et \(Z_{i}=\binom{c X_{i}}{d X_{i}}\).\\
b) Montrer que la famille ( \(Y_{1}, Z_{1}, \ldots, Y_{n}, Z_{n}\) ) est libre.\\
c) En déduire que \(U * A\) est semblable à la matrice diagonale dont les éléments diagonaux sont \(\gamma_{1} \mu_{1}, \gamma_{2} \mu_{1}, \ldots, \gamma_{1} \mu_{n}, \gamma_{2} \mu_{n}\).\\
d) En conclure que \(\mathcal{E}(U * A)=\mathcal{E}(U) \times \mathcal{E}(A)\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{9}
  \item Un exemple - On considère un graphe \(G_{n}\), non orienté et sans boucle, dont les sommets sont \(1, \ldots, n\) et l'ensemble des arêtes est noté \(\mathcal{A}_{n}\). On définit le graphe \(G_{2 n}\) dont les sommets sont \(1, \ldots, 2 n\) et les arêtes sont celles de \(G_{n}\), ainsi que, pour toute arête \(\{i, j\} \in \mathcal{A}_{n}\), les arêtes \(\{i+n, j\}\) et \(\{i, j+n\}\).\\
Voici un exemple de représentation de \(G_{4}\) et \(G_{8}:\)\\
\includegraphics[max width=\textwidth, alt={}, center]{41eeb5ab-b63a-4b68-9248-b12b4496cda4-4_470_373_625_573}\\
\includegraphics[max width=\textwidth, alt={}, center]{41eeb5ab-b63a-4b68-9248-b12b4496cda4-4_464_563_628_1007}
\end{enumerate}

On note \(A_{n}\) et \(A_{2 n}\) les matrices d'adjacence de \(G_{n}\) et \(G_{2 n}\).\\
a) Déterminer \(U\) telle que \(A_{2 n}=U * A_{n}\).\\
b) En déduire que \(\mathcal{E}\left(A_{2 n}\right)=\sqrt{5} \mathcal{E}\left(A_{n}\right)\).

\section*{Partie 3 - Encadrement de l'énergie d'une matrice d'adjacence}
Soit \(m\), \(n\) et \(p\) des entiers tels que \(m \geqslant 1\), \(n \geqslant p \geqslant 2\).\\
On suppose dans cette partie que \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\) est la matrice d'adjacence d'un graphe \(G(A)\), non orienté sans boucle, à \(n\) sommets \(1, \ldots, n, m\) arêtes et \(n-p\) sommets isolés, c'est-à-dire de degré 0 .

On note \(\left(E_{1}, \ldots, E_{n}\right)\) la base canonique de \(\mathcal{M}_{n, 1}(\mathbb{R})\) et \(I\) l'ensemble des sommets non isolés de \(G(A)\).\\
11. a) Montrer que \(\sum_{1 \leqslant i, j \leqslant n} a_{i, j}=\sum_{(i, j) \in I^{2}} a_{i, j}=2 m\).\\
b) Établir que : \(1 \leqslant \frac{2 m}{p} \leqslant p-1\).\\
12. a) Justifier qu'il existe une matrice carrée inversible \(P\) appartenant à \(\mathcal{M}_{n}(\mathbb{R})\) telle que \(P^{-1} A P\) soit une matrice diagonale différente de la matrice nulle.

\begin{itemize}
  \item Dans la suite on note \(D\) cette matrice diagonale.\\
b) En déduire que \(\operatorname{tr}(D)=0, \operatorname{tr}\left(D^{2}\right)=\sum_{1 \leqslant i, j \leqslant n} a_{i, j}^{2}=2 m\).
  \item On suppose dans la suite que \(P\) est telle que les éléments diagonaux de \(D, \lambda_{1}, \ldots, \lambda_{n}\) vérifient \(\left|\lambda_{1}\right| \geqslant \ldots \geqslant\left|\lambda_{n}\right|\). On pose \(\theta=\max _{1 \leqslant k \leqslant n} \lambda_{k}\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{12}
  \item a) Soit \(k\) un sommet isolé. Montrer que \(E_{k} \in \operatorname{ker}(A)\).
\end{enumerate}

En déduire que \(\operatorname{dim}(\operatorname{ker}(A)) \geqslant n-p\) puis que, si \(p<n, \lambda_{p+1}=\ldots=\lambda_{n}=0\).\\
b) Montrer que \(\sum_{k=1}^{p} \lambda_{k}^{2}=2 m\) puis que \(0<\theta \leqslant \sqrt{2 m}\).\\
c) Soit \(r \in \mathbb{N}^{*}\) et \(x_{1}, \ldots, x_{r}\) des réels. Montrer que : \(\sum_{1 \leqslant i, j \leqslant r} 2 x_{i} x_{j} \leqslant \sum_{1 \leqslant i, j \leqslant r}\left(x_{i}^{2}+x_{j}^{2}\right)\). En déduire que \(\left(\sum_{i=1}^{r} x_{i}\right)^{2} \leqslant r\left(\sum_{i=1}^{r} x_{i}^{2}\right)\).\\
d) En conclure que \(\mathcal{E}(A) \leqslant \theta+\sqrt{(p-1)\left(2 m-\theta^{2}\right)}\).\\
14. On admet qu'on peut choisir la matrice \(P\) de la question 12.a) de sorte que \(P^{-1}={ }^{t} P\). On pose alors \(Q={ }^{t} P\).\\
Soit \(X=\left(\begin{array}{c}x_{1} \\ \vdots \\ x_{n}\end{array}\right)\) une matrice colonne appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R})\) et \(Y=Q X=\left(\begin{array}{c}y_{1} \\ \vdots \\ y_{n}\end{array}\right)\).

\begin{itemize}
  \item On admet que si \(M\) est une matrice carrée appartenant à \(\mathcal{M}_{n}(\mathbb{R})\) et \(Z\) une matrice colonne appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R})\) alors \({ }^{t}(M Z)={ }^{t} Z^{t} M\).
  \item Si \(U\) et \(V\) sont deux matrices colonnes appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R}),{ }^{t} U V\) est une matrice carrée appartenant à \(\mathcal{M}_{1,1}(\mathbb{R})\), on l'identifie à son unique coefficient. Donc \({ }^{t} U V \in \mathbb{R}\).\\
a) Montrer que \(Q^{-1}={ }^{t} Q\) puis que \(A={ }^{t} Q D Q\) et \({ }^{t} Y Y={ }^{t} X X\).\\
b) Montrer que \({ }^{t} X A X={ }^{t} Y D Y=\sum_{k=1}^{n} \lambda_{k} y_{k}^{2}\).\\
c) En remarquant que \(\sum_{k=1}^{n} y_{k}^{2}={ }^{t} Y Y\), en déduire que \({ }^{t} X A X \leqslant \theta^{t} X X\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{14}
  \item Soit \(U\) la matrice colonne appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R})\) dont le \(i\) ème coefficient vaut 1 si \(i\) n'est pas isolé et 0 sinon.\\
a) Montrer que \({ }^{t} U A U=\sum_{(i, j) \in I^{2}} a_{i, j}=2 m\). En déduire que \(\frac{2 m}{p} \leqslant \theta\).\\
b) Établir que : \(\frac{1}{\sqrt{p}} \leqslant \frac{\sqrt{2 m}}{p} \leqslant \frac{\theta}{\sqrt{2 m}} \leqslant 1\).
  \item a) Étudier la fonction \(F: x \mapsto x+\sqrt{(p-1)\left(1-x^{2}\right)}\) sur \([0,1]\).\\
b) En déduire que \(\mathcal{E}(A) \leqslant \sqrt{2 m} F\left(\frac{\sqrt{2 m}}{p}\right)\), c'est-à-dire que :
\end{enumerate}

\[
\mathcal{E}(A) \leqslant \frac{2 m}{p}+\frac{1}{p} \sqrt{(p-1) 2 m\left(p^{2}-2 m\right)}
\]

\begin{enumerate}
  \setcounter{enumi}{16}
  \item On suppose dans cette question que \(A\) est la matrice d'adjacence d'un graphe complet de sommets \(1, \ldots, n\) donc \(m=\frac{n(n-1)}{2}\) et \(p=n\).\\
a) Représenter la matrice \(A\).\\
b) Montrer -1 est une valeur propre de \(A\) et que le sous-espace propre associé est de dimension \(n-1\).\\
c) Établir aussi que \(n-1\) est une valeur propre de \(A\). En déduire que \(\mathcal{E}(A)=2(n-1)\) et que l'inégalité (1) est alors une égalité.
\end{enumerate}

\begin{itemize}
  \item On note \(\alpha=\min _{1 \leqslant k \leqslant p}\left|\lambda_{k}\right|\) et \(\beta=\max _{1 \leqslant k \leqslant p}\left|\lambda_{k}\right|\). On note aussi \(d\) le degré maximal des sommets du graphe \(G(A)\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{17}
  \item Écrire une fonction Python \(\operatorname{degMax}(\mathrm{A})\) qui renvoie le maximum des degrés des sommets du graphe \(G(A)\), celui-ci étant donné par sa matrice d'adjacence sous la forme du tableau numpy A .
  \item a) Montrer que pour tout \(j \in\{1, \ldots, p\},\left|\lambda_{j}\right|(\alpha+\beta) \geqslant \lambda_{j}^{2}+\alpha \beta\).\\
b) En déduire que \((\alpha+\beta) \mathcal{E}(A) \geqslant \operatorname{tr}\left(A^{2}\right)+p \alpha \beta\), puis que \(\mathcal{E}(A) \geqslant \frac{2 m+p \alpha \beta}{\alpha+\beta}\).\\
c) Soit \(a\) et \(b\) deux réels strictement positifs tels que \(a \leqslant b^{2}\). Étudier les variations de \(\varphi: t \mapsto \frac{a+b t}{b+t}\) sur \(\mathbb{R}^{+}\).\\
d) Montrer que \(2 m \leqslant p \beta^{2}\). En déduire que \(\mathcal{E}(A) \geqslant \frac{2 m}{\beta}\).
  \item Soit \(X=\left(\begin{array}{c}x_{1} \\ \vdots \\ x_{n}\end{array}\right)\) un vecteur propre pour une valeur propre \(\lambda\) de \(A\) telle que \(|\lambda|=\beta\).\\
a) Montrer que pour tout \(i \in\{1, \ldots, n\}, \beta\left|x_{i}\right| \leqslant d \max _{1 \leqslant j \leqslant n}\left|x_{j}\right|\).\\
b) En conclure que \(\mathcal{E}(A) \geqslant \frac{2 m}{d} \geqslant \frac{2 m}{p-1}\)\\
c) Montrer que l'égalité dans (2) est réalisée pour la matrice \(A\) carrée appartenant à \(\mathcal{M}_{n}(\mathbb{R})\) associée au graphe dont l'unique arête est \(\{1,2\}\).
\end{enumerate}

\section*{Aide-mémoire Python}
On suppose que l'on a exécuté import numpy as np, numpy.linalg as al en début de session.

\begin{itemize}
  \item Si T est un tableau numpy, np.shape(T) renvoie le nombre de lignes et le nombre de colonnes de T , dans cet ordre, sous la forme d'un couple.
  \item np.zeros( \([p, q]\) ) crée un tableau numpy à \(p\) lignes et \(q\) colonnes ne contenant que des 0 .
  \item np.ones \(([p, q])\) crée un tableau numpy à \(p\) lignes et \(q\) colonnes ne contenant que des 1 .
  \item np.eye(p) crée un tableau numpy à \(p\) lignes et \(p\) colonnes ne contenant que des 1 sur sa diagonale et des 0 ailleurs.
  \item La fonction al.eigvals, appliquée à un tableau numpy représentant une matrice symétrique \(A\), renvoie le tableau des coefficients d'une matrice diagonale semblable à \(A\).
\end{itemize}

\end{document}