L_HESS

=L_HESS(matrix,[output_form])

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 = UHU^T where U is a unitary matrix (U^TU=UU^T=I) and H is the Hessenberg form of A. The function does not currently support complex numbers so we use U^T 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 = UHU^T.

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(x₁)∥x∥₂e₁ where x₁ is the first element of x, ∥x∥₂ is the 2-norm of x or L_MAGNITUDE(x), and e₁ is the first unit basis vector or VSTACK(1,L_ZEROS(ROWS(x)-1,1)).
3. Compute the Householder matrix: P_k = I - 2*(vv^T)/(v^Tv)
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): A_new = 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.

/**
* 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)
))));

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

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}

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