I've been tasked with the following:
- Prove that a complete bipartite graph with n + m nodes has a spectrum $(\sqrt{mn} ,0,..,0,-\sqrt{mn})$
- Prove that a complete graph with n nodes has a spectrum $(n-1,-1,..,-1)$
I completely understand what those graphs are, but I didn't know where I should start. I would be glad for any help.
For the first problem let $A$ be the adjacency matrix of the graph. Notice $A^2$ is a block diagonal matrix, in which there is a block of $m$'s of size $n$ and a block of $n$'s of size $m$. it follows the spectrum of $A^2$ is $\{[nm]^2,[0]^{n+m-2}\}$.
Therefore the spectrum of $A$ is as desired (since the trace is $0$).
For the second problem let $A$ be the adjacency matrix of the graph. Notice $A+I$ is the constant $1$ matrix, which has spectrum $\{[n]^1,[0]^{n-1}\}$, it follows $A$ has spectrum $\{[n-1],[-1]^{n-1}\}$