Eigenvalues of the Laplacian Matrix of the Complete Graph

A complete graph (source: David Benbennick)

We will show that the eigenvalues of the Laplacian matrix of the complete graph are where  the eigenvalue has (algebraic) multiplicity and the eigenvalue has multiplicity .

Advertisements

Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots

In this post, I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:

1. The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
2. The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
3. The reader holds a copy of the SS paper while reading my post.

First, I will mention the main theorems (actually, I will mention only what they “roughly” say).