≡ ▼
```=L_HESS(matrix,[output_form])
```
ArgumentDescriptionExample
matrixThe beginning value in the vector2
output_formOutput "H" (default), "HU" where H and U are stacked vertically"H"

## Description

The L_HESS function creates an upper Hessenberg matrix that is similar to the original matrix. Similar refers to the property that the two matrices have the same eigenvalues. The Hessenberg matrix has zeros below the first subdiagonal. This property tends to improve the algorithm for finding eigenvalues.

The Hessenberg decomposition of matrix A results in A = UHUT where U is a unitary matrix (UTU=UUT=I) and H is the Hessenberg form of A. The function does not currently support complex numbers so we use UT instead of the conjugate transpose U*.

Update 2/28/24: For cases involving finding eigenvectors when H is used to improve an eigenvalue algorithm, you may need the U matrix, so the output_form parameter of L_HESS allows you to choose "HU" to output H and U stacked vertically. Verify that A = UHUT.

The L_HESS function uses the Householder transformation as demonstrated in this video by Patrick Jones.

### Procedure

The following procedure is the method used in L_HESS

Initialization: Start with a square matrix A of size nxn.

Householder Transformations: For each column k from 1 to n-2, do the following:

1. Let x be the rows of column k from k+1 to n (i.e. Drop the first k elements of row k).
2. Compute the Householder Vector: Vector v is used to reflect x so that all elements below the first become zero. v = x + SIGN(x1)∥x∥2e1 where x1 is the first element of x, ∥x∥2 is the 2-norm of x or L_MAGNITUDE(x), and e1 is the first unit basis vector or VSTACK(1,L_ZEROS(ROWS(x)-1,1)).
3. Compute the Householder matrix: Pk = I - 2*(vvT)/(vTv)
4. Make the Householder matrix the same size as A: This is done by padding with the identity and zeros like this H = [ MUNIT(k) ZEROS(k,n-k); ZEROS(n-k,k) Pk]
5. Apply the Householder Transformation: Update the matrix A by applying the Householder matrix H to it from both the left and the right (to maintain symmetry in case of a symmetric matrix): Anew = HAH. Ahah! - This step zeros out all of the elements below the first subdiagonal in column k.

Repeat: Repeat the Householder Transformation for each column from k=1 to n-2.

Result: After applying all of the transformations, the matrix A is transformed into an upper Hessenberg matrix.

## Lambda Formula

This code for using L_HESS in Excel is provided under the License as part of the LAMBDA Library, but to use just this function, you may copy the following code directly into your spreadsheet.

### Code for AFE Workbook Module (Excel Labs Add-in)

```/**
* Return the Hessenberg of a square matrix using the Householder
* transformation algorithm.
*/
L_HESS = LAMBDA(matrix,[output_form],
IF(ROWS(matrix)<>COLUMNS(matrix),"Error: not square",
IF(ROWS(matrix)<3,"Must be > 2x2",
LET(doc,"https://www.vertex42.com/labmda/hess.html",
output_form,IF(ISOMITTED(output_form),"H",output_form),
n,ROWS(matrix),
ks,SEQUENCE(n-2),
HUk,REDUCE(VSTACK(matrix,MUNIT(n)),ks,LAMBDA(acc,k,
LET(Amat,DROP(acc,-n),
x,DROP(INDEX(Amat,0,k),k),
v,x+SIGN(INDEX(x,1))*VSTACK(SQRT(SUM(x^2)),SEQUENCE(ROWS(x)-1,1,0,0)),
Pk,MUNIT(ROWS(x))-2*MMULT(v,TRANSPOSE(v))/MMULT(TRANSPOSE(v),v),
Uk,VSTACK(HSTACK(MUNIT(k),SEQUENCE(k,n-k,0,0)),HSTACK(SEQUENCE(n-k,k,0,0),Pk)),
new_A,MMULT(MMULT(Uk,Amat),Uk),
VSTACK(new_A,MMULT(Uk,DROP(acc,n)))
))
),
H,DROP(HUk,-n,0),
IF(output_form="HU",VSTACK(H,TRANSPOSE(DROP(HUk,n,0))),H)
))));
```

### Named Function for Google Sheets

```Name: L_HESS
Description: Returns the Hessenberg form of a matrix
Arguments: matrix, output_form
Function:

=IF(ROWS(matrix)<>COLUMNS(matrix),"Error: not square",
IF(ROWS(matrix)<3,"Must be > 2x2",
LET(doc,"https://www.vertex42.com/labmda/hess.html",
n,ROWS(matrix),
ks,SEQUENCE(n-2),
HUk,ARRAYFORMULA(REDUCE(VSTACK(matrix,MUNIT(n)),ks,LAMBDA(acc,k,
LET(Amat,L_DROP(acc,-n,0),
x,L_DROP(INDEX(Amat,0,k),k,0),
v,x+SIGN(INDEX(x,1))*VSTACK(SQRT(SUM(x^2)),SEQUENCE(ROWS(x)-1,1,0,0)),
Pk,MUNIT(ROWS(x))-2*MMULT(v,TRANSPOSE(v))/MMULT(TRANSPOSE(v),v),
H,VSTACK(HSTACK(MUNIT(k),SEQUENCE(k,n-k,0,0)),HSTACK(SEQUENCE(n-k,k,0,0),Pk)),
new_A,MMULT(MMULT(H,Amat),H),
VSTACK(new_A,MMULT(Uk,L_DROP(acc,n,0)))
)
))),

)))
```

## L_HESS Examples

Example 1

Find the Hessenberg matrix for the example shown in this youtube video.

```Test: Copy and Paste this LET function into a cell
=LET(
matrix, {1,0,2,3;-1,0,5,2;2,-2,0,0;2,-1,2,0},
L_HESS(matrix)
)

Result: {1,  3.3333, -1.2667,   0.5333;
3,       0,  2.1333,   0.0667;
0,      -5,  0.7733,   2.5867;
0,       0, -0.7467,  -0.7733}
```
Example 2

Find the Hessenberg matrix for a random square matrix of integers between -10 and 10.

```Test: Copy and Paste this LET function into a cell
=LET(
matrix, RANDARRAY(5,5,-10,10,TRUE),
L_HESS(matrix)
)

Result: varies

matrix = {5, -4, -9,  6, -10;
2, -5, -5, -3,  -7;
6, -3, -3,  2,   4;
7,  6,  7,  0, -10;
2,  6,  6,  7,  -2}

result =
{ 5.0000,  4.1478,  2.4360, -8.9583, -11.3846;
-9.6437,  2.8172, -6.8654, -0.7516,   3.4187;
0, 12.5706, -5.4531, -0.3878,  -4.1466;
0,       0, -11.735, -3.9510,   3.5440;
0,       0,       0, -2.4590,  -3.4132}
```

### Revision History

• 2/22/24 - Added output_form option to allow output of both H and U
References & Resources