Eigenvalues of complete graph and its line graph

Question

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)$?

Answer 1

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$.

Answer 2

Let me elaborate on @PeterMcCoy's answer. $A(K_n)=B(K_n)B(K_n)^T -(n-1)Id$, so it suffices to find the eigenvalues of $B(K_n)B(K_n)^T$; but these are the same (possibly up to 0) of $B(K_n)^TB(K_n)=:Q(K_n)$ (a general phenomenon for matrices of the form $MM^T$ vs $M^TM$). As already observed, the eigenvalues of $A(K_n)$ and $Q(K_n)$ agree, up to a shift by $n-1$: i.e., an eigenvalue $\lambda$ of $A(K_n)$ is transformed into an eigenvalue $n-1+\lambda$ of $Q(K_n)$. Since you already know the eigenvalues of $A(K_n)$, you are done. ($Q$ is sometimes called the "signless Laplacian" of a graph.)

(More precisely: you still have to check whether $0$ is an eigenvalue of $B^T B$, i.e., whethere there are non-trivial elements of the null space of $B$; by general properties of the incidence matrix (cf. Theorem 8.2.1 in Godsil-Royle) this is certainly the case if the graph has more edges than nodes, like for $K_n$ for any $n>3$; so $-2$ is an eigenvalue for any $n>3$. The same theorem shows that the null space of $K_3$ is trivial, so $-2$ is not an eigenvalue of $A(K_3)$.)