MTH 102: Linear Algebra February 20, 2013

Department of Mathematics and Statistics Time: 2 hours

Indian Institute of Technology - Kanpur Maximum Score: 60

Mid-Semester Examination

INSTRUCTIONS
i. Please write your Name, Roll Number and Section correctly on the answer booklet.
ii. Attempt each question on a new page and attempt all parts of a question at the same
place.
iii. Attempt all questions. Each question carries 12 marks.
iv. Please make a table on the front cover page indicating the question number
and respective page number.

 
1
1. Let A be a symmetric matrix of size 3 × 3 with the third column 0. It is also known
0
that A has the cofactor C23 = 1 and
   
1 3
A 1 = 1 .
2 1
(a) Write down the matrix A. Is A invertible? [8+1]
   
a11 a12
Solution: If A1 = a21  and A2 = a22  are first two columns of A respectively,
a31 a32
then from the given third column and the fact that AT = A, we have (1 mark)
a31 = 1 (1)
and (1 mark)
a32 = 0. (2)
 T  T
Now, from the condition A 1 1 2 = 3 1 1 , we also have
   
1 3
A1 + A2 + 2 0 = 1
0 1
which leads to equations (2 marks; 1 for each correct equation)
a11 + a12 = 1, (3)
and
a21 + a22 = 1. (4)
2

From the given cofactor, we have (1 mark)

1 = C23 = (−1)(a11 a32 − a31 a12 ) = −(a11 )(0) + (1)(a12 ) ⇒ a12 = 1. (5)
Using (5) in (3), we get (1 mark) a11 = 0.
From AT = A, we have (1 mark) a21 = a12 = 1,
and finally, from (4), we get (1 mark) a22 = 0.
Thus,
 
0 1 1
A = 1 0 0 .
1 0 0
The matrix A is not invertible. One can conclude this from det(A) = 0 (two identical
columns or two identical rows) or rank(A) = 2 or N(A) 6= {0}, etc. (1 mark for this
step.)
(b) Find the complete solution to [3]
 
3
Ax = 1 .
1
 
1
Solution: We already know that a particular solution is 1. (1 mark for this step.)
2
One can find a basis for the one dimensional null space of A, either directly by
observation,
  or by solving the homogeneous equation. One such basis is (1 mark)
0
 1 (any multiple of this vector also works).
-1
Hence, the complete solution is (1 mark)
   
1 0
1 + c  1 ,
2 -1
where c is an arbitrary real constant.
2. Let α with |α| < 1 be an eigen-value of a 2 × 2 symmetric matrix
 
a b
A=
b d
where non-negative entries a, b and d of A satisfy a + b = 1 and b + d = 1.
(a) Rewrite the matrix A in terms of α. In other words, describe entries a, b, d of A as
functions of α. (Hint: One method begins by finding the second eigen-value !) [6]

Solution: From equations a + b = 1 and b + d = 1, we have a = d. (1 mark)

 3

One eigen-value, say λ1 , is given to be α, i.e., λ1 = α. Let λ2 be the second eigen-

value. Then,
α + λ2 = λ1 + λ2 = Tr(A) = 2a, (6)
and
αλ2 = λ1 λ2 = det(A) = a2 − b2 = (a + b)(a − b) = 2a − 1.
Using (6) in the above equation, we get, (1 − α)λ2 = 1 − α ⇒ λ2 = 1. (2 marks for
finding the second eigen-value)
From (6), we have (3 marks; 1 each for a, b and d.)
a = d = (1 + α)/2 and b = 1 − a = (1 − α)/2.
Thus,
 
(1 + α)/2 (1 − α)/2
A= .
(1 − α)/2 (1 + α)/2
(b) Compute eigen-vectors of A. [2]
 
1
Solution: An eigen-vector corresponding to λ1 = α is (1 mark; any multiple
-1
 
1
also works) and one corresponding to λ2 = 1 is (1 mark; any multiple also works).
1
(c) Write A2013 in its simplest form, that is, write all entries of the matrix A2013 . [4]

Solution: Let, S be the eigen-vector matrix and Λ be the eigen value matrix. Then
     
α 0 1 1 −1 1 1 -1
Λ= , S= and S = .
0 1 -1 1 2 1 1
As A2013 = SΛ2013 S −1 , we have (2 marks)
    
2013 1 1 α2013 0 1 1 -1
A = .
-1 1 0 1 2 1 1
Therefore, in the simplest form, (2 marks)
 
2013 (1 + α2013 )/2 (1 − α2013 )/2
A = .
(1 − α2013 )/2 (1 + α2013 )/2

3. Suppose q1 , q2 , q3 , q4 are orthonormal vectors in R5 .

(a) Find the length of the vector v = q1 − 2q2 + 3q3 − 4q4 . [2]

Solution: By orthogonality, kvk2 = kq1 − 2q2 + 3q3√− 4q4 k2 = 1 + 4 + 9 + 16 = 30.

Therefore, the length of v, given by kvk, is equal to 30. (2 marks)
(b) What five vectors does Gram-Schmidt process produce when it orthonormalizes the
vectors q1 , q2 , q3 , q4 , u, where u is any vector in R5 outside the span of q1 , q2 , q3 and
q4 ? [5]
4

Solution: q1 , q2 , q3 , q4 and
u − (q1T u)q1 − (q2T u)q2 − (q3T u)q3 − (q4T u)q4
q5 = .
ku − (q1T u)q1 − (q2T u)q2 − (q3T u)q3 − (q4T u)q4 k
(4 marks for the correct numerator (1 each for removing components along q1 , q2 , q3
and q4 ) and 1 mark for normalizing.)
(c) If u in part (b) is the vector v in part (a), why does Gram-Schmidt process break
down? Find a non-zero vector in the nullspace of the 5 × 5 matrix [2+3]
 
A = q1 q 2 q3 q4 v .

Solution: Gram-Schmidt fails because v is a linear combination of qi ’s : 5 vectors

 T
are not linearly independent. (2 marks) A vector in N (A) is 1 -2 3 -4 -1 . (3
marks)
4. Suppose A is an m × n matrix with rank(A) = n and satisfy A = QR where the m × n
matrix Q has orthonormal columns and the matrix R is an upper-triangular matrix.
(a) Is it true that R is a square invertible matrix? Explain your answer. [2]

Solution: The matrix R is clearly an n × n matrix (follows from shapes of matrices

A and Q) (1 mark). Note that N (R) ⊆ N (QR) = N (A) = {0}. Thus, N (R) = {0}
and hence R is invertible (1 mark; any other correct reasoning is acceptable as well).
(b) Explain why column spaces of A and Q are the same. Then use this fact to show that
the projection matrix P that projects vectors in Rm orthogonally onto the column
space of A is given by [2+3]
P = QQT .

Solution:
Reasoning for C(A)=C(Q):
Clearly, C(A) = C(QR) ⊆ C(Q) (1 mark). Also, dim(C(A)) = dim(C(Q)) = n (1
mark).. Thus, C(Q) = C(A).
Alternate reasoning for C(A)=C(Q):
Clearly, C(A) = C(QR) ⊆ C(Q) (1 mark). Need to show that C(Q) ⊆ C(A). Let
x ∈ C(Q). Then there is a vector c ∈ Rn such that x = Qc. Now, x = Qc =
QRR−1 c = A(R−1 c) imply that x ∈ C(A). This shows that C(Q) ⊆ C(A) (1 mark)
and therefore C(Q) = C(A).
Method 1 for P = QQT :
In general, the projection matrix P that projects vectors in Rm orthogonally onto
the column space of A is given by P = A(AT A)−1 AT (1 mark). However, as C(A) =
C(Q), it is equivalent to find a projection matrix P that projects vectors in Rm
orthogonally onto the column space of Q (1 mark). Thus, (1 mark for using QT Q = I
to get the final expression.)
P = Q(QT Q)−1 QT = QQT (as QT Q = I).
 5

Method 2 for P = QQT :

We need to find P such that, for all b ∈ Rm ,
i. P b ∈ C(A), and
ii. b − P b ⊥ C(A).
As P b ∈ C(A) = C(Q), we can assume that P b = Qc for some c ∈ Rn (1 mark).
Also, we require 0 = QT (b − P b) = QT (b − Qc) (1 mark). Thus, QT b = QT Qc = c (1
mark). Therefore, P b = Qc = QQT b and hence the projection matrix P = QQT .
(c) Let
 
1/5 -2/5 -4/5  
2/5 1/5 2/5 1 -2 1
A= 2/5 -4/5 2/5 0 4 -1 .
 
0 0 2
4/5 2/5 -1/5
 
-1
 1
 1 .
Solve Ax = b in the least-squares sense for b =  
-2
T T
(Hint: Solve Q Ax = Q b !) [5]

Solution: The linear system QT Ax = QT b is equivalent to the upper triangular

system QT QRx = QT b. (2 marks)
 
     -1  
1 -2 1 x1 1/5 2/5 2/5 4/5   -1
T 1  
Rx = Q b ⇒ 0 4 -1 x 2 =
 -2/5 1/5 -4/5 2/5 
 1 = -1 .
 (7)
0 0 2 x3 -4/5 2/5 2/5 -1/5 2
-2
 
-2
Solving equation (7) using back-substitution yields x =  0 (3 marks; 1 for each
1
correct component.).
5. For each of the following statements, determine if it is always true. If so, answer TRUE
and explain why it is always true; otherwise answer FALSE and provide a counter example.
Note that no credit will be given to a correct guess without any explanation
or followed by an incorrect justification.
(a) There is no orthogonal matrix Q where one of its eigen-values is 0. [2]

Solution: The statement is TRUE. Every orthogonal matrix is non-singular as

columns are orthonormal and hence independent. Matrices with non-zero deter-
minant can not have a zero eigen-value (det = product of eigen-values !) (2 marks
for a correct explaination.)
(b) If A5 = 0, where 0 is a 5 × 5 matrix with all entries equal to zero, then A = 0. [2]
6

Solution: The statement is FALSE. A counter example is

 
0 0 0 0 1
0 0 0 0 0
 
0 0 0 0 0
 .
0 0 0 0 0
0 0 0 0 0
(1 mark for a counter-example and 1 mark for showing why that counter-example
works.) Easy to check that A2 = 0 and therefore A5 = 0 but A 6= 0.
(c) There is no 3 × 3 matrix A of the form
 
1 a b
A =  c 1 d
e f 1
that satisfies A2 = 2A. [4]
Solution: The statement is TRUE. Suppose there is such a matrix, then all its eigen
values are either 0 or 2. (1 mark for this observation and 1 mark for explaning why
this is true.) This is because if λ is an eigen-value of A with a non-zero eigen-vector
x, then
A2 = 2A ⇒ A2 x = 2Ax ⇒ λ2 x = 2λx ⇒ λ(λ − 2)x = 0 ⇒ λ = 0 or λ = 2.
But the sum of eigen-values of A is Tr(A) = 3 (1 mark for this observation.) which
can not be obtained by adding 0’s and 2’s. (1 mark for this observation.)
(d) If A be a 2 × 2 matrix, then N (A2 ) = N (A3 ). [4]
Solution: The statement is TRUE.
Clearly, N (Ak ) ⊆ N (Ak+1 ) and therefore dim(N (Ak )) ≤ dim(N (Ak+1 )) for all k ≥ 0.
Note that dim(N (A)) is either 0, 1 or 2.
If dim(N (A)) = 0, that is, if A is invertible, then A2 and A3 are also invertible and
hence N (A2 ) = {0} = N (A3 ). (1 mark for this observation.)
If dim(N (A)) = 2, then dim(N (A)) = dim(N (A2 )) = dim(N (A3 )) = 2. (1 mark for
this observation.)
If dim(N (A)) = 1, then either dim(N (A2 )) = 1 or dim(N (A2 )) = 2. If dim(N (A2 )) =
2, then dim(N (A2 )) = dim(N (A3 )) = 2 and long with N (A2 ) ⊆ N (A3 ) imply
N (A2 ) = N (A3 ). (1 mark for this observation.) Otherwise dim(N (A)) = dim(N (A2 )) =
1 along with N (A) ⊆ N (A2 ) imply that N (A) = N (A2 ). This in turn imply that
N (A3 ) = N (A2 ). (1 mark for this observation.)