Déterminant, trace et fonction zêta d'un graphe

Le but de cet exercice est d'établir une relation fondamentale entre le déterminant et la trace via les séries entières, puis d'appliquer ce résultat à l'étude combinatoire des graphes.

Soit $A \in \mathcal{M}_{n}(\mathbb{C})$ . On note $\rho(A)$ son rayon spectral. Montrer que pour tout complexe $z$ tel que $|z| < \frac{1}{\rho(A)}$ , on a l'identité suivante : $\det(I_{n} + z A) = \exp \left( \sum_{k=1}^{+\infty} \frac{(-1)^{k-1} \operatorname{Tr}(A^{k})}{k} z^{k} \right)$
On considère un graphe non orienté $G$ $G$ possédant $m$ $m$ sommets, numérotés de $1$ $1$ à $m$ $m$ . On note $M \in \mathcal{M}_{m}(\mathbb{Z})$ $M \in M_{m} (Z)$ sa matrice d'adjacence, définie par $M_{i,j}=1$ $M_{i, j} = 1$ si les sommets $i$ $i$ et $j$ $j$ sont reliés par une arête, et $0$ $0$ sinon. Pour tout $n \in \mathbb{N}^*$ $n \in N^{*}$ , on note $N_n(G)$ $N_{n} (G)$ le nombre de chemins fermés de longueur $n$ $n$ dans le graphe.
1. Justifier que $N_n(G) = \operatorname{Tr}(M^n)$ .
2. On définit la fonction zêta du graphe par la série : $\zeta_{G}(z) = \exp \left( \sum_{n=1}^{+\infty} \frac{N_{n}(G)}{n} z^{n} \right)$ Montrer que pour tout complexe $z$ de module strictement inférieur à $1/\rho(M)$ , on a : $\zeta_{G}(z) = \frac{1}{\det(I_{m} - z M)}$

1.

Pour la première question, utiliser le fait que toute matrice de $\mathcal{M}_n(\mathbb{C})$ est trigonalisable. Exprimer le déterminant et la trace à l'aide des valeurs propres.

2.

Utiliser le développement en série entière de la fonction $u \mapsto \ln(1+u)$ pour $|u| < 1$ .

3.

Pour la question 2.(a), interpréter le coefficient $(M^n)_{i,j}$ comme le nombre de chemins de longueur $n$ allant de $i$ vers $j$ .

4.

Pour la question 2.(b), appliquer la formule de la question 1 avec une matrice et une variable $z$ bien choisies.

Idées clés

•

Trigonalisation sur $\mathbb{C}$ pour ramener le problème aux valeurs propres.

•

Utilisation des séries entières ( $\ln$ et $\exp$ ).

•

Lien combinatoire entre puissances de la matrice d'adjacence et dénombrement de chemins.

1. Preuve de l'identité déterminant-trace.

Soit $A \in \mathcal{M}_n(\mathbb{C})$ . Le corps $\mathbb{C}$ étant algébriquement clos, le polynôme caractéristique de $A$ est scindé.

Par conséquent, $A$ est trigonalisable dans $\mathcal{M}_n(\mathbb{C})$ . Il existe $P \in GL_n(\mathbb{C})$ et une matrice triangulaire supérieure $T$ telles que :

A = P T P^{-1}

Les coefficients diagonaux de $T$ sont les valeurs propres $\lambda_1, \dots, \lambda_n$ de $A$ (comptées avec multiplicité).

Pour tout $k \in \mathbb{N}^*$ , on a $A^k = P T^k P^{-1}$ . La matrice $T^k$ est également triangulaire et ses coefficients diagonaux sont $\lambda_1^k, \dots, \lambda_n^k$ . On en déduit :

\operatorname{Tr}(A^k) = \operatorname{Tr}(T^k) = \sum_{i=1}^n \lambda_i^k

Considérons maintenant $z \in \mathbb{C}$ tel que $|z| < \frac{1}{\rho(A)}$ . Par définition du rayon spectral, pour tout $i \in \{1, \dots, n\}$ , on a $|\lambda_i| \le \rho(A)$ , donc $|z \lambda_i| < 1$ .

Le déterminant étant invariant par similitude :

\det(I_n + zA) = \det(P(I_n + zT)P^{-1}) = \det(I_n + zT)

Comme $I_n + zT$ est triangulaire, son déterminant est le produit de ses coefficients diagonaux :

\det(I_n + zA) = \prod_{i=1}^n (1 + z\lambda_i)

En utilisant la fonction exponentielle et le développement en série entière de $\ln(1+u)$ pour $|u| < 1$ , on obtient :

\det(I_n + zA) = \exp \left( \sum_{i=1}^n \ln(1 + z\lambda_i) \right)

\det(I_n + zA) = \exp \left( \sum_{i=1}^n \sum_{k=1}^{+\infty} \frac{(-1)^{k-1} (z\lambda_i)^k}{k} \right)

Comme les sommes sont finies sur $i$ , on peut intervertir les symboles $\sum$ :

\det(I_n + zA) = \exp \left( \sum_{k=1}^{+\infty} \frac{(-1)^{k-1} z^k}{k} \sum_{i=1}^n \lambda_i^k \right)

En remplaçant la somme des puissances des valeurs propres par la trace, on obtient le résultat :

\boxed{ \det(I_n + zA) = \exp \left( \sum_{k=1}^{+\infty} \frac{(-1)^{k-1} \operatorname{Tr}(A^k)}{k} z^k \right) }

2. Application aux graphes.

Nombre de chemins fermés. Par une récurrence classique sur $n$ , on montre que le coefficient $(M^n)_{i,j}$ de la matrice $M^n$ est égal au nombre de chemins de longueur $n$ joignant le sommet $i$ au sommet $j$ . Un chemin fermé de longueur $n$ est un chemin qui part d'un sommet $i$ et revient à ce même sommet $i$ en $n$ étapes. Pour un sommet $i$ fixé, ce nombre est donné par $(M^n)_{i,i}$ . Le nombre total de chemins fermés de longueur $n$ dans le graphe est donc la somme de ces coefficients sur tous les sommets possibles : $N_n(G) = \sum_{i=1}^m (M^n)_{i,i} = \boxed{ \operatorname{Tr}(M^n) }$
Expression de la fonction zêta. On utilise l'identité démontrée à la question 1 en remplaçant $A$ par $-M$ . Pour $|z| < 1/\rho(M)$ , on a : $\det(I_m + z(-M)) = \exp \left( \sum_{k=1}^{+\infty} \frac{(-1)^{k-1} \operatorname{Tr}((-M)^k)}{k} z^k \right)$
Observons que $\operatorname{Tr}((-M)^k) = \operatorname{Tr}((-1)^k M^k) = (-1)^k \operatorname{Tr}(M^k)$ . Le terme général de la somme devient :
$\frac{(-1)^{k-1} (-1)^k \operatorname{Tr}(M^k)}{k} z^k = \frac{(-1)^{2k-1} \operatorname{Tr}(M^k)}{k} z^k = - \frac{\operatorname{Tr}(M^k)}{k} z^k$
Ainsi :
$\det(I_m - zM) = \exp \left( - \sum_{k=1}^{+\infty} \frac{\operatorname{Tr}(M^k)}{k} z^k \right)$
Par définition de la fonction zêta et en utilisant $N_k(G) = \operatorname{Tr}(M^k)$ , on a :
$\zeta_G(z) = \exp \left( \sum_{k=1}^{+\infty} \frac{\operatorname{Tr}(M^k)}{k} z^k \right)$
On en déduit immédiatement :
$\det(I_m - zM) = \frac{1}{\zeta_G(z)}$ Ce qui donne bien : $\boxed{ \zeta_G(z) = \frac{1}{\det(I_m - zM)} }$

Attention au domaine de validité de la formule. Elle repose sur le développement en série entière du logarithme, ce qui impose que toutes les quantités $z\lambda_i$ soient de module strictement inférieur à $1$ . C'est pourquoi la condition $|z| < 1/\rho(A)$ est cruciale.