Please answer the following questions in complete sentences in a typed, clearly prepared manuscript and submit the solution by the due date on Blackboard (Monday, October 30th, 2017, around 4-5 am)
Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.
Make sure you have included your source-code and prepared your solution according to the most recent Piazza note on homework submissions.
People seem to like these questions!
The eigenvalues of an real-valued matrix are always real.
The solution to is unique for any .
Every matrix can be written as the sum of two non-singular matrices.
An real-valued matrix has an orthogonal set of eigenvectors.
An matrix and its transpose have the same set of eigenvalues.
We'll show that the humble power-method is really rather more interesting than we saw in class! It's a flexible starting point that serves as the basis for almost all of the eigenvalue algorithms.
(Warm up) Consider the power method as a Julia code:
maxit = 1000
lam = 0
for i=1:maxit
x = A*x
x = x./norm(x)
lam = x'*A*x
end
Let be the value of x
at the start of the th
instance of this loop. And let be the value of
lam
at the start of the th iteration. Suppose that
and are the true eigenvector, eigenvalue pair that we
are converging too. If , show
that: is (where the
constant may depend on the matrix ).
(Warm up) Show that if is an eigenvector of with eigenvalue , then is an eigenvector of . What is the eigenvalue?
Let have a complete set of eigenvalues , for all and associated eigenvectors . For the sake of simplicity, let's suppose that all the eigenvalues are real. Suppose we run the following Julia code:
maxit = 1000
F = lufact(A)
for i=1:maxit
x = F\x
x = x./norm(x)
lam = x'*A*x
end
Does this converge? If so, what does it converge to, and how fast does it converge?
Make the power method converge faster to any eigenvalue, eigenvector pair! Dense linear algebra is cheap. Work in pairs. Your friend says that you should look at this algorithm:
maxit = 1000
for i=1:maxit
x = (A - lam*eye(size(A,1)))\x)
x = x./norm(x)
lam = x'*A*x
end
This algorithm is called "Rayleigh Quotient Iteration" and the standard result is that converges to an eigenvector cubically. That is, of , then . Look up this result in a textbook, or on the web, and explain the proof in your own words.
In class, I derived PageRank as the solution of the linear system: where is a column-stochastic matrix, and is a non-negative vector whose elements sum to 1.
(Warm up) Use eigenvalue properties of to show that it is a non-singular matrix. (Hint: recall that for any norm. Is there a norm where we know has a known value?)
The standard definition of PageRank is as the largest eigenvector of the matrix: normalized to have sum one (instead of the standard 2-norm scaling). Consider the power method, without normalization, applied to starting from the vector : Show that the iterates from this method are always non-negative and sum to 1.
Use this fact to simplify the iteration and show that the power method will converge to the solution of the linear system . You should get the same iteration that I discussed in class.
Download the data purdue_web.mat
from
http://www.cs.purdue.edu/homes/dgleich/cs515-2017/homeworks/purdue_web.mat
Load the data.
using MAT
file = matopen("purdue_web.mat")
urls = read(file, "urls")
P = read(file, "P")
close(file)
It contains the matrix for Purdue's website
from 2001. The url
variable contains the URL for each row/column
of the matrix. Use url[1]
to show the first url.
n = size(P,1)
v = ones(n)./n
alpha = 0.85
What is x[1]
? Use the following code to sort the vector and output
the top 27 entries:
p = sortperm(x,rev=true);
urls[p[1:27]]
Report the output from this code.