3
$\begingroup$

Let $n,H$ two fixed positive integers.

Let $P\in\mathbb{Z}[X]$ a monic integral polynomial of height $H$ and degree $n$ taken uniformly at random (i.e. each of the $n$ free coefficients of $P$ is sampled uniformly and independently in the set $\{-H,\dots, +H\}$. Assuming that $P$ is irreducible, consider the set of its complex roots $\theta_1, \dots, \theta_n$ and construct the associated $n\times n$ Vandermonde matrix $V = V(\theta_1, \dots, \theta_n)$.

I'm interested in the behaviour of the absolute value of the smallest singular value of $V$ (smallest eigenvalue of $\bar{V}^T.V$). I've managed to obtain an exponentially small lower bound (in $H$ and $n$) on it, but I don't know if something better is reachable.

Experimentally it seems that the average value is 1, independently of the dimension or the height, but I didn't manage to (dis)prove this observation. The point is that the roots of $P$ are not varying too "randomly" ( in particular they can't be arbitrary close of one-another since the discriminant of $P$ is necessarly greater than 1).

Can we derive interesting absolute lower bounds on this smallest SV, or on its expected value?

Maybe in a simpler manner, can we derive similar statements for a random Vandermonde matrix (for which the parameters are taken uniformly and independently in the compact ball of radius H). I've seen some asynptotics results of that kind when they are sampled in the unit circle, but nothing more general.

Improve this question
$\endgroup$
3
  • $\begingroup$ You can try any of the deterministic bounds given in the following article : library.utia.cas.cz/separaty/2009/AS/… After what, you can take the expectation. You may have to use Jensen to bound from below this last expectation. $\endgroup$
    – Synia
    Commented Aug 31, 2017 at 1:01
  • $\begingroup$ The problem is that these kind of deterministic bounds only yields exponentially small bounds... Which are too far from 1 to explain this strange behaviour on expectations... $\endgroup$
    – user70925
    Commented Sep 1, 2017 at 15:45
  • $\begingroup$ Other suggestion : if $ s_1 $ is the smallest singular value, you have $ s_1 = \min_{ | x | = 1 } || V x ||^2 $ since this is the min of the quadratic form $ q_V(x) := x^* A x $ with $ A = V^* V $. You can play with this definition by particularising to interesting $x$, or even use the fact that $ s_1 \leq \int_B q_V(x) dx $ where $B$ is the unit ball and $ dx $ the Haar measure (not sure it gives something, though). The second moment method (Markov-Bienaymé-Tchebychev) tells you to look for the expectation of the square of $ \min_{|x| = 1} x^*(A - I) x $ since you want to compare to $1=|x|$. $\endgroup$
    – Synia
    Commented Sep 1, 2017 at 17:17

0

Reset to default

You must log in to answer this question.