12.4.3. Hessenberg Decomposition

Algorithms that diagonalize a matrix usually begin by finding the Hessenberg decomposition because it is a quick, direct calculation. The Hessenberg form [1] of a matrix has all zeros below the subdiagonal. [2] A Householder transform on each column clears the values below the subdiagonal. To maintain similarity, the transpose of each Householder transform is multiplied from the right.

\[\mathbf{A} = \mathbf{P\,H\,P}^H\]

Note

When converted to Hessenberg form, a symmetric matrix becomes tridiagonal, where only the subdiagonal, diagonal, and superdiagonal hold nonzero elements.

MATLAB has a function called hess that converts a matrix to Hessenberg form. The hessForm function shows an implementation of shifting a matrix to Hessenberg form.

function [P, H] = hessForm(A)
% HESSFORM - Convert A to upper Hessenberg form.
%  H = HESSFORM(A) is the Hessenberg form of the matrix A.
%     The Hessenberg form of a matrix is zero below the first
%     subdiagonal and has the same eigenvalues as A. If the matrix
%     is symmetric or Hermitian, the form is tridiagonal.
%
%  [P,H] = HESSFORM(A) produces a unitary matrix P and a Hessenberg
%     matrix H so that A = P*H*P' and P'*P = EYE(SIZE(P)).
%
% A - input real or complex square matrix n-by-n.

    [m, n] = size(A);
    if m ~= n
        error('Matrix must be square')
    end
    P = eye(n);
    for k = 1:n-1
        Hr = householder(A(k+1:m, k), m, k);
        A = Hr*A*Hr';
        A(k+2:m, k) = zeros(m-k-1, 1); % no round-off error
        P = P*Hr';
        % For real numbers, H = H', but not in the complex case
    end
    if nargout<=1, P = A; else, H = A; end
end

Footnotes