Sequence Converges to the Largest Eigenvalue of a Matrix

Problem 403

Let $A$ be an $n\times n$ matrix. Suppose that $A$ has real eigenvalues $\lambda_1, \lambda_2, \dots, \lambda_n$ with corresponding eigenvectors $\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n$.
Furthermore, suppose that
\[|\lambda_1| > |\lambda_2| \geq \cdots \geq |\lambda_n|.\] Let
\[\mathbf{x}_0=c_1\mathbf{u}_1+c_2\mathbf{u}_2+\cdots+c_n\mathbf{u}_n\] for some real numbers $c_1, c_2, \dots, c_n$ and $c_1\neq 0$.

Define
\[\mathbf{x}_{k+1}=A\mathbf{x}_k \text{ for } k=0, 1, 2,\dots\] and let
\[\beta_k=\frac{\mathbf{x}_k\cdot \mathbf{x}_{k+1}}{\mathbf{x}_k \cdot \mathbf{x}_k}=\frac{\mathbf{x}_k^{\trans} \mathbf{x}_{k+1}}{\mathbf{x}_k^{\trans} \mathbf{x}_k}.\]

Prove that
\[\lim_{k\to \infty} \beta_k=\lambda_1.\]

 
Add to solve later

Sponsored Links

Proof.

We have
\begin{align*}
x_k=A\mathbf{x}_{k-1}=A^2\mathbf{x}_{k-2}=\cdots=A^k\mathbf{x}_0
\end{align*}
by applying the definition of $\mathbf{x}_k$ successively.
Then we have
\begin{align*}
\mathbf{x}_k&=A^k\mathbf{x}_0\\
&=A^k(c_1\mathbf{u}_1+c_2\mathbf{u}_2+\cdots+c_n\mathbf{u}_n)\\
&=c_1A^k\mathbf{u}_1+c_2A^k\mathbf{u}_2+\cdots+c_nA^k\mathbf{u}_n\\
&=c_1\lambda_1^k\mathbf{u}_1+c_2\lambda_2^k\mathbf{u}_2+\cdots+c_n\lambda_n^k\mathbf{u}_n,
\end{align*}
where the last step follows from the equalities $A^k\mathbf{u}_i=\lambda_i^k \mathbf{u}_i$, which in turn follows from the definitions of eigenvalues and eigenvectors $A\mathbf{u}_i=\lambda_i\mathbf{u}_i$.
Using the sum notation, we simply write it as
\[\mathbf{x}_k=\sum_{i=1}^nc_i\lambda_i^k\mathbf{u}_i.\] This formula is true for any nonnegative integer $k$.

---

Let us next compute the dot product $\mathbf{x}_k\cdot \mathbf{x}_k$. We have
\begin{align*}
\mathbf{x}_k\cdot \mathbf{x}_k&=\left(\, \sum_{i=1}^nc_i\lambda_i^k\mathbf{u}_i \,\right)\cdot \left(\, \sum_{j=1}^nc_j\lambda_j^k\mathbf{u}_j \,\right)\\
&=\sum_{i=1}^n\sum_{j=1}^nc_ic_j\lambda_i^k\lambda_j^k\mathbf{u}_i \cdot \mathbf{u}_j\\
&=\lambda_1^{2k}\sum_{i=1}^n\sum_{j=1}^nc_ic_j \left(\, \frac{\lambda_i}{\lambda_1} \,\right)^k\left(\, \frac{\lambda_j}{\lambda_1} \,\right)^k\mathbf{u}_i \cdot \mathbf{u}_j.
\end{align*}
Since $\lambda_1$ is strictly larger than any other eigenvalues, we have
\begin{align*}
\lim_{k \to \infty} \left(\, \frac{\lambda_i}{\lambda_1} \,\right)^k
=\begin{cases} 1 & \text{ if } i=1\\
0 & \text{ if } i=2, 3,\dots, n.
\end{cases}
\end{align*}
It follows that
\begin{align*}
\lim_{k \to \infty}\mathbf{x}_k\cdot \mathbf{x}_k=\lambda_1^{2k}c_1^2 \mathbf{u}_1\cdot \mathbf{u}_1.
\end{align*}

---

Similarly, we compute
\begin{align*}
\mathbf{x}_k\cdot \mathbf{x}_{k+1}&=\left(\, \sum_{i=1}^nc_i\lambda_i^k\mathbf{u}_i \,\right)\cdot \left(\, \sum_{j=1}^nc_j\lambda_j^{k+1}\mathbf{u}_j \,\right)\\
&=\sum_{i=1}^n\sum_{j=1}^nc_ic_j\lambda_i^k\lambda_j^{k+1}\mathbf{u}_i \cdot \mathbf{u}_j\\
&=\lambda_1^{2k+1}\sum_{i=1}^n\sum_{j=1}^nc_ic_j \left(\, \frac{\lambda_i}{\lambda_1} \,\right)^k\left(\, \frac{\lambda_j}{\lambda_1} \,\right)^{k+1}\mathbf{u}_i \cdot \mathbf{u}_j.
\end{align*}

Thus we obtain
\begin{align*}
\lim_{k\to \infty} \mathbf{x}_k\cdot \mathbf{x}_{k+1}=\lambda_1^{2k+1}c_1^2\mathbf{u}_1\cdot \mathbf{u}_1.
\end{align*}

---

Combining these computations, we have
\begin{align*}
\lim_{k\to \infty}\beta_k&=\frac{\lim_{k\to \infty}\mathbf{x}_k\cdot \mathbf{x}_{k+1}}{\lim_{k\to \infty}\mathbf{x}_k \cdot \mathbf{x}_k}\\[6pt] &=\frac{\lambda_1^{2k+1}c_1^2 \mathbf{u}_1\cdot \mathbf{u}_1}{\lambda_1^{2k}c_1^2\mathbf{u}_1\cdot \mathbf{u}_1}\\[6pt] &=\lambda_1
\end{align*}
as required. This completes the proof.

Click here if solved 13
Add to solve later

Sponsored Links