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 .

### Like this:

Like Loading...

*Related*

## 4 comments

Comments feed for this article

September 29, 2015 at 1:25 am

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

September 29, 2015 at 9:20 am

saad0105050Yes, fixed it. Thanks a lot.

July 27, 2016 at 6:18 pm

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

July 27, 2016 at 8:06 pm

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