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

We will show that the eigenvalues of the n\times n Laplacian matrix L of the complete graph K_n are \{0,1\} where  the eigenvalue 0 has (algebraic) multiplicity 1 and the eigenvalue n has multiplicity n-1.

Read the rest of this entry »

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).

Read the rest of this entry »