# Eigenvalues of the Laplacian Matrix of the Complete Graph

We will show that the eigenvalues of the $n\times n$ Laplacian matrix $L$ of the complete graph $K_n$ are $\{0,n\}$ 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, $z_i=(n-1)y_i -\sum_{j\neq i}{y_j}.\ \ \ \ (2)$

Further simplification shows that $z_i=n\cdot y_i -(y_i+\sum_{j\neq i}{y_j})=n\cdot y_i -\sum_j{y_j}$.

According to Equation $(1)$, the sum in the right hand side is $0$. Hence, we see that $z_i=n\cdot y_i$

and therefore $Ly=z=n\cdot y$.

Thus we showed that every non-zero eigenvalue of $L$ must be $n$.

## 5 thoughts on “Eigenvalues of the Laplacian Matrix of the Complete Graph”

1. Santiago says:

Hello! The elements in the diagonal should be 3, not 4 🙂

1. saad0105050 says:

Yes, fixed it. Thanks a lot.

2. Sathya says:

Hi, nice post! Is there any interpretation for the number of unique eigenvalues of the graph laplacian? or at least the maximum over the multiplicities?

1. saad0105050 says:

3. Susovan PAL says:
Typo: We will show that the eigenvalues of the $n\times n$ Laplacian matrix $L$ of the complete graph $K_n$ are $\{0,1\}$, should be $\{0,n\}$