Existence, uniqueness and algorithms for matrix unitary reduction to semiseparable form

This paper concerns the study of a unitary transformation from a generic symmetric matrix A into a semiseparable matrix. The problem is studied both theoretically and from an algorithmic point of view. In particular, we first give a proof of the existence of such a transformation and then we discuss the uniqueness of such transformation proving an Implicit-Q Theorem for semiseparable matrices. Finally, we study structural properties of the factors of the QR-decomposition of a semiseparable matrix. These properties allows us to design a method based on the QR iterations applied to a semiseparable matrix for reducing a symmetric matrix to semiseparable form. This method has the same asymptotic cost of the reduction of a symmetric matrix to tridiagonal form. Once the transformation has been accomplished, if one is interested in computing the eigenvalues each further QR iteration can be done in linear time.