You are currently browsing the tag archive for the ‘eigenvalues’ tag.

*In which we analyze a nearly-linear time algorithm for finding an approximate eigenvector for the second eigenvalue of a graph adjacency matrix, to be used in the spectral partitioning algorithm.*

In past lectures, we showed that, if is a -regular graph, and is its normalized adjacency matrix with eigenvalues , given an eigenvector of , the algorithm SpectralPartition finds, in nearly-linear time , a cut such that .

More generally, if, instead of being given an eigenvector such that , we are given a vector such that , then the algorithm finds a cut such that . In this lecture we describe and analyze an algorithm that computes such a vector using arithmetic operations.

A symmetric matrix is *positive semi-definite* (abbreviated PSD) if all its eigenvalues are nonnegative. We begin by describing an algorithm that approximates the largest eigenvalue of a given symmetric PSD matrix. This might not seem to help very much because the adjacency matrix of a graph is not PSD, and because we want to compute the second largest, not the largest, eigenvalue. We will see, however, that the algorithm is easily modified to approximate the second eigenvalue of a PSD matrix (if an eigenvector of the first eigenvalue is known), and that the adjacency matrix of a graph can easily be modified to be PSD.

*In which we talk about the spectrum of Cayley graphs of abelian groups, we compute the eigenvalues and eigenvectors of the cycle and of the hypercube, and we verify the tightness of the Cheeger inequalities and of the analysis of spectral partitioning*

In this lecture we will prove the following results:

- The dimension- hypercube has and , giving an infinite family of graphs for which , showing that the first Cheeger inequality is exactly tight.
- The -cycle has , and , giving an infinite family of graphs for which , showing that the second Cheeger inequality is tight up to a constant.
- There is an eigenvector of the second eigenvalue of the hypercube , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut of expansion , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.

*In which we review linear algebra and introduce spectral graph theory.*

**1. Eigenvalues and Eigenvectors **

*Spectral graph theory* studies how the eigenvalues of the adjacency matrix of a graph, which are purely algebraic quantities, relate to combinatorial properties of the graph.

We begin with a brief review of linear algebra.

If is a complex number, then we let denote its *conjugate*.

If is a square matrix, is a scalar, is a non-zero vector and we have

then we say that is an *eigenvalue* of and that is *eigenvector* of corresponding to the eigenvalue .

When (1) is satisfied, then we equivalently have

for a non-zero vector , which is equivalent to

For a fixed matrix , the function is a univariate polynomial of degree in and so, over the complex numbers, the equation (2) has exactly solutions, counting multiplicities.

If is a graph, then we will be interested in the adjacency matrix of , that is the matrix such that if and otherwise. If is a multigraph or a weighted graph, then is equal to the number of edges between , or the weight of the edge , respectively.

The adjacency matrix of an undirected graph is symmetric, and this implies that its eigenvalues are all real.

Definition 1A matrix is Hermitian if for every .

Note that a real symmetric matrix is always Hermitian.

Lemma 2If is Hermitian, then all the eigenvalues of are real.

*Proof:* Let be an Hermitian matrix and let be a scalar and be a non-zero vector such that . We will show that , which implies that is a real number. We define the following *inner product* operation over vectors in :

Notice that, by definition, we have and . The lemma follows by observing that

where we use the fact that is Hermitian, and that

and

so that .

From the discussion so far, we have that if is the adjacency matrix of an undirected graph then it has real eigenvalues, counting multiplicities of the number of solutions to .

If is a -regular graph, then instead of working with the adjacency matrix of it is somewhat more convenient to work with the normalized matrix .

In the rest of this section we shall prove the following relations between the eigenvalues of and certain purely combinatorial properties of .

Theorem 3Let be a -regular undirected graph, and be its normalized adjacency matrix. Let be the real eigenvalues of with multiplicities. Then

- and .
- if and only if is disconnected.
- if and only if at least one of the connected components of is bipartite.

In the next lecture we will begin to explore an “approximate” version of the second claim, and to show that is close to 1 if and only if has a sparse cut.

## Recent Comments