Prove that the spectrum of $K_n$ is $((n-1)^1, (-1)^{(n-1)})$

Question

I am trying to prove that the spectrum of the complete graph $K_n$ is $((n-1)^1, (-1)^{(n-1)})$ (where superscripts denote multiplicities of eigenvalues, not exponents). I have part of the proof but having trouble completing it.

The adjacency matrix $A(K_n)$ is the $n \times n$ matrix:

$$ A(K_n) =\begin{pmatrix} 0 & 1 & 1 & \ldots & 1 & 1 \\ 1 & 0 & 1 & \ldots& 1 & 1 \\ 1 & 1 & \ddots & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & \ddots & 1 & 1 \\ 1 & 1& \ldots & 1 & 0 & 1 \\ 1 & 1 & \ldots & 1 & 1 & 0 \\ \end{pmatrix} $$

The eigenvalues of A ($\lambda_1, \lambda_2, \ldots \lambda_n$) can be found by solving:

$$det(\lambda I - A) = 0$$

$$\begin{vmatrix} \lambda & -1 & -1 & \ldots & -1 & -1 \\ -1 & \lambda & -1 & \ldots & -1 &- 1 \\ -1 & -1 & \ddots & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & \ddots & -1 & -1 \\ -1 & -1& \ldots & -1 & \lambda & -1 \\ -1 & -1 & \ldots & -1 & -1 & \lambda \\ \end{vmatrix} = 0 $$

I understand that one way to show $det(\lambda I - A) = 0$ for a given $\lambda$ is to show that the matrix $(\lambda I - A)$ is linearly dependent ie. one row is a linear combination of the others. From this it follows that $\lambda$ is an eigenvalue.

For $\lambda = (n-1)$ we have the matrix

$$\begin{pmatrix} (n-1) & -1 & -1 & \ldots & -1 & -1 \\ -1 & (n-1) & -1 & \ldots & -1 &- 1 \\ -1 & -1 & \ddots & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & \ddots & -1 & -1 \\ -1 & -1& \ldots & -1 & (n-1) & -1 \\ -1 & -1 & \ldots & -1 & -1 & (n-1) \\ \end{pmatrix} $$

It can be readily seen that any particular row is a linear combination of all of the other rows, specifically that $Row_i = \sum_{j \neq i} (-1)Row_j$, hence $\lambda = (n-1)$ is an eigenvalue.

Also for $\lambda = (-1)$ we have the matrix:

$$\begin{pmatrix} -1 & -1 & -1 & \ldots & -1 & -1 \\ -1 & -1 & -1 & \ldots & -1 &- 1 \\ -1 & -1 & \ddots & \ldots & \ldots & \vdots \\ \vdots & \ldots & \ldots & \ddots & -1 & -1 \\ -1 & -1& \ldots & -1 & -1 & -1 \\ -1 & -1 & \ldots & -1 & -1 & -1 \\ \end{pmatrix} $$

Clearly every row is identical hence each of the rows is a linear combination of any of the other rows, so the matrix is linearly dependent and $\lambda = (-1)$ is an eigenvalue also.

However I do not know how to show their multiplicities. (Can we appeal to the fact that the eigenvalue $(n-1)$ reduces the rank by 1 hence has multiplicity 1, while the eigenvalue $(-1)$ reduces the rank by $(n-1)$, hence has multiplicity $(n-1)$?)

Also I feel there may be a much simpler proof?

Answer 1

Hint: Try to use induction with the Laplace expansion of the determinant to get the characteristic polynomial of $A(K_n)$.

Answer 2

Hint: The $n - 1$ vectors $$ \left\{ \begin{bmatrix} 1 \\ -1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ -1 \\ \vdots \\ 0 \end{bmatrix}, \ldots, \begin{bmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ -1 \end{bmatrix} \right\} $$ are all in the kernel of $\lambda I - A$ for $\lambda = -1$. Why are these vectors linearly independent? What does that say about the multiplicity of $-1$ as an eigenvalue?

Answer 3

Let the adjacency matrix of $K_n$ be A, then as you wrote the matrix contains 1 in every row and column except for the diagonal.

Let J be a matrix containing one's in every row and column, then we can say that A=J-I (I here is the identity matrix).

It is known that for symmetric matrixes, from spectral theory you can write any $B=B^T$ as $B=VDV^{-1}$ where D - is diagonal and contains the eigenvalues of B and V is the orthogonal matrix. So $J=VDV^{-1}$ and also notice that $I=VIV^{-1}$.

It follows that $ A=J-I = VDV^{-1}-VIV^{-1}=V(D-I)V^{-1}$

Now it is left to estimate the eigenvalues of J, we can easily see that a vector of 1's multiplied by the matrix is an eigenvector and the corresponding eigenvalue would be n, notice that the other eigenvalues would be zeros since $Nulity(J)=n-1$.

So eigenvalues of A are: $\lambda_1=n-1, \lambda_2=...=\lambda_n=-1$