You are currently browsing the category archive for the ‘Computer Science’ category.

This is an elementary (yet important) fact in matrix analysis.

**Statement**

Let be an complex Hermitian matrix which means where denote the conjugate transpose operation. Let be two different eigenvalues of . Let be the two eigenvectors of corresponding to the two eigenvalues and , respectively.

Then the following is true:

Here denote the usual inner product of two vectors , i.e.,

.

You must have known it already, but I can’t stop myself from showing off the interplay of const with pointers in C/C++.

Here goes the code. It’s simple.

void main() { int arr[]={1,2,3,4}; // data const int *p1 = &arr[0]; // non-const ptr to const data int const *p2 = &arr[0]; // non-const ptr to const data int* const p3 = &arr[0]; // const ptr to non-const data const int* const p4 = &arr[0]; // const ptr to const data p1++; // ok p1[0]++; // compile error: modifying const data p2++; // ok p2[0]++; // compile error: modifying const data p3++; // compile error: modifying const ptr p3[0]++; // ok p4++; // compile error: modifying const ptr p4[0]++; // compile error: modifying const data }

We want to show that for , the following holds:

First, recall the power series . For , this sum is definitely larger than its th term only. In other words, , which implies . Now,

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

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 .

In this post, we provide a proof of Kirchhoff’s Matrix Tree theorem [1] which is quite beautiful in our biased opinion. This is a 160-year-old theorem which connects several fundamental concepts of matrix analysis and graph theory (e.g., eigenvalues, determinants, cofactor/minor, Laplacian matrix, incidence matrix, connectedness, graphs, and trees etc.). There are already many expository articles/proof sketches/proofs of this theorem (for example, see [4-6, 8,9]). Here we compile yet-another-expository-article and present arguments in a way which should be accessible to the beginners.

## Statement

Suppose is the Laplacian of a connected simple graph with vertices. Then the number of spanning trees in , denoted by , is the following:

the product of all non-zero eigenvalues of .

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:

- The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
- 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.
- 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).

**Introduction**

This is a beautiful theorem which states that the difference between a positive integer and a prime power of , , is divisible by . It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.

Riemann zeta function is a rather simple-looking function. For any number , the zeta function is the sum of the reciprocals of all natural numbers raised to the power.

Although the variable is a complex number, for the sake of simplicity, we will treat as real. (Real numbers are a subset of complex numbers.)