A Finite Procedure for the Tridiagonalization of a General Matrix

Interest in the problem of the tridiagonalization of an arbitrary square complex matrix by similarity transformation has been renewed recently through work by Geist, Parlett, Tang and others. To our knowledge, no procedure has so far been presented to compute a tridiagonal matrix similar to a general square complex matrix that requires only a finite number of operations and works for any matrix. In this paper, finite algorithms that are guaranteed to reduce an unreduced Hessenberg matrix or a general matrix to tridiagonal form via similarity transformations are presented. The algorithms are mainly of theoretical interest; that of finding a practical, cost-effective procedure for solving the problem remains an open problem.