Solved-Project 01- Solution

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 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?

• 3

1 2 0 3

6	0 0 0 0	7	; b = (b1; b2; b3)T .
6		7

• 5

2 4 0 1

2. Find a basis for the nullspace of A.

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

2. Find a basis for the column space of A.

2. What is the rank of A^T ?

3. Use the Gram-Schmidt 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 A100. 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

4. 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 .

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

4. 1. For any matrix A, the nullspace of A^T A equals the nullspace of A.

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

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

4. 4. A orthogonal implies kAxk = kxk.

1. • 5. A orthogonal if and only if kAx Ayk = kx yk.

1. • 5. Let A orthogonal matrix and x₁; x₂; : : : x_n be an orthonormal basis for Rⁿ, then Ax₁; : : : Ax_n is an orthonormal basis for Rⁿ too.

     6. Every permutation matrix P satis es P ² = I

     7. A matrix that satis es P ² = I is a permutation matrix.

     8. Multiplication of permutation matrices is commutative.

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

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

1. • 5. If Q is an orthogonal matrix then Q ¹ is an orthogonal matrix

1. • 5. If A has eigenvalues 1; 1; 2 then A is diagonalizable

1. • 5. If S is a matrix whose columns are linear independent eigenvectors of A then A is invertible

1. • 5. If A is PSD and Q is orthogonal Q^T AQ is PSD

     6. If A is PSD and Q is orthogonal Q^T AQ is diagonal

6. 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 ¹ 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 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

• 3

1 2

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

1. 7. • 5

1 2

1. 7. Let f : Rⁿ $ R^m be a linear map. Show how to compute the unique matrix such that f(x) = Ax for every vector in Rⁿ. 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ⁿ‘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 = (w₁; w₂; : : : ; w_n) with w₁ w₂ : : : w_n, each voter awards his or her rst choice candidate w₁ points, second choice w₂ points, and so on with w_n 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 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 rank-many rank-one matrices. Suppose that G is approximated by a rank-one matrix sq^T with s 2 Rⁿ and q 2 R^m 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 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.

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;