MIT 18.

06 Final Exam, Fall 2018: Solutions

Problem 1 (5+10 points):

The matrix A has the diagonalization A = XΛX −1 with
   
1 1 −1 0 1
 1 2 1   2 
X= , Λ =  .
 1 0   −2 
1 −1

(a) Give a basis for the nullspace N (M ) of the matrix M = A4 − 2A2 − 8I.
(Hint: not much calculation required!)
 
2
 3 
(b) Write down the solution x(t) to the ODE dx dt = Ax for x(0) =  1  .
 

−1
Your final answer should contain no matrix exponentials or matrix in-
verses, just a sum of vectors (whose components you give explicitly as
numbers) multiplied by given scalar coefficients (that may depend on t).

Solution:
(a) The eigenvalues of A are λ = 1, 2, −2, −1, from Λ. The eigenvalues of
M are then λ4 − 2λ2 − 8, with the same corresponding eigenvectors. M
therefore has two zero eigenvalues (which come from the ±2 eigenvalues
of A), and so the corresponding eigenvectors are a basis for N (M ), i.e.
   
1 −1
1  2 
N (M ) = span of 
0 ,  1  .
  

0 0

(b) We know that the general solution to the ODE may be written as
       
1 1 −1 0
t 0 2t 1 −2t  2  −t 1
       
x(t) = c1 e   + c2 e   + c3 e  1  + c4 e 0
0 0
0 0 0 1

1
 where c1 , c2 , c3 and c4 are constants that are determined by the initial
condition: Xc = x(0). Since X is upper triangular, we can solve for c by
backsubstitution:

c1 + c2 − c3 = 2,
c2 + 2c3 + c4 = 3,
c3 = 1,
c4 = −1.

Backsubstitution gives c1 = 1, c2 = 2, c3 = 1 and c4 = −1.

Problem 2 (3+3+3+3+3 points):

The real m × n matrix A has a QR factorization A = QR of the form
 
1 −2 2 0 0 0

 2 −3 0 0 0 


 1 0 0 0 
Q = q1 q2 q3 q4 q5 q6 , R =  .

 3 1 −1 

 1 2 
1

where q1 , . . . , q6 are six orthonormal vectors in Rm .

(a) Give as much true information as possible about m, n, and the rank of A.
(b) If a5 is the 5th column of A, write it in the basis q1 , . . . , q6 , i.e. write
it as a5 = c1 q1 + c2 q2 + · · · + c6 q6 , by giving the numerical values of the
coefficients c1 , · · · , c6 .
(c) What is ka5 k?
(d) This pattern of zero entries in R means that columns .......... of A must
be .......... to columns .......... of A.
(e) If A is a square matrix, what is | det A| (the absolute value of the deter-
minant)?

Solution:
(a) Since R is 6 × 6 , A must have 6 columns so that n = 6. The column
space of A is spanned by 6 orthonormal vectors, so the rank of A is 6. The
number of rows must be greater than or equal to the rank, so m ≥ 6.
(b) From the QR factorization we see that a5 = q4 + q5 : this is just Q multi-
plied by the 5th column of R.
(c) ka5 k2 = aT5 a5 = (q4 + q5 )T (q4 + q√5 ) = kq4 k2 + kq5 k2 = 2 (from orthonor-
mality of the q’s) and so ka5 k = 2.

2
 (d) This pattern of zero entries in R means that columns 1–3 of A must be
orthogonal to columns 4–6 of A. (Columns 1–3 of A are spanned by
q1 , q2 , q3 , whereas columns 4–6 are spanned by q4 , q5 , q6 . Equivalently, to
get that 3×3 block of zeros in the upper-right corner of R, a Gram–Schmidt
process must have encountered dot products that were already zero when
projecting columns 4–6 to be orthogonal to the first three columns.)
(e) By properties of the determinant, we know that det A = det Q det R. Since
Q is an orthogonal matrix, we know that det Q = ±1. Since R is an
upper triangular matrix, we know that det R is the product of the diagonal
elements of R, i.e. det R = 6. Hence, | det A| = 6.

Problem 3 (8+3+4 points):

You are given the matrix
 
1 2 1 0
A= 2 5 1 1 
0 1 1 3
(a) Give bases for the four fundamental subspaces of A.
(b) Which of Ax = b or AT y = c will not have unique solutions for x or y
(assuming a solution exists)?
(c) Which of Ax = b or AT y = c may not have a solution? For that equation,
give a right-hand side (b or c) for which a solution exists, and that has
only two nonzero entries in the right-hand side.

Solution:
(a) We can use row operations to put A into reduced row echelon form (rref):
 
1 0 0 −5
A → 0 1 0 2 .
0 0 1 1
From here we can see that A is a rank 3 matrix: The column space of A
is three dimensional, but the column space of A is a subspace of R3 . So
any three, linearly independent vectors in R3 will form a basis for C(A).
For example, we can use the standard basis, or we could use the columns
of A that correspond to the pivot columns:
     
1 0 0
C(A) = span of 0 , 1 , 0
0 0 1
     
1 2 1
= span of 2 , 5 , 1 .
0 1 1

3
 The row space is also three dimensional. Since the row space is preserved
by row operations, we can use the rows of the rref matrix (this is useful
for part c):      
1 0 0
0    0
1
C(AT ) = span of 
     
 0  , 0 , 1 .
−5 2 1
The nullspace has dimension 4−3 = 1. So there is a single special solution
to Ax = 0:  
5
−2
N (A) = span of 
−1 .


1
Finally, the left nullspace has dimension 3 − 3 = 0 , and so is a trivial
vector space only containing the zero vector, i.e.
n o
N (AT ) = ~0

(b) Since dim(N (A)) > 0 , Ax = b does not have a unique solution: we can
add any nonzero vector from the nullspace to a particular solution of the
system to get a different solution.
(c) Since C(AT ) 6= R4 , AT y = c may not have a solution. In fact, it will only
have a solution if c ∈ C(AT ). To give an example of such a c with only
two nonzero entries, we can use any of the three basis vectors we wrote
down in part (a), e.g.  
1
0
c= 0 .


−5
T ⊥
Alternatively, we can
 use the fact that C(A ) = N (A) : we only have
5
−2
a solution if c ⊥ 
−1, where we used the N (A) basis from (a). So,


1
 
c1
c2 
for example, if we look for a c of the form 
 0 , we get the condition


0 
2
5
5c1 − 2c2 = 0. For example, we could use c = 0.


4
Problem 4 (5+10 points):
A vector x̂ minimizes kAx − bk over all possible vectors x.

(a) If x̂ = 0, then b must be in which fundamental subspace of A?

   
1 2 1
(b) If A =  0 0  and b =  1 , what is the minimum possible kAx −
0 0 1
bk? Describe (with as much detail as you can) all possible x̂ that give this
minimum.

Solution:
(a) If x̂ minimizes kAx − bk over all possible vectors x, then AT Ax̂ = AT b. If
x̂ = 0, then AT b = 0, and so b ∈ N (AT ). Another way to see this is that
if x̂ = 0, then the projection of b onto the column space of A is the zero
vector, which means that b must be orthogonal to C(A), i.e. b ∈ N (AT ).
(b) The minimum possible kAx − bk occurs when p = Ax is the projection of
b onto the column space of A.The column space of A is one dimensional,
1
and is spanned by the vector 0, and so we can compute this projection
0
easily using the projection formula:
 T  
1 1
0 1    
0 1 1 1
p =  T   0 = 0 .
1 1 0 0
0 0
0 0
   
1 1 √
So the minimum value of kAx − bk is given by 0 − 1 = 2.
0 1
To find a particular x̂ that gives thisminimum,
 we firstly find an x̂ that
1
satisfies Ax̂ = p , for instance x̂ = . We can then add to this any
0  
2
multiple of a vector in N (A), which is spanned by . The most
−1
general x̂ then takes the form:
   
1 2
x̂ = +c ,
0 −1

where c is some constant.

5
Problem 5 (5+10 points):
Suppose that A = AT is a real-symmetric 10 × 10 matrix whose eigenvalues are
11, 10, 9, 8, 7, 6, 5, 4, 3, 2. Corresponding eigenvectors of A, each normalized to
have length kxk = 1, are (to three significant digits) the columns of the matrix:
 
−0.179 0.415 −0.173 0.115 −0.125 0.079 −0.676 −0.066 0.3 −0.423
−0.239 −0.168 −0.53 −0.08 0.232 −0.281 −0.386 −0.223 −0.353 0.413 
 
 −0.35 0.116 −0.201 −0.41 0.547 0.197 0.182 0.373 0.38 0.029 
 
−0.399 −0.238 −0.079 −0.46 −0.279 −0.139 0.259 −0.427 −0.028 −0.468
 
−0.378 −0.132 0.013 0.28 −0.374 −0.332 0.096 0.056 0.582 0.4 
X= −0.227 0.352
.
 0.195 0.336 0.388 0.137 0.242 −0.657 0.042 0.109 

−0.404 0.327 0.566 −0.143 0.024 −0.399 −0.123 0.277 −0.371 0.03 
 
−0.001 0.628 −0.369 −0.162 −0.46 0.172 0.3 0.05 −0.202 0.261 
 
−0.303 −0.07 −0.331 0.6 0.07 −0.052 0.288 0.329 −0.29 −0.389
−0.425 −0.285 0.195 0.047 −0.213 0.732 −0.194 0.051 −0.194 0.195

(That is, the first column of X is an eigenvector for λ = 11, and so on.)
Consider the recurrence relation xn+1 − xn = −αAxn on vectors xn ∈ R10 ,
where α > 0 is some positive real number.
(a) For what values of α (if any) can the recurrence have solutions that diverge
in magnitude as n → ∞?
For α= 1, give a good approximation for the vector x100 given x0 =
(b) 
1
 0 
 
 0 
 
 0 
 
 0 
 0 . You can leave your answer in the form of some vector times
 
 
 0 
 
 0 
 
 0 
0
some coefficient(s) without carrying out the multiplications, but give all
the numbers in your coefficients and vectors to 3 significant digits.

Solution:
(a) We can rewrite the recurrence relation as xn+1 = (I − αA)xn . The so-
lutions xn can diverge provided I − αA has at least one eigenvalue with
absolute value greater than 1. The eigenvalues of I − αA are 1 − αλ, where
λ is an eignvalue of A. Since α > 0, and all the eigenvalues are positive,
2
divergence can first occur when 1 − 11α < −1, i.e. when α > 11 .
(b) Suppose α = 1. We know that x100 = (I − A)100 x0 . We can write any
P10
x0 in terms of the eigenvector basis as x0 = i=1 ci vi , where vi is the

6
 ith column of X. The eigenvalue of (I − A) with largest absolute value
is 1 − 11 = −10, with eigenvector v1 , and so x100 ≈ c1 (−10)100 v1 . Since
the eigenvectors are orthogonal (A is real-symmetric with distinct λ’s), we
can compute c1 using projection:

v1T x0
c1 = = −0.179,
v1T v1

(where v1T v1 = 1 since you were told that the columns are normalized)
and so:
 
0.179
0.239
 
 0.35 
 
0.399
 
100 100 0.378
 
x100 ≈ −0.179 × (−10) v1 = 0.179 × 10  .
 0.227 
0.404
 
0.001
 
0.303
0.425

(Indeed, we could write down the “exact” x100 by including all of the other
eigenvectors. But you actually gain no accuracy by doing so: you were
only given the eigenvectors to three significant digits, but 9100 is more
than 104 times smaller than 10100 , so all of the “corrections” from the
other eigenvectors are too small to be distinguished from the unknown
digits of our coefficients.)

Problem 6 (5+10 points):

√data points (tk , yk ) = (1, 6), (4, 7), (9, 12), (16, 14)
You are trying to fit of a sequence of four
to a function of the form y(t) = α + β t for unknown coefficients α and β .
(a) Write down a minimization problem of the form “minimize ............. over
all possible α, β” that we could solve for a “best fit” curve using 18.06
techniques. (Don’t solve it.)
(b) Write down a 2 × 2 system of equations of the form
    
some α some
=
matrix β vector

whose solution gives the “best” fit coefficients α and β for your minimiza-
tion problem from part (a). You don’t need to solve it! You can leave
the matrix and vector as a product of other matrices/vectors/transposes,
but give the numerical values of each of the terms (no matrix inverses
allowed).

7
Solution:
(a) The thing we know how to do in 18.06 is to find the
√ least-squares fit of
our data. For a function of the form y(t) = α + β t, we therefore want
to minimize
4
X √
(yk − α − β tk )2 ,
k=1

over all (real) αand β.

(b) We can write the minimization problem in matrix form as

min kAx − bk2 ,

x

where
 √     
1 √1 1 1   6
1 4  1 2 α 7
A= √ = , x= , b=
12 .

1  1 3 β
√9
1 16 1 4 14

The solution to this minimization problem is then given by x̂, where x̂

satisfies the normal equations:

AT Ax̂ = AT b.

Problem 7 (10 points):

Suppose that you want to multiply each of the three matrices
 
  1 1
1 2

A= , B =  −1 0 , C = 4 5 ,
3 4
0 1

by each of the two vectors x, y ∈ R2 . That is, you want to compute the six
vectors xA = Ax, xB = Bx, xC = Cx, yA = Ay, yB = By, and yC = Cy. Write
all of these products in the form of a single matrix–matrix multiplication:
   
some matrix in terms of some matrix in terms of

= x y .
xA , xB , xC , yA , yB , yC A, B, C

Note that the third matrix here is the 2 × 2 matrix whose columns are x and y.
That is, give the sizes of the other two matrices and how their contents
are arranged.
[For example, a possible but wrong(!) answer for the second matrix would
be the 2 × 6 matrix A B T C T .]

8
Solution:
We can write all of these products as the following single matrix-matrix multi-
plication:    
xA yA A

xB yB  = B  x y .
xC yC C
The first and second matrices are both 6 × 2 matrices, while the third is a 2 × 2
matrix.