On Orthogonal Reduction to Hessenberg Form with Small Bandwidth
Abstract
Numerous algorithms in numerical linear algebra are based on the reduction of a given matrix A to a more convenient form. One of the most useful types of such reduction is the orthogonal reduction to (upper) Hessenberg form. This reduction can be computed by the Arnoldi algorithm. When A is Hermitian, the resulting upper Hessenberg matrix is tridiagonal. In this paper we study necessary and sufficient conditions on A so that the orthogonal Hessenberg reduction yields a Hessenberg matrix with small bandwidth. Our proof utilizes the idea of a "minimal counterexample", which is standard in combinatorial optimization, but rarely used in the context of linear algebra.