INSTRUCTIONS
All homeworks will have many problems, both theoretical and practical.
Solutions need to be submitted via CANVAS by uploading les. 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 prob-
lem. Correct answers with no support work will not receive full credit.
1. DO NOT SUBMIT SOLUTION to problem one, only for your review!: This rst 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?2
5; 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 nd an orthonormal basis for the row space, column
space and the nullspace of the matrix A below.
, without using MATLAB nd 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 de nite?
(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 ATA equals the nullspace of A.
ii. For any matrix A, the rank of ATA 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 satis es P2 = I
viii. A matrix that satis es P2 = 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 QTAQ is PSD
xvi. If A is PSD and Q is orthogonal QTAQ 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 decompo-
sition.
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 nd the singular value
decomposition of the 2m 2m matrix:
0 AT
A 0
(g) Find the best straight-line t (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 nd the projection of b = (4;3;1;0) onto the
column space of A =
(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 rst 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 rank-
aggregation (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 rst-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 rst 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 rst 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 ve di erent vectors W
making 5 predictions of the election. Can you choose them to make any of the ve 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 di culty: 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 di culty 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 s2Rn and q2Rm
with non-negative components. Can you use this fact to give a di culty 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 di culty 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 di erence 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 di culty.
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 di culty 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 (avail-
able 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;