Find the eigenvalues and eigenvectors of \(A = \begin{pmatrix}1 \amp 2 \\ 4 \amp 3 \end{pmatrix}\) by hand.

In the matrix \(A = \begin{pmatrix}1 \amp 2 \amp 3 \\ 4 \amp 5 \amp 6 \\ 7 \amp 8 \amp 9 \end{pmatrix}\) one of the eigenvalues is \(\lambda_1 = 0\).

1. What does that tell us about the matrix \(A\)?

2. What is the eigenvector \(\bv_1\) associated with \(\lambda_1 = 0\)?

Find matrices \(P\) and \(D\) such that \(A = \begin{pmatrix}1 \amp 2 \\ 4 \amp 3 \end{pmatrix}\) can be written as \(A = PDP^{-1}\) where \(P\) is a dense \(2 \times 2\) matrix and \(D\) is a diagonal matrix. Once you have this factorization of \(A\), use it to determine \(A^{10}\).

Let \(A\) be an \(n \times n\) matrix with \(n\) distinct eigenvectors \(\bv_1, \bv_2, \dots, \bv_n\) and let \(\bx \in \mathbb{R}^n\) be a vector such that \(\bx = \sum_{j=1}^n c_j \bv_j\). Find expressions for \(A\bx\), \(A^2 \bx\), \(A^3\bx\), …

In this problem we first describes the mathematical idea for the power method for computing the largest eigenvalue / eigenvector pair. Then we write an algorithm for find the largest eigen-pair numerically.

1. Assume that \(A\) has \(n\) linearly independent eigenvectors \(\bv_1, \bv_2, \dots, \bv_n\) and choose \(\bx = \sum_{j=1}^n c_j \bv_j\). From the previous problem, \begin{equation*} A^k \bx = \underline{\hspace{2in}} \end{equation*}

2. Factor the right-hand side so that \begin{equation*} A^k \bx = \lambda_1^k \left( c_1 \bv_1 + c_2 \left( \frac{\lambda_2}{\lambda_1} \right)^k \bv_2 + c_3 \left( \frac{\lambda_3}{\lambda_1} \right)^k \bv_3 + \cdots + c_n \left( \frac{\lambda_n}{\lambda_1} \right)^k \bv_n \right) \end{equation*}

3. If \(\lambda_1 > \lambda_2 \ge \lambda_3 \ge \cdots \ge \lambda_n\) then what happens to each of the \((\lambda_j/\lambda_1)^k\) terms as \(k \to \infty\)? Using this answer, what is \(\lim_{k \to \infty} A^k \bx\)?

The Power Method Algorithm: This algorithm will quickly find the eigenvalue of largest absolute value for a square matrix \(A \in \mathbb{R}^{n \times n}\) as well as the associated (normalized) eigenvector. We are assuming that there are \(n\) linearly independent eigenvectors of \(A\).

• Given a nonzero vector \(\bx\), set \(\bv^{(1)} = \bx / \|\bx\|\). (Here the superscript indiates the iteration number)

• For \(k=2, 3, \ldots\)

  • Compute \(\tilde{\bv}^{(k)} = A \bv^{(k-1)}\) (this gives a non-normalized version of the next estimate of the dominant eigenvector.)

  • Set \(\lambda^{(k)} = \left\lt \tilde{\bv}^{(k)} , \bv^{(k-1)} \right>\). (this gives an approximation of the eigenvalue since if \(\bv^{(k-1)}\) was the actual eigenvector we would have \(\lambda = \left\lt A \bv^{(k-1)}, \bv^{(k-1)} \right>\))

  • Normalize \(\tilde{\bv}^{(k)}\) by computing \(\bv^{(k)} = \tilde{\bv}^{(k)} / \| \tilde{\bv}^{(k)} \|\). (This guarantees that you will be sending a unit vector into the next iteration of the loop)

Write a MATLAB function to implement the power method for finding the eigenvalue of largest absolute value and the associated eigenvector. Test it on a matrix where you know the eigenvalue of interest.

On pages 312 and 313 of the textbook the author describes the “deflation” technique for finding the eigenvector associated with the second largest eigenvalue. Write a MATLAB function “MyPower2” to find the second largest eigenvalue and eigenvector pair by putting the author's exposition into practice. Test your code on a symmetric matrix \(A\) and compare against MATLAB's “eig” command.