5.7 The QR Factorization
As pointed out above, the LU factorization is not a mathematically respectable thing because it
does not always exist. There is another factorization which does always exist. Much more can be
said about it than I will say here. At this time, I will only deal with real matrices and so the inner
product will be the usual real dot product. Letting A be an m × n real matrix and letting
denote the usual real inner product,
Thus, when you take the matrix across the comma, you replace with a transpose.
Definition 5.7.1 An n × n real matrix Q is called an orthogonal matrix if
Thus an orthogonal matrix is one whose inverse is equal to its transpose.
From the above observation,
This shows that orthogonal transformations preserve distances. Conversely you can
also show that if you have a matrix which does preserve distances, then it must be
Example 5.7.2 One of the most important examples of an orthogonal matrix is the so called
Householder matrix. You have v a unit vector and you form the matrix
This is an orthogonal matrix which is also symmetric. To see this, you use the rules of matrix
operations. so it is symmetric. Now to show it is orthogonal, because vTv
= v ⋅ v
= 1. Therefore, this is an example of an orthogonal matrix.
Consider the following problem.
Problem 5.7.3 Given two vectors x,y such that
0 but x≠y and you want an
orthogonal matrix Q such that Qx
= y and Qy
= x. The thing which works is the Householder
Here is why this works. Hence Adding these equations,
= 2y and subtracting them yields
A picture of the geometric significance follows.
The orthogonal matrix Q reflects across the dotted line taking x to y and y to
Definition 5.7.4 Let A be an m×n matrix. Then a QR factorization of A consists of two
matrices, Q orthogonal and R upper triangular (right triangular) having all the entries on
the main diagonal nonnegative such that A = QR.
With the solution to this simple problem, here is how to obtain a QR factorization for any
matrix A. Let
where the ai are the columns. If a1 = 0, let Q1 = I. If a1≠0, let
and form the Householder matrix
As in the above problem Q1a1 = b and so
where A2 is a m− 1 ×n− 1 matrix. Now find in the same way as was just done a m− 1 ×m− 1
Continuing this way until the result is upper triangular, you get a sequence of orthogonal matrices
where R is upper triangular.
Now if Q1 and Q2 are orthogonal, then from properties of matrix multiplication,
Thus the product of orthogonal matrices is orthogonal. Also the transpose of an orthogonal matrix
is orthogonal directly from the definition. Therefore, from 5.4
This proves the following theorem.
Theorem 5.7.5 Let A be any real m×n matrix. Then there exists an orthogonal matrix Q and
an upper triangular matrix R having nonnegative entries on the main diagonal such
and this factorization can be accomplished in a systematic manner.