Connectez-vous pour consulter le corrigé.
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 fin de sujet.
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}}\).
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\) ?
En notant \(\lambda_{1}, \ldots, \lambda_{n}\) les éléments diagonaux de \(P^{-1} A P\), on pose alors \(\mathcal{E}(A)= \displaystyle \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\).
Montrer que \(\mathcal{E}(A)=3\) si \(A= \begin{pmatrix} 1 & -1 & -1 \\ -1 & 0 & 0 \\ -1 & 0 & 0 \end{pmatrix}\).
Écrire une fonction Python
energie(A) qui renvoie l’énergie de la matrice
symétrique représentée par le tableau numpy
A.
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 : \[\operatorname{tr}(A)=\sum_{i=1}^{n} a_{i, i}\]
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}\).
Montrer que : \(\displaystyle \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}\).
En déduire que : \(\displaystyle \operatorname{tr}(A B)=\operatorname{tr}(B A)\) et \(\displaystyle \operatorname{tr}({}^t\!A A)=\sum_{1 \leqslant i, j \leqslant n} a_{j, i}^{2}\).
Que peut-on dire de \(A\) si \(\operatorname{tr}({}^t\!A A)=0\) ?
Si \(A\) et \(B\) sont semblables, montrer que \(\operatorname{tr}(A)=\operatorname{tr}(B)\).
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.
Montrer que \(\left| \mathrm{Tr}(A) \right| \leqslant \mathcal{E}(A)\).
Justifier que \(\operatorname{tr}(A^{2})= \displaystyle \sum_{k=1}^{n} \lambda_{k}^{2}\).
Dans la console Python, on obtient
:
>>> energie(3*np.eye(3)-np.ones([3,3]))
6.0
Déterminer quelle est la matrice \(A\) associée au tableau
3*np.eye([3,3])-np.ones([3,3]).
En calculant \(\operatorname{tr}(A)\), \(\operatorname{tr}(A^{2})\) et en déterminant une valeur propre évidente de \(A\), expliciter son spectre et retrouver son énergie.
Soit \(U= \begin{pmatrix} u & v \\ v & w \end{pmatrix}\) 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 \(\begin{pmatrix} u A & v A \\ v A & w A \end{pmatrix}\) (écriture par blocs).
Par exemple, si \(U= \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}\) et \(A= \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}\), alors \(U * A= \begin{pmatrix} 2 A & A \\ A & 0_{3} \end{pmatrix}\) par blocs, d’où \(U * A= \begin{pmatrix} 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{pmatrix} \quad\) (\(0_{3}\) désigne la matrice nulle de \(\mathcal{M}_{3}(\mathbb{R})\)).
Si \(X\) est une matrice colonne appartenant à \(\mathcal{M}_{2 n, 1}(\mathbb{R}),\) \(X= \begin{pmatrix} x_{1} \\ \vdots \\ x_{2 n} \end{pmatrix}\), on écrira \(X= \begin{pmatrix} X_{1} \\ X_{2} \end{pmatrix}\) avec \(X_{1}= \begin{pmatrix} x_{1} \\ \vdots \\ x_{n} \end{pmatrix}\) et \(X_{2}= \begin{pmatrix} x_{n+1} \\ \vdots \\ x_{2 n} \end{pmatrix}\).
On admet qu’alors la matrice colonne \(\left( U * A \right) X\) de \(\mathcal{M}_{2 n, 1}(\mathbb{R})\) est égale à \(\begin{pmatrix} u A X_{1}+v A X_{2} \\ v A X_{1}+w A X_{2} \end{pmatrix}\).
Écrire une fonction Python
prod2K(u,v,w,A) qui étant donné \(U= \begin{pmatrix} u & v \\ v & w
\end{pmatrix}\) et \(A\),
représentée par un tableau numpy, renvoie
\(U * A\) sous la forme d’un tableau
numpy.
Compléter le code suivant s’affichant dans la console
Python :
>>> prod2K(....,-1,....,....)
array([[-2., 1., 2.,-1.],
[ 1.,-2.,-1., 2.],
[ 2.,-1.,-4., 2.],
[-1., 2., 2.,-4.]])
Soit \(\begin{pmatrix} a \\ b \end{pmatrix}\) un vecteur propre de \(U\) pour la valeur propre \(\lambda\) et \(X\) un vecteur propre de \(A\) pour \(\mu\). On pose \(Y= \begin{pmatrix} a X \\ b X \end{pmatrix}\).
Établir l’égalité : \(\left( U * A \right) Y=\mu \begin{pmatrix} (u a+v b) X \\ (v a+w b) X \end{pmatrix}\).
Montrer que \(Y\) est un vecteur propre de \(U * A\) et préciser pour quelle valeur propre.
Justifier l’existence d’une base \(\left( \begin{pmatrix} a \\ b \end{pmatrix} , \begin{pmatrix} c \\ d \end{pmatrix} \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.
\(\blacktriangleright\) On note \(\gamma_{1}\) et \(\gamma_{2}\) les valeurs propres associées à \(\begin{pmatrix} a \\ b \end{pmatrix}\) et \(\begin{pmatrix} c \\ d \end{pmatrix}\) respectivement et \(\mu_{1}, \ldots, \mu_{n}\) celles associées à \(X_{1}, \ldots, X_{n}\) respectivement.
On pose, pour tout \(i \in \left[\!\left[1, n\right]\!\right], \ Y_{i}= \begin{pmatrix} a X_{i} \\ b X_{i} \end{pmatrix}\) et \(Z_{i}= \begin{pmatrix} c X_{i} \\ d X_{i} \end{pmatrix}\).
Montrer que la famille \(\left(Y_{1}, Z_{1}, \ldots, Y_{n}, Z_{n}\right)\) est libre.
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}\).
En conclure que \(\mathcal{E}(U * A)= \mathcal{E}(U) \times \mathcal{E}(A_{n})\).
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}\) :
On note \(A_{n}\) et \(A_{2 n}\) les matrices d’adjacence de \(G_{n}\) et \(G_{2 n}\).
Déterminer \(U\) telle que \(A_{2 n}=U * A_{n}\).
En déduire que \(\mathcal{E}(A_{2 n})=\sqrt{5} \, \mathcal{E}(A_{n})\).
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)\).
Montrer que \(\displaystyle \sum_{1 \leqslant i, j \leqslant n} a_{i, j}=\sum_{(i, j) \in I^{2}} a_{i, j}=2 m\).
Établir que : \(\displaystyle 1 \leqslant \frac{2 m}{p} \leqslant p-1\).
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.
\(\blacktriangleright\) Dans la suite on note \(D\) cette matrice diagonale.
En déduire que \(\displaystyle \operatorname{tr}(D)=0, \ \operatorname{tr}(D^{2})=\sum_{1 \leqslant i, j \leqslant n} a_{i, j}^{2}=2 m\).
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\limits _{1 \leqslant k \leqslant n} \lambda_{k}\).
Soit \(k\) un sommet isolé. Montrer que \(E_{k} \in \operatorname{ker}(A)\). En déduire que \(\operatorname{dim}(\operatorname{ker}(A)) \geqslant n-p\) puis que, si \(p<n\), \(\lambda_{p+1}=\ldots=\lambda_{n}=0\).
Montrer que \(\displaystyle \sum_{k=1}^{p} \lambda_{k}^{2}=2 m\) puis que \(0<\theta \leqslant \sqrt{2 m}\).
Soit \(r \in \mathbb{N}^{*}\) et \(x_{1}, \ldots, x_{r}\) des réels. Montrer que : \(\displaystyle \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 \(\displaystyle \left(\sum_{i=1}^{r} x_{i}\right)^{2} \leqslant r\left(\sum_{i=1}^{r} x_{i}^{2}\right)\).
En conclure que \(\mathcal{E}(A) \leqslant \theta+\sqrt{(p-1)\left(2 m-\theta^{2}\right)}\).
On admet qu’on peut choisir la matrice \(P\) de la question 12a de sorte que \(P^{-1}={}^t\!P\). On pose alors \(Q={}^t\!P\).
Soit \(X= \begin{pmatrix} x_{1} \\ \vdots \\ x_{n} \end{pmatrix}\) une matrice colonne appartenant à \(\mathcal{M}_{n, 1}(\mathbb{R})\) et \(Y=Q X= \begin{pmatrix} y_{1} \\ \vdots \\ y_{n} \end{pmatrix}\).
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\!\left( M Z \right)={}^t\!Z\,{}^t\!M\).
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}\).
Montrer que \(Q^{-1}={}^t\!\, Q\) puis que \(A={}^t\!\, Q D Q\) et \({}^t\!\, Y Y={}^t\!X X\).
Montrer que \(\displaystyle {}^t\!X A X={}^t\!\, Y D Y=\sum_{k=1}^{n} \lambda_{k} y_{k}^{2}\).
En remarquant que \(\displaystyle \sum_{k=1}^{n} y_{k}^{2}={}^t\!\, Y Y\), en déduire que \({}^t\!X A X \leqslant \theta \,{}^t\!X X\).
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.
Montrer que \(\displaystyle {}^t\!\, U A U=\sum_{(i, j) \in I^{2}} a_{i, j}=2m\). En déduire que \(\displaystyle \frac{2 m}{p} \leqslant \theta\).
Établir que : \(\displaystyle \frac{1}{\sqrt{p}} \leqslant \frac{\sqrt{2 m}}{p} \leqslant \frac{\theta}{\sqrt{2 m}} \leqslant 1\).
Étudier la fonction \(F: x \mapsto x+\sqrt{(p-1)\left(1-x^{2}\right)}\) sur \([0,1]\).
En déduire que \(\displaystyle \mathcal{E}(A) \leqslant \sqrt{2 m} \, F \! \left(\frac{\sqrt{2 m}}{p}\right)\), c’est-à-dire que :
\[\mathcal{E}(A) \leqslant \frac{2 m}{p}+\frac{1}{p} \sqrt{ \left( p-1 \right) 2 m\left(p^{2}-2 m\right)} \tag{1}\]
On suppose dans cette question que \(A\) est la matrice d’adjacence d’un graphe complet de sommets \(1, \ldots, n\) donc \(\displaystyle m=\frac{n \left(n-1 \right)}{2}\) et \(p=n\).
Représenter la matrice \(A\).
Montrer \(- 1\) est une valeur propre de \(A\) et que le sous-espace propre associé est de dimension \(n-1\).
Établir aussi que \(n-1\) est une valeur propre de \(A\). En déduire que \(\mathcal{E}(A)=2 \left(n-1 \right)\) et que l’inégalité (1) est alors une égalité.
On note \(\displaystyle \alpha=\min _{1 \leqslant k \leqslant p}\left|\lambda_{k}\right|\) et \(\displaystyle \beta=\max _{1 \leqslant k \leqslant p}\left|\lambda_{k}\right|\). On note aussi \(d\) le degré maximal des sommets du graphe \(G(A)\).
Écrire une fonction Python
degMax(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.
Montrer que pour tout \(j \in\{1, \ldots, p\}\), \(\left|\lambda_{j}\right|(\alpha+\beta) \geqslant \lambda_{j}^{2}+\alpha \beta\).
En déduire que \(\left( \alpha+\beta \right) \mathcal{E}(A) \geqslant \operatorname{tr}(A^{2})+p \alpha \beta\), puis que \(\displaystyle \mathcal{E}(A) \geqslant \frac{2 m+p \alpha \beta}{\alpha+\beta}\).
Soit \(a\) et \(b\) deux réels strictement positifs tels que \(a \leqslant b^{2}\). Étudier les variations de \(\varphi: t \mapsto \displaystyle \frac{a+b t}{b+t}\) sur \(\mathbb{R}^{+}\).
Montrer que \(2 m \leqslant p \beta^{2}\). En déduire que \(\displaystyle \mathcal{E}(A) \geqslant \frac{2 m}{\beta}\).
Soit \(X= \begin{pmatrix} x_{1} \\ \vdots \\ x_{n} \end{pmatrix}\) un vecteur propre pour une valeur propre \(\lambda\) de \(A\) telle que \(|\lambda|=\beta\).
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|\).
En conclure que \(\displaystyle \mathcal{E}(A) \geqslant \frac{2 m}{d} \geqslant \frac{2 m}{p-1}\).
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\}\).
On suppose que l’on a exécuté import numpy as np, numpy.linalg as al en début de session.
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.
np.zeros([p,q]) crée un tableau
numpy à \(p\)
lignes et \(q\) colonnes ne contenant
que des 0.
np.ones([p,q]) crée un tableau
numpy à \(p\)
lignes et \(q\) colonnes ne contenant
que des 1.
np.eye([p,q]) crée un tableau
numpy à \(p\)
lignes et \(p\) colonnes ne contenant
que des 1 sur sa diagonale et des 0 ailleurs.
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\).
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
