Similarly, lower Hessenberg has zeros above the first superdiagonal.
Theorem: Every square matrix is unitarily similar to a matrix in Hessenberg form: $A = QHQ^*$ where $Q$ is unitary.
Hessenberg form is used as an intermediate step in eigenvalue algorithms (like the QR algorithm) because it is nearly triangular and cheaper to work with than a full matrix. The reduction to Hessenberg form can be done in $O(n^3)$ operations using Householder reflections.
**Definition:** A square matrix $H$ is in **upper Hessenberg form** if all entries below the first subdiagonal are zero: $h_{ij} = 0$ for $i > j + 1$.
$$H = \begin{pmatrix} * & * & * & * & * \\ * & * & * & * & * \\ 0 & * & * & * & * \\ 0 & 0 & * & * & * \\ 0 & 0 & 0 & * & * \end{pmatrix}$$
Similarly, **lower Hessenberg** has zeros above the first superdiagonal.
**Theorem:** Every square matrix is unitarily similar to a matrix in Hessenberg form: $A = QHQ^*$ where $Q$ is unitary.
Hessenberg form is used as an intermediate step in eigenvalue algorithms (like the QR algorithm) because it is nearly triangular and cheaper to work with than a full matrix. The reduction to Hessenberg form can be done in $O(n^3)$ operations using Householder reflections.