Q of the QR decomposition is an upper Hessenberg matrix

Question

Let $A=\{a_{ij}\}_{i,j=1}^n$ be a nonsingular upper hessenberg matrix, i.e., $a_{i,j}=0$ for $i>j+1$.

I want to show that if $A=QR$ is the QR-decomposition of $A$ then $Q$ is also an upper hessenberg matrix.

$$$$

For the QR decomposition, we can apply the Gram-Schmidt Algorithm: $$\tilde{q}_1=a_1 \Rightarrow q_1=\frac{\tilde{q}_1}{\|\tilde{q}_1\|_2} \\ \tilde{q}_{k+1}=a_{k+1}-\sum_{i=1}^k(a_{k+1}, q_i)q_i \Rightarrow q_{k+1}=\frac{\tilde{q}_{k+1}}{\|\tilde{q}_{k+1}\|_2} $$

That means that each column of the $Q$ matrix involves a linear combination of all the previous columns, right?

We have that $A$ is an upper Hessenberg matrix, i.e. it holds that $a_{ij}=0$ for $i>j+1$.

How could we continue? Could yoyu giive me a hint?

Answer 1

You have $Q=AR^{-1}$ and the arithmetic of upper diagonal and upper sub-diagonal matrices tells you that $Q$ has the same structure as $A$.