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 ℓ increase...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2017-09, Vol.528, p.185-205
Main Author: Dax, Achiya
Format: Article
Language:English
Subjects:
Clustering
Clustering theorems
Eigenvalues
Krylov matrices
Krylov subspaces
Lie groups
Linear algebra
Mathematical analysis
Matrix
Matrix methods
Numerical rank
Partition theorems
Proof theory
Symmetric matrices
The Vandermonde–Pascal–Toeplitz equality
Theorems
Vandermonde matrices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2016.07.022