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