## Description

1. A ring-like network of links between web pages is shown below. Assume all feasible

transitions are equally likely.

a) Find the unweighted adjacency matrix for this network.

b) Find the weighted adjacency matrix for this network. Note that the entries in

each column of the weighted adjacency matrix are nonnegative and sum to one.

Such a matrix is called a column stochastic matrix.

c) Suppose the entries of a vector b sum to one. It is easy to show that the entries

of Ab also sum to one since each column of the weighted adjacency matrix A

sums to one. The PageRank algorithm thus uses the power method without

normalizing the length of the vector at each iteration. Each iteration gives a new

vector with positive entries that sum to one. Find the estimate of the PageRank

vector after one iteration using an initial vector b0 =

1

8

1

1

.

.

.

1

. The initial vector

b0 gives equal importance to all pages.

1 of 3

d) Find the estimate of the PageRank vector after 1000 iterations of the power

method using an initial vector b0 =

1

8

1

1

.

.

.

1

. A skeleton script is available. You

will need to enter the adjacency matrix into the code.

e) Do any nodes seem to be more important than other nodes? Explain.

2. A hub-like network of links between web pages is shown below. Assume all feasible

transitions are equally likely.

a) Find the unweighted adjacency matrix for this network.

b) Find the weighted adjacency matrix for this network.

c) Find the estimate of the PageRank vector after one iteration using an initial

vector b0 =

1

9

1

1

.

.

.

1

.

d) Find the estimate of the PageRank vector after 1000 iterations of the power

2 of 3

method using an initial vector b0 =

1

9

1

1

.

.

.

1

.

e) Are any nodes more important than other nodes? Explain.

f) Experiment with the number of iterations of the power method that are needed

to find an answer that is correct to three decimal places.

3. Consider expressing the SVD of a rank-r matrix X as

X =

∑r

i=1

σiuiv

T

i

where σi

is the ith singular value with left singular vector ui and right singular vector

vi

. Is the sign of the singular vectors unique? Why or why not? Hint: Consider

replacing u1 with u˜1 = −u1.

3 of 3