Eigenvalues of the Laplacian Matrix of the Complete Graph

A complete graph (source: David Benbennick)

We will show that the eigenvalues of the $n\times n$ Laplacian matrix $L$ of the complete graph $K_n$ are $\{0,1\}$ where the eigenvalue $0$ has (algebraic) multiplicity $1$ and the eigenvalue $n$ has multiplicity $n-1$ .

Recall that the Laplacian matrix $L$ is a symmetric, positive semidefinite matrix. For the graph $K_4$ , its Laplacian matrix is as follows:

$\begin{bmatrix}3 & -1 &-1&-1\\-1 & 3 &-1&-1\\-1 & -1 &3&-1\\-1 & -1 &-1&3\\\end{bmatrix}$

The following proof is taken from the lecture notes of Prof. Jonathan Kelner in MIT opencourseware.

Proof that $0$ is an eigenvalue with multiplicity $1$

Since the sum of entries along a row/column of $L$ is $0$ , $\mathrm{rank}(L)\leq n$ and hence $0$ must be an eigenvalue of any Laplacian matrix. The corresponding eigenvector $x$ is any constant vector, that is, a vector whose all entries are equal. Thus we have

$x=k\cdot [1 1 1 \cdots 1 1 1]^T$ and $Lx=0$ .

It can be easily verified that the rank of $L$ is $n-1$ because we cannot obtain the zero vector by summing up less than $n$ row/column vectors. Using the Rank-Nullity theorem, this implies that the dimension of the nullspace of $L$ is $1$ , which means the vector $[1 1 1 \cdots 1 1 1]^T$ spans the null-space of $L$ and there cannot be any other vector $\tilde{x}$ which is not parallel to $x$ and $L\tilde{x}=0$ . Hence, $0$ can appear only once as the eigenvalue of $L$ .

Proof that $n$ is an eigenvalue with multiplicity $n-1$

Suppose $\lambda$ is a non-zero eigenvalue of the Laplacian matrix $L$ of the undirected unweighted complete graph with $n$ vertices, $K_n$ . Let $y$ be the associated eigenvector. Since $\lambda \neq 0$ , we have $Ly\neq 0$ and hence $y$ must be perpendicular to the constant vector, which means the dot product of

$[y_1 y_2 \cdots y_n]^T$ and $[1 1 1 ... 1 1]^T$

must be $0$ . This, in turn, implies that

$\sum_i{y_i}=0\ \ \ \ (1)$ .

That is, the sum of the entries of $y$ will be zero.

Now we want to find out the vector $z=Ly$ (which is equal to $\lambda y$ because $\lambda$ is a non-zero eigenvalue of $L$ ).

Consider the $i^\text{th}$ entry $z_i$ of $z$ , which is obtained by multiplying the $i^\text{th}$ row of $L$ with $y$ . Since the graph $K_n$ is unweighted, this row vector will have $(n-1)$ at the $i^\text{th}$ position and $-1$ at everywhere else. Therefore,