Exercises: Computing with Graph Laplacians
Recommended exercises for Lectures 2–3
Conventions (as in the Lecture 2 notes). \(G = (V, E, w)\) is an undirected graph with positive edge weights, \(n = |V|\), no self-loops, and no isolated vertices unless stated otherwise. “Unweighted” means \(w \equiv 1\). We use \[ L = D - A, \qquad L_{rw} = D^{-1}L = I - P, \qquad \mathcal L = D^{-1/2} L D^{-1/2}, \] with eigenvalues listed in increasing order, \(\lambda_1 \le \lambda_2 \le \dots \le \lambda_n\). Recall that \(L_{rw}\) and \(\mathcal L\) have the same spectrum, and that \[ f^\top L f = \sum_{\{i,j\} \in E} w_{ij}(f_i - f_j)^2 . \] Exercises 1–3 are the core. Exercises 4–7 are hand computations and Courant–Fischer practice. Exercises 8–9 practice §3–§6 of the Lecture 2 notes (covered in Lecture 3).
Exercise 1. The kernel counts connected components
Let \(G\) have \(c\) connected components \(V_1, \dots, V_c\).
- (a) Prove that \(\ker L = \operatorname{span}\{\mathbf 1_{V_1}, \dots, \mathbf 1_{V_c}\}\). Conclude that the eigenvalue \(0\) of \(L\) has multiplicity exactly \(c\).
- (b) Prove the same for \(L_{rw}\) and \(\mathcal L\). What is \(\ker \mathcal L\)? Be careful about what “multiplicity” means for the non-symmetric matrix \(L_{rw}\).
- (c) Conclude that \(\lambda_2 > 0\) if and only if \(G\) is connected, for all three matrices.
Hint. \(Lf = 0\) implies \(f^\top L f = 0\).
Exercise 2. The top of the spectrum and bipartiteness
- (a) Prove that \(\lambda_n(\mathcal L) \le 2\), with equality if and only if some connected component of \(G\) is bipartite.
- (b) Prove that \(\lambda_n(L) \le 2 d_{\max}\), with equality if and only if some connected component of \(G\) is bipartite and all of its vertices have degree \(d_{\max}\).
Hint 1. Work with \(L_{rw}\) and its Rayleigh quotient in \(L^2(d)\): \(\lambda_n(L_{rw}) = \max_{f \ne 0} \frac{f^\top L f}{f^\top D f}\).
Hint 2. The signless Laplacian \(D + A\) satisfies \(f^\top (D + A) f = \sum_{\{i,j\}\in E} w_{ij}(f_i + f_j)^2\). What does \(f^\top(D+A)f = 0\) say about \(f\) on each component?
Exercise 3. Bipartite spectra are symmetric, and conversely
- (a) Let \(G\) be bipartite. Prove that the spectrum of \(\mathcal L\) is symmetric about \(1\), with multiplicities: \(\lambda\) and \(2 - \lambda\) are eigenvalues with the same multiplicity. Describe how the eigenvectors correspond.
- (b) Prove the converse: if the spectrum of \(\mathcal L\) is symmetric about \(1\), then \(G\) is bipartite. Do not assume \(G\) is connected.
- (c) Show by example that the spectrum of the unnormalized \(L\) of a bipartite graph need not be symmetric about any point.
Hint for (a). Let \(S\) be the diagonal matrix with \(S_{ii} = +1\) on one side and \(-1\) on the other. Compute \(SAS\) and \(SDS\).
Hint for (b). Translate the condition into a statement about the eigenvalues of \(P = I - L_{rw}\). Then look at \(\operatorname{tr} P^k\) for odd \(k\), and interpret \((P^k)_{ii}\) in terms of walks.
Exercise 4. Spectra by hand
All graphs here are unweighted. For each graph below, compute the full spectrum of \(L\) and of \(\mathcal L\), with multiplicities, and give an eigenvector for each eigenvalue.
- (a) The complete graph \(K_n\).
- (b) The star \(K_{1,m}\) (\(n = m+1\)).
- (c) The complete bipartite graph \(K_{a,b}\).
- (d) Find two non-isomorphic graphs with the same \(\mathcal L\)-spectrum. Do they have the same \(L\)-spectrum?
Hint. Look first for eigenvectors supported on a set of vertices with identical neighborhoods and summing to zero there. The trace gives you the last eigenvalue for free.
Exercise 5. Products, the hypercube, and the grid
The Cartesian product \(G \,\square\, H\) has vertex set \(V_G \times V_H\). Its edges are \((g,h) \sim (g',h)\) with weight \(w_G(g,g')\) whenever \(g \sim g'\), and \((g,h) \sim (g,h')\) with weight \(w_H(h,h')\) whenever \(h \sim h'\).
- (a) Prove that \(L_{G \square H} = L_G \otimes I + I \otimes L_H\). Conclude that if \(L_G \varphi = \alpha \varphi\) and \(L_H \psi = \beta \psi\), then \(\varphi \otimes \psi\) is an eigenvector of \(L_{G\square H}\) with eigenvalue \(\alpha + \beta\), and that these give a full eigenbasis.
- (b) The hypercube is \(Q_d = K_2 \,\square\, \cdots \,\square\, K_2\) (\(d\) factors), with vertex set \(\{0,1\}^d\). Find all eigenvalues of \(L(Q_d)\) and \(L_{rw}(Q_d)\) with multiplicities. Show that the functions \(\chi_S(x) = (-1)^{\sum_{i \in S} x_i}\), \(S \subseteq [d]\), form an eigenbasis. Check the spectral gap \(2/d\) used in the Lecture 2 notes, §6.5.
- (c) Suppose \(G\) is \(d_G\)-regular and \(H\) is \(d_H\)-regular. Express \(L_{rw}(G \square H)\) in terms of \(L_{rw}(G)\) and \(L_{rw}(H)\), and describe its spectrum.
- (d) Without regularity, (c) fails. Let \(G = H = P_3\), the path on three vertices, so that \(G \square H\) is the \(3 \times 3\) grid.
- Find the spectrum of \(L_{rw}(P_3)\) and an eigenvector \(\varphi\) for the eigenvalue \(1\).
- Show that \(\varphi \otimes \mathbf 1\) is not an eigenvector of \(L_{rw}\) of the grid. The formula of (c) with \(d_G = d_H\) would predict eigenvalue \(\tfrac12\).
- Compute \(\lambda_2(L_{rw})\) of the \(3\times 3\) grid exactly.
Hint for (d)3. Look for an eigenvector that is odd under the reflection \(x \mapsto -x\) (coordinates \(\{-1,0,1\}\)) and even under \(y \mapsto -y\). It vanishes on the middle column and is determined by two numbers.
Exercise 6. Trace bounds and test functions
- (a) Show that \(\operatorname{tr} L = \sum_i d_i = 2\sum_{e \in E} w_e\) and \(\operatorname{tr} \mathcal L = n\).
- (b) Deduce that \(\lambda_2(\mathcal L) \le \frac{n}{n-1} \le \lambda_n(\mathcal L)\).
- (c) Show that \(\lambda_2(\mathcal L) = \frac{n}{n-1}\) if and only if \(G\) is a complete graph with all edge weights equal. In particular, among unweighted graphs, equality holds only for \(K_n\).
- (d) Using the test function \(f = e_v - \frac1n \mathbf 1\), prove that \[ \lambda_2(L) \le \frac{n}{n-1}\, d_{\min} \qquad \text{and} \qquad \lambda_n(L) \ge \frac{n}{n-1}\, d_{\max}. \] When are these tight?
Hint for (c). If \(\lambda_2 = \frac{n}{n-1}\), part (b) forces all nonzero eigenvalues to be equal. Write \(\mathcal L\) in terms of the unit \(0\)-eigenvector \(u = D^{1/2}\mathbf 1 / \sqrt{\mathrm{vol}(V)}\), then read off \(A\). Use that \(A\) has zero diagonal.
Exercise 7. Adding an edge
Let \(H\) be obtained from \(G\) by adding an edge \(e = \{u,v\}\) of weight \(w_e > 0\), or by increasing the weight of an existing edge by \(w_e\).
- (a) Prove that \(\lambda_k(L_H) \ge \lambda_k(L_G)\) for every \(k\).
- (b) Let \(G\) be unweighted with at least one edge. Using (a) and Exercise 4, prove that \(\lambda_n(L) \ge d_{\max} + 1\). Compare with Exercise 6(d).
- (c) Show that (a) fails for \(\mathcal L\): adding one edge to \(P_3\) decreases \(\lambda_3(\mathcal L)\).
- (d) Show that adding one edge can also decrease \(\lambda_2(\mathcal L)\). Find an example on four vertices and compute both values exactly. Explain what goes wrong in the proof of (a).
Hint for (a). Write \(L_H - L_G\) as a rank-one matrix and use Courant–Fischer.
Hint for (d). Start from the star \(K_{1,3}\) and join two leaves. Use the symmetry swapping those two leaves to split the eigenvalue problem into small pieces.
Exercise 8. The two-state chain, exactly
Let \(0 < a, b \le 1\) and \[ P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}. \] This is the random walk on a two-vertex weighted graph with self-loops. Like every two-state chain, it is reversible. Consider the continuous-time walk \(H_t = e^{-t(I - P)}\) started at \(\delta_1\), and write \(\mu_t = \delta_1^\top H_t\).
- (a) Find the stationary distribution \(\pi\) and the eigenvalues of \(L_{rw} = I - P\). With \(\lambda = a + b\), show that \[ H_t = \mathbf 1 \pi^\top + e^{-\lambda t}\,(I - \mathbf 1\pi^\top). \]
- (b) Let \(s = e^{-\lambda t}\). Compute \(\|\mu_t - \pi\|_{TV}\), \(\chi^2(\mu_t \Vert \pi)\) and \(D(\mu_t \Vert \pi)\) exactly as functions of \(s\), \(\pi_1\), \(\pi_2\).
- (c) Check that \(\chi^2\) decays exactly like \(e^{-2\lambda t}\). Why is the theorem of the Lecture 2 notes, §4 an equality here?
- (d) Compute the ratio \(2\|\mu_t - \pi\|_{TV} / \sqrt{\chi^2(\mu_t \Vert \pi)}\). When is comparison (1) of the Lecture 2 notes, §3 tight?
- (e) Show that \(D(\mu_t\Vert\pi) \sim \frac12 \chi^2(\mu_t\Vert\pi)\) as \(t \to \infty\). What does this say about comparison (3), \(D \le \log(1+\chi^2) \le \chi^2\), at \(t = 0\) and as \(t \to \infty\)?
- (f) Compute \(t_{\rm mix}(\varepsilon)\) exactly, worst case over both starting states. Suppose \(\pi_1 \to 0\). Compare with the two-sided bound of §5.1. Which side is tight? Where does the upper bound lose, given that there are only two states?
Hint for (a). Show that \(E = I - \mathbf 1\pi^\top\) is idempotent and that \(L_{rw} = \lambda E\).
Exercise 9. The barbell
The barbell \(B_m\) consists of two disjoint copies of \(K_m\) (\(m \ge 2\)) joined by one bridge edge \(\{u, v\}\), with \(u\) in the first clique and \(v\) in the second. It is unweighted, with \(n = 2m\). Let \(\lambda = \lambda_2(L_{rw})\).
- (a) Compute the degrees and \(\mathrm{vol}(V)\). Use a test function to show that \[ \lambda \le \frac{4}{\mathrm{vol}(V)} = \frac{2}{m^2 - m + 1}. \]
- (b) Route canonical paths as follows. Within a clique, use the direct edge. From \(a\) in the first clique to \(b\) in the second, go \(a \to u \to v \to b\), dropping the first or last step if \(a = u\) or \(b = v\); route the reverse pairs the same way. Use unit lengths and the \(\pi\)-weighted canonical-paths bound of the Lecture 2 notes, §6.1, to prove \[ \lambda \ge \frac{\mathrm{vol}(V)}{3m^4} = \frac{2(m^2 - m + 1)}{3m^4}. \]
- (c) Conclude that \(\lambda = \Theta(1/m^2)\) and give upper and lower bounds on \(t_{\rm mix}\) for the continuous-time walk. Compare with \(K_{2m}\) on the same vertex set: how many edges does the barbell lack, and what does that cost in spectral gap?
Hint for (b). There are three kinds of edges: the bridge, clique edges at \(u\) or \(v\), and all other clique edges. Bound the load on each separately, using \(\pi_a \le m/\mathrm{vol}(V)\) for every vertex.