Form of Q in extended QR decomposition calculated with Householder reflections Let $A = QR$ be the extended QR decomposition of matrix $A \in \mathbb{R}^{m \times n}$ which is calculated by using $n$ Householder reflections. Prove by construction that there exist an upper triangular matrix $U \in \mathbb{R}^{n \times n}$ and such a matrix $W \in \mathbb{R}^{m \times n}$ that $Q = I - WUW^T$.
I've tried solving this problem by rearranging equations algebraically but this didn't give me any ideas. I assume that I have to use the fact that Q = $\prod_{i = 1}^n{(I - \frac{2}{w_i^Tw_i}w_iw_i^T)}$ for some vectors $w_i$ but I really don't know how use it. I know $w_i$ aren't just "some" vectors but I couldn't think of any property they have which would help me solve the problem. Any help is much appreciated.
 A: First of all, write
$$
Q = I - WUW^T = I - \sum_{i \leq j}^n u_{ij}\, w_iw_j^T .
$$
Now, consider what happens when you multiply $Q$ by a Householder matrix $I - 2ww^T$ (for some unit vector $w$) from the right.
\begin{align}
Q(I - ww^T) &= 
\left(I - \sum_{i \leq j}^n u_{ij}\, w_iw_j^T \right)(I - 2ww^T)
\\ & = I - 2ww^T - \sum_{i \leq j}^n u_{ij}\, w_iw_j^T + 2\sum_{i \leq j}^n u_{ij}\, w_iw_j^Tww^T
\\ & = I - 2ww^T + \sum_{i \leq j}^n u_{ij}\, w_iw_j^T + 2\sum_{i=1}^n w_i\left(\sum_{j=i}^n u_{ij}w_j^T w\right)w^T
\end{align}
Try to construct a matrix $\tilde U$, which consists of $U$ with an additional row and column, and a matrix $\tilde W$, which consists of $W$ with the column $w$ added to the end, such that the final line above can be expressed as
$$
I - \sum_{i \leq j}^{n+1} \tilde u_{ij}\,\tilde w_i\tilde w_j^T = I - \tilde W \tilde U \tilde W^T.
$$
With that, you'll have proved the result by induction.

In particular, I claim that we can take
$$
\tilde U = \pmatrix{U & x\\0 & -2}, 
$$
where $x$ denotes the column-vector
$$
x = \left[\sum_{j=1}^n u_{1j}w_j^T w \quad 
\sum_{j=2}^n u_{2j}w_j^T w \quad \cdots \quad u_{nn}w_n^T w\right]^T.
$$
