Function Repository Resource:

GaussianHessenbergDecomposition

Source Notebook

Compute the Gaussian Hessenberg decomposition of a matrix

Contributed by: Jan Mangaldan

ResourceFunction["GaussianHessenbergDecomposition"][m]

gives the Gaussian Hessenberg decomposition of a square matrix m.

ResourceFunction["GaussianHessenbergDecomposition"][{m,a}]

gives the Gaussian Hessenberg-triangular decomposition of the matrix pencil {m,a}.

Details

ResourceFunction["GaussianHessenbergDecomposition"][m] gives a result of the form {p,h}, where the matrices p and h satisfy the relation p.h.Inverse[p]==m.

In the Gaussian Hessenberg decomposition, the matrix h is an upper Hessenberg matrix that is similar to (in other words, has the same eigenvalues as) the original matrix, while the matrix p is a product of permutation matrices and stabilized elementary matrices (Gauss transforms).

ResourceFunction["GaussianHessenbergDecomposition"][{m,a}] yields a list of matrices {q,h,p,t}, where h is an upper Hessenberg matrix and t is an upper‐triangular matrix, such that m is given by q.h.p and a is given by q.t.p.

The matrices q and p in the Gaussian Hessenberg-triangular decomposition are products of permutation matrices and stabilized elementary matrices (Gauss transforms).

Examples

Basic Examples (2)

Find the Gaussian Hessenberg decomposition of a 4×4 matrix:

In[1]:=

${p, h} = ResourceFunction["GaussianHessenbergDecomposition"][\!$\* TagBox[ RowBox[{"(", "", GridBox[{ {"1", "2", "3", "5"}, {"2", "4", "1", "6"}, {"1", "2", RowBox[{"-", "1"}], "3"}, {"2", "0", "1", "3"} }, GridBoxAlignment->{"Columns" -> {{Center}}, "Rows" -> {{Baseline}}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}}], "", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]$]$

Out[1]=

The matrix h is an upper Hessenberg matrix:

In[2]:=

Out[2]=

Scope (6)

The Gaussian Hessenberg decomposition for a complex matrix:

In[3]:=

ResourceFunction["GaussianHessenbergDecomposition"][({
{1 + I, 3 + I, 2 - I, 1 + I},
{3 + I, 2 - I, 1 + I, 3 + I},
{4 + I, 5 + I, 6 - I, 2 + I},
{1 + I, 3 - I, 3 - I, 2 - I}
})]

Out[3]=

In[4]:=

Out[4]=

The Gaussian Hessenberg decomposition for a numeric matrix:

In[5]:=

ResourceFunction["GaussianHessenbergDecomposition"][({
{1., 2., 3., 4.},
{5., 6., 7., 8.},
{9., 10., 11., 12.},
{13., 14., 15., 16.}
})]

Out[5]=

In[6]:=

Out[6]=

The Gaussian Hessenberg decomposition for a matrix with entries having 24digit precision:

In[7]:=

ResourceFunction["GaussianHessenbergDecomposition"][N[({
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
}), 24]]

Out[7]=

The Gaussian Hessenberg decomposition for a symbolic matrix:

In[8]:=

Out[8]=

The Gaussian Hessenberg-triangular decomposition for an exact matrix pencil:

In[9]:=

MatrixForm /@ ResourceFunction["GaussianHessenbergDecomposition"][{( {
{50, -60, 50, -27, 6, 6},
{38, -28, 27, -17, 5, 5},
{27, -17, 27, -17, 5, 5},
{27, -28, 38, -17, 5, 5},
{27, -28, 27, -17, 16, 5},
{27, -28, 27, -17, 5, 16}
} ), ( {
{16, 5, 5, 5, -6, 5},
{5, 16, 5, 5, -6, 5},
{5, 5, 16, 5, -6, 5},
{5, 5, 5, 16, -6, 5},
{5, 5, 5, 5, -6, 16},
{6, 6, 6, 6, -5, 6}
} )}]

Out[9]=

The Gaussian Hessenberg-triangular decomposition for a numeric matrix pencil:

In[10]:=

MatrixForm /@ ResourceFunction["GaussianHessenbergDecomposition"][{N[( {
{50, -60, 50, -27, 6, 6},
{38, -28, 27, -17, 5, 5},
{27, -17, 27, -17, 5, 5},
{27, -28, 38, -17, 5, 5},
{27, -28, 27, -17, 16, 5},
{27, -28, 27, -17, 5, 16}
} )], N[( {
{16, 5, 5, 5, -6, 5},
{5, 16, 5, 5, -6, 5},
{5, 5, 16, 5, -6, 5},
{5, 5, 5, 16, -6, 5},
{5, 5, 5, 5, -6, 16},
{6, 6, 6, 6, -5, 6}
} )]}]

Out[10]=

Properties and Relations (3)

A 4×4 matrix:

In[11]:=

$m = \!$\* TagBox[ RowBox[{"(", "", GridBox[{ {"1", "2", "3", "5"}, {"2", "4", "1", "6"}, {"1", "2", RowBox[{"-", "1"}], "3"}, {"2", "0", "1", "3"} }, GridBoxAlignment->{"Columns" -> {{Center}}, "Rows" -> {{Baseline}}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}}], "", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]$;$

Compute its Gaussian Hessenberg decomposition:

In[12]:=

Out[12]=

The matrix h is upper Hessenberg:

In[13]:=

Out[13]=

In[14]:=

$Cases[%[[All, 1]], {i_, j_} /; (i - j > 1)]$

Out[14]=

The original matrix m is given by p.h.Inverse[p]:

In[15]:=

Out[15]=

A pair of 4×4 matrices:

In[16]:=

Compute the Gaussian Hessenberg-triangular decomposition of the corresponding pencil:

In[17]:=

Out[17]=

The matrix h is upper Hessenberg:

In[18]:=

Out[18]=

In[19]:=

$Cases[%[[All, 1]], {i_, j_} /; (i - j > 1)]$

Out[19]=

The matrix t is upper triangular:

In[20]:=

Out[20]=

In[21]:=

$Cases[%[[All, 1]], {i_, j_} /; (i - j > 0)]$

Out[21]=

The matrix m is given by q.h.p:

In[22]:=

Out[22]=

The matrix a is given by q.t.p:

In[23]:=

Out[23]=

GaussianHessenbergDecomposition gives a different result from the built-in HessenbergDecomposition:

In[24]:=

m = N[({
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
})];

In[25]:=

Out[25]=

In[26]:=

Out[26]=

Both decompositions yield upper Hessenberg matrices that are similar to the original matrix:

In[27]:=

Out[27]=

HessenbergDecomposition yields a unitary transformation matrix, while GaussianHessenbergDecomposition does not:

In[28]:=

Out[28]=

Version History

1.0.0 – 17 May 2021

Source Metadata

Citation:
- Kaufman L., The LZ-Algorithm to Solve the Generalized Eigenvalue Problem. SIAM Journal on Numerical Analysis, vol. 11, no. 5, 997-1024, 1974.
  DOI: 10.1137/0711078
- Martin R.S., Wilkinson J.H., Similarity reduction of a general matrix to Hessenberg form. Numerische Mathematik, vol. 12, 349-368, 1968.
  DOI: 10.1007/BF02161358

Related Resources

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License