GRAM-SCHMIDT ALGORITHM AND QR FACTORIZATION

1. Motivating Problem
In many situations we have a basis of a subspace, V , but want to find an or-
thonormal basis. This is useful, for example, in giving a formula for projV . The
Gram-Schmidt algorithm allows us to convert any basis of V to an orthonormal
basis. Strategy (for two dimensional V ):
(1) Scale first vector to make it unit.
(2) Project second vector onto orthogonal complement of first to make it or-
thogonal to first.
(3) Scale second vector to make it unit.
   
2 2
EXAMPLE: Find an orthonormal basis of V = span 2 , 0. First, set
1 2
   
2 2/3
1 1
~u1 = ~v1 = 2 = 2/3 .
||~v1 || 3
1 1/3
Next, project onto orthogonal space to ~u1
     
2 2/3 2/3
||
~v2⊥ = ~v2 − ~v2 = ~v2 − (~v2 · ~u1 )~u1 = 0 − 2 2/3 = −4/3 .
2 1/3 4/3
Finally, normalize the length of this vector:
   
2/3 1/3
1 1
~u2 = ⊥ ~v2⊥ = −4/3 = −2/3
||~v2 || 2
4/3 2/3
So ~u1 , ~u2 is an orthonormal basis of V . Observe that
~v1 = 3~u1 and ~v2 = 2~u1 + 2~u2
That is,
 
3 2
SB→U =
0 2
where
B = (~v1 , ~v2 ) and U = (~u1 , ~u2 )
In other words,
 
    3 2
~v1 | ~v2 = ~u1 | ~u2 .
0 2
1
2 GRAM-SCHMIDT ALGORITHM AND QR FACTORIZATION

2. Gram-Schmidt algorithm
We generalize the above procedure so that it holds any basis. Key Idea: Turn
a basis B = (~v1 , . . . , ~vm ) of V ⊂ Rn into a orthonormal basis U = (~un1 , o
. . . , ~um ) of
V . In order to write this most compactly, we observe that when V = ~0 , then for
any ~x,
projV (~x) = ~0.
The algorithm is:
(1) Start i = 1
(2) (Project) Let
i−1
X
~vi⊥ := ~vi − projVi (~vi ) = ~vi − (~uj · ~vi )~uj
j=1

where Vi = span(~v1 , . . . , ~vi−1 ) = span(~v1 , . . . , ~vi−1 ).

(3) (Scale) Let ~ui = ||~v1⊥ || ~vi⊥
i
(4) If i < m, then increment i and start again at (2). Otherwise, we are done.
n o
In the above, by construction, V1 = ~0 so the first projection does nothing.
Some comments:
(1) One is constructing the orthonormal basis, ~u1 , . . . , ~ui−1 , of Vi from the pre-
vious steps in the algorithm. This means one can compute the orthogonal
projection in a straightforward manner.
(2) The fact that B is a basis is what ensures that ||~vi⊥ || > 0.
EXAMPLE: Compute an orthonormal basis of
 
1 3 0 −2
ker .
0 0 1 2
This matrix is in rref already so we have
   
−3 2
 1   0 
 0  , −2
ker = span    

0 1
Lets take a basis to be    
2 −3
0 1
~v1 = 
−2 and ~v2 =  0 
  

1 0
We apply the Gram-Schmidt algorithm to this to obtain:
 
2
1 0
~u1 =  
3 −2

1
and      
−3 2 −5
1 1 2
+  =  3 
0
~v2⊥ = ~v2 − (~v2 · ~u1 )~u1 = 
     
 0  3 −2 3 −4
0 1 2
 GRAM-SCHMIDT ALGORITHM AND QR FACTORIZATION 3

and
2p 2√ √
||~v2⊥ || = (−5)2 + 32 + (−4)2 + 22 = 54 = 2 6.
3 3
Hence,    
−5 √ −5
1 3  = 6  3 .
 
~u2 = √ 
3 6 −4
  18 −4
2 2
3. QR factorization
Let B = (~v1 , . . . , ~vm ) be a basis of V ⊂ Rn . Suppose that U = (~u1 , . . . , ~um ) is
the basis obtained from B by the Gram-Schmidt algorithm. If we write
   
R = SB→U , M = ~v1 | · · · | ~vm and Q = ~u1 | · · · | ~um ,
then we have
M = QR
If one looks at how the Gram-Schmidt algorithm works, it is not hard to see that R
is upper triangular and the diagonal elements are all positive. Such a factorization
is called a QR-factorization and is useful in many computational settings. Notice,
that by definition, if M has a QR-factorization M = QR, then the columns of Q
form an orthonormal basis of Im (M ).
EXAMPLE: Compute the QR factorization of
 
2 0
M = 1 6
−2 −6
Have    
2 0
~v1 =  1  and ~v2 =  6  .
−2 −6
As such,  
2/3
1
~u1 = ~v1 =  1/3 
3
−2/3
and      
0 2/3 −4
~v2⊥ = ~v2 − (~v2 · ~u1 )~u1 =  6  − 6  1/3  =  4 
−6 −2/3 −2
and    
−4 −2/3
1  
~u2 = 4 = 2/3  .
6
−2 −1/3
Clearly, ~v1 = 3~u1 and ~v2 = 6~u1 + 6~u2 and so
   
2 0 2/3 −2/3  
1 3 6
6  =  1/3 2/3 
0 6
−2 −6 −2/3 −1/3 | {z }
| {z } | {z } R
M Q