Homework (linear algebra methods)

Homework (linear algebra methods)

INSTRUCTIONS
All homeworks will have many problems, both theoretical and practical.
Solutions need to be submitted via CANVAS by uploading files. No homeworks
will be accepted in person. Mark your team members clearly.
Write legibly preferably using word processing if your hand-writing is unclear.
Be organized and use the notation appropriately. Show your work on every problem. Correct answers with no support work will not receive full credit.
1. DO NOT SUBMIT SOLUTION to problem one, only for your review!: This first three
weeks of the course, I assume you know linear algebra. The 3 exercises below should give you a
chance to remember.
(a) For the matrix A below, under what conditions on b does the system of equations has a solution?




1 2 0 3
0 0 0 0
2 4 0 1




, b = (b1, b2, b3)
T
.
(b) Find a basis for the nullspace of A.
(c) Find a general solution of Ax = b, when solution exists.
(d) Find a basis for the column space of A.
(e) What is the rank of AT
?
(f) Use the Gram-Schmidt procedure to find an orthonormal basis for the row space, column
space and the nullspace of the matrix A below.
(b) If A =
"
4 3
1 2 #
, without using MATLAB find the value of A100. HINT: You dont need to
multiply 100 matrices.
(c) For what range of numbers a,b are the matrices A,B positive definite?
A =




a 2 2
2 a 2
2 2 a




B =




1 2 4
2 b 8
4 8 7




(d) Let A, B be real m × n matrices. Show that if the nullspace of B is contained in the nullspace
of A implies that the range of BT
contains that of AT
.
(e) Please decide whether each statement is TRUE or FALSE (no reasoning gives you zero points):
i. For any matrix A, the nullspace of AT A equals the nullspace of A.
ii. For any matrix A, the rank of AT A equals the rank of AT
.
iii. If A, B are orthogonal matrices then A + B is orthogonal too.
iv. A orthogonal implies kAxk = kxk.
v. A orthogonal if and only if kAx − Ayk = kx − yk.
vi. Let A orthogonal matrix and x1, x2, . . . xn be an orthonormal basis for Rn
, then Ax1, . . . Axn
is an orthonormal basis for Rn
too.
vii. Every permutation matrix P satisfies P
2 = I
viii. A matrix that satisfies P
2 = I is a permutation matrix.
ix. Multiplication of permutation matrices is commutative.
x. Let P be a permutation matrix their determinant is always 1.
xi. If the matrix A has eigenvalues 2, 2, 5 then the matrix is invertible.
xii. If Q is an orthogonal matrix then Q−1
is an orthogonal matrix
xiii. If A has eigenvalues 1, 1, 2 then A is diagonalizable
xiv. If S is a matrix whose columns are linear independent eigenvectors of A then A is invertible
xv. If A is PSD and Q is orthogonal QT AQ is PSD
xvi. If A is PSD and Q is orthogonal QT AQ is diagonal
(f) The Singular Value Decomposition of a matrix is very important. Here are a few theoretical
questions:
• What are the singular values of a 1 × n matrix? Write down its singular value decomposition.
• Prove that if A is a square non-singular matrix then the singular values of the A−1 are the
reciprocals of the singular values of A.
• Suppose A is an m×m matrix with SVD A = UΣV
T
. Use this to find the singular value
decomposition of the 2m × 2m matrix:
?
0 AT
A 0
?
(g) Find the best straight-line fit (least squares) to the measurements b = 4 at t = −2, b = 3 at
t = −1, b = 1 at t = 0 and b = 0 at t = 2. The find the projection of b = (4, 3, 1, 0) onto the
column space of A =







1 −2
1 −1
1 0
1 2







(h) Let f : Rn ↔ Rm be a linear map. Show how to compute the unique matrix such that
f(x) = Ax for every vector in Rn
. If we think of the space of polynomials of degree less or
equal to 5 as a vector space, its derivative is a linear map. If we think of the corresponding
isomorphic Rn
’s, what is the matrix?
2. PROJECT (linear algebra for ranking): You are supposed to use the linear algebra methods
to make a decision regarding choice of winners in elections and in rating the value of objects or
services.
For the first part of the homework we have collected the ranking of 5 presidential candidates for
more than 200 people. Using the ranking data available at
https://www.math.ucdavis.edu/~deloera/TEACHING/MATH160/rankingcandidates.dat
write MATLAB code to predict the winner of the presidential election based on the following rankaggregation (aka voting) methods. You will make a total of 8 predictions:
• Using Plurality vote method (voters top choice is counted for each candidate, winner has the
most first-place votes.)
• Using Average rank method (in this case each of n candidates has been given a position from
1 to n by each of the voters, the integers representing the positions are averaged to create
a rank-aggregated list. If ties occur, then pick a ranking list that appears most often as the
“tie-breaking list”. If i, j are in a tie, but in the list we choose i is ahead of j then that is the
order.)
• Borda count method (For n candidates each voter awards his or her first choice candidate n−1
points, second choice n − 2 points, and so on with 0 points for person last place. these are
borda points. Winner is the candidate with the most total Borda points as awarded by the
voters.
• W-borda count method (For a given vector W = (w1, w2, . . . , wn) with w1 ≥ w2 ≥ . . . ≥ wn,
each voter awards his or her first choice candidate w1 points, second choice w2 points, and so
on with wn points for person last place. These are W-Borda points. Winner is the candidate
with the most total W-borda points as awarded by the voters. Try five different vectors W
making 5 predictions of the election. Can you choose them to make any of the five candidates
win?
• Finally, use the Pagerank algorithm to rank the candidates.
• Report your predictions and compare the situation. Which is in your opinion the fairest method
to count votes?
3. PROJECT Using SVD’s or a network to decide the ranking of difficulty: An exam with
m question is given to n students of MATH 16000. The clever instructor collects all grades in an
n × m matrix G, with Gij the grade obtained by student i on question j. The professor would like
to assign a difficulty score or rating to each question based on the available data, rather than use
the subjective perception of students.
• From the theory of SVD’s we know G can be decomposed as a sum of rank-many rank-one
matrices. Suppose that G is approximated by a rank-one matrix sqT with s ∈ Rn and q ∈ Rm
with non-negative components. Can you use this fact to give a difficulty score or rating? What
is the possible meaning of the vector s? Note one can use the top singular value decomposition
to get this score vector!
• There is another way to rank the difficulty of test questions using Networks: Each student gives
scores for each problem, then we construct a network whose nodes/vertices are the problems
of the exam. There is an arc from problem A to B for student k that did better in problem B
than in problem A, (i.e., if sA, sB are the scores of those problems, sB sA). The weight of
the arc yk associated to student k equals (approximately) the difference of score the student
received in those two problems sB − sA = yk. Explain why the Massey least square method
we saw in class for rating movies can be use for rating exam problems by difficulty.
• The data available at
https://www.math.ucdavis.edu/~deloera/TEACHING/MATH160/examscores.dat
has the scores of 31 students in a 7 question exam (each problem was graded on a scale of 0
to 6). Use the data and give a rating of the difficulty of each question in the test using
– SVD method.
– Massey’s network method.
– Colley’s method.
4. PROJECT Using SVD to analyze images Download the image called mandril.mat (available at https://www.math.ucdavis.edu/~deloera/TEACHING/MATH160/mandril.mat) using the
following MATLAB command (This loads a matrix X containing a face of a cute mandrill, and a
map containing a colormap of the image. ) load mandrill;`