2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great answer, thanks! $\endgroup$ – user403203 Dec 31 '16 at 21:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You actually have $H^2=I$, i.e., $H^{-1}=H$. $\endgroup$ – Dr. Lutz Lehmann Dec 31 '16 at 18:37
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.