How to prove $\sum_{i<j} \lambda_{i}\times\lambda_{j} = -m$ , where $\lambda$ is the eigenvalues

230 Views Asked by At

I'm trying to prove this, but I have no idea even how to start.

Let G a graph with n vertices , m edges and eigenvalues $\lambda_1,\lambda_2,...,\lambda_n \\ $ $\\$ Show that: $\sum_{1\leq i\leq j \leq n}^{n} \lambda_i \cdot \lambda_j = -m$ $\\$. This section is using adjacency matrix. I'm working with regular graphs.

1

There are 1 best solutions below

0
On

Let $v_i$ be the list of vertices and $A = (a_{ij})$ be the adjacency matrix for an $\color{red}{\text{undirected graph}}$. Since no vertex connects to itself, the diagonal entries of A are all zero. This implies $$\sum_i \lambda_i = \operatorname{tr} A = \sum_{i} a_{ii} = 0$$

Furthermore, we have: $$\sum_i \lambda_i^2 = \operatorname{tr} A^2 = \sum_{ij} a_{ij} a_{ji} = \sum_{ij} a_{ij}^2 = \Big|\Big\{ (i,j) : v_i \text{ connects to } v_j\Big\}\Big| = 2m$$

because each edge in an undirected graph contributes 2 in above sum. As a result,

$$\sum_{i < j}\lambda_i \lambda_j = \frac12 \sum_{i\ne j} \lambda_i \lambda_j = \frac12 \left( ( \sum_i \lambda_i )^2 - \sum_i \lambda_i^2 \right) = \frac12 ( 0 - 2m ) = -m.$$

If the graph is directed, without oddities like self loops and multiple arcs, then above formula still works with $m$ replaced by the number of pairs of vertices which are connected by edges in both direction.