.. _hess:

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.

.. math:: \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.

.. index:: hess

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.

.. index:: hessForm

::

   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

.. index:: Hessenberg decomposition
.. index:: Hessenberg form

.. rubric:: Footnotes

.. [1]
   Karl Hessenberg (1904–1959) was a German electrical engineer and
   mathematician. He wrote the report where he introduced the Hessenberg
   form while he was a Ph.D. student at Technische Hochschule
   Darmstadt [HESSENBERG40]_.

.. [2]
   The subdiagonal is the diagonal below the main diagonal.