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,
∑ ∑ ∑ ∑ ∑ ( )
(Ax, y) = (Ax)iyi = Aijxjyi = AT yixj
i i j j i ji
∑ ( T ) ( T )
= A y jxj = x,A y
j
Thus, when you take the matrix across the comma, you replace with a transpose.
Definition 5.7.1An n × n real matrix Q is called an orthogonal matrix if
QQT = QT Q = I.
Thus an orthogonal matrix is one whose inverse is equal to its transpose.
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
orthogonal.
Example 5.7.2One of the most important examples of an orthogonal matrix is the so calledHouseholder matrix. You have v a unit vector and you form the matrix
T
I − 2vv
This is an orthogonal matrix which is also symmetric. To see this, you use the rules of matrixoperations.
( T)T T ( T)T
I − 2vv = I − 2vv
= I − 2vvT
so it is symmetric. Now to show it is orthogonal,
( )( )
I − 2vvT I − 2vvT = I − 2vvT − 2vvT + 4vvT vvT
T T
= I − 4vv + 4vv = I
because v^{T}v = v ⋅ v =
|v|
^{2} = 1. Therefore, this is an example of an orthogonal matrix.
Consider the following problem.
Problem 5.7.3Given two vectorsx,ysuch that
|x|
=
|y|
≠0 butx≠yand you want anorthogonal matrix Q such that Qx = yand Qy = x.The thing which works is the Householdermatrix
x− y T
Q ≡ I − 2 |x-−-y|2-(x − y)
Here is why this works.
x-−-y-- T
Q(x − y) = (x− y)− 2 |x − y|2 (x − y) (x − y)
x − y 2
= (x− y)− 2 -----2-|x − y| = y− x
|x − y|
Adding these equations, 2Qx = 2y and subtracting them yields 2Qy = 2x.
A picture of the geometric significance follows.
PICT
The orthogonal matrix Q reflects across the dotted line taking x to y and y to
x.
Definition 5.7.4Let A be an m×n matrix. Then a QR factorizationof A consists of twomatrices, Q orthogonal and R upper triangular (right triangular) having all the entries onthe 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
A = (a1,a2,⋅⋅⋅,an)
where the a_{i} are the columns. If a_{1} = 0, let Q_{1} = I. If a_{1}≠0, let
( )
| |a1| |
|| 0 ||
b ≡ | .. |
( . )
0
and form the Householder matrix
Q ≡ I − 2(a1 −-b-)(a − b)T
1 |a1 − b|2 1
As in the above problem Q_{1}a_{1} = b and so
( )
|a1| ∗
Q1A = 0 A2
where A_{2} is a m− 1 ×n− 1 matrix. Now find in the same way as was just done a m− 1 ×m− 1
matrix
^
Q
_{2} such that
( )
∗ ∗
^Q2A2 = 0 A3
Let
( 1 0 )
Q2 ≡ ^ .
0 Q2
Then
( ) ( )
Q Q A = 1 0 |a1| ∗
2 1 0 ^Q2 0 A2
( )
| |a1| ∗ ∗ |
= |( ... ∗ ∗ |)
0 0 A
3
Continuing this way until the result is upper triangular, you get a sequence of orthogonal matrices
Q_{p}Q_{p−1}
⋅⋅⋅
Q_{1} such that
QpQp −1⋅⋅⋅Q1A = R (5.4)
(5.4)
where R is upper triangular.
Now if Q_{1} and Q_{2} are orthogonal, then from properties of matrix multiplication,
Q1Q2 (Q1Q2 )T = Q1Q2QT2QT1 = Q1IQT1 = I
and similarly
(Q1Q2 )T Q1Q2 = I.
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
A = (QpQp −1⋅⋅⋅Q1)T R ≡ QR.
This proves the following theorem.
Theorem 5.7.5Let A be any real m×n matrix. Then thereexists an orthogonal matrix Q andan upper triangular matrix R having nonnegative entries on the main diagonal suchthat
A = QR
and this factorization can be accomplished in a systematic manner.