# Hessenberg vs upper triangular matrix for eigenvalues (QR algorithm)

You compute A = QR by using givens rotations, and use the QR algorithm for finding eigenvalues of A. The process of finding eigenvalues can be sped up by transforming A to a Hessenberg matrix (by using givens).

I'm guessing using a Hessenberg matrix is more efficient because of the fact that for every QR factorization you now do, you have to do less givens rotations? Correct me on this if I'm wrong.

Now onto the question: Why don't we transform A to an upper triangular matrix to begin with? Why stop at a Hessenberg form?

Yes, in Hessenbergform, you only need ~$n$ Givens-Rotations per QR step, in full form that requires ~$n^2/2$ rotations.
• Note that the next matrix in the QR algorithm is $A_+=RQ=Q^TAQ$. What the Givens rotation (or Householder reflection) on the left sets to zero, the same operation after application from the right can disturb. The best you can get in one step is Hessenberg. Commented Jan 21, 2016 at 23:47