Behavior of the minimum singular value of a random Vandermonde matrix

In this work we examine the behavior of the minimum singular value of random Vandermonde matrices. In particular, we prove that the minimum singular value s1(N) is at most N exp(-C−šN) where N is the dimension of the matrix and C is a constant. Furthermore, the value of the constant C is determined explicitly. The main result is obtained in two different ways. One approach uses techniques from stochastic processes and in particular, a construction related to the Brownian bridge. The other one is a more direct analytical approach involving combinatorics and complex analysis. As a consequence, we obtain a lower bound on the maximum absolute value of a random polynomial on the unit circle, which may be of independent mathematical interest.