*29 July 2020*

In this post, you will learn about the power method for finding the eigenvector corresponding to the largest eigenvalue.

Throughout, let $A$ denote an $n \times n$ matrix. The power method is given by the following iteration:

- Start with a random vector $v_0 \in \mathbb{R}^n$.
- Define future $v_i$’s via the recurrence relation:

where $|w|$ denotes the *length* or *norm* of the vector $w$.

Under appropriate conditions on $A$ (that you will discover in the homework), the sequence $v_0, v_1, v_2, \dots$ converges to some vector $v$ which satisfies

\[v = \frac{Av}{|Av|}.\]# Homework

Questions 1 and 2 are due on 11 Aug (Tuesday). Question 3 is due on 17 Aug (Monday). Feel free to email me if you get stuck or have any questions.

## Question 1

For this question, the following formulas might be helpful:

- Scalars can be moved in and out of matrix products: $A\,(cv) = c\, Av$
- Scalars can be moved in and out of dot products: $v \cdot (cw) = c (v \cdot w) = (cv) \cdot w$
- Formula for the norm: $|v| = \sqrt{v \cdot v}$

**a)** Show that any $v$ satisfying $v = \frac{Av}{|Av|}$ is an eigenvector of $A$. What is the corresponding eigenvalue?

**b)** Let $v$ be the vector from (a). Use the formula for the norm and the fact that $v$ is an eigenvector to show that $|Av| = v \cdot Av$.

**c)** Returning to the power method, give a formula for $v_{i+1}$ in terms of only $A$ and $v_0$. (This should also tell you why the method is called the *power* method).

## Question 2

Now suppose that $u_1, u_2, \dots u_n$ are all the eigenvectors of $A$, with corresponding eigenvalues $\lambda_1,\dots, \lambda_n$.

Suppose also that $|\lambda_1| > |\lambda_i|$ for all other $i$.

Let $v_0 = c_1 u_1 + c_2 u_2 + \dots + c_n u_n$ for some scalars $c_1,\dots, c_n$.

**a)** For any $i \neq 1$, what is $\left(\frac{\lambda_i}{\lambda_1}\right)^k$ as $k$ goes to infinity?

**b)** Express $A^k v_0$ in terms of $k$ and all the $c_i, \lambda_i, u_i$’s.

**c)** Use your answer in (b) to express $\frac{A^k v_0}{\lambda_1^k}$. What happens as $k$ goes to infinity?

**d)** Now use $v_0$ as the starting vector in the power method. Show that $v_k$ converges to $u_1$ as $k$ goes to infinity.

**e)** Can you guess what might go wrong if $\lambda_2 = \lambda_1$?

## Question 3

For this coding question, you may use the following, unless stated otherwise:

`np.linalg.norm(v)`

returns the norm of a vector`np.dot(v,w)`

returns the dot product of two vectors (note that this is the same as`v @ w`

)`np.sqrt(c)`

returns the square root of a number`np.random.rand(n)`

returns an $n$-dim vector, with entries randomly chosen from the interval [0,1].`np.random.rand(n,m)`

returns an $n \times m$ array, with entries randomly chosen from the interval [0,1].`np.allclose(v,w)`

returns`True`

if`v`

and`w`

are close to each other. It is best to use this instead of`v == w`

, since there might be some differences due to precision.

**a)** Write your own function `my_norm(v)`

to compute the norm of a vector $v$, without using `np.linalg.norm`

. Compare the results of your function with `np.linalg.norm`

to make sure it is correct.

**b)** Write a function `power_method(A,v0,k)`

that returns `k`

iterations of the power method, applied to the matrix `A`

and the starting vector `v0`

. You may now use `np.linalg.norm`

if you want.

**c)** Apply your function to any matrix and starting vector of your choice, for a large number of iterations (50 should be more than enough).

**d)** Verify that the result is indeed an eigenvector, and compute the corresponding eigenvalue (Question 1 might be useful).