1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Actually, it is not true without further assumptions. If the graph has no edges, the only eigenvalue will be 0. However, except for that case --

Hint: As you have noticed, the matrix can be diagonalized. What is the trace of a diagonal matrix? What is the trace of the adjacency matrix?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – wf34 Apr 5 '14 at 11:10
  • $\begingroup$ @wf34: And what do you know about traces of matrices under change of basis? $\endgroup$ – Henning Makholm Apr 5 '14 at 11:12
  • $\begingroup$ Trace is equal to the sum of eigenvalues and invariant with respect to a change of basis. $\endgroup$ – wf34 Apr 5 '14 at 11:16
  • $\begingroup$ 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$ $\endgroup$ – wf34 Apr 5 '14 at 11:23
  • $\begingroup$ @wf34: So now you know that the sum of the eigenvalues is 0. If all the eigenvalues are 0, then the diagonalized matrix is the zero matrix, and therefore the adjacency matrix is zero too, and the graph has no edges. Otherwise at least one eigenvalue is nonzero, and since their sum is 0 ... $\endgroup$ – Henning Makholm Apr 5 '14 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.