Eigenvalues of the Laplacian Matrix of the Complete Graph

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$ .

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

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

saad0105050 says:

September 29, 2015 at 9:20 am

Yes, fixed it. Thanks a lot.

Reply

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?

saad0105050 says:

July 27, 2016 at 8:06 pm

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

Reply

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\}$

Eigenvalues of the Laplacian Matrix of the Complete Graph

Published by saad0105050

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by saad0105050

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

Leave a Reply Cancel reply