Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$?

share|improve this question
    
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
add comment

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$.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.