Question involving Householder Matrix

Question

This is an exam question that I'm having trouble solving. Given a unit vector $v^Tv=1$, the Householder matrix is defined as $H=I-2vv^T$.

The first question is: given column vector $x$, if $Hx=c\cdot e_1$ where $c$ is constant and $e_1$ is the first vector of the canonical basis, find $c$.

After some algebra, I found that

$$c=x_1-2v_1\sum_{i=1}^n{v_ix_i}$$

I was unable to simplify it further.

The second question that I've been unable to solve is:

What is $v$, so that $H=I-2vv^T$ satisfies $Hx=c\cdot e_1$?

Answer 1

It might be a little simpler to look at what $H$ does. If $x || v$ then $Hx = -x$ and if $x \bot v$, we have $Hx = x$. So to invert, we just apply $H$ again.

To confirm, check that $H^2 = I$, in fact, $H$ is orthogonal, which gives it desirable numerical properties.

I suspect the purpose of the question was not to have you perform the algebraic manoeuvre $c=e_1^T Hx= e_1^T(x-2v^Tx v) = x_1 - 2v_1(v^T x)$, but to note that $\|Hx\| = \|ce_1\|$ from which we get $c = \pm \|x\|$.

To compute a relevant $v$, note that we want to reflect the vector $x$ onto the vector $\pm \|x\| e_1$. Use $y=\pm e_1$ to represent the desired target unit vector. Then we want to find the hyperplane that bisects the angle between $x$ and $\|x\| y$, we can do this by choosing direction $u = x - \|x\|y$, and letting $v= {u \over \|u\| }$. Then a quick calculation (using $\|x-\|x\|y\|^2 = 2 ( \|x\|^2- \|x\| x^Ty)$) shows that $Hx = y$.

We choose $\pm$ so that $u \neq 0$.

Answer 2

Your result for question one is correct. For completeness $$(I-2vv^T)x=ce_1 \rightarrow x-(2v^Tx)v=ce_1 \rightarrow c=(x-(2v^Tx)v)_1$$ For second question we have to find x. For that note that the householder matrix, $(I-2vv^T)$, is invertible because its determinant is -1 and also, as pointed out, $H^2=I$ and thus $H^{-1}=H$. So
$$(I-2vv^T)x=ce_1 \rightarrow x=c(I-2vv^T)^{-1}e_1$$

Answer 3

A Householder reflection is an isometric operation, thus $|c|=\|x\|$.

To get more information, observe that as $Hx=ce_1$, so also $H(ce_1)=x$ and consequently $$ ce_1-2cvv_1=x\implies c-2cv_1^2=x_1, \;c=\frac{x_1}{1-2v_1^2} $$ and thus $$ x=\frac{(e_1-2vv_1)x_1}{1-2v_1^2} $$ is up to a scaling factor completely determined by $v$.

This also is half the way to solve the second task.