Homework #1 -- Math 307/101, Fall 2011, Joel Friedman

PROBLEM 1. Copy the lines below and paste them into Matlab or Octave;
comment on the output (you don't have to hand in the output, just
comment on it).

A = [ 3/4 , 1/4  ;  1/2 , 1/2 ]

A, A^2, A^3, A^4, A^5, A^6

A^10

eigs(A)

v = [ 12 , 12 ]

v, v*A, v*A^2, v * A^3, v * A^4, v * A^10

How does the sum of the eigenvalues of A compare to the sum of the
diagonal entries of A?
 

PROBLEM 2.  Same question as problem 1, with the same  v  but with

A = [ 3/4 , 1/4 ; 1/8 , 7/8 ]  .


PROBLEM 3.  Solve for the eigenvalues of 

A = [ 3/4 , 1/4 ; 1/8 , 7/8 ]  

using the method described in class: write  det( A - I lambda ) = 0.
Solve for the eigenvectors once you get the eigenvalues.  Then write
v = [ 12 , 12 ]  as a linear combination of to eigenvectors, and use
that to write an explicit formula for  v * A^k  in terms of k.  Finally
use the diagonalization of A ( as S^(-1) D S  with D a diagonal matrix)
to compute the limit of A^k as k tends to infinity.


PROBLEM 4. Find the matrix  H  and PageRank in the following cases:

(1) Two websites, A,B, such that:  
     A has 5 links to itself and 2 links to B;
     B has 1 link to A (and no links to itself).

(2) Three websites, A,C,D such that:
     A has 5 links to itself, one link to C, one link to D;
     C has 1 link to A and no other links;
     D has 1 link to A and no other links.

What similarities are there between the two PageRank vectors, and
can you explain why this happens?

NOTE: Unlike the book, we will allow websites to have more than one
link to another page, and even link to itself.  So, for example, in
case (1), the website A has 7 links in total, and therefore the H
matrix row corresponding to A would be  [ 5/7  2/7 ] .