Subtracting orthogonal projection matrix to find second largest eigenvalue

Question

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?

Answer 1

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$.