The Google page rank algorithm has a lot to do with the eigenvector corresponding to the largest eigenvalue of a so-called stochastic matrix, which describes the links between websites. Stochastic matrices have non-negative entries and each column sums to 1, and one can show (under a few technical assumptions) that it has the eigenvalues ₁ = 1 > |₂| . . . |_n|. Thus, we can use the power method3 to find the eigenvector v corresponding to ₁, which can be shown to have either all negative or all positive entries. These entries can be interpreted as the importance of individual websites. Let us construct a large stochastic matrices (pick a size n 100, the size of our "toy internet") in MATLAB as follows:

I = eye(n);

A = 0.5*I(randperm(n),:) + (max(2,randn(n,n))-2);

A = A - diag(diag(A));

L = A*diag(1./(max(1e-10,sum(A,1))));

(a) Plot the sparsity structure of L (i.e., the nonzero entries in the matrix) using the command spy. Each non-zero entry corresponds to a link between two websites.

(b) Plot the (complex) eigenvalues of L by plotting the real part of the eigenvalues on the x-axis, and the imaginary part on the y-axis. Additionally, plot the unit circle and check that all eigenvalues are inside the unit circle, but ₁ = 1.

(c) The matrix L contains many zeros. One of the technical assumptions for proving theorems is that all entries in L are positive. As a remedy, one considers the matrices S = L+(1)E, where E is a matrix with entries 1/n in every component. Study the influence of numerically by visualizing the eigenvalues of S for different values of .

Why will < 1 improve the speed of convergence of the power method?