On orthogonal reduction to Hessenberg form with small bandwidth (Q1027782)

Numerous algorithms in numerical linear algebra are based on the reduction of a given matrix \(A\) to a more convenient form, as for instance 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, which is a computational advantage. In this paper, the authors present necessary and sufficient conditions on \(A\) so that the orthogonal Hessenberg reduction yields a Hessenberg matrix with small bandwidth. This includes the orthogonal reduction to tridiagonal form as a special case (orthogonality here is meant with respect to some given but unspecified inner product). The main result is already implied by the Faber-Manteuffel theorem [see \textit{J. Liesen} and \textit{Z. Strakoš}, SIAM Rev. 50, No. 3, 485--503 (2008; Zbl 1148.65023)]. However, the authors present in this paper a new and less technical proof. This proof uses the idea of a a ``minimal counterexample'' which is standard in combinatorial optimization.