Description
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 handwriting 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.

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?

3
1 2 0 3

6
0 0 0 0
7
; b = (b_{1}; b_{2}; b_{3})^{T} .
6
7

5
2 4 0 1

Find a basis for the nullspace of A.

Find a general solution of Ax = b, when solution exists.

Find a basis for the column space of A.

What is the rank of A^{T} ?

Use the GramSchmidt procedure to nd an orthonormal basis for the row space, column
space and the nullspace of the matrix A below.

4
3
^{#}, without using MATLAB nd the value of A^{100}. HINT: You dont need to
(b) If A = ^{“} _{1}
2
multiply 100 matrices.
(c) For what range of numbers a,b are the matrices A,B positive de nite?
A =
^{2} 2 a 2 ^{3}
B =
^{2} 2 b 8 ^{3}
a
2
2
1
2
4
^{6} 2
2
a ^{7}
^{6} 4
8
7 ^{7}
6
7
6
7
4
5
4
5

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 B^{T} contains that of A^{T} .

Please decide whether each statement is TRUE or FALSE (no reasoning gives you zero points):


For any matrix A, the nullspace of A^{T} A equals the nullspace of A.

For any matrix A, the rank of A^{T} A equals the rank of A^{T} .

If A; B are orthogonal matrices then A + B is orthogonal too.



A orthogonal implies kAxk = kxk.




A orthogonal if and only if kAx Ayk = kx yk.





Let A orthogonal matrix and x_{1}; x_{2}; : : : x_{n} be an orthonormal basis for R^{n}, then Ax_{1}; : : : Ax_{n} is an orthonormal basis for R^{n} too.

Every permutation matrix P satis es P ^{2} = I

A matrix that satis es P ^{2} = I is a permutation matrix.

Multiplication of permutation matrices is commutative.





Let P be a permutation matrix their determinant is always 1.





If the matrix A has eigenvalues 2; 2; 5 then the matrix is invertible.





If Q is an orthogonal matrix then Q ^{1} is an orthogonal matrix





If A has eigenvalues 1; 1; 2 then A is diagonalizable





If S is a matrix whose columns are linear independent eigenvectors of A then A is invertible





If A is PSD and Q is orthogonal Q^{T} AQ is PSD

If A is PSD and Q is orthogonal Q^{T} AQ is diagonal



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 nonsingular 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} _{A}T
(g) Find the best straightline 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

3
1 2

6
1
1
7
6
7
column space of A = 6
1
0
7
6
7
6
7



5


1 2


Let f : R^{n} $ R^{m} be a linear map. Show how to compute the unique matrix such that f(x) = Ax for every vector in R^{n}. 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 R^{n}‘s, what is the matrix?


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 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 rstplace 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 rankaggregated list. If ties occur, then pick a ranking list that appears most often as the \tiebreaking 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.
Wborda count method (For a given vector W = (w_{1}; w_{2}; : : : ; w_{n}) with w_{1} w_{2} : : : w_{n}, each voter awards his or her rst choice candidate w_{1} points, second choice w_{2} points, and so on with w_{n} points for person last place. These are WBorda 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?

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 G_{ij} 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 rankmany rankone matrices. Suppose that G is approximated by a rankone matrix sq^{T} with s 2 R^{n} and q 2 R^{m} with nonnegative 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 s_{A}, s_{B} are the scores of those problems, s_{B} > s_{A}). The weight of the arc y_{k} associated to student k equals (approximately) the di erence of score the student received in those two problems s_{B} s_{A} = y_{k}. 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.

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;