ON THE SINGULAR VALUES OF MATRICES WITH DISPLACEMENT STRUCTURE

Matrices with displacement structure such as Pick, Vandermonde, and Hankel matrices appear in a diverse range of applications. In this paper, we use an extremal problem involving rational functions to derive explicit bounds on the singular values of such matrices. For example, we show that the k th singular value of a real n x n positive de finite Hankel matrix, H-n, is bounded by C rho(-k/logn) || H-n || 2 with explicitly given constants C > 0 and rho > 1, where || H-n ||2 is the spectral norm. This means that a real n x n positive de fi nite Hankel matrix can be approximated, up to an accuracy of is an element of|| H-n || 2 with 0 < is an element of < 1, by a rank O (log n log(1/is an element of)) matrix. Analogous results are obtained for Pick, Cauchy, real Vandermonde, Lowner, and certain Krylov matrices.