214 CHAPTER 10. A FEW FACTORIZATIONS
Procedure 10.7.3 Given two vectors x,y such that |x| = |y| ̸= 0 but x ̸= y and you wantan orthogonal matrix Q such that Qx = y and Qy = x. The thing which works is the House-holder matrix
Q≡ I−2x−y|x−y|2
(x−y)T
Here is why this works.
Q(x−y) = (x−y)−2x−y|x−y|2
(x−y)T (x−y)
= (x−y)−2x−y|x−y|2
|x−y|2 = y−x
Q(x+y) = (x+y)−2x−y|x−y|2
(x−y)T (x+y)
= (x+y)−2x−y|x−y|2
((x−y) · (x+y))
= (x+y)−2x−y|x−y|2
(|x|2−|y|2
)= x+y
Hence
Qx+Qy = x+yQx−Qy = y−x
Adding these equations, 2Qx = 2y and subtracting them yields 2Qy = 2x.
Definition 10.7.4 Let A be an m×n matrix. Then a QR factorization of A consists of twomatrices, Q orthogonal and R upper triangular or in other words equal to zero below themain diagonal such that A = QR.
With the solution to this simple problem, here is how to obtain a QR factorization forany matrix A. Let
A = (a1,a2, · · · ,an)
where the ai are the columns. If a1 = 0, let Q1 = I. If a1 ̸= 0, let
b≡
|a1|0...0
and form the Householder matrix
Q1 ≡ I−2(a1−b)|a1−b|2
(a1−b)T