In a first section of this chapter we will investigate ``a type'' of -factorization of Hessenberg-like plus diagonal matrices. We say a type of because we will show in the next section, that the -factorization is not necessarily unique. The factorization we propose is based on the paper . In the factorization presented in this paper, the orthogonal matrix is constructed as a product of Givens transformations, with the dimension of the matrix. Suppose we have a Hessenberg-like plus diagonal matrix . It will be shown that a first sequence of Givens transformations will transform the matrix into an upper triangular matrix . These Givens transformations will transform the matrix into a Hessenberg matrix. Our resulting matrix will therefore be Hessenberg. The second sequence of Givens transformations will reduce the Hessenberg matrix to upper triangular form.
The concept of irreducibility is an important topic for the construction of implicit -algorithms. We define what is meant with an unreduced Hessenberg-like matrix. It will be shown later on that this unreducedness demand plays a very important role in the implicit -theorem and in the construction of the implicit -algorithm. Moreover, using the definition of an unreduced Hessenberg-like matrix, it is rather easy to prove the essential uniqueness of the -factorization for Hessenberg-like matrices. With essentially unique we mean that two -factorizations only differ for the sign of the elements.
In the third section we will investigate the structure of a Hessenberg-like matrix after having applied a step of the -algorithm with shift. First we show that the choice of the -factorization is essential to obtain again a Hessenberg-like matrix after a -step. This fact is illustrated by an example in the Hessenberg and in the Hessenberg-like case. Using the -factorization for Hessenberg-like matrices as explained in Section 7.1, we will prove the following theorems: The structure of a Hessenberg-like matrix is maintained after a step of without shift; The weakly lower triangular structure of a matrix is maintained after a -step with shift; The Hessenberg-like structure is maintained after a -step with shift; The diagonal in a Hessenberg-like plus diagonal matrix is maintained after applying a step of with shift. Note that for these theorems, no assumptions concerning the singularity of the matrices are made.
In the second section we defined unreduced Hessenberg-like matrices and in Section 7.5 we will prove an implicit -theorem for Hessenberg-like matrices. This implicit -theorem strongly depends on the unreducedness of the Hessenberg-like matrix. Therefore we will provide in Section 7.4 an easy way of transforming a Hessenberg-like matrix to unreduced form. The algorithm provided performs in fact a special -step without shift on the Hessenberg-like matrix. This results in an algorithm, revealing immediately the singularities of the corresponding Hessenberg-like matrix.
In Section 7.5 of this chapter we will provide an implicit -theorem for Hessenberg-like matrices. The theorem is quite similar to the theorem for Hessenberg matrices. It will prove to be very powerful in the next chapter when we start with the construction of the different -algorithms.