Eigenvalues of the Laplacian Matrix of the Complete Graph

Computer Science, Expository, Graph Theory, Mathematics, Matrix Analysis, Spectral Graph Theory, Uncategorized 2 Minutes
611px-Complete_graph_K7.svg
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,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.

Published by saad0105050

Published

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

  2. 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?

    Reply

Leave a comment