A Fast Eigenvalue Algorithm for Hankel Matrices

We present an O(n 2 log n) algorithm for finding all the eigenvalues of an n \Theta n complex Hankel matrix. Keywords: Hankel matrix, Toeplitz matrix, circulant matrix, fast Fourier transform, Lanczos tridiagonalization, eigenvalue decomposition, complex-symmetric matrix, complex-orthogonal transformations 1. INTRODUCTION The eigenvalue decomposition of a structured matrix has important applications in signal processing. Common occurring structures include an n \Theta n Hankel matrix: H = 0 B B B B @ h 1 h 2 : : : hn\Gamma1 hn h 2 h 3 : : : hn hn+1 . . . . . . . . . . . . . . . hn\Gamma1 hn : : : h 2n\Gamma3 h 2n\Gamma2 hn hn+1 : : : h 2n\Gamma2 h 2n\Gamma1 1 C C C C A ; (1) or an n \Theta n Toeplitz matrix: T = 0 B B B B @ t n t n\Gamma1 : : : t 2 t 1 t n+1 t n : : : t 3 t 2 . . . . . . . . . . . . . . . t 2n\Gamma2 t 2n\Gamma3 : : : t n t n\Gamma1 t 2n\Gamma1 t 2n\Gamma2 : : : t n+1 t n 1 C C C C A : (2) There is extensive literature on inverting such matrices or s..