REU 2005 · Potpourri · Lecture 4

Instructor: László Babai Scribe: N. Raghunathan

July 25, 2005. Last updated July 27, 2005

4 Eigenvalues of graphs

4.1 Powers of Adjacency matrix

Definition 4.1 (Adjacency Matrix). Let G = (V, E) be a graph; assume V = {1, 2, …, n}. The adjacency matrix A_{G} = (a_{ij})of G is the n × n (0, 1) matrix defined by:

a_{ij} = \{ \begin{matrix}1 & i ∼ j \\ 0 & i ≁ j \end{matrix}

The (i, j) entry of (A_{G})^{k} gives the number of walks of length k between vertex i and vertex j. The (i, i)th entry of (A_{G})^{k} corresponds to the number of closed walks of length k containing vertex i. Hence we get that

tr(A_{G}^{2}) = ∑_{i} deg_{i} = 2m = λ_{1}^{2} + λ_{2}^{2} + ⋯ + λ_{n}^{2}

where m is the number of edges of G. Similarly we get,

tr(A_{G}^{3}) = 6t = λ_{1}^{2} + λ_{2}^{2} + ⋯ + λ_{n}^{2}

where t is the number of triangles in G.

4.2 Proof of deg_{min} ≤ λ_{1} ≤ deg_{max}

For this section we use the following notation: G is a graph on {1, 2, …, n} and A is the adjacency matrix of G. The eigenvalues of A are λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}

Claim 4.2. (∀i)(λ_{i} ≤ deg_{max}).

Proof. Let \underline{0} ≠ \underline{x} ∈ ℝ^{n} be such that A\underline{x} = λ_{i}\underline{x}. Let j be an index such that |x_{j}| is the maximum.

λ_{i}|x_{j}| = |(A\underline{x})_{j}| = |∑_{k} a_{jk}x_{k}|
= |∑_{k:k∼j} x_{k}| ≤ ∑_{k:k∼j} |x_{k}|
≤ ∑_{k:k∼j} |x_{j}| ≤ deg_{max} |x_{j}|

The above proof actually proves a stronger statement. If G is a directed graph and A is the adjacency matrix of G, then the largest eigenvalue λ_{1} of A is at most the maximum outgedree of G.

Definition 4.3 (Quadratic Form). The quadratic form associated with a real symmetric matrix A is a function Q_{A}(\underline{x}) : ℝ^{n} → ℝ, defined by

Q_{A}(\underline{x}) = \underline{x}^{T} A\underline{x} = ∑_{i,j} a_{ij}x_{i}x_{j}

Definition 4.4. A set of vectors a_{1}, …, a_{n} is orthonormal if a_{i} · a_{j} = δ_{ij} where δ_{ij} = 1 if i = j and δ_{ij} = 0 otherwise.

Theorem 4.5 (Spectral Theorem). If A is a real symmetric matrix, then all the eigenvalues of A are real and A has an orthonormal eigenbasis.

If A is a real symmetric matrix, then A has an orthonormal eigenbasis \underline{e}_{1}, …, \underline{e}_{n}. Then a vector \underline{x} ∈ ℝ^{n} can be written as \underline{x} = ∑_{i=1}^{n} r_{i}\underline{e}_{i}. We can now write the quadratic form in a very compact manner.

Q_{A}(\underline{x}) = \underline{x} · A\underline{x}
= (∑_{i=1}^{n} r_{i}\underline{e}_{i}) · A (∑_{i=1}^{n} r_{i}\underline{e}_{i})

= (∑_{i=1}^{n} r_{i}\underline{e}_{i}) · (∑_{i=1}^{n} r_{i}λ_{i}\underline{e}_{i})

From the orthonormality of the \underline{e}_{i}s, we get that

Q_{A}(\underline{x}) = ∑_{i=1}^{n} λ_{i}r_{i}^{2}  (4.1)

Definition 4.6 (Rayleigh Quotient). If A is a real symmetric matrix, the Rayleigh quotient is the function R_{A}(x) : ℝ^{n} → R defined by

R_{A}(\underline{x}) = \frac{\underline{x}^{T} A\underline{x}}{\underline{x}^{T} \underline{x}}

Theorem 4.7 (Courant-Fischer Theorem, baby case). If A is a real symmetric matrix with the largest eigenvalue λ_{1} then,

λ_{1} = max_{x∈ℝ^{n}}R_{A}(\underline{x})

Proof. We prove this in two steps:

1. (∃\underline{x} ∈ ℝ^{n})(R_{A}(\underline{x}) = λ_{1}).

2. (∀\underline{x} ∈ ℝ^{n})(R_{A}(\underline{x}) ≤ λ_{1}).

Item 1 above is easy to see. Let \underline{x} be an eigenvector for λ_{1}. The Rayleigh quotient for \underline{x} is R_{A}(\underline{x}) = λ_{1}.

Now we prove item 2. Let \underline{x} = ∑_{i} r_{i}\underline{e}_{i} be a vector in ℝ^{n} where e_{i}s are the orthonormal eigenbasis for A guaranteed by the spectral theorem. Then by equation 4.1, we know that Q_{A}(\underline{x}) = ∑_{i} λ_{i}r_{i}^{2}. Since λ_{1} ≥ λ_{i}, we get that

Q_{A}(\underline{x}) = ∑_{i} λ_{i}r_{i}^{2}
≤ ∑_{i} λ_{1}r_{i}^{2}
= λ_{1} ∑_{i} r_{i}^{2}

Since \underline{x}^{T} \underline{x} = ∑_{i} r_{i}^{2}, the statement of the theorem follows.

Claim 4.8.

λ_{1} ≥ \frac{2m}{n}

where m is the number of edges in the graph G.

Proof. Due to Courant-Fischer theorem, for all vectors \underline{x} ∈ ℝ^{n}, λ_{1} ≥ R_{A}(\underline{x}). We choose a particular vector \underline{x} such that R_{A}(\underline{x}) ≥ \frac{2m}{n}.

Let \underline{1} be the all 1’s vector. It is easy to see that \underline{1}^{T} A\underline{1} = 2m where m is the number of edges in the graph. Since \underline{1}^{T} \underline{1} = n, we get that R_{A}(\underline{1}) = \frac{2m}{n}.

Since \frac{2m}{n} ≥ deg_{min}, it follows that λ_{1} ≥ deg_{min}.

Exercise 4.9. Prove that λ_{1} ≥ \sqrt{\frac{∑_{i}(deg_{i})^{2}}{n}}.

Study Question 4.10. When is λ_{1} = \frac{2m}{n}?

Study Question 4.11. When is λ_{1} = deg_{max}?

4.3 Interleaving theorem

Theorem 4.12 (Interleaving Theorem). If A is an n × n real symmetric matrix, denote by A^{(−i)}, the (n − 1) × (n − 1) symmetric matrix obtained by removing the i^{th} row and the i^{th} column of A. Let λ_{1} ≥ ⋯ ≥ λ_{n} be the eigenvalues of A and μ_{1} ≥ ⋯ ≥ μ_{n−1} be the eigenvalues of A^{(−i)}. Then,

λ_{1} ≥ μ_{1} ≥ λ_{2} ≥ μ_{2} ≥ ⋯ μ_{n−1} ≥ λ_{n}.

Proof of λ_{1} ≥ μ_{1}: Without loss of generality assume that we remove that last row and the last column. Let B = A^{(−n)}. Let \underline{y} ∈ ℝ^{n−1} be such that B\underline{y} = μ_{1}\underline{y}. Hence

μ_{1} = \underline{y}^{T} B\underline{y}.

Now consider a vector \underline{x} ∈ ℝ^{n} obtained by adding 0 as the nth coordinate to \underline{y}. That is

\underline{x} = ( \underline{y} ; 0 ) .

Notice that \underline{x}^{T} A\underline{x} = \underline{y}^{T} B\underline{y} and \underline{x}^{T} \underline{x} = \underline{y}^{T} \underline{y}. Hence by Courant-Fischer Theorem,

λ_{1} ≥ R_{A}(\underline{x}) = R_{B}(\underline{y}) = μ_{1}

To prove the other inequalities, we need the full power of Courant-Fischer theorem.

Theorem 4.13 (Courant-Fischer Theorem, general case). If A is a real symmetric matrix with eigenvalues λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} then,

λ_{i} = max_{dim(U)=k^{U≤ℝ^{n}}} min_{\underline{x}∈U} R_{A}(\underline{x})

Exercise 4.14. Prove the Courant-Fischer theorem (Theorem 4.13). (Hint: Use the spectral theorem)

Exercise 4.15. Use the Fischer-Courant Theorem (Theorem 4.13) to prove the interleaving theorem.

4.4 Isoperimetric Inequality

Definition 4.16 (Laplacian). We define the Laplacian of the graph to be

L_{G} = D_{G} − A_{G}

where A_{G} is the adjacency matrix and D_{G} is a diagonal matrix D_{G}(i, i) = deg_{G}(i). Let the eigenvalues of L_{G} be λ_{0} ≥ λ_{1} ≥ ⋯ ≥ λ_{n−1}.

Exercise 4.17. Prove that λ_{0} = 0. Exercise 4.18. Prove that λ_{1} > 0 ⟺ G is connected. Definition 4.19 (Iso-perimetric ratio). If A ⊆ G we denote by δ(A) the number of edges between A and A = V \ A. The isoperimetric ratio for A is \frac{δ(A)}{|A|}.

The next result shows the important fact that if λ_{1} is large then G is highly expanding”. Exercise 4.20. Prove that \frac{|δA|}{|A|} ≥ \frac{λ_{1}}{2}