In reading the well known book on Algebraic graph theory I came across a theorem that could be stated in the following way:
If $G$ is a graph of diameter $d$ then the adjacency matrix of $G$ has at least $d+1$ distinct eigenvalues.
The proof shows that if $A$ is the adjacency matrix of a graph $G$ that has diameter $d$, then $I,A,A^2, \ldots, A^d$ are linearly independent. And then the main theorem somehow follows from here.
I assume what is used is the fact that if $A$ is a symmetric matrix and $I,A,\ldots,A^d$ are linearly independent, then $A$ has at least $d+1$ distinct eigenvalues?
Am I right? If yes, how can one quickly prove this fact?
Best Answer
Yes, you are: If $A$ is a symmetric matrix then $A$ is diagonalizable (semi-simple). Hence, the minimal polynomial of $A$, $m_A(x)$ consists of linear factors of multiplicity $1$ each, i.e. $m_A(x)=(x-\lambda_1)\cdot...\cdot(x-\lambda_k)$, where $\lambda_1,...,\lambda_k$ are all the distinct eigenvalues of $A$.
Now, you know that $I,A,…,A^d$ are linearly independent, which implies that there is no polynomial of degree $\leq d$ annulling $A$ (applying any such polynomial to gives you a linear combination of $I,A,…,A^d$). Since $m_A(x)$ is annulling $A$, it follows that $d<\deg(m_A(x))=k$. Hence $k\geq d+1$.