Question
Consider an undirected, unweighed, graph $G$ with no self loops with at least one edge. Let the eigenvalues of the adjacency matrix $A(G)$ be denoted by $\lambda_i$, I would like to show that $min(\lambda_i) \le -1$ and $max(\lambda_i) \ge 1$.
Attempted Solution
Let $D = A(G)_n - x \; Id_n$, then we have $Det(D)=\epsilon^{i_1 \; \cdots \; i_n} D_{1 \; i_1} \; \cdots D_{n \; i_n} = 0$
- Given there are no self loops the resulting polynomial will have a $(-x)^n$ term.
- The Levi Civita symbol ensures there can be no $(-x)^{n-1}$ term
- Similarly the $(-x)^{n-1}$ term must have opposite sign since they come from one swap of two indices.
- Since it is unweighed the coefficients must be integers, although $(-x)^n$ always has a coefficient of 1
Basicly I am trying to construct enough information about the polynomial to ensure it zeros at above $1$ and below $-1$, however the above information does not do this. Eg as a counter example of a polynomial meeting the about conditions without having the required roots is $x^4 - x^2 + x = 0$.
Am I on the right track to prove this?
You can use the Cachy interlacing theorem:
Given a simmetric matrix $A$, let $B$ be a simmetric minor of $A$, of dimension $n-k$. If $a_i$ are the eigenvalues of $A$, and $b_i$ those of $B$, both ordered in a decreasing way, then
$$ a_i\ge b_i\ge a_{i+k} \;\; \forall i\le n-k $$
Since there's an edge, a simmetric minor of your adjacency matrix is
$$\begin{pmatrix} 0 & 1\\1 & 0 \end{pmatrix} $$
that has $1,-1$ as eigenvalues, so $\;a_1\ge 1\;$ and $\;a_n\le -1$