Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.