## Description

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;