Corrigé EDHEC 2026 Maths appliquées ECG — Problème, partie 3 (Q4 à Q8) : Matrice d'adjacence d'un graphe de Moore : symétrie, coefficients 0 ou 1, diagonale de A² égale au degré, relation A² + A = (d − 1)Iₙ + Jₙ

$G$ est un graphe de Moore : $n=d^2+1$. Sa matrice d'adjacence est $A=(a_{i,j})\in {\mathcal{M}}_n(\mathbb{R})$, où $a_{i,j}$ est le nombre d'arêtes reliant les sommets $i$ et $j$. On rappelle la définition du produit matriciel : $(EF{)}_{i,j}={\sum }_k{e}_{i,k}{f}_{k,j}$. On admet que chaque sommet est de degré $d$ et est relié à tout autre sommet par exactement une chaîne, de longueur $1$ ou $2$. On pose $B=A^2=(b_{i,j})$ ; $b_{i,j}$ est le nombre de chaînes de longueur $2$ reliant $i$ et $j$.

Q4. Rappeler pourquoi $A$ est symétrique.
Q5. (a) Justifier que $a_{i,j}\in \{0,1\}$. (b) Expliquer pourquoi $a_{i,i}=0$.
Q6. (a) Montrer que $b_{i,j}={\sum }_{k=1}^n{a}_{i,k}{a}_{j,k}$. (b) Montrer que $b_{i,i}={\sum }_{k=1}^n{a}_{i,k}$, puis que $b_{i,i}=d$.
Q7. Soient $i\ne j$. (a) Établir que ($a_{i,j}=0$ et $b_{i,j}=1$) ou ($a_{i,j}=1$ et $b_{i,j}=0$). (b) En déduire $b_{i,j}+a_{i,j}$. (c) Donner $b_{i,i}+a_{i,i}$.
Q8. Déduire de Q7(b) et Q7(c) que $A^2+A=(d-1)I_n+J_n$.