(a) Define Householder reflections and show that a real Householder reflection is symmetric and orthogonal. Moreover, show that if $H, A \in \mathbb{R}^{n \times n}$, where $H$ is a Householder reflection and $A$ is a full matrix, then the computational cost (number of arithmetic operations) of computing $H A H^{-1}$ can be $\mathcal{O}\left(n^{2}\right)$ operations, as opposed to $\mathcal{O}\left(n^{3}\right)$ for standard matrix products.

(b) Show that for any $A \in \mathbb{R}^{n \times n}$ there exists an orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ such that

$$Q A Q^{T}=T=\left[\begin{array}{ccccc} t_{1,1} & t_{1,2} & t_{1,3} & \cdots & t_{1, n} \\ t_{2,1} & t_{2,2} & t_{2,3} & \cdots & t_{2, n} \\ 0 & t_{3,2} & t_{3,3} & \cdots & t_{3, n} \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & t_{n, n-1} & t_{n, n} \end{array}\right]$$

In particular, $T$ has zero entries below the first subdiagonal. Show that one can compute such a $T$ and $Q$ (they may not be unique) using $\mathcal{O}\left(n^{3}\right)$ arithmetic operations.

[Hint: Multiply A from the left and right with Householder reflections.]