2
$\begingroup$

Let α = λ/(v'v), with λ being A's largest eigenvalue and v its corresponding eigenvector, how do I prove that the largest absolute eigenvalue of A − αvv' equals the second largest eigenvalue of A by use of the power method? I think that αvv' is an ortogonal projection matrix but what is the use of multiplying it by λ and subtracting from A?

$\endgroup$
  • 1
    $\begingroup$ Try looking at what this does in the case that $A$ is diagonal, and I think it should then be clear why this works in general $\endgroup$ – Ben Grossmann Oct 31 '18 at 18:03
  • 1
    $\begingroup$ Do you assume $A$ is square and diagonalizable? $\endgroup$ – abolfazl Oct 31 '18 at 19:07
1
$\begingroup$

I assume $A$ is an $n\times n$ square matrix having $n$ eigenvectors. Therefore, $A = VDV^{-1}$ where I assume columns of $V$ are orthogonal to each other but, they are not normalized. We can write $A$ equivalently as $A = \lambda_1v_1v_1^\top+\sum_{i=2}^n\lambda_iv_iv_i^\top$. Let $B = A-\alpha v_1v_1^\top$ where $\alpha = \frac{\lambda_1}{\|v_1\|_2^2}$. Then, $B = \lambda_1(1-\frac{1}{\|v_1\|_2^2})v_1v_1^\top+\sum_{i=2}^n\lambda_iv_iv_i^\top$. So, if $$\lambda_1(1-\frac{1}{\|v_1\|_2^2}) > \lambda_2,$$ the largest absolute eigenvalue of $B = A-\alpha v_1v_1^\top$ DOES NOT equal the second largest eigenvalue of $A$. You can easily construct many counterexamples. If you have MATLAB, the following code generates a random counterexample:

clear; clc;
Q = randn(3); Q = orth(Q)*diag([3,2,1])
sum(Q.^2)
D = diag([200,1.5,1])
A = Q*D*Q^(-1)
eig(A)
a = 2/norm(Q(:,1))^2
B = A-a*Q(:,1)*Q(:,1)'
eig(B)

If the eigenvectors where normalized, $\lambda_1(1-\frac{1}{\|v_1\|_2^2}) = 0$ and you could easily see $\lambda_2$ is the largest eigenvalue of $B$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That’s great, thank you! How could I, without using matlab, show that the last term is not greater than lambda2, so that the power method would indeed return the second greatest? $\endgroup$ – Walter Nap Oct 31 '18 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.