3
$\begingroup$

Let $G$ be a simple undirected graph with $n$ vertices, and let $A_G$ be the corresponding adjacency matrix. Let $\kappa_1, \dots , \kappa_n$ be the eigenvalues of the adjacency matrix $A_G$. I have read that $ \kappa_1 + \dots + \kappa_n = 0, $ and I have checked this by hand for $n \leq 3$ along with a few "random" graphs. It is true in all the cases I have checked.

It seems that we want to write $A_G = U^{T} D U$, where $D$ is a diagonal matrix with trace $\text{tr}(D) = 0$, but I have been unable to supply a proof. How would one prove this?

  • 0
    For sake of full disclosure, please note t$h$at the link I have provided give this as an exercise, but I am not associated with the authors of the paper in any way, and this is not homework.2012-11-21

1 Answers 1

3

If there are no self loops, diagonal entries of a adjacency matrix are all zeros which implies $trace(A_G)=0$. Also, it is a symmetric matrix. Now use the connection between the trace of a symmetric matrix and sum of the eigenvalues (they are equal). To prove this, since $A_G$ is symmetric, $A_G=U^{-1}DU$ for some unitary matrix $U$. Now, note that trace has circularity property, i.e. $trace(ABC)=trace(BCA)$. So \begin{align} 0=trace(A_G)=trace(U^{-1}DU)=trace(DUU^{-1})=trace(D) \end{align} and $trace(D)$ is the sum of eigen values.

  • 0
    @JavaMan you have just have to mention its a unitary matrix. So that transpose and inverse are same.2012-11-21