Editing Hessenberg matrix (section)

===Householder transformations===
Any <math>n \times n</math> matrix can be transformed into a Hessenberg matrix by a similarity transformation using [[Householder transformation]]s. The following procedure for such a transformation is adapted from '''A Second Course In Linear Algebra''' by ''Garcia & Roger''.<ref>{{cite book |last1=Ramon Garcia |first1=Stephan |last2=Horn |first2=Roger |title=A Second Course In Linear Algebra |date=2017 |publisher=Cambridge University Press |isbn=9781107103818}}</ref>

Let <math>A</math> be any real or complex <math>n \times n</math> matrix, then let <math>A^\prime</math> be the <math>(n - 1) \times n</math> submatrix of <math>A</math> constructed by removing the first row in <math>A</math> and let <math>\mathbf{a}^\prime_1</math> be the first column of <math>A'</math>. Construct the <math>(n-1) \times (n-1)</math> householder matrix <math>V_1 = I_{(n-1)} - 2\frac{ww^*}{\|w\|^2}</math> where
<math display="block">
w = \begin{cases}
\|\mathbf{a}^\prime_1\|_2\mathbf{e}_1 - \mathbf{a}^\prime_1 \;\;\;\;\;\;\;\; , \;\;\; a^\prime_{11} = 0 \\
\|\mathbf{a}^\prime_1\|_2\mathbf{e}_1 + \frac{\overline{a^\prime_{11}}}{|a^\prime_{11}|}\mathbf{a}^\prime_1 \;\;\; , \;\;\; a^\prime_{11} \neq 0 \\
\end{cases}
</math>

This householder matrix will map <math>\mathbf{a}^\prime_1</math> to <math>\|\mathbf{a}^\prime_1\| \mathbf{e}_1</math> and as such, the block matrix <math>U_1 = \begin{bmatrix}1 & \mathbf{0} \\ \mathbf{0} & V_1 \end{bmatrix}</math> will map the matrix <math>A</math> to the matrix <math>U_1A</math> which has only zeros below the second entry of the first column. Now construct <math>(n-2) \times (n-2)</math> householder matrix <math>V_2</math> in a similar manner as <math>V_1</math> such that <math>V_2</math> maps the first column of <math>A^{\prime\prime}</math> to <math>\|\mathbf{a}^{\prime\prime}_1\| \mathbf{e}_1</math>, where <math>A^{\prime\prime}</math> is the submatrix of <math>A^{\prime}</math> constructed by removing the first row and the first column of <math>A^{\prime}</math>, then let <math>U_2 = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & V_2\end{bmatrix}</math> which maps <math>U_1A</math> to the matrix <math>U_2U_1A</math> which has only zeros below the first and second entry of the subdiagonal. Now construct <math>V_3</math> and then <math>U_3</math> in a similar manner, but for the matrix <math>A^{\prime\prime\prime}</math> constructed by removing the first row and first column of <math>A^{\prime\prime}</math> and proceed as in the previous steps. Continue like this for a total of <math>n-2</math> steps.

By construction of <math>U_k</math>, the first <math>k</math> columns of any <math>n \times n</math> matrix are invariant under multiplication by <math>U_k^*</math> from the right. Hence, any matrix can be transformed to an upper Hessenberg matrix by a similarity transformation of the form <math>U_{(n-2)}( \dots (U_2(U_1 A U_1^*)U_2^*) \dots )U_{(n-2)}^* = U_{(n-2)} \dots U_2U_1A(U_{(n-2)} \dots U_2U_1)^* = UAU^*</math>.