It is well known that (square) Vandermonde matrices are badly conditioned (e.g. Gautschi: "How Unstable Are Vandermonde Systems").
But what about non square Vandermonde matrices?
This plot shows the average condition number vs. number of rows for a non-square Vandermonde matrix with 3 columns:
It is interesting to see that the condition number is very high for a small number of rows but becomes small when the number of rows becomes large (much larger than columns).
For reference, this plot has been generated with the following MATLAB Code:
for trial=1:trials for N=1:1000 V = fliplr(vander(randn(N,1))); V = V(:,2:4); conds(trial,N) = cond(V); end end semilogx(1:1000, 10*log10(mean(conds)));
Why is this the case and can this be explained in an analytical way? Instead of condition number, I would also be happy with an argument based on the the determinant of $V^T V$