Hessenberg Factorization

Background

If A is symmetric then Householder's method can be used to reduce it to a similar symmetric tridiagonal matrix.If A is nonsymmetric then Householder's method can be used to reduce it to a similar Hessenberg matrix.These are the preliminary steps that are made before applying the QR method for finding eigenvalues of .

Definition(Hessenberg Matrix)

An matrix withfor is called a Hessenberg matrix.The form of a Hessenberg matrix is

Definition(Unitary Matrix)

(i) For real matrices, a unitary matrix is a matrixfor which.

(ii)For complex matrices, a unitary matrix is a matrixfor which.

Theorem (Hessenberg Factorization of a Matrix)

There are two cases to consider.

(iii)Given a real matrix , there exists a unitary matrix and Hessenberg matrix so that

.

(iv) Given a complex matrix , there exists a unitary matrix and Hessenberg matrix so that

.

Theorem (Hessenberg Factorization of a Symmetric Matrix)Given a real symmetric matrix , there exists a unitary matrix and tri-diagonal symmetric matrix so that

.

Remark.This is the case that is easiest to illustrate in a first course in numerical methods.

TheoremIfthen is similar to and the eigenvalues of are the same as the eigenvectors of .

Remark.The eigenvectors of are in general different from the eigenvectors of .

Program (Householder Reduction to Upper-Hessenberg Form).To reduce thereal matrixto a Hessenberg matrix form by using Householder transformations.The following version of the program uses "loops" extensively and is more traditional in programming structure.It also contains a print statement so that you can watch the Householder transformations perform their "magic."
Disclaimer.The following subroutine is for pedagogical purposes only, it may not work for all cases.

Program (Householder Reduction to Upper-Hessenberg Form).To reduce thereal matrixto a Hessenberg form form by using Householder transformations.The following version of the program uses "objects" extensively and is more like "object oriented programming."
Disclaimer.The following subroutine is for pedagogical purposes only, it may not work for all cases.

Caveat.The above subroutines will not reduce ancomplex matrix to Hessenberg form.You should use Mathematica's built in procedureHessenbergDecompositionif you use complex matrices.If you do use Mathematica's built in procedure you will need to learn how software developers are permitted to dig into Mathematica's kernel and use its internal mathematical subroutines (i.e. picking Mathematica's brain).