The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan

Eigenvalues of the Laplacian Matrix of the Complete Graph

We will show that the eigenvalues of the Laplacian matrix of the complete graph are where the eigenvalue has (algebraic) multiplicity and the eigenvalue has multiplicity .

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

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

Proof that is an eigenvalue with multiplicity

Since the sum of entries along a row/column of is , and hence must be an eigenvalue of any Laplacian matrix. The corresponding eigenvector is any constant vector, that is, a vector whose all entries are equal. Thus we have

and .

It can be easily verified that the rank of is because we cannot obtain the zero vector by summing up less than row/column vectors. Using the Rank-Nullity theorem, this implies that the dimension of the nullspace of is , which means the vector spans the null-space of and there cannot be any other vector which is not parallel to and . Hence, can appear only once as the eigenvalue of .

Proof that is an eigenvalue with multiplicity

Suppose is a non-zero eigenvalue of the Laplacian matrix of the undirected unweighted complete graph with vertices, . Let be the associated eigenvector. Since , we have and hence must be perpendicular to the constant vector, which means the dot product of

and

must be . This, in turn, implies that

.

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

Now we want to find out the vector (which is equal to because is a non-zero eigenvalue of ).

Consider the entry of , which is obtained by multiplying the row of with . Since the graph is unweighted, this row vector will have at the position and at everywhere else. Therefore,

Further simplification shows that

.

According to Equation , the sum in the right hand side is . Hence, we see that

and therefore

.

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

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?

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

Yes, fixed it. Thanks a lot.

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?

Not from the top my head. Let me think about it.