This is an elementary (yet important) fact in matrix analysis.
Let be an complex Hermitian matrix which means where denotes 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 denotes the usual inner product of two vectors .
In this post, we provide a proof of Kirchhoff’s Matrix Tree theorem  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.
Suppose is the Laplacian of a connected simple graph with vertices. Then the number of spanning trees in , denoted by , is 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).