# Prove that adjacency matrix has negative eigenvalue

We are given non-oriented graph without loops. Task is to prove that adjacency matrix of that graph has negative eigenvalue.

I put some effort into drawing a proof here , but it seems that I'm missing some links between statements. So any pointers would be appreciated.
According to eigenvalue definition, $det(A - \lambda \cdot I) = 0$ should hold.
Taking in account given description of graph, matrix would be somewhat like:
$A =\left( \begin{array}_ 0 & a_{1,2} & ... & a_{1,n} \\ a_{2,1} & 0 & ... & a_{2,n} \\ ... & ... &... & ... \\ a_{n,1} & a_{n,2} & ... & 0 \\ \end{array} \right)$
where $a_{i,j} > 0$.
Also it might be important that since it's an adjacency matrix, it's symmetric, hence diagonalizable.

• Yep, I agree with your counterexample and I have rechecked my task, there isn't no mention about that. Probably they imply that graph have some edges. mmm. $A_{diagonalized} = \left( \begin{array}_ d_1 & 0 & ... & 0 \\ 0 & d_2 & ... & 0 \\ ... & ... &... & ... \\ 0 & 0 & ... & d_n \\ \end{array} \right)$ $tr(A_{diagonalized}) = \sum_{i=1}^n d_i$ $tr(A) = 0$ Then, obviously, $tr(A)$ and $tr(A_{diagonalized})$ supposed to be equal. – wf34 Apr 5 '14 at 11:10
• It was information easy to find, but I'm not sure that I see where it supposed to lead me. But I got some ideas, are they of any usefulness?: $det(A - \lambda \cdot I) = 0$ $\prod_{i=1}^n (d_i-\lambda)= 0$ $\sum_{i=1}^n d_i = 0$ – wf34 Apr 5 '14 at 11:23