Opening Spectral Graph Theory III: Eigenvalues of the Laplacian
Spectral Graph Theory III: Eigenvalues of the Laplacian
- Length
- 22 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Recap of graph setup and operators
The eigenvalues of a graph's normalized Laplacian govern how random walks on that graph behave. O'Donnell first recalls the invariant distribution, the transition operator and from earlier sessions of his Carnegie Mellon graduate course, the CS Theory Toolkit. He shows that has an orthonormal basis of real eigenvectors with non-negative eigenvalues , which shares with eigenvalues . Expanding a vertex function in this basis turns inner products into dot products of spectral coefficients. Variance becomes the sum of squared coefficients beyond the constant one, by analogy with Fourier analysis on the hypercube. The session assumes linear algebra and basic random walks, and prepares later work on conductance and sparsest cut.

Your comment is kept while you sign up.Sign in
O'Donnell expands graph functions in Laplacian eigenvectors, turning inner products and variance into coefficient sums.
The eigenvalues of a graph's normalized Laplacian govern how random walks on that graph behave. O'Donnell first recalls the invariant distribution, the transition operator and from earlier sessions of his Carnegie Mellon graduate course, the CS Theory Toolkit. He shows that has an orthonormal basis of real eigenvectors with non-negative eigenvalues , which shares with eigenvalues . Expanding a vertex function in this basis turns inner products into dot products of spectral coefficients. Variance becomes the sum of squared coefficients beyond the constant one, by analogy with Fourier analysis on the hypercube. The session assumes linear algebra and basic random walks, and prepares later work on conductance and sparsest cut.
This lecture
Lecture 45 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.