Question

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 \times n\), all of whose entries are equal to \(1 / n\), and let \(\alpha\) be a scalar, \(0<\alpha<1\). (a) Show that \(A(\alpha)=\alpha P+(1-\alpha) E\) is also a column-stochastic matrix. (b) What are the largest eigenvalue and corresponding eigenvector of \(A(\alpha)\) ? (c) Show that the second largest eigenvalue of \(A(\alpha)\) is bounded (in absolute value) by \(\alpha\). (d) Suppose the dominant eigenvector of \(A(\alpha)\) is to be computed using the power method. This vector, if normalized so that its \(\ell_{1}\) -norm is equal to 1 , is called the stationary distribution vector. i. Show how matrix-vector products with \(P(\alpha)\) 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 \(\mathbf{v}_{0}\) satisfies \(\left\|\mathbf{v}_{0}\right\|_{1}=1\), then all subsequent iterates \(\mathbf{v}_{k}\) also have a unit \(\ell_{1}\) -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).]

Short answer

In summary, we have shown that the matrix \(A(\alpha)\) is a column-stochastic matrix and determined its largest eigenvalue and corresponding eigenvector. We also proved that the second-largest eigenvalue of \(A(\alpha)\) is bounded in absolute value by \(\alpha\). Furthermore, we demonstrated that products with \(A(\alpha)\) can be computed efficiently in terms of storage, and that if the initial guess has a unit 1-norm, all subsequent iterates in the power method will also have a unit 1-norm, thus eliminating the need for normalization during the power method iteration.

Step-by-step solution

Show A(α) is a column-stochastic matrix

First, let's show that \(A(\alpha)\) is also a column-stochastic matrix. Recall that a matrix is column-stochastic if all its entries are nonnegative and the sum of the entries in each column is equal to 1. Since \(P\) is column-stochastic by definition, and \(E\) consists of non-negative entries, it follows that the linear combination \(\alpha P + (1 - \alpha)E\) will have non-negative entries. Now, let's check if the sum of the entries in each column of \(A(\alpha)\) is equal to 1. \(∑_{i} A_{ij}(\alpha) = ∑_{i}(\alpha P_{ij} + (1 - \alpha)E_{ij}) = ∑_{i}(\alpha P_{ij})+(1 - \alpha)∑_{i}E_{ij}= \alpha ∑_{i}P_{ij} + (1-\alpha)n\frac{1}{n}= \alpha +1 - \alpha=1\) Since the entries of \(A(\alpha)\) are nonnegative and the sum of its column entries is equal to 1, \(A(\alpha)\) is a column-stochastic matrix.

Find the largest eigenvalue and corresponding eigenvector of A(α)

To find the largest eigenvalue and the corresponding eigenvector of \(A(\alpha)\), we need to look at the largest eigenvalue of the matrix \(P\). Since \(P\) is a column-stochastic matrix, its largest eigenvalue is 1. (This can be shown using the Perron-Frobenius theorem for non-negative matrices). Now, let's find the largest eigenvalue of \(A(\alpha)\). \(A(\alpha)e = (\alpha P + (1-\alpha)E)e = \alpha P e + (1-\alpha)E e \) Since \(Pe=e\) we get, \(A(\alpha)e=\alpha e+(1-\alpha)Ee\) Now let's analyse \(Ee\). Since all elements in \(E\) are \(\frac{1}{n}\) and \(e\) is a unit vector, \(Ee = \Big(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}\Big)^T\) Now, substituting back, we get, \(A(\alpha)e=\alpha e+(1-\alpha)e\) This implies that the largest eigenvalue of \(A(\alpha)\) is 1 (same as the largest eigenvalue of \(P\)) and the corresponding eigenvector is \(e\).

Show that the second-largest eigenvalue of A(α) is bounded by α

Let \(\lambda_1 = 1, \lambda_2, \dots, \lambda_n\) be the eigenvalues of \(P\), and \(|\lambda_2| \ge |\lambda_3| \ge \dots \ge |\lambda_n|\). We need to show that the second-largest eigenvalue of \(A(\alpha)\) is bounded in absolute value by \(\alpha\). Consider the eigenvalue equation for the matrix \(A(\alpha)\) and an eigenvalue \(\lambda\) (excluding the largest eigenvalue 1): \(A(\alpha) x=\lambda x \Rightarrow (\alpha P + (1-\alpha)E)x = \lambda x\) Since \(A(\alpha)e=e\) (which we showed in Step 2), we have \(\lambda \neq 1\). Let's solve for \(x\), \((\alpha P + (1-\alpha)E-\lambda I)x = 0 \Rightarrow (\alpha (P-\lambda I)+ (1-\alpha)(E-\lambda I))x = 0\) Let's rewrite the equation as below, \(P x=\frac{(1-\alpha)(\lambda I-E)+\lambda I}{\alpha}x\) Now since \(\frac{(1-\alpha)(\lambda I-E)+\lambda I}{\alpha}\) is a column-stochastic matrix (because \(E\) is), applying the same Perron-Frobenius theorem, we get that the largest eigenvalue of \(\frac{(1-\alpha)(\lambda I-E)+\lambda I}{\alpha}\) is 1. Since \(\lambda \neq 1\) and \(P\) already has largest eigenvalue 1 with eigenvector \(e\), it follows that \(\frac{(1-\alpha)(\lambda I-E)+\lambda I}{\alpha}\) must correspond to the second-largest eigenvalue of \(P\). Therefore, \(|\lambda_2|=\left|\frac{(1-\alpha)(\lambda I-E)+\lambda I}{\alpha}\right|=\frac{1-\alpha}{\alpha} \Rightarrow |\alpha\lambda_2|=1-\alpha\) This implies that \(|\alpha\lambda_2| < 1\) for \(0<\alpha<1\), and as a result, the second largest eigenvalue of \(A(\alpha)\) is bounded in absolute value by \(\alpha\).

Power method considerations

(d) i. To perform the matrix-vector products with \(A(\alpha)\) efficiently in terms of storage, we use the sparsity of \(P\). Given \(y = A(\alpha)x\), we obtain \(y = \alpha P x + (1 - \alpha)Ex\). Since \(P\) is sparse, the product \(Px\) can be computed efficiently, taking into account only the non-zero elements of \(P\). Further, the product \(E x\) can also be computed efficiently, since each entry of \(E\) is equal to \(\frac{1}{n}\) and the sum of the elements of the resulting vector is \(e^Tx\). Thus, we have \(Ex=\frac{1}{n}(e^Tx)e\) Thus, computing products with \(A(\alpha)\) in a memory-efficient manner is achievable. (d) ii. To show that if the initial guess \(v_0\) satisfies \(\lVert v_0 \rVert_1 = 1\), then all subsequent iterates \(v_k\) also have a unit 1-norm, let's write \(v_{k+1} = A(\alpha)v_k\). Taking the 1-norm of both sides, we get: \(\lVert v_{k+1} \rVert_1 = \lVert A(\alpha)v_k \rVert_1\) Since \(A(\alpha)\) is a column-stochastic matrix, the preservation of the 1-norm is maintained during the multiplication. This implies that if \(v_0\) has a 1-norm of 1, then all subsequent iterates \(v_k\) will also have a 1-norm of 1, and there is no need for normalization during the power method iteration.

Key concepts

Eigenvalues and Eigenvectors

Understanding the concept of eigenvalues and eigenvectors is fundamental in various areas of mathematics and engineering, particularly in the study of linear transformations. An eigenvalue is a number that indicates how a linear transformation will compress or stretch a vector, and the eigenvector is the direction that is not changed by the transformation.

In the context of matrices, finding the eigenvalues and eigenvectors involves solving the characteristic equation, \( A - \lambda I \), where \( A \) is the matrix in question, \( \lambda \) represents the eigenvalues, and \( I \) is the identity matrix. The solutions to this equation yield the eigenvalues, and by substituting these back into the equation, we can solve for the eigenvectors.

For a column-stochastic matrix, a matrix with nonnegative entries and columns summing to one, the largest eigenvalue is always 1. This is because the corresponding eigenvector can be thought of as a steady-state probability distribution in certain applications, like in Markov chains, where the stochastic matrix represents transition probabilities.

Perron-Frobenius Theorem

The Perron-Frobenius theorem is a powerful result in linear algebra that applies to non-negative matrices, which include column-stochastic matrices. It guarantees the existence of a positive eigenvalue that has magnitude greater than or equal to the magnitude of all other eigenvalues, known as the \( Perron \) root. This dominant eigenvalue also has a corresponding eigenvector with strictly positive entries.

This theorem helps us in understanding the long-term behavior of systems that can be modeled with such matrices. In the context of our exercise, it guarantees that the largest eigenvalue of the matrix \( A(\alpha) \) is 1 and that all other eigenvalues have a smaller magnitude. Thus, when applied to column-stochastic matrices, it provides a solid basis for predicting the system's behavior as it evolves over time, which is particularly relevant in fields such as economics, biology, and the study of algorithms.

Power Method

The power method is an iterative algorithm used to approximate the largest eigenvalue and corresponding eigenvector of a matrix. It is particularly useful when dealing with large and sparse matrices, where traditional eigenvalue algorithms may be computationally intensive.

The procedure begins with an initial guess vector, and by consecutively multiplying by the matrix, each iteration's result converges to the eigenvector associated with the dominant eigenvalue. For a column-stochastic matrix \( A(\alpha) \) as described in the exercise, the power method is an efficient means of finding the 'stationary distribution vector.'

The beauty of the power method in this context is that, thanks to the column-stochastic nature of our matrix \( A(\alpha) \) and the initial normalization of the guess vector \( \mathbf{v}_0 \) to have a 1-norm, no further normalization is needed. Subsequent iterations will preserve this 1-norm, ensuring computational simplicity and accuracy during each step of the algorithm.