Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
Can you kindly explain why $\{ A^k\}_{k=0}^{k=diameter}$ is linearly independent? – user6818 Mar 10 '15 at 19:57

Your Answer


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.