Power method

[Bob2]

Hi everyone,

 

I have to solve the following problem, but I can't find the solution:

 

A is an 12x12 symmetric matrix.

 

Let v be an eigenvector for lambda1. Explain why the power method (in almost all cases) converges to the eigenvalue lambda2, (the eigenvalue of A with the seconde largest absolute eigenvalue), if one starts with a vector x₀, which is orthogonal to v.

They give the following hint: note that A is symmetric, and write x₀ as a linear combination of eigenvectors

 

Thanks a lot for your replies. It would really help me if someone knows how to solve this question.

 

Kind regards,

 

Bob

 

[timo]

Assume you have a vector expressed as a linear combination of the eigenvectors of A, i.e. [math] \vec v = \sum_{i=1}^{12} \alpha_i \vec e_i[/math]. What is [math]A \vec v[/math]? What is [math]A^n \vec v[/math]?

[Bob2]

Timo,

 

If I understand you correct you mean this:

But how does this help me to solve the question? Where can I use the orthogonality of x0 to v?

 

Thanks for your reply.

Edited December 13, 2010 by Bob2

[timo]

Let [math]\vec e_0[/math] be the eigenvector with the largest eigenvalue. What is [math]\alpha_0[/math]? I think that helps a lot.

[Bob2]

[math] \alpha_0 [/math] is 0 right?

[timo]

Yes [math]\alpha_0[/math] (called [math] c_1 [/math] in the snippet you posted) is zero. It had been cooler if you had added the reason for that in your post, since it sounds a bit like random guessing this way. But well, don't bother now. Just make sure you understand why that is the case.

[Bob2]

I thought it was zero, because due to the fact that v1 is orthogonal to x0, there is no component in the v1 direction when you write x0 as a linear combination of v1,...,v12.

 

The full proof would then be:

 

 

Could you check whether the rest is correct?

 

Thanks a lot!

[timo]

When I was a 1st year math student a professor in a seminar asked me if I knew what a proof is. I told him something along the lines of "series of logical steps ultimately tracing back to the basic axioms". He said "well, actually it's an argument that people understand and agree with". So whether your proof is correct, complete or even a proof at all somewhat depends on whom you want to convince. Anyways, you're not asking for anecdotes but for more specific replies. So a few comments that come to my mind:

- It better be [math]| \lambda_2 | > |\lambda_3|[/math], not [math]| \lambda_2 | \geq |\lambda_3|[/math] for your statement to work.

- I'm not sure what you need the proof for. I'd try a more specific definition of what convergence towards eigenvector [math]{\bf v}_2[/math] means. Or in other words, saying that [math] \lim_{k\to \infty} A^k {\bf x}_0 / \lambda_2{}^k = c_2 {\bf v}_2[/math] is fine, but I'd motivate more why you look at [math]A^k {\bf x}_0 / \lambda_2{}^k [/math] in the sense of why the convergence of this term towards the 2nd eigenvector means that [math]A^k {\bf x}_0 [/math] converges to (a multiple of) [math]{\bf v}_2[/math].

- Strictly speaking, it is possible that [math]{\bf x}_0[/math] is orthogonal to the eigenvector of the 2nd largest eigenvalue.

- What if there is more than one eigenvector to the 2nd largest eigenvalue?

 

I'm not sure to what extent my points above are relevant for your actual problem, so decide that for yourself.

[Bob2]

Thanks Timo.

It better be , not for your statement to work. Agree, thanks

I'm not sure what you need the proof for. I'd try a more specific definition of what convergence towards eigenvector means. Or in other words, saying that is fine, but I'd motivate more why you look at in the sense of why the convergence of this term towards the 2nd eigenvector means that converges to (a multiple of) . Lay uses in his book Linear Algebra and Its applications a similar proof for the proof/explanation of the power method. Moreover the question is not explictily proof, but it says explain, so a semi formal proof will suffice, I think.

Strictly speaking, it is possible that is orthogonal to the eigenvector of the 2nd largest eigenvalue. This is fortunately not the case in the situation.

What if there is more than one eigenvector to the 2nd largest eigenvalue? There are always more eigenvectors, all multiples are also eigenvectors. But you probably mean that the geometric multiplicity is not one. I don't know how this works in relation to the power method, because in all examples I have seen there is just one approximation for an eigenvector. So I probably don't have to worry about this.

 

There is another question, that I have to solve:

 

I don't know how the to show that 2 matrices have the same eigenvectors. If you would have to show that 2 matrices have the same eigenvalues, then you would have to proof that they have the same characteristic equation. But how about eigenvectors?

 

Thanks for your help.

[timo]

Thanks Timo

You're very much welcome.

I don't know how the to show that 2 matrices have the same eigenvectors. If you would have to show that 2 matrices have the same eigenvalues, then you would have to proof that they have the same characteristic equation. But how about eigenvectors?

I would try it heads on. Take a vector [math] {\bf v}_i [/math] which is an eigenvector to the i'th largest eigenvalue, and show that it is an eigenvector to both matrices (of course you don't have to explicitly show that for matrix A since that was the condition that you start with). Hint: [math] \left( {\bf vv}^T \right) {\bf x} = {\bf v} \left( {\bf v}^T {\bf x} \right) [/math] (you might want to verify that first, if you don't know why).

[Bob2]

Your hint is just basic rule for vector multiplication, just like with real numbers, that (6*3)*7=6*(3*7) holds. Something similar also holds for matrices and vectors.

 

 

I think I now managed to prove that they have the same eigenvectors:

 

Was this what you meant?

 

Now the rest of the question seems still quite difficult, because I do not really see the link between what I just proved and what I have to prove (see above in previous post). Namely what do I know about labda2, apart from it's definition. In other words: when I am in a proof how that this specific eigenvector I have in the proof is really labda2 and not something else.

I hope you know what I mean. Otherwise I will ry to explain it again.

Edited December 23, 2010 by Bob2

[timo]

Your hint is just basic rule for vector multiplication, just like with real numbers, that (6*3)*7=6*(3*7) holds. Something similar also holds for matrices and vectors.

Yes. But perhaps you should be a bit more careful. After all, another relation which looks very similar, [math] ( {\bf a} {\bf b} ) {\bf c} = {\bf a} ({\bf b} {\bf c})[/math] does usually not hold (left-hand side is parallel to c, right-hand side is parallel to a).

 

I think I now managed to prove that they have the same eigenvectors:

[...]

Was this what you meant?

Partly. You have shown that the eigenvector [math]{\bf \lambda}[/math] is an eigenvector to the new matrix, too. You have to at least prove that for all of the other eigenvectors, also. Strictly speaking, you'd then have to go on and prove that there is no eigenvector of the new matrix, which is not an eigenvector of A.

 

 

Now the rest of the question seems still quite difficult, because I do not really see the link between what I just proved and what I have to prove (see above in previous post). Namely what do I know about labda2, apart from it's definition.

You have already found that the eigenvalue to the eigenvector [math]{\bf \lambda}[/math] is zero. You will find that for the other eigenvectors, the eigenvalues are the same as they were for A during the proof that all other eigenvectors are the same for both matrices.