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;`