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,

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.

Advertisements