In which we introduce the Laplacian matrix and we prove our first results in spectral graph theory.
1. The Basics of Spectral Graph Theory
Given an undirected graph , the approach of spectral graph theory is to associate a symmetric real-valued matrix to , and to related the eigenvalues of the matrix to combinatorial properties of .
For the sake of this lecture, we will restrict ourselves to the case in which is a -regular graph, and we will then see how to extend our results to apply to irregular graphs as well.
The most natural matrix to associate to is the adjacency matrix such that if and otherwise. In the second part of the course, in which we will study expander graphs, the adjacency matrix will indeed be the most convenient matrix to work with. For the sake of the algorithms that we will analyze in the first part of the course, however, a slight variation called the normalized Laplacian is more convenient.
There are a few ways to motivate the definition of the Laplacian. One way is the following: the variational characterization of the eigenvalues of real symmetric matrices tells us that we can think of the eigenvalues of as optima of min-max optimization problems in which vectors are feasible solutions and the cost function is the Rayleigh quotient
We know that every homogeneous polynomial of degree 2 can be realized as for some matrix , and,if we want to study cuts in a graph , it makes sense to choose a matrix such that
because, if is a Boolean vector, representing a cut in the graph, then the right-hand-side expression above is counting the number of edges that cross the cut, and so optimization problems with the above cost functions will be relaxations of cut problems.
Some calculations show that the matrix having such a property is , which is called the Laplacian matrix of . Indeed, we can verify that
because both expressions are easily seen to be equal to
As we will see in a moment, the eigenvalues of are in the range , and it is not hard to see that their sum is , so it is convenient to divide the Laplacian matrix by so that the range and the average values of the eigenvalues of the resulting matrix are independent of the degree. (This degree independence will make it possible to generalize results to the irregular case.)
We have thus reached the following definition.
Definition 1 (Normalized Laplacian) The normalized Laplacian matrix of an undirected -regular graph is .
We shall now prove the following relations between the eigenvalues of and certain purely combinatorial properties of .
Theorem 2 Let be a -regular undirected graph, let be the adjacency matrix of , and be the normalized Laplacian matrix of . Let be the real eigenvalues of with multiplicities, in nondecreasing order. Then
- and .
- if and only if has at least connected components.
- if and only if at least one of the connected components of is bipartite.
Note that the first two properties imply that the multiplicity of 0 as an eigenvalue is precisely the number of connected components of .
Proof: By the characterization of the Rayleigh quotient of that we established above, and from the variational characterization of eigenvalues, we have
and so because the Rayleigh quotient, being a ratio of sums of squares, is always non-negative.
If we take to be the all-one vector, we see that its Rayleigh quotient is , and so is the smallest eigenvalue of , with being one of the vectors in the eigenspace of 1.
We also have the following formula for :
So, if , there must exist a -dimensional space such that for every and every , we have , and so for every which are in the same connected component. This means that each must be constant within each connected component of , and so the dimension of can be at most the number of connected components of , meaning that has at least connected components.
Conversely, if has at least connected components, we can let be the space of vectors that are constant within each component, and is a space of dimension at least such that for every element of we have
meaning that is a witness of the fact that .
Finally, to study , we first note that we have the formula
from the variational characterization of eigenvalues (see Handout 0).
We also observe that for every vector we have
from which it follows that
and if then there must be a non-zero vector such that
which means that for every edge .
Let us now define and . The set is non-empty (otherwise we would have ) and is either the entire graph, or else it is disconnected from the rest of the graph, because otherwise an edge with an endpoint in and an endpoint in would give a positive contribution to ; furthermore, every edge incident on a vertex on must have the other endpoint in , and vice versa. Thus, is a connected component, or a collection of connected components, of which is bipartite, with the bipartition .