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