Generalized Vandermonde Matrices with Missing Row-Powers

Let $[n] := \{0, 1, 2, \cdots, n -1 \}$ . Let $x = (x_0, \cdots, x_{n-1})$ with distinc $x_j$ s. Let $R = \{0 = r_1, r_2, \cdots, r_{n-1} = r$ be a set of distinct nonnegative row-powers. Consider the $n \times n$ Generalized Vandermonde matrix $V(x ; R) := \left( x_j^{r_i} \right)_{i,j \in [n]}$ . When $R = [n]$ , this matrix becomes the ordinary Vandermonde matrix, $V(x)$ .

An equivalent description of $R$ is the largest row-power $r \in R$ and the set of missing rows from $[r]$ : that is, the items that are in $[r]$ but not in $R$ . Let $L_r = \{\ell_0, \ell_1, \cdots \}$ be this set. Define the punctured Generalized Vandermonde matrix $V_{\perp}(x; L_r) := V(x; R)$ . Let $s_k(x)$ be the $k$ th elementary symmetric polynomial.

Now we are ready to present some interesting results without proof, from the paper “Lower bound on Sequence Complexity” by Kolokotronis, Limniotis, and Kalouptsidis.

$det V_{\perp}(x ; \{\ell \}) = det V(x) \ s_{n-\ell}(x).$

$det V_{\perp}(x ; \{\ell_0, \ell_1\}) = det V(x) \ det \left( s_{n-\ell_i+j}(x) \right)_{i,j \in [2]}.$

$det V_{\perp}(x ; L) = det V(x) \ det \left( s_{n-\ell_i+j}(x) \right)_{i,j \in [s]} \text{ where } L = \{ \ell_0, \ell_1, \cdots, \ell_{s-1}\}.$

I will add some applications later on.

In a Hermitian Matrix, the Eigenvectors of Different Eigenvalues are Orthogonal

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

Statement

Let $M$ be an $n\times n$ complex Hermitian matrix which means $M=M^*$ where $*$ denotes the conjugate transpose operation. Let $\lambda_1, \neq \lambda_2$ be two different eigenvalues of $M$ . Let $x, y$ be the two eigenvectors of $M$ corresponding to the two eigenvalues $\lambda_1$ and $\lambda_2$ , respectively.

Then the following is true:

$\boxed{\lambda_1 \neq \lambda_2 \Longrightarrow \langle x, y \rangle = 0.}$

Here $\langle x,y \rangle := y^*x$ denotes the usual inner product of two vectors $x,y$ .

Continue reading “In a Hermitian Matrix, the Eigenvectors of Different Eigenvalues are Orthogonal” →

Eigenvalues of the Laplacian Matrix of the Complete Graph

A complete graph (source: David Benbennick)

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

Continue reading “Eigenvalues of the Laplacian Matrix of the Complete Graph” →

Kirchhoff’s Matrix Tree Theorem for Counting Spanning Trees — A Proof for Beginners

Rectilinear minimum spanning tree (source: Rocchini)

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 $L$ is the Laplacian of a connected simple graph $G$ with $n$ vertices. Then the number of spanning trees in $G$ , denoted by $t(G)$ , is the following:

$t(G)=\frac{1}{n} \times \{$ the product of all non-zero eigenvalues of $L\ \}$ .

Continue reading “Kirchhoff’s Matrix Tree Theorem for Counting Spanning Trees — A Proof for Beginners” →

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:

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

Continue reading “Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots” →

Eigenvalues of a Hermitian Matrix are Real

In this post, we prove the following:

Statement: All eigenvalues of a Hermitian matrix are real.

Proof:

Continue reading “Eigenvalues of a Hermitian Matrix are Real” →