The daily problem set

Ecco un esercizio per il corso Theoretical Computer Science.

Esercizio. Sia $G = (V,E)$ un grafo di diametro $d$. Provare che la matrice di adiacenza di $G$, $A_G$, ammette almeno $d+1$ autovalori distinti.

Svolgimento. Poniamo $A:=A_G$. Siano $x$ e $y$ vertici di $G$ tali che $\mathrm{dist}(x,y)=d$, e sia $x=v_0, v_1,\dots,v_d=y$ un path di lunghezza $d$ da $x$ a $y$. Allora, per ogni $i \in \{1,\dots,d\}$ esiste un cammino di lunghezza $i$ (ma non più breve) che collega $x=v_0$ a $v_i$. Pertanto $A^i$ ha entrata non nulla in corrispondenza di $(v_0,v_i)$, mentre la stessa entrata nella matrice $A^j$, $j\in \{0,\dots,i-1\}$. Da ciò segue che, per ogni $i \in \{1,\dots,d\}$, $\{I,A,\dots,A^i\}$ sono linearmente indipendenti, e, in particolare, $\{I,A,\dots,A^d\}$ sono linearmente indipendenti.
Inoltre, si noti che $A$ è simmetrica, quindi diagonalizzabile. Allora il polinomio minimo di $A$ si può scrivere nella forma $m_A=(x-\mu_1)\cdots(x-\mu_k)$, dove $\mu_1,\dots,\mu_k$ sono gli autovalori distinti di $A$. Avendo provato che $I,A,\dots,A^d$ sono linearmente indipendenti, non esiste alcun polinomio $\widetilde m$ di grado minore o uguale a $d$ tale che $\widetilde m(A)=0$. Poiché per definizione $m_A(A)=0$, si ha che $k=\deg(m_A)>d$, ovvero $k\geq d+1$. $\square$