0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.