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;
