A column-stochastic matrix P is a matrix whose entries are nonnegative and whose column sums are all equal to 1. In practice such matrices are often large and sparse. Let E be a matrix of the same size as P, say, n ×n, all of whose entries are equal to 1/n, and let α be a scalar, 0

(a) Show that A(α) = αP +(1-α)E is also a column-stochastic matrix.

(b) What are the largest eigenvalue and corresponding eigenvector of A(α)?

(c) Show that the second largest eigenvalue of A(α) is bounded (in absolute value) by α.

(d) Suppose the dominant eigenvector of A(α) is to be computed using the power method. This vector, if normalized so that its l1-norm is equal to 1, is called the stationary distribution vector.

i. Show how matrix-vector products with P(α) can be performed in an efficient manner in terms of storage. (Assume n is very large, and recall that E is dense.)

ii. Show that if the power method is applied, then if the initial guess v₀ satisfies ||v0||1 = 1, then all subsequent iterates v_k also have a unit l1-norm, and hence there is no need to normalize throughout the iteration. [Warning: Item (d) and even more so item (c) above are significantly tougher nuts to crack than items (a) and (b).]