## Reduction of a Real Matrix to Upper Hessenberg Form

A matrix is in upper Hessenberg form if all elements to the left and below the subdiagonal are 0. An upper Hessenberg matrix is also called an almost upper triangular matrix. Every square*n×n*matrix is similar to some

*n×n*upper Hessenberg matrix. Below are two routines which reduce a square matrix to a similar upper Hessenberg matrix. The first routine uses a sequence of Householder transformations to reduce the input matrix to upper Hessenberg form and the second routine uses a sequence of elementary transformations to reduce the input matrix to upper Hessenberg form.

A Householder transformation is an orthogonal transformation of the form

**Q**=

**I**- 2

**u u**, where

^{T}/ u^{T}u**u**is a column vector.

### Function List

- int Hessenberg_Form_Orthogonal( double *A, double *U, int n )

Given the*n×n*real matrix**A**, the routine Hessenberg_Form_Orthogonal transforms**A**to a matrix in upper Hessenberg form by a sequence of Householder transformations. The transformation matrix,**U**, where**A U**=**U H**, and**H**is the upper Hessenberg matrix, is returned in the array*U*. The matrix*U*should be dimensioned at least*n²*in the calling routine. The matrix**A**is replaced with the orthogonally similar matrix in upper Hessenberg form.

The function returns 0 if it is successful and -1 if there is not enough memory for working storage.

- int Hessenberg_Form_Elementary(double *A, double *S, int n)

Given the*n×n*real matrix**A**, the routine Hessenberg_Form_Elementary transforms**A**to a matrix in upper Hessenberg form by a sequence of Elementary transformations. The transformation matrix,**S**, where**A S**=**S H**, and**H**is the upper Hessenberg matrix, is returned in the array*S*. The matrix*S*should be dimensioned at least*n²*in the calling routine. The matrix**A**is replaced with the similar matrix in upper Hessenberg form.

The function returns 0 if it is successful and -1 if there is not enough memory for working storage.

*C* Source Code

- The file, hessenberg_orthog.c, contains the routine

Hessenberg_Form_Orthogonal( ).

- The file, hessenberg_elementary.c, contains the routine Hessenberg_Form_Elementary( ).