Reduction to Hessenberg Form

Every iterative method in this topic — inverse iteration, and the QR algorithm that follows — requires repeatedly factoring or solving systems involving $A$, at $O(n^3)$ cost per step for a general dense matrix. This note builds a one-time preprocessing step, Hessenberg reduction, that reduces $A$ to a form with almost all entries below the first sub-diagonal already zero — after which every subsequent iteration costs only $O(n^2)$, a dramatic saving that makes large-scale eigenvalue computation practical at all.

Learning objectives. By the end of this note you should be able to: