Spectrum of a labelled complete graph $K_n$

225 Views Asked by At

Suppose, $K_n$ is a complete simple graph with each edge label $k$. Then its adjacency matrix $A(K_n)$ has all the entries zero along the diagonal, and each non-diagonal entries are $k$.

What are the eigenvalues or, the spectrum of $K_n$? Is there any known formula for this?

1

There are 1 best solutions below

2
On BEST ANSWER

If $A$ is your matrix, then $A+kI$ is the matrix where all entries are $k$'s, which has rank $1$. Therefore $-k$ is an eigenvalue of your matrix with multiplicity $n-1$.

(In general, $\lambda$ is an eigenvalue with multiplicity $m$ if the rank of $A - \lambda I$ is $n-m$.)

This gives us all but one of the eigenvalues. But we know that the trace of $A$ is $0$, so the eigenvalues have to add up to $0$. If $n-1$ of them are $-k$, then the remaining one should be $(n-1)k$.