# Sum of the eigenvalues of adjacency matrix

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?

-
For sake of full disclosure, please note that 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. – JavaMan Nov 21 '12 at 8:11

## 1 Answer

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.

-
You do not even need symmetry (allthough it yields the fact that all eigenvalues are real). For any quadratic matrix $A$ over a field $F$ it is true that the trace equals the sum of all eigenvalues (possibly in some (finite) extension of $F$). – Sebastian Schoennenbeck Nov 21 '12 at 8:44
@dinesh: Thank you for your response. I had a typo in my post above (it is way too late here). I meant to write $A_G = U^T DU$ rather than what I originally wrote, though your comment seems to settle the issue. – JavaMan Nov 21 '12 at 8:50
@SebastianSchoennenbeck Thanks for the point. I edited the answer, I wanted to bring in the circularity of trace here which is why I depended on symmetry so as to connect to eigen decomposition. Now I realize schur decomposition is enough to argue that. – dineshdileep Nov 21 '12 at 8:50
@JavaMan you have just have to mention its a unitary matrix. So that transpose and inverse are same. – dineshdileep Nov 21 '12 at 8:54
@dinish. Like I said, it's way too late here! – JavaMan Nov 21 '12 at 8:56