MA1522 Linear Algebra for Computing

Chapter 5: Orthogonality, Projection, and Least Square Solution

5.1 Orthogonality
Discussion

Let u = (ui ) and v = (vi ) be vectors in Rn . Recall that

▶ The inner product of vectors u = (ui ) and v = (vi ) is defined to be

u · v = u1 v1 + u2 v2 + · · · + un vn .

▶ The norm of a vector u is

√ q
∥u∥ = u·u= u12 + u22 + · · · + un2 .
▶ The angle between nonzero vectors u, v ̸= 0 is
 
u·v
θ = cos−1 , 0 ≤ θ ≤ π.
∥u∥∥v∥

So suppose u, v ̸= 0 and u · v = 0, what is the angle between u and v?

Orthogonal

Definition
Two vectors u, v in Rn are orthogonal if
u · v = 0.

Suppose u, v ∈ Rn are orthogonal.

▶ Case 1: Either u = 0 or v = 0.

▶ Case 2: Otherwise,
u·v
cos(θ) = =0
∥u∥∥v∥
π
tells us that θ = 2, that is, u and v are perpendicular.

That is, u, v are orthogonal if and only if either one of them is the zero vector or they are perpendicular to each other.
Example

   
1 1
1. 1 ·  0  = (1)(1) + (1)(0) + (1)(−1) = 1 + 0 − 1 = 0.
1 −1

   
1 0
2. 0 · 1 = (1)(0) + (0)(1) + (0)(0) = 0 + 0 + 0 = 0.
0 0
Example

   
1 0
3. 1 · 0 = (1)(0) + (1)(0) + (0)(1) = 0 + 0 + 0 = 0.
0 1
Question

Suppose u and v are orthogonal. Is it true that for any real numbers s, t ∈ R, su and tv are orthogonal.
Orthogonal and Orthonormal Sets

Definition
A set S = {v1 , v2 , ..., vk } of vectors in Rn of vectors is orthogonal if vi · vj = 0 for every i ̸= j, that is, vectors in S
are pairwise orthogonal.

The set S = {v1 , v2 , ..., vk } is orthonormal if for all i, j = 1, ..., k,


0 if i ̸= j,
vi · vj =
1 if i = j.

That is, S is orthogonal, and all the vectors are unit vectors.
Example

For each of the following sets, decide if it is orthogonal only, orthonormal, or not orthogonal. For the sets that are
orthogonal only, normalize it to an orthonormal set, if possible.

     
 1 0 0 
1. S = 0 , 1 , 0 This set is orthonormal.
0 0 1
 

          
 1 0 −1  0 −1
2. S = 1 ,  1  ,  0  This set is not orthogonal since  1  ·  0  = −1 ̸= 0.
1 −1 1 −1 1
 
Example
      
 1 1 1 
3. S = 1 ,  0  , −2 This set is orthogonal but not orthonormal. Normalizing, we have
1 −1
  1  
 
  
 1 1 1 
√1 1 , √1  0  , √1 −2 .
 3 2 6
1 −1 1

 √   √   
 1/√2 −1/√ 2 0 
4. S = 1/ 2 ,  1/ 2  , 0 This is an orthonomal set.
0 0 1
 

     
 1 1 0 
5. S = 1 , −1 , 0 This is an orthogonal but not orthonormal set. It cannot be normalized since it
0 0 0
 
contains the zero vector.
Question

(i) Can an orthogonal set can contain the zero vector 0?

(ii) Can an orthonormal set can contain the zero vector 0?

Orthogonal to a Subspace

Definition
Let V be a subspace of Rn . A vector n is orthogonal to V if for every v in V , n · v = 0, that is, n is orthogonal to
every vector in V . We will denote it as n ⊥ V .

n⊥V ⇔ n · v = 0 for all v ∈ V

If n ̸= 0.

Remark
The zero vector 0 is orthogonal to every subspace, 0 ⊥ V .
Example
       
 x  a x
Let V = y  ax + by + cz = 0 . Let n = b . Given any vector y  in V ,
z c z
 

   
a x
b  · y  = (ax + by + cz) = 0,
c z

tells us that n is orthogonal to V . This shows that we may define a subspace plane by a nonzero orthogonal vector,

V = { v ∈ R3 v·n=0 }

for some n ∈ R3 , n ̸= 0. n is commonly known as the normal to the plane V .

More generally, a hyperplane V in Rn can be defined using a nonzero orthogonal vector,

V ={ v v · n = 0 }, for some n ̸= 0.
Orthogonal to a Subspace
Theorem
Let V be a subspace of Rn be a subspace and S = {u1 , u2 , ..., uk } be a spanning set for V , span(S) = V . Then a
vector w is orthogonal to V if and only if w · ui = 0 for all i = 1, ..., k.

Proof.
(⇒) Suppose w is orthogonal to V , w · v = 0 for all v ∈ V . Then since ui ∈ V for all i, then w · ui = 0 for all i.
(⇐) Suppose w · ui = 0 for all i = 1, ..., k. Now given any v ∈ V , since S spans V , we can write

v = c1 u1 + c2 u2 + · · · + ck uk

for some c1 , c2 , ..., ck ∈ R. Then

w·v = w · (c1 u1 + c2 u2 + · · · + ck uk ) = c1 w · u1 + c2 w · u2 + · · · + ck w · uk
= c1 (0) + c2 (0) + · · · + ck (0) = 0

which proves that w · v = 0 for all v ∈ V .

That is, to check that w is orthogonal to V , suffice to check that it is orthogonal to every vector in a spanning set.
Example
      

 1 0   w1
 1  1  w2 
Let V be a subspace spanned by S = u1 =  1 , u2 = −1. A vector w = w3  is orthogonal to V if and
    

 
2 0 w4
 
only if w · u1 = w1 + w2 + w3 + 2w4 = 0 and w · u2 = w2 − w3 = 0. That is,
  
w1 + w2 + w3 + 2w4 = 0 1 1 1 2
or w = 0.
w2 − w3 = 0 0 1 −1 0
   T
1 1 1 2 u1
Observe that the rows of the coefficient matrix are the vectors in S, A = = . Solving the
0 1 −1 0 uT
2
system,    
1 1 1 2 0 RREF 1 0 2 2 0
−−−→
0 1 −1 0 0 0 1 −1 0 0
    

 −2 −2 
    
1 , 0  .

we conclude that w is orthogonal to V is and only if it is in span   1   0 

 
0 1
 
Algorithm to check for Orthogonal to a Subspace

Theorem
Let V be a subspace of Rn and S = {u1 , u2 , ..., uk } be a spanning

set for V . Then w is orthogonal to V if and only
if w is in the nullspace of AT , where A = u1 u2 · · · uk ;

w⊥V ⇔ w ∈ Null(AT )

Sketch of Proof.
By previous theorem, w ⊥ V if and only if uT
i w = ui · w = 0 for all i = 1, 2, ..., k. By block multiplication, this is
equivalent to  T  T   
u1 u1 w 0
T T 
u  2  0
u w
   

T  2
AT w = u1 u2 · · · uk w =  .  w =  .  =  . 
 ..   ..   .. 
uT
k uT
k w 0
Example
     

 1 −2 −1 
     
1  0   0 

Let V = {(w , x, y , z) | w − x + 2y + z = 0}. S =   ,   ,   is a basis for V . Then w ⊥ V if and


 0 1 0 
0 0 1
 
 
1 1 0 0
only if −2 0 1 0 w = 0.
−1 0 0 1
   
1 1 0 0 0 1 0 0 −1 0
RREF
 −2 0 1 0 0  −−−→  0 1 0 1 0 
−1 0 0 1 0 0 0 1 −2 0
 

 1 
 
−1

⇒ w ⊥ V ⇔ w ∈ span   .
 2 

 
1
 
Orthogonal Complement

Observe that in all the examples above, the set of vectors that are orthogonal to a subspace V is a subspace. If fact,
it is the nullspace of the matrix whose rows are vectors in a spanning set of V .

Definition
Let V be a subspace of Rn . The orthogonal complement of V is the set of all vectors that are orthogonal to V , and
is denoted as
V ⊥ = { w ∈ Rn w · v = 0 for all v in V }.

Theorem

Let V be a subspace of Rn and S = {u1 , u2 , ..., uk } be a spanning set for V . Let A = u1 u2 ··· uk . Then the
orthogonal complement of V is the nullspace of AT ,

V ⊥ = Null(AT ).
Challenge

Let A be a m × n matrix. Show that the nullspace of A is the orthogonal complement of the row space of A,

Row(A)⊥ = Null(A).
5.2 Orthogonal and Orthonormal Bases
Examples

Observe that the following orthogonal sets are linearly independent.

     
 1 0 0 
1. S = 0 , 1 , 0 is linearly independent.
0 0 1
 
      
 1 0 −2 
2. S = 1 ,  1  ,  1 
1 −1 1
 
   
1 0 −2 1 0 0
RREF
1 1 1  −−−→ 0 1 0
1 −1 1 0 0 1
Examples

      
 1 1 1 
3. S = 1 ,  0  , −2
1 −1 1
 
   
1 1 1 1 0 0
RREF
1 0 −2 −−−→ 0 1 0
1 −1 1 0 0 1
 √   √   
 1/√2 −1/√ 2 0 
4. S = 1/ 2 ,  1/ 2  , 0
0 0 1
 

 √ √   
1/√2 −1/√ 2 0 1 0 0
RREF
1/ 2 1/ 2 0 −−−→ 0 1 0
0 0 1 0 0 1
Question

Which of the following statements is/are true?

1. Every orthogonal set is linearly independent.

2. Every orthonormal set is linearly independent.

Orthogonal and Orthonormal Basis
Theorem
Suppose S = {u1 , u2 , ..., uk } is an orthogonal set of nonzero vectors. Then S is linearly independent.

Proof.
Let c1 , c2 , ..., ck be coefficients such that c1 u1 + c2 u2 + · · · + ck uk = 0. For each i = 1, ..., k,

0 = ui · 0 = ui · (c1 u1 + c2 u2 + · · · + ck uk ) = c1 ui · u1 + · · · + ci ui · ui + · · · + ck ui · uk
= c1 (0) + · · · + ci ∥ui ∥2 + · · · + ck (0)
= ci ∥ui ∥2 ,

where the 4th equality follows from the fact that S is orthogonal. Since ui ̸= 0 is nonzero, this means that necessary
ci = 0 for all i = 1, ..., n. Hence, S is linearly independent.

Corollary
Every orthonormal set is linearly independent.
Orthogonal and Orthonormal basis

Definition
Let V be a subspace of Rn . A set S is an orthogonal basis (resp, orthonormal basis) for V if S is a basis of V and S
is an orthogonal (resp, orthonormal) set.
Coordinates Relative to an Orthogonal Basis

Let S = {u1 , u2 , ..., uk } be an orthogonal basis for a subspace V , and let v ∈ V . Express
v = c1 u1 + c2 u2 + · · · + ck uk as a linear combination of vectors in the basis S.

Then since S is orthogonal,

ui · v = ui · (c1 u1 + c2 u2 + · · · + ck uk ) = c1 ui · u1 + · · · + ci ui · ui + · · · + ck ui · uk
= c1 (0) + · · · + ci ∥ui ∥2 + · · · + ck (0)
= ci ∥ui ∥2 .

u1 · v/∥u1 ∥2
 
 u2 · v/∥u2 ∥2 
ui ·v
This means that ci = ∥u , for all i = 1, ..., k. Equivalently, [v] =
 
i∥
2 S  .. 
 . 
uk · v/∥uk ∥2
Coordinates Relative to an Orthogonal Basis

Theorem
Let S = {u1 , u2 , ..., uk } be an orthogonal basis for a subspace V of Rn . Then for any v ∈ V ,
     
v · u1 v · u2 v · uk
v= u1 + u 2 + · · · + uk
∥u1 ∥2 ∥u2 ∥2 ∥uk ∥2

If further S is an orthonormal basis, then

v = (v · u1 ) u1 + (v · u2 ) u2 + · · · + (v · uk ) uk .
 v·u 
1  
∥u ∥2 v · u1
 v·u1 2  v · u2 
 ∥u2 ∥2 
that is S orthogonal, [v]S =   , S orthonormal, [v]S = 
 ..  .

 . .  . 
 . 
v·uk v · uk
∥u ∥2 k
Example

 
v1
 v2 
Standard basis E = {e1 , e2 , ..., en } is an orthonormal basis. For v =  .  ∈ Rn ,
 
 .. 
vn
ei · v = v i .
 
 
e1 · v v1
 e2 · v   v 2 
Thus, [v]E =  .  =  .  = v.
   
 ..   .. 
en · v vn
Example
    
 1 1 
S = u1 = 1 , u2 = −1 is an orthogonal basis for the hyperplane V in R3 defined by z = 0.
0 0
 
 
x
For any v = y  ∈ V , v · u1 = x + y , and v · u2 = x − y . So,
0
! !
v · u1 v · u2
v = 2 u1 + 2 u2
∥u1 ∥ ∥u2 ∥
x +y x −y
= u1 + u2 .
2 2
That is,
 x+y 
[v]S = 2 .
x−y
2
Example

      
 1 1  2
S = √13 1 , √12  0  and V = span(S). S is an orthonormal basis for V . Let v = 1 ∈ V . Then
1 −1 0
 

             
1 2 1 1 2 1
v =  √1 1 · 1 √1 1 +  √1  0  · 1 √1  0 
3 1 0 3 1 2 −1 0 2 −1
   
  1   1
3 1 2 1
= √ √ 1 + √ √ 0
3 3 1 2 2 −1

That is, √ 
3
[v]S = √ .
2
Question

Note
that this
 only
 worksif 
S= {u1 , u2 , ...,uk 
} is an orthogonal or orthonormal basis. Example,
 1 1  2
S = u1 = 1 , u2 = 0 , and w = 1. Then
0 0 0
 

     
    1 1 7
w · u1 w · u2 3  1
u1 + u2 = 1 + 2 0 = 3 ̸= w.
∥u1 ∥2 ∥u2 ∥2 2 2
0 0 0

Why is this so?

Challenge

Let V be a subspace of Rn and S an orthonormal basis of V . Show that for any u, v ∈ V ,

1. u · v = [u]S · [v]S .

2. ∥u − v∥ = ∥[u]S − [v]S ∥.
Discussion


Let S = {u1 , u2 , ..., uk } be a set of vectors in Rn . Construct the n × k matrix Q = u1 u2 ··· uk whose
columns are the vectors in S. Consider the product
 T  T
u1 u1 uT T
  
u1 1 u2 · · · u1 uk u1 · u1 u1 · u2 ··· u1 · uk
uT T T T

 2 1u u u2 2u · · · u u
2 k  2 · u1
u u2 · u2 ··· u2 · uk 
   
 2
QT Q =  .  u1 u2 · · · uk =  . = . ..  ,

. . .
..   .. .. ..
 ..   .. .. .. 
. . . 
T T T T uk · u1 uk · u2 ··· uk · uk
uk uk u1 uk u2 · · · uk uk

that is, the (i, j)-entry of the product QT Q is the inner product ui · uj . Hence,
 
orthogonal T a diagonal matrix
S is ⇔ Q Q is .
orthonormal the identity matrix

▶ In particular, if k = n, then Q is a square matrix and QT Q = In implies that QT = Q−1 .

▶ That is, S is orthonormal if and only if QT = Q−1 .
Orthogonal matrices

Definition
A n × n square matrix A is orthogonal if AT = A−1 , equivalently, AT A = I = AAT .

Theorem
Let A be a square matrix of order n. The following statements are equivalent.
(i) A is an orthogonal matrix.

(ii) The columns of A form an orthonormal basis for Rn .

(iii) The rows of A form an orthonormal basis for Rn .

Remarks

▶ Note that A is an orthogonal matrix if and only if the columns/rows form an orthonormal basis for Rn .

▶ We do not have a name given to matrices whose the rows or columns form an orthogonal basis.

▶ While some textbooks may define a square matrix whose inverse is the transpose as an orthonormal matrix, this
course will follow the majority of the literature and call it an orthogonal matrix instead.
Example
 
1 0√ 0√
1. A = 0 1/√2 −1/√ 2.
0 1/ 2 1/ 2
    
1 0√ 0√ 1 0√ 0√ 1 0 0
AT A = 0 1/ √2 1/√2 0 1/√2 −1/√ 2 = 0 1 0
0 −1/ 2 1/ 2 0 1/ 2 1/ 2 0 0 1

 √ √ √ 
1/√3 1/ √2 1/√6
2. A = 1/√3 −1/ 2 1/ √6 .
1/ 3 0 −2/ 6
√ √ √  √ √ √   
1/√3 1/ √3 1/ 3 1/√3 1/ √2 1/√6 1 0 0
AT A = 1/√2 −1/√ 2 0√  1/√3 −1/ 2 1/ √6  = 0 1 0
1/ 6 1/ 6 −2/ 6 1/ 3 0 −2/ 6 0 0 1
Question

 
1/2 1/2 √0
1/2 −1/2 2/2 
Let A = 
1/2
. Then
1/2 √0

1/2 −1/2 − 2/2
 
  1/2 1/2 √0
 
1/2 1/2 1/2 1/2 1 0 0
1/2 −1/2 2/2 
AT A = 1/2 −1/2
√ 1/2 −1/2
√

1/2
 = 0 1 0 .
1/2 √0

0 2/2 0 − 2/2 0 0 1
1/2 −1/2 − 2/2

Is A an orthogonal matrix?
5.3 Orthogonal Projection
Question

Let S = {u1 , u2 , ..., uk } be an orthonormal basis for a subspace V of Rn . We have seen that if v is in V , then

v = (v · u1 )u1 + (v · u2 )u2 + · · · + (v · uk )uk .

Suppose now w is a vector not in V , w ̸∈ V. What is

w′ = (w · u1 )u1 + (w · u2 )u2 + · · · + (w · uk )uk ?

1. Is it a vector in V ?

2. Is it equal to w?

3. Is there a geometrical interpretation of w′ ?

Example
          
 x  1  1 0 
Let V = y  z =0 and w = 1. e1 = 0 , e2 = 1 is an orthonormal basis for V . Then
z 1 0 0
   

 
1
w′ = (w · e1 )e1 + (w · e2 )e2 = 1.
0
    
 1 1 
Consider now another orthonormal basis v = √12 1 , u = √12 −1 for V . Check that
0 0
 

 
1
w′ = (w · v)v + (w · u)u = 1.
0

It seems that regardless of the choice of orthonormal basis for the result is the same.
Discussion

Recall that the angle between 2 nonzero vectors u and v is

given by
u·v
cos(θ) = .
∥u∥∥v∥
Recall also that the projection of u onto the direction of v
is
v u·v v u·v
∥u∥ cos(θ) = ∥u∥ = v.
∥v∥ ∥u∥∥v∥ ∥v∥ v·v
Discussion
▶ Now suppose S = {u1 , u2 } is an orthogonal basis for a subspace V . Then

▶ Then w′ = w·u1 w·u2

u1 ·u1 u1 + u2 ·u2 u2 is the projection of w onto span(S) = V .

▶ Moreover, the vector w′ is independent of the choice of orthogonal basis for V . See
https://www.geogebra.org/m/mndafgcp.
Orthogonal Projection
Theorem (Orthogonal projection theorem)
Let V be a subspace of Rn . Every vector w in Rn can be decomposed uniquely as a sum

w = wp + wn ,

where wn is orthogonal to V and wp is a vector in V , wn ⊥ V , wp ∈ V . Moreover, if S = {u1 , u2 , ..., uk } is an

orthogonal basis for V , then
w · u1 w · u2 w · uk
wp = u1 + u2 + · · · + uk .
u1 · u1 u2 · u2 uk · uk

Definition
Define the vector wp in the theorem above as the
orthogonal projection (or just projection) of w onto
the subspace V .
Example

      
 1 1  1
S= v= √1 1 , u = √1 −1 is an orthonormal basis subspace V in R 3
defined by z = 0. Let w = 1.
2 2
0 0 1
 
Then    
1 0
wp = (w · v)v + (w · u)u = 1 , and wn = w − wp = 0 .
0 1
It is clear that wp is in V and wn is orthogonal to V .
Best Approximation Theorem

Theorem (Best approximation theorem)

Let V be a subspace of Rn and w a vector in Rn . Let wp be the projection of w onto V . Then wp is vector in V
closest to w; that is,
∥w − wp ∥ ≤ ∥w − v∥
for all v in V .

Proof.
For any v in V , v − wp is in V . Thus, v − wp is
orthogonal to w − wp . Hence, by Pythagorean theorem,

∥w − v∥2 = ∥w − wp ∥2 + ∥v − wp ∥2 .

Since ∥v − wp ∥2 ≥ 0, the inequality ∥w − wp ∥ ≤ ∥w − v∥

is established.
Question

Let V be a subspace in Rn and let w be a vector in V . In the decomposition

w = wp + wn ,

where wp is the projection of w onto V and wn is orthogonal to V , what is wp and wn ?

Challenge

Prove the orthogonal projection theorem.

Theorem (Orthogonal projection theorem)

Let V be a subspace of Rn . Every vector w in Rn can be decomposed uniquely as a sum

w = wp + wn ,

where wn is orthogonal to V and wp is a vector in V , wn ⊥ V , wp ∈ V .

Introduction to Gram-Schmidt Process

▶ To compute the projection of a vector w onto a subspace V , we need to find an orthogonal or orthonormal basis.

▶ Suppose now S is a basis for a subspace V . The Gram-Schmidt process converts S to an orthonormal basis.

▶ Given a linear independent set {u1 , u2 , ..., uk }, we want to find an orthogonal set {v1 , v2 , ..., vk } such that
span{u1 , u2 , ..., uk } = span{v1 , v2 , ..., vk }.
▶ Let v1 = u1 , then span{u1 } = span{v1 }.

▶ If we let v2 = u2 − u′2 , where u′2 is the projection of u2 onto span{v1 }, then v2 is orthogonal to v1 . Moreover, it
should be clear that span{u1 , u2 } = span{v1 , v2 }.
▶ Continue this process, where we define vi+1 = ui+1 − u′i+1 , where u′i+1 is the projection of ui+1 onto
span{u1 , u2 , ..., ui }.
▶ Then {v1 , v2 , ..., vk } will be an orthogonal set such that span{u1 , u2 , ..., uk } = span{v1 , v2 , ..., vk }.

▶ If we normalize {v1 , v2 , ..., vk }, we will have an orthonormal basis.

Gram-Schmidt Process
We will give a visualization of the Gram-Schmidt process in R3 .

⇓
Gram-Schmidt Process
Let S = {u1 , u2 , ..., uk } be a linearly independent set. Let

v1 = u1
 
v1 · u2
v2 = u2 − v1
∥v1 ∥2
   
v1 · u3 v2 · u3
v3 = u3 − v1 − v2
∥v1 ∥2 ∥v2 ∥2
..
.      
v1 · uk v2 · uk vk−1 · uk
vk = uk − v1 − v2 − · · · − vk−1 .
∥v1 ∥2 ∥v2 ∥2 ∥vk−1 ∥2

Then {v1 , v2 , ..., vk } is an orthogonal set (of nonzero vectors), and hence,
 
v1 v2 vk
, , ...,
∥v1 ∥ ∥v2 ∥ ∥vk ∥

is an orthonormal set such that span{v1 , ..., vk } = span{uk , ..., uk }.

Example
     
 1 1 1 
Convert S = 2 , 1 , 1 into an orthonormal basis for R3 .
1 1 2
 

 
1
v1 = 2
1
     
1 1 1
2 1
v2 = 1 − 2 = −1 ,
3 3
1 1 1
       
1 1 1 −1
5 2 1
v3 = 1 − 2 − −1 =  0 
6 3 2
2 1 1 1
       
 1 1 −1 
So √16 2 , √13 −1 , √12  0  is an orthonormal basis for R3 .
1 1 1
 
Discussion

Let S = {u1 , u2 , u3 , u4 } be a set in R4 . After performing the Gram-Schmidt process on S, v4 = 0, but v3 ̸= 0. What
can you conclude?
5.4 QR Factorization
QR Factorization
Suppose now A is a m × n matrix with linearly independent columns, i.e. rank(A) = n. Write


A = a1 a2 · · · an .

Since the set S = {a1 , a2 , ..., an } is linearly independent we may apply the Gram-Schmidt process on S to obtain an
orthonormal set {q1 , q2 , ..., qn }. Set

Q = q1 q2 · · · qn .
Recall that for any j = 1, 2, ..., n, span{a1 , a2 , ..., aj } = span{q1 , q2 , ..., qj }. In particular, aj is in span{q1 , q2 , ..., qj }.
Thus we may write
 
r1j
 .. 
.
 

 rjj 
aj = r1j q1 + r2j q2 + · · · + rjj qj + 0qj+1 + · · · + 0qn = q1 · · · qj · · · qn  0

 
 .. 
.
0
QR Factorization
Explicitly,
 
r11
0

 Thus, we may write

a1 = r11 q1 = q1 ··· qn  . 
 .. 

A = a1 a2 ··· an
0  
  r11 r12 ··· r1n
r12
0

 r22 ··· r2n 
r22 

 = q1 q2 ··· qn  .
 
··· .. .. .. 
a2 = r12 q1 + r22 q2 = q1 qn  .   .. . . . 
 .. 
0 0 ··· rnn
0
= QR
..
. 
r1n
 for some m × n matrix Q with orthonormal columns,
and a upper triangular n × n matrix R.
r2n 

 
an = r1n q1 + r2n q2 + · · · + rnn qn = q1 ··· qn  . 
 .. 
rnn
Exercise

1. Prove that QT Q = In .

2. Prove that the diagonal entries of R are positive, rii > 0 for all i = 1, ..., n.

 
r11 r12 ··· r1n
0 r22 ··· r2n 
3. Prove that the upper triangular matrix R =  . ..  is invertible.
 
.. ..
 .. . . . 
0 0 ··· rnn
QR Factorization

Theorem (QR Factorization)

Suppose A is a m × n matrix with linearly independent columns. Then A can be written as

A = QR

for some m × n matrix Q such that QT Q = In and invertible upper triangular matrix R with positive diagonal entries.

Definition
The decomposition given in the theorem above is called a QR factorization of A.
Example
 
1 0 0
1 1 0
Find a QR factorization of A = 
1
.
1 1
1 1 1

 
1
1
v1 = 
1 ,
 ∥v1 ∥ = 2
1 So,
      √
0 1 −3/4 √

1/2 − 3/2

3 √ p0
1 =  1/4  , ∥v2 ∥ = 3
1
− √
   1/2 1/(2 3) 2/3
v2 1 −
=  √

4 1  1/4  2 Q=
 .
1/2 1/(2√3) 1/√6 
1 1 1/4
        1/2 1/(2 3) 1/ 6
0 1 −3 0 r
0 11 − 1  1  = −2/3 , ∥v3 ∥ = 2
    
v3 1 −
=  
2 1 6  1   1/3  3
1 1 1 1/3
Example

To compute R, recall that QT Q = I. So, premultiplying QT to both sides of the equation A = QR, we have

QT A = QT QR = R.

1 1 1

1  1

0 0
  
2
√ 2 2 2 2 √3/2 1√
− 3 1
√ 1
√ 1  1
√ 1 0 

R= 2 2q3 2 3 2 3 
 = 0 3/2 1/ 3  .
1 1 1 p
0 − 2 √1 √1 0 0 2/3
3 6 6 1 1 1
Hence,  √ 
1/2 − 3/2
√ p0
 
2 √3/2 1√
1/2 1/(2 3)
√ − √ 2/3
 0
A=
 3/2 1/ 3 
1/2 1/(2√3) 1/√6  p
0 0 2/3
1/2 1/(2 3) 1/ 6
Algorithm to QR Factorization

Let A be a m × n matrix with linearly independent columns.

1. Perform Gram-Schmidt on the columns of A = a1 a2 ··· an to obtain an orthonormal set {q1 , q2 , ..., qn }.


2. Set Q = q1 q2 ··· qn .

3. Compute R = QT A.
Exercise

Use QR factorization to prove the following

Corollary
Suppose A is a m × n matrix with linearly independent columns, i.e. rank(A) = n. Then AT A is invertible, and A
has a left inverse; that is, there is a B such that
BA = In .
5.5 Least Square Approximation
Introduction
▶ Recall that the column space of a m × n matrix A is the set of all vectors b such that Ax = b is consistent,

Col(A) = { b ∈ Rm Ax = b is consistent } = { Au u ∈ Rn }.

▶ Now suppose Ax = b is inconsistent, that is, b is not in the column space of A.

▶ We may ask for a vector b′ in the column of A that is the closest to b, that is, find a u such that Au = b′ is the
closest to b.
▶ This is equivalent to finding a u in Rn such that ∥Au − b∥ is minimized.
Least Square Approximation

Definition
Let A be a m × n matrix and b a vector in ∈ Rm . A vector u in Rn is a least square solution of Ax = b if for every
vector v ∈ Rn ,
∥Au − b∥ ≤ ∥Av − b∥.

Geometrically, by the best approximation theorem, the vector b′ = Au in Col(A) closest to b is the projection of b
onto Col(A).
Least Square Approximation

Theorem
Let A be a m × n matrix and b a vector in Rm . A vector u in Rn is a least square solution to Ax = b if and only if
Au is the projection of b onto the column space of Col(A).

Theorem
Let A be a m × n matrix and b a vector in Rm . A vector u in Rn is a least square solution to Ax = b if and only if u
is a solution to AT Ax = AT b.

Proof.
Au is the projection of b onto the column space of A if and only if Au − b is orthogonal to the column space of A.
By the orthogonal to a subspace theorem, since the columns of A spans the column space of A, Au − b is
orthogonal to the column space of A if and only if Au − b is in the nullspace of AT ,

AT (Au − b) = 0

Rearranging the equation, we have

AT Au = AT b.
Examples

   
1 1 0 1 1
Let A = 0 1 1 0 and b = 1. Is Ax = b consistent?
1 2 1 1 1
   
1 1 0 1 1 1 0 −1 1 0
RREF
 0 1 1 0 1  −−−→  0 1 1 0 0 
1 2 1 1 1 0 0 0 0 1
The system is inconsistent, thus b is not in Col(A).
Example
   
1 1 0 1 1
Let A = 0 1 1 0 and b = 1. Find a least square solution of Ax = b, that is, solve AT Ax = AT b.
1 2 1 1 1
   
2 3 1 2 2
3 6 3 3
 , AT b = 4
AT A = 
  
1 3 2 1 2
2 3 1 2 2
   
2 3 1 2 2 1 0 −1 1 0
 3 6 3 3 4  RREF  0 1 1 0 2/3 
  −−−→  
 1 3 2 1 2   0 0 0 0 0 
2 3 1 2 2 0 0 0 0 0
     
0 1 −1
2/3 −1 0
 0  + s  1  + t  0 , s, t ∈ R. This shows that least square solution might not be unique.
General solution:     

0 0 1
Example

   
1 1 0 1 1
Let A = 0 1 1 0 and b = 1. Find a least square solution of Ax = b, that is, solve AT Ax = AT b.
1 2 1 1 1
     
0 1 −1
2/3 −1 0
General solution to AT Ax = AT b:
     
 0  + s  1  + t  0 , s, t ∈ R.
  

0 0 1
Now for any s, t ∈ R,        
0 1 −1 0  
2/3 −1  0  2/3 2 1
A 0  + s  1  + t  0  = A  0  = 3 1 .
         
2
0 0 1 0
So, for any choice of least square solution u, the projection Au is unique.
Example
Find the least square solutions to 

 x − y + z = 1
−x + y + z = 2


 x + z = 2
−x + y − z = −1

   
4 −3 2 2 1 0 0 1/2
RREF
(AT A | AT b) =  −3 3 −1 0  −−−→  0 1 0 1 
2 −1 4 6 0 0 1 3/2
 
1/2
Unique least square solution:  1 .
3/2
T
In this case, observe that A A is invertible. So, could have computed the least square solution by
    
11/8 5/4 −3/8 2 1/2
u = (AT A)−1 AT b =  5/4 3/2 −1/4 0 =  1  .
−3/8 −1/4 3/8 6 3/2
Challenge

Let A be a m × n matrix and b a vector in Rm . Prove that for any choice of least square solution u, that is, for any
solution u of AT Ax = AT b, the projection Au is unique.
Orthogonal Projection (Revisit)
We may use least square solutions to find the projection of a vector onto a subspace.

▶ Let V be subspace of Rn . Let S = {u1 , ..., uk } be a basis for V .

▶ Define A = u1 · · · uk , by construction, the column space of A is V , V = Col(A).

▶ Let w be a vector in Rn , and u a least square solution to Ax = w. Then wp = Au is the projection of w onto
Col(A) = V .
Orthogonal Projection (Revisit)

▶ Now u is a least square solution to Ax = w if and only if it is a solution to AT Ax = AT w. But since the
columns of A are linearly independent, AT A is invertible.
▶ This means that u = (AT A)−1 AT w.

▶ Hence, the projection is

T
wp = Au = A(A A)−1 AT w.

Theorem
Let V be a subspace of Rn and S = {u1 , u2 , ..., uk } be a basis for V . Then the orthogonal projection of a vector w
onto V is
T
wp = A(A A)−1 AT w,


where A = u1 u2 · · · uk .
Examples
       
 1 1  1 1 x
Let S = 1 , −1 and V = span(S). Let A = 1 −1. Then the orthogonal projection of w = y 
0 0 0 0 z
 
onto V is
 
1 1  −1  
2 0 x +y
A(AT A)−1 AT w = 1 −1
0 2 x −y
0 0
 
1/2 1/2  
x +y
= 1/2 −1/2
x −y
0 0
 
x
= y  .
0

Indeed, since V is the xy -plane in R3 .

Question

Suppose the system Ax = b is consistent.

1. Suppose u is a solution to Ax = b. Is u a least square solution to Ax = b?

2. Suppose u is a least square solution to Ax = b. Is u a solution to Ax = b?

Exercise

Suppose A is a m × n matrix with linearly independent columns, i.e. rank(A) = n. QR factorize A,

A = QR.

Show that the unique least square solution of Ax = b is

u = R−1 QT b.

That is, suffice to solve for

Rx = QT b.
This is easy to solve by hand since R is a upper triangular matrix (i.e. a REF).
Challenge

Let V ⊆ Rn be a subspace and suppose {w1 , w2 , ..., wk } is an orthonormal basis of V . Write

Q = w1 w2 · · · wk .

Then for any w ∈ Rn , the projection of w onto V is

QQT w.