Tridiagonalize matrices with Householder transformation

Question

I know that it is possible to tridiagonalize symmetric matrices by using a Householder trafo. I also found that we can get any matrix to Hessenberg form by using Householder trafos, but I still don't see why we cannot tridiagonalize any matrix with the Householder algorithm that we use for symmetric matrices. Where does this algorithm fail then?

Answer 1

For any square matrix $A\in\mathbb{R}^{n\times n}$ there is an orthogonal $U\in\mathbb{R}^{n\times n}$ such that $A=UHU^T$ is in a Hessenberg form (upper/lower). The fact that a symmetric $A$ can be transformed to a tridiagonal form is a consequence of the simple fact that $A$ is symmetric iff $H$ is symmetric and a Hessenberg matrix, which is symmetric, is tridiagonal.

One might find some examples of $A$'s which can be transformed by an orthogonal $U$ to a non-symmetric tridiagonal matrix. However, not all matrices can be "tridiagonalized" in this way. However, if you allow for more general transformations, e.g., different orthogonal factors from the left and right, you can obtain an algorithm which does something similar: it transforms a generally non-symmetric (even works for rectangular) matrix to a bidiagonal form.