# Householder Transformation

Let $\mathbf{a}\in\mathbb{R}^{n}$ be a non-zero vector. Develop a numerically stable procedure to compute a Householder transformation P such that $$P\mathbf{a}=\left(\begin{array}{c} |\mathbf{a}|_{2}\\ 0 \end{array}\right)$$

What I have:

Let $$P=\left(\begin{array}{cccc} p_{11} & p_{12} & \cdots & p_{1n}\\ p_{21} & p_{22} & \cdots & p_{2n} \end{array}\right)$$

and

$$\mathbf{a}=\left(\begin{array}{c} a_{1}\\ a_{2}\\ \cdots\\ a_{n} \end{array}\right)$$

then we have

$$\left(\begin{array}{cccc} p_{11} & p_{12} & \cdots & p_{1n}\\ p_{21} & p_{22} & \cdots & p_{2n} \end{array}\right)\left(\begin{array}{c} a_{1}\\ a_{2}\\ \cdots\\ a_{n} \end{array}\right)=\left(\begin{array}{c} |\mathbf{a}|_{2}\\ 0 \end{array}\right)$$

$$\left(\begin{array}{cccc} p_{11}a_{1}+ & p_{12}a_{2}+ & \cdots & +p_{1n}a_{n}\\ p_{21}a_{1}+ & p_{22}a_{2}+ & \cdots & +p_{2n}a_{n} \end{array}\right)=\left(\begin{array}{c} \sqrt{a_{1}^{2}\cdots a_{n}^{2}}\\ 0 \end{array}\right)$$

Thus we must satisfy these two equations

$$p_{11}a_{1}+p_{12}a_{2}+\cdots+p_{1n}a_{n}=\sqrt{a_{1}^{2}+\cdots+a_{n}^{2}}$$

$$p_{21}a_{1}+p_{22}a_{2}+\cdots+p_{2n}a_{n}=0$$

The second equation is just a 1 by n system and can be solved easily.

The first one implies that

$$(p_{11}a_{1}+p_{12}a_{2}+\cdots+p_{1n}a_{n})^{2}=a_{1}^{2}+\cdots+a_{n}^{2}$$ $$p_{11}^{2}a_{1}^{2}+\cdots+p_{1n}^{2}a_{n}^{2}+cross terms=a_{1}^{2}+\cdots+a_{n}^{2}$$

And this is where I got stuck.

Also there is the wierdness that household transformation P should be n by n matrix. But the wording of this problem requires P to be exactly 2 by n. If you have an alternative interpretation of the question I would really appreciate it.

-
Huh? The Householder transformation is always a square matrix, being a rank-$1$ correction to the identity matrix. What textbook are you using? (Otherwise, the book by Golub and Van Loan has a good description of the basic algorithm.) –  Ｊ. Ｍ. May 8 '12 at 11:21
Hi J.M. The book I am using is Numerical Analysis by Burden and Faires. and yes I know the Householder transformation must be square matrix. That's why the wording of the question is very strange. The original document is here: math.berkeley.edu/~mgu/MA128B2012S/SampleFinal2012S.pdf. It's the last question. –  Xiaowen Li May 8 '12 at 11:56
Unfortunately, I don't have a copy of that book. How does your book define the Householder transformation? (I know of at least two definitions, and I want to be sure which one you're using before proceeding.) –  Ｊ. Ｍ. May 8 '12 at 11:58
Hi J.M. It defines it as $P = I - 2w*w^t$, where I is the identity matrix and w is n-vector with $w^t*w=1$ –  Xiaowen Li May 8 '12 at 12:17
And what happens if you multiply that matrix you have into your vector? –  Ｊ. Ｍ. May 8 '12 at 12:52