# Eigenvalues of a Complete graph

Using the following command in MATLAB, I am finding out that the eigenvalues of a complete graph are $-1$ with the multiplicity $n-1$ and $n-1$ with multiplicity of $1$. However I believe that the eigenvalues of $K_n$ should be zero with multiplicity $1$ and $n$ with multiplicity $n-1$. To make matters worse I have just noted that the determinant of the adjacency matrix of a complete graph with n vectors is $(-1)^{n-1}(n-1)$ which also mean my belief is also not correct.

n = 6;
i = 1;
while (i <= n)
i = i + 1;
M = ones(i) - eye(i);
[v, d] = eig(M)
end


How can I determine the spectrum of a complete graph analytically?

• Related and gives the answer math.stackexchange.com/questions/957126/… Sep 5, 2015 at 13:21
• @BertrandR, the user [ math.stackexchange.com/questions/957126/… has asked how one can show that $K_n$ is uniquely determined by its spectrum. But I want a method of finding that spectrum using a proof. Please, help in that area. Sep 5, 2015 at 13:31
• I will make such corrections @MorganRodgers. Sep 5, 2015 at 17:01
• Thanks for the hints @Rogers, would you post the hints or the answer in the answer box, that would be considered a great favour Sep 5, 2015 at 17:07

The eigenvalues should be $n-1$, with multiplicity $1$, and $-1$, with multiplicity $n-1$. The best way to see this in this particular case is through explicitly giving the eigenvectors.

First, the graph $K_{n}$ is $(n-1)$-regular; a $k$-regular graph always has $k$ as an eigenvalue with eigenvector $j$ (the all-ones vector). All other eigenvectors will have to be orthogonal to $j$.

To find the other eigenvectors, consider the adjacency matrix $A$ of $K_{n}$; it is all $1$s, except with $0$ on the diagonal. If we consider $A+I$, we get the all-ones matrix, which has rank $1$ (and so its null space has dimension $n-1$, giving $n-1$ linearly independent eigenvectors for the eigenvalue $-1$). These vectors all take the form $e_{i}-e_{j}$ for $i \neq j$ (where $e_{i}$ represents the vector with a $1$ in position $i$ and a $0$ everywhere else). We can find $n-1$ linearly independent vectors of this type, it is easiest to just consider $e_{1} - e_{j}$ for $0 < j \leq n$.

• Thanks @MorganRodgers, I find this solution to be useful. Sep 6, 2015 at 9:04

It's worth adding that the eigenvalues of the Laplacian matrix of a complete graph are $$0$$ with multiplicity $$1$$ and $$n$$ with multiplicity $$n-1$$.

Recall that the Laplacian matrix for graph $$G$$ is

$$L_G = D - A$$

where $$D$$ is the diagonal degree matrix of the graph. For $$K_n$$, this has $$n-1$$ on the diagonal, and $$-1$$ everywhere else. The constant vector $$\mathbf{1}$$ is then an eigenvector with eigenvalue $$0$$. The vectors $$v^i$$ with $$v^i_0 = -1$$ and $$v^i_i = 1$$ for $$i \in [2,n]$$ give the remaining eigenvectors with eigenvalue $$n$$.