On two generalized inverse eigenvalue problems for Hessenberg-upper triangular pencils and their application to the study of GMRES convergence

We discuss two generalized inverse eigenvalue problems. The first one: For a given unreduced upper Hessenberg matrix H, find a nonsingular upper triangular matrix T such that all the pencils Hk−λTk have prescribed eigenvalues, where Hk and Tk are the leading k×k principal submatrices of H and T, respectively. The second one: For a given unitary unreduced upper Hessenberg matrix Q, find a nonsingular upper triangular matrix T such that all the pencils Tk−θQk⁎ have prescribed eigenvalues, where Tk is the leading k×k principal submatrix of T, and Qk⁎ is the conjugate transpose of the leading k×k principal submatrix of Q. We present the necessary and sufficient conditions for the solvability of the two problems. Our results lead to an alternative proof for the statement that any admissible Ritz value set or admissible harmonic Ritz value set is possible for the prescribed GMRES residual norms. Here, the term “admissible” means there are some restrictions on the sets if GMRES stagnates at some iterations.