Vandermonde matrices with nodes in the unit disk and the large sieve (Q2424624): Difference between revisions

Let \(z_{1},\dots,z_{K}\) be distinct complex numbers and consider the \(N\times K\) Vandermonde matrix \(V\) with \(K\leq N\) whose \(k\)-th column is \((1,z_{k} ,\dots,z_{k}^{N-1})^{T}\). If the nodes \(z_{k}\) are all real then it is known that \(V\) is a poorly conditioned matrix and that the condition number of \(V\) grows exponentially with \(K\), but for complex nodes the situation is more complicated; for example, the matrix used in the discrete Fourier transform has \(2\)-norm equal to \(1\). In the present paper, the authors use a relationship between the singular values of \(V\) and an inequality which is central to the study of the large sieve in analytic number theory. This relationship was recently observed in [\textit{A. Moitra}, in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 821--830 (2015; Zbl 1321.68421)] but was already known to A. Selberg in the 1940s. We shall assume \(z_{k}=\left\vert z_{k}\right\vert e^{2\pi i\xi_{k}}\) with \(0\leq\xi_{1}<\xi_{2}<\dots<\xi_{K}<1\) and define \(\delta\) to be the minimum value of \(\xi_{k+1}-\xi_{k}\) (\(k=1,\dots,K-1)\) and \(\xi_{1}-\xi_{K}+1\). Put \(S_{y,N}(z):=\sum_{n=0}^{N-1}y_{n}\bar{z}^{n}\) where \(y:=(y_{0},\dots,y_{N-1})\). Then there is a bound \(\Delta\) depending on \(N,\left\vert z_{1}\right\vert ,\dots,\left\vert z_{K}\right\vert \) and \(\delta\) such that \[ \sum_{k=1}^{K}\left\vert S_{y,N}(z_{k})\right\vert ^{2}\leq\Delta\sum _{n=0}^{N-1}\left\vert y_{n}\right\vert ^{2}. \] In computing a bound we can use scaling to reduce the problem to the case where all \(\left\vert z_{k}\right\vert \leq1\). If all \(\left\vert z_{k}\right\vert =1\) then the inequality has been extensively studied and the best bound which is known is \(\Delta=N-1+\delta^{-1}\) (see [\textit{H. L. Montgomery}, Bull. Am. Math. Soc. 84, 547--567 (1978; Zbl 0408.10033)]). In the present paper, the authors obtain a similar but more complicated estimate of \(\Delta\) for the general case. This leads to estimates of the largest and smallest singular values of \(V\) and hence bounds on the \(2\)-condition number. In the final section, the authors compare their bounds with those given in [\textit{F. S. V. Bazán}, SIAM J. Matrix Anal. Appl. 21, No. 2, 679--693 (2000; Zbl 0952.15006)].