I need some help with this proof:
Let G be a k-regular graph. prove that: a) If G is bipartite then -k is an eigenvalue of G's adjacency matrix. b) If -k is an eigenvalue of G's adjacency matrix then G is bipartite.
Got stuck in figuring out what the general form of such an adjacency matrix. Thanks!
On
For (a) you first prove that $k$ is an eigenvalue of $G$'s adjacency matrix $A$. This is simple and is already explained in Hidalgo's answer: $A-kI$ is not invertible.
Now I will show (a) in a different way from Hidalgo. This is taken from Bartlett's lecture notes: write $$\mathbf A=\begin{bmatrix}\mathbf0&\mathbf B\\\mathbf B^T&\mathbf0\end{bmatrix}\qquad\mathbf v=\begin{bmatrix}\mathbf a\\\mathbf b\end{bmatrix}\qquad \mathbf{Av}=k\mathbf v$$ where $\mathbf B$ has dimensions $m×n$, $\mathbf a$ has length $m$ and $\mathbf b$ has length $n$. It is then easy to check that $(\mathbf a,-\mathbf b)^T$ is an eigenvector of $A$ associated to $-k$.
To prove (b) without counting walks, assuming $G$ is connected (otherwise, as Hidalgo's example shows, this is false in general) normalise the eigenvector $\mathbf v$ associated to $-k$ such that some component (say it lies at index $i$; these indices also label $G$'s vertices) is $1$ and all other components have absolute value at most $1$. Then, looking at the $i$th component of $\mathbf{Av}=-k\mathbf v$: $$\sum_{j=1}^na_{ij}v_j=\sum_{j\text{ adjacent to }i}v_j=-kv_i$$ With the magnitude restrictions, $G$'s $k$-regularity and $v_i=1$, this means $v_j=-1$ for all neighbours $j$ of $i$. Negate $\mathbf v$ and repeat the argument for all the neighbours $j$; iterate until the whole graph is covered, by connectivity. This shows that all elements of $\mathbf v$ are $+1$ or $-1$ with signs differing if the corresponding vertices are adjacent in $G$.
Now assume $G$ is not bipartite, then it contains an odd cycle. However, the sign assignment above will run into a contradiction on this odd cycle. Hence $G$ is bipartite.
Combining the (b) argument with the proof in Bartlett's notes that $G$ having $\Delta(G)$ as an eigenvalue implies it is regular gives a proof that if a connected $G$ has $-\Delta(G)$ as an eigenvalue it is regular and bipartite.
First we prove that if $G$ is regular then $k$ is an eigenvalue:
The easiest way to prove $k$ is an eigenvalue is to notice that $A-kI$ is not invertible because each row has sum $0$, but I provide another proof:
Recall that the sum of the $\lambda_i^j$ gives the number of closed walks of length $j$.
We can easily show the number of closed walks of even length $j$ is at least $k^{j-D}$ where $D$ is the diameter of the graph.
Notice that if the largest eigenvalue is less than $k$ we will have too few closed path of even length $j$ for large values of $j$.
An analogous proof can be used to prove no eigenvalue can be larger than $\Delta$ in any graph.
Now we assume $G$ is bipartite then $-k$ is an eigenvalue.
One way is to assume it is not and notice that the sum of $\lambda_i^j$ will be positive for large odd $j$.
Another way is to look at the adjacency matrix, notice it is of form $\begin{pmatrix} 0A \\\ A^T0 \end{pmatrix}$
It is thus clear that if we write the characteristic polynomial and use the formula for the determinant as a sum of permutations, that each non-zero summand will need to have an even number of $x$ factors, so the characteristic polynomial can be expressed with the variable $x^2$, which means it can be factored in the way $(x^2-a_i)$, which tells us the spectrum is symmetric.
Now we must prove that if $-k$ is an eigenvalue the $G$ is bipartite.
Notice that this is not true in general, but it is if we ask for connectivity ( for a counterexample consider a graph with $K_4$ and $K_{3,3}$ as the only components)
Assume that it is not bipartite, we can prove that the number of closed walks of odd length $j+1$ is at least $d^{j-2D-l}$ where $l$ is the length of some odd cycle.
However for odd values the sum of $\lambda_i^j$ cancels out $k$ and $-k$, so we only have values of $\lambda_i$ with norm smaller than $k$. This means the sum is too small for large values of $j$.
For this part we need for $k$ to have multiplicity $1$, this can be verified by noticing $A^{2m+1}$ has only positive entries for large $m$, and using Perron-Frobenius on it.