Given a graph $\Gamma$, the eigenvalues of $\Gamma$ are the eigenvalues of its adjacency matrix $A(\Gamma)$.
A complete graph $K_n$ has the adjacency matrix $A(K_n) = J – I$ with $J = jj^T$ and $j$ the "all ones vector". So $K_n$ has the eigenvalues $n-1$ and $-1$ with multiplicity $n-1$.
Now I want to determine the eigenvalues of its line graph $L(K_n) =: L$. I know that $B(K_n)^TB(K_n) = 2I_{|E|}+A(L)$ with $|E| = \binom{n}{2}$ and $B(K_n)$ the incidence matrix of $K_n$.
Let $V = \{v_1,\dots,v_n\}$ and $E = \{e_1,\dots,e_{|E|}\}$ be the set of vertices and edges of $K_n$.
I know that $B(K_n) = (b_{ij}) = \begin{cases} 1, \text{ if $v_i \in e_j$} \\ 0, \text{ else } \end{cases}$.
How do I determine the spectrum of $A(L)$?
Best Answer
If someone is interested in the answer, I've made some progress after consulting Chris Godsil's book "Algebraic graph theory". So the upper equation is correct but there also exists a similar one for the adjacency matrix:
$$B(K_n)B(K_n)^T = \Delta(K_n) + A(K_n)$$ with $\Delta(K_n) = (n-1)I_n$ the "degree matrix".
Since $\Delta(K_n)$ and $A(K_n)$ commute (one matrix is a multiple of the identity), the eigenvalues of $B(K_n)B(K_n)^T$ are the sum of the eigenvalues of the both matrices and the multiplicities of the eigenvalues are determined by the multiplicities of the eigenvalues of $A(K_n)$. That means the spectrum of the matrix is $\sigma(B(K_n)B(K_n)^T) = \{n-2,2n-2\}$.
Since both $B(K_n)B(K_n)^T$ and $B(K_n)^TB(K_n)$ are defined, $\det(I_n - B(K_n)B(K_n)^T) = \det(I_{|E|} - B(K_n)^TB(K_n))$.
Therefore both characteristic polynomials $f$ of $B(K_n)B(K_n)^T$ and $g$ of $B(K_n)^TB(K_n)$ only differ by a multiplied power of $x$. More specific for all $n \geq 3: g = x^{|E|-n}\cdot f$. Using this observation and the upper equation $B(K_n)^TB(K_n) = 2I_{|E|} + A(L)$ the conclusion is that the spectrum of the line graph is: $\sigma(A(L)) = \{-2,n-4,2n-4\}$ for $n \geq 4$ and $\{n-4,2n-4\}$ for $n = 3$.