Are all adjacency matrices (graph theory) diagonalizables?

Question

If $A$ is an adjacency matrix of a graph $G$ and it can be diagonalized to get it in the form $A=PDP^{-1}$, with $D$ diagonal, is there any graph-theoretic interpretation to the matrices $P$ and $D$?

Answer 1

The eigenvalues tell us quite a bit about the graph structure. For example, we have that: $2E = \sum_{i=1}^{n} \lambda_{i}^{2}$ and $6C_{3} = \sum_{i=1}^{n} \lambda_{i}^{3}$.

We have as well that $G$ is bipartite if and only if $\lambda_{i} = \lambda_{n-i+1}$ for all $i$. In addition, $\overline{d(G)} \leq \lambda_{1} \leq \Delta(G)$, with equality when $G$ is regular. That is, $\lambda_{1}$ lies between the average and largest vertex degrees of $G$.

The dominant eigenvector ranks the vertices in terms of centrality.

There are many more spectral results associated with graphs. Cvetkovic, Rowlinson, and Cimic is a good text to use, but it is a tough read (comparable to Rudin). http://www.amazon.com/Introduction-Spectra-Mathematical-Society-Student/dp/0521134080