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.
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. $$