# Eigenvalues of Krylov matrices

Let an $n\times n$ matrix ${\bf A}$, the all ones vector ${\bf w}$, and the $n\times n$ Krylov matrix $${\bf K}_n = \left[ {\bf w}\;\;{\bf A}{\bf w}\;\;\ldots \;\; {\bf A}^{n-1}{\bf w}\right].$$ Is there a way to characterize the spectrum of ${\bf K}_n$ in terms of the eigenvalues of ${\bf A}$?

-
Why the "random-matrices" tag? –  Yemon Choi Nov 6 '11 at 3:39
I guess because I consider ${\bf A}$ to be "generic" or random. –  Anadim Nov 6 '11 at 4:45
One trivial situation arises when $w$ is an eigenvector of $A$. –  Suvrit Nov 6 '11 at 10:22
Where do you meet these matrices? What is known about them? I know they used in integrable system theor to construct separated variaables.... –  Alexander Chervov Nov 6 '11 at 10:28

## 3 Answers

Certainly not in terms of the eigenvalues of $A$, because this won't be invariant under similarity transformations on $A$. One thing I can say is that for any vector $b$, $K b = \sum_{j=0}^{n-1} b_{j+1} A^j w$. So $K$ is singular if and only if $w$ is in the null space of a nontrivial polynomial in $A$ of degree $\le n-1$.

-

I don't see any reason for there to be a nice characterization. For instance if $A$ is diagonal then $K_n$ is a Vandermonde matrix, so its spectrum is fairly complicated...

-
Would you suggest any particular references on random Vandermonde matrices? –  Anadim Nov 6 '11 at 4:48
Sorry, but I don't know of any. –  Faisal Nov 6 '11 at 19:41

The short answer is: no. You can see the difficulty if $w$ is an eigenvector of $A$:the Krylov matrix becomes singular, while $A$ may not be.

The Krylov matrix is generated, as you probably know, during the Arnoldi iteration for locating eigenvalues of A. As part of the (stabilized version) of the process, A is partially reduced through orthogonal projections onto $\cal{K}_n$ to Hessenberg form, $H_n$. The eigenvalues of $H_m$, $m<n$, are fairly readily computed. I think the question of why the (Ritz) eigenvalues of $H_n$ converge to those of $A$ is an open question for general $A$.

-