The numerical rank of Krylov matrices

In this paper we expose interesting features of Krylov matrices and Vandermonde matrices. Let S be a large symmetric matrix of order n. Let x be a real n-vector, and let Kℓ denote the related n×ℓ Krylov matrix. The question considered in this paper is how the numerical rank of Kℓ grows as ℓ increases. The key for answering this question lies in the close link between Kℓ and the n×ℓ Vandermonde matrix which is generated by the eigenvalues of S. Analysis of large Vandermonde matrices shows that the numerical rank is expected to remain much smaller than ℓ. The proof is based on partition theorems and clustering theorems. The basic tool is a new matrix equality: The Vandermonde-Pascal-Toeplitz equality. The actual numerical rank of a Vandermonde (or Krylov) matrix depends on the distribution of the eigenvalues, but often the rank is remarkable small. Numerical experiments illustrate these points. The observation that the numerical rank of Krylov matrices stays small has important practical consequences.