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.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
2  
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
add comment

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.