Background:
Suppose $\mathbf{A}$ is an $n \times n$ matrix and it is upper Hessenberg.
Using QR-factorization, we have $\mathbf{A=QR}$,
where $\mathbf{R}$ is an upper triangular matrix and $\mathbf{Q}$ is orthogonal.
Problem:
Prove that $\mathbf{Q}$ is upper Hessenberg.
I have little idea to move on. Does it construct the $\mathbf{Q}$ directly by writing entries of both sides of $\mathbf{A=QR}$ and compare the entries? Thank you in advance.
Best Answer
Since $A=QR$ and $R$ is upper triangular, the $k$th column of $A$ is a linear combination of the first $k$ columns of $Q$ (the coefficients of this linear combination are contained in the $k$th column of $R$). The matrix $A$ has a certain structure of nonzeros so the same structure must be preserved by these combinations, that is, by the columns of $Q$.
As a basis of proving this formally, you can proceed by induction on the number of columns of $A$. If $A$ has just one column, the statement is trivial since $Q$ is just a scalar multiple of $A$. Now assume that $A=[\tilde{A},a]\in\mathbb{R}^{n\times k}$ is upper Hessenberg, where $a$ is a column vector, and that the statement is true for $n\times(k-1)$ matrices. Let $$ A=[\tilde{A},a]=[\tilde{Q},q]\begin{bmatrix}\tilde{R}&r\\0&\rho\end{bmatrix}=QR $$ be a QR factorization of $A$. By evaluating the partitioned matrix product, we get $\tilde{A}=\tilde{Q}\tilde{R}$, which means that this is a QR factorization of the $n\times(k-1)$ matrix $\tilde{A}$, and by the induction assumption, $\tilde{Q}$ is upper Hessenberg. We have $$ a=\tilde{Q}r+\rho q\implies \rho q=a-\tilde{Q}r. $$ Since $A$ and $\tilde{Q}$ are upper Hessenberg, $a$ can have nonzeros only in entries $1,\ldots,\min\{k+1,n\}$ and $\tilde{Q}r$ can have nonzeros only in entries $1,\ldots,\min\{k,n\}$. Therefore, $q$ has (generally) the same structure of nonzeros as $a$, which, together with the fact that $\tilde{Q}$ is upper Hessenberg, proves that $Q$ is upper Hessenberg.