When can a matrix be decomposed to a Hessenburg form vs Jordan Canonical Form? I understand that if a matrix is normal ($A^*A = AA^*$), then it is diagonalizable.
If it is not diagonalizable, then it has a Jordan canonical of form. 
However, a matrix can also be written as $A=Q^*HQ$ where H is a Hessenberg matrix.
Sounds like the Hessenberg reduction and Jordan canonical form is doing similar things to non-diagonalizable matrices. 
Just wondering what is their difference and when one should use one vs the other. 
 A: The Jordan form is block-diagonal with triangular blocks, not merely triangular. It characterizes the matrix by its generalized eigenspaces. It is basically the next best thing to a diagonalization when you have a nondiagonalizable matrix, but it can at least in principle be used for the same purposes (for example, to compute matrix exponentials). In practice computing a Jordan form at all is often difficult (because a nondiagonalizable matrix "looks diagonalizable" to most numerical routines).
The Hessenberg form is not even really triangular, it has an extra diagonal that isn't filled with zeros. In the nonsymmetric case it is usually even dense (in the symmetric case it is tridiagonal, thus sparse). As far as I know it is almost exclusively used as a finite preprocessing step in algorithms for computing eigenvalues/eigenvectors (for example in the QR algorithm).
By the way, normality is necessary and sufficient for unitary diagonalization. It is not necessary for diagonalization in general.
