# Invertibility of random Vandermonde matrix

Let $\kappa, d \in\mathbb{N}$ and $f$ is a uniform probability measure on $\mathcal{D} = \left[-1,1\right]^{\kappa}$. In addition, let

\begin{equation*} p = p\left(\kappa,d\right) := \left(\begin{array}{c} \kappa + d\\ \kappa \end{array}\right) \end{equation*}

and define $\mathcal{I}_{\kappa,d} = \left\{\left(j_1,\ldots,j_{\kappa}\right):\; 0 \leq j_1+\ldots+j_{\kappa} \leq d\right\}$ as the set of indices of all monomials of degree at most $d$ ( Notice that $\left\lvert \mathcal{I}_{\kappa,d} \right\rvert = p$).

Suppose that $\left\{s_i\right\}^p_{i=1} = \left\{\left(s_i\left(1\right),\ldots, s_i\left(\kappa\right)\right)\in\mathcal{D}:\; i = 1,\ldots,p\right\}$ are drawn independently by $f$. Is it true to say that the multi-variate Vandermonde matrix which is given by

\begin{equation*} \mathcal{V}_{d,\kappa}\left(s_1,\ldots,s_p\right) = \left( s^I_l\right)^{I\in\mathcal{I}_{\kappa,d}}_{l=1,\ldots,p} = \left( s_l\left(1\right)^{j_1}\ldots s_l\left(\kappa\right)^{j_{\kappa}}\right)^{I\in\mathcal{I}_{\kappa,d}}_{l=1,\ldots,p} \end{equation*}

is non-singular almost surely.

• Thanks for the proof. I could not connect the proof to the probability measure $f$. So, it seems that the result can be generalized to any probability measure on $\mathcal{D}$. However, if $f$ is purely atomic in the sense that there is a finite set $\mathcal{D}_0\subset \mathcal{D}$ such that $f\left(\mathcal{D}_0\right) = 1$ then $\mathcal{V}$ has at least two identical rows with non-zero probability and therefore is singular. In addition, I think the result still holds for any non-atomic distribution on $\mathcal{D}$. – Student Aug 7 '14 at 21:25