Vandermonde matrix rank

Question

Let ${\bf A} \in \mathbb{C}^{M\times N}$ be a Vandermonde matrix

\begin{equation} \bf A = \begin{bmatrix}1&1&\cdots&1 \\ z_1&z_2&\cdots&z_N\\ \vdots&\vdots&\ddots&\vdots\\ z_1^{M-1}&z_2^{M-1}&\cdots&z_N^{M-1} \end{bmatrix} \end{equation} where $z_n=e^{i\omega_n}$.

It is known that the rank of $\bf A $ is $N$ if $M\geq N$ and $z_m\neq z_n$ when $m\neq n$. Is there any formal proof?

Thanks.

Answer 1

It suffices to show that the first $N$ rows are linearly independent. In this regard, you may see ProofWiki for two different proofs.

Answer 2

You can easely prove by induction that

$$\det \begin{bmatrix}1&1&\cdots&1 \\ z_1&z_2&\cdots&z_N\\ \vdots&\vdots&\ddots&\vdots\\ z_1^{N-1}&z_2^{N-1}&\cdots&z_N^{N-1} \end{bmatrix} = \prod_{1 \leq i< j \leq N}(Z_j-Z_i)$$

Thus, if the $z_i$ are pairwise distinct, this determinant is non-zero, which shows that the first $N$ rows of your matrix are linearly independent.

Answer 3

You need to be careful. Although the determinant is never zero, the condition number of Vandermonde matrices tends to be very large.