Matrix Eigenvalue Problems: Power Method, Jacobi, QR Algorithm

Core Concepts

1. Eigenvalues and Eigenvectors: Definition and Geometric Interpretation

An eigenvalue $\lambda$ and its corresponding eigenvector $\mathbf{v}$ of a square matrix $A$ satisfy: $$A\mathbf{v}=\lambda \mathbf{v}$$

• Geometric meaning: $\mathbf{v}$ is stretched/shrunk by $\lambda$ when multiplied by $A$.
• Algebraic meaning: Solve the characteristic equation $\det (A-\lambda I)=0$ for $\lambda$, then substitute back to find $\mathbf{v}$.

Worked Example 1: Find eigenvalues and eigenvectors of $A=\left[\begin{array}{cc}4& 1\\ 2& 3\end{array}\right]$.

1. Characteristic equation: $$\det (A-\lambda I)=\det \left[\begin{array}{cc}4-\lambda & 1\\ 2& 3-\lambda \end{array}\right]=(4-\lambda )(3-\lambda )-2={\lambda }^2-7\lambda +10=0$$ Solutions: ${\lambda }_1=5$, ${\lambda }_2=2$.
2. Eigenvectors:
   • For ${\lambda }_1=5$: $(A-5I)\mathbf{v}=0\Rightarrow {\mathbf{v}}_1=\left[\begin{array}{c}1\\ 2\end{array}\right]$.
   • For ${\lambda }_2=2$: $(A-2I)\mathbf{v}=0\Rightarrow {\mathbf{v}}_2=\left[\begin{array}{c}-1\\ 1\end{array}\right]$.

2. Iterative Methods for Eigenvalues

A. Power Method (for Dominant Eigenvalue)

How it works:

1. Start with a guess vector ${\mathbf{x}}_0$.
2. Iterate: ${\mathbf{x}}_{k+1}=\frac{A{\mathbf{x}}_k}{\Vert A{\mathbf{x}}_k\Vert }$.
3. Converges to the eigenvector of the largest-magnitude eigenvalue ${\lambda }_{\text{max}}$.

Convergence condition: The matrix must have a real dominant eigenvalue (i.e., $|{\lambda }_{\text{max}}|>|{\lambda }_i|$ for all $i\ne 1$).

flowchart TD
    A["Start: Choose x₀"] --> B["Compute y = A x₀"]
    B --> C["Normalize: x₁ = y / ||y||"]
    C --> D["Check convergence: ||x₁ - x₀|| < ε?"]
    D -->|"No"| C
    D -->|"Yes"| E["λ ≈ (x₁ᵀ A x₁) / (x₁ᵀ x₁)"]

Worked Example 2: Find the largest eigenvalue of $A=\left[\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right]$ using the power method.

1. Start with ${\mathbf{x}}_0=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$.
2. Iterate:
   • ${\mathbf{x}}_1=\frac{A{\mathbf{x}}_0}{\Vert A{\mathbf{x}}_0\Vert }=\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]$ (after normalization).
   • ${\mathbf{x}}_2=\frac{A{\mathbf{x}}_1}{\Vert A{\mathbf{x}}_1\Vert }=\left[\begin{array}{c}-0.5\\ 1\\ -0.5\end{array}\right]$.
3. Converges to $\mathbf{v}=\left[\begin{array}{c}1\\ -2\\ 1\end{array}\right]$ (scaled), with ${\lambda }_{\text{max}}=4$.

B. Inverse Power Method (for Smallest Eigenvalue)

Use $A^{-1}$ instead of $A$ to find the smallest-magnitude eigenvalue.

C. Jacobi Method (for All Eigenvalues)

Steps:

1. Diagonalize $A$ via rotations: $A=R^{T}DR$, where $D$ is diagonal (eigenvalues).
2. Use Givens rotations to zero off-diagonal elements iteratively.

Advantages:

• Works for symmetric matrices.
• No convergence issues like the power method.

Disadvantages:

• Computationally expensive for large matrices ($O(n^3)$).

D. QR Algorithm (for All Eigenvalues)

Steps:

1. Factorize $A=QR$ (orthogonal $Q$, upper triangular $R$).
2. Compute $A_{k+1}=R_k{Q}_k$.
3. Repeat until $A_k$ is nearly diagonal.

Convergence: Faster than Jacobi for large matrices ($O(n^3)$ per iteration).

flowchart TD
    A["Start: A₀ = A"] --> B["Factorize: Aₖ = Qₖ Rₖ"]
    B --> C["Compute Aₖ₊₁ = Rₖ Qₖ"]
    C --> D["Check if Aₖ₊₁ is diagonal?"]
    D -->|"No"| B
    D -->|"Yes"| E["Eigenvalues ≈ diagonal of Aₖ₊₁"]

3. Applications in Engineering

A. Structural Vibration Analysis

• Eigenvalues of stiffness matrices determine natural frequencies of bridges/buildings.
• Example: The Sundarbans Bridge (Nepal) uses eigenvalue analysis to design vibration-resistant piers.

B. Google’s PageRank Algorithm

• Uses the power method on a web-link matrix to rank pages by importance.
• Matrix: $A_{ij}=1/\text{outlinks of page }j$ if page $i$ links to $j$, else 0.
• Eigenvector: Represents page rankings.

C. Stability Analysis in Control Systems

• Eigenvalues of system matrices determine stability (e.g., aircraft autopilot).
• Example: Nepal Airlines’ flight control systems use eigenvalue analysis to ensure stable flight paths.

4. Comparison of Methods

5. Worked Example: Real-World Problem

Problem: NTC’s Network Traffic Routing NTC’s traffic matrix $A$ (simplified) models data flow between nodes: $$A=\left[\begin{array}{ccc}2& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$$ Find the dominant eigenvalue (critical for load balancing).

Solution:

1. Apply the power method with ${\mathbf{x}}_0=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$.
2. After 3 iterations, ${\mathbf{x}}_3\approx \left[\begin{array}{c}0.45\\ 0.77\\ 0.45\end{array}\right]$.
3. Compute ${\lambda }_{\text{max}}=\frac{{\mathbf{x}}_3^{T}A{\mathbf{x}}_3}{{\mathbf{x}}_3^T{\mathbf{x}}_3}\approx 4.236$.

In the Real World

1. Google’s PageRank:

   • Uses the power method on a web-link adjacency matrix to rank search results.
   • Example: If Page A links to Page B (and vice versa), their eigenvector values rise together.

2. Nepal’s Stock Market (NEPSE):

   • Portfolio optimization uses eigenvalue decomposition of covariance matrices to minimize risk.
   • Example: A matrix $A$ with entries $A_{ij}=\text{covariance}(S_i,S_j)$ helps find uncorrelated stocks.

3. Pathao’s Ride Allocation:

   • The QR algorithm optimizes driver-passenger matching by solving a bipartite graph eigenvalue problem.
   • Example: Eigenvalues of a cost matrix determine the most efficient ride assignments.

Exam Tip

1. Power Method Questions:

   • Always show one full iteration with normalization.
   • State the convergence condition ($|{\lambda }_{\text{max}}|>|{\lambda }_i|$).
   • For past exams, expect 3x3 matrices with symmetric properties.

2. Jacobi/QR Algorithm:

   • Sketch the rotation matrix or QR factorization steps.
   • Mention symmetric matrices for Jacobi (faster convergence).

3. Theory Questions:

   • Define eigenvalue and eigenvector clearly.
   • Compare power vs. inverse power methods in terms of eigenvalues found.

4. Common Pitfalls:

   • Forgetting to normalize in the power method.
   • Misapplying the characteristic equation for non-symmetric matrices.
   • Ignoring convergence criteria in iterative methods.

Key Formulae to Memorize:

1. Characteristic equation: $\det (A-\lambda I)=0$.
2. Power method update: ${\mathbf{x}}_{k+1}=\frac{A{\mathbf{x}}_k}{\Vert A{\mathbf{x}}_k\Vert }$.
3. Eigenvalue estimate: $\lambda \approx \frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}$.