3. Eigenvalues and Eigenvectors

Note – This document was created using AI translation.

3.1 Overview

An eigenvalue problem for a matrix A involves finding a scalar λ and a vector x that satisfy:

  
  Ax = λx,  x ≠ 0

 
where λ is called an eigenvalue and x an eigenvector. If A is an n x n matrix, it has n eigenvalues, each associated with an eigenvector.

In many applications, the problem of finding eigenvalues of symmetric matrices is of particular interest. Thus, we consider the case of symmetric matrices.

If A is symmetric, all its eigenvalues are real numbers. Conversely, for a general (non-symmetric) matrix, even if A is real, its eigenvalues may be complex numbers.

Eigenvalues satisfy the following equation:

  
  det(A - λI) = 0

 
This is called the characteristic equation, which is an n-th degree algebraic equation in λ. Solving this algebraic equation directly allows us to determine the eigenvalues λ. However, since computing the coefficients of this equation requires a significant amount of calculation and numerical solving of algebraic equations can be difficult, other methods are used.

3.2 Methods for Solving Eigenvalue Problems

3.2.1 Finding Only the Eigenvalue with Largest Magnitude (or Specific Eigenvalue)

Starting with an arbitrary initial vector x0, perform the following iteration:

 
  x1 = Ax0, x2 = Ax1, ..., xk = Axk-1

 
The vector xk converges to the eigenvector corresponding to the eigenvalue with largest magnitude. The eigenvalue is given by:

 
  λ = (xk, xk)/(xk, xk-1)

 
where ( , ) represents the inner product of vectors.

This method is called the “power method,” which is a classical technique that remains effective today. This method requires that the eigenvalue with largest magnitude is unique (not multiple root).

The eigenvalues of A-1 is given by λ-1.

  
  A-1x = λ-1x,  x ≠ 0

 
Applying the power method to A-1 yields the eigenvalue with largest magnitude λ-1, which corresponds to the eigenvalue with the smallest magnitude λ. This method is called the inverse power method. Additionally, applying the method to (A – σI)-1 allows us to find the eigenvalue closest to σ.

3.2.2 Finding All Eigenvalues

A standard approach for finding all eigenvalues involves transforming the matrix into a tridiagonal form.

3.2.2.1 Tridiagonalization

First, transform matrix A into a tridiagonal matrix (a matrix where only the diagonal and adjacent elements are nonzero) without altering its eigenvalues. This transformation is commonly done using the Householder transformation.

For an n-vector u, we define the following n x n matrix H:

 
  H = I - 2uuT/(uTu)

 
This matrix H satisfies the following properties, meaning it is an orthogonal matrix:

 
  H-1 = HT = H

 
The following transformation of matrix A using H is called the Householder transformation:

 
  H-1AH = HAH

 
A transformation of the form P-1AP is called a similarity transformation, and it preserves the eigenvalues of A. The Householder transformation has the advantage of computing the similarity transformation without explicitly determining the inverse matrix H.

Next, let the first column elements of matrix A be written as a11, a21, …, an1, and define the vector u as follows:

 
      (    0    )
      ( a21 + s )
  u = ( a31 )
      ( a41 )
          ...   
      ( an1 )

  where s2 = Σai12 (i = 2 ～ n)
  and, s is chosen to have the same sign as a21

 
By selecting u in this manner, after applying the Householder transformation, the first column of A is transformed as follows:

 
  ( a11 )
  ( -s  )
  (  0  )
    ...   
  (  0  )

  where s2 = Σai12 (i = 2 ～ n)

 
Thus, all elements in the first column from the third row onward become zero. Due to symmetry, all elements in the first row from the third column onward also become zero.

Repeating this transformation for the second column, third column, …, up to the
(n-2)-th column, the matrix A is converted into a tridiagonal matrix without changing its eigenvalues.

3.2.2.2 Computing Eigenvalues and Eigenvectors

Once A is transformed into a tridiagonal matrix, its eigenvalues are obtained using iterative methods, such as the QR method.

The QR decomposition of matrix A is expressed as:

 
  A = QR

 
where Q is an orthogonal matrix and R is an upper triangular matrix.

After performing the QR decomposition of A and reversing the order of multiplication, we obtain:

 
  RQ = Q-1AQ = QTAQ

 
which is a similarity transformation that preserves the eigenvalues.

Repeating this process iteratively leads to convergence toward a diagonal matrix, with eigenvalues appearing on the diagonal.

It may seem that applying QR decomposition directly from the beginning is sufficient, but for a tridiagonal matrix, convergence is faster and more efficient computation procedures exist. As a result, even when accounting for the tridiagonalization step, the overall computational cost remains lower.

3.3 Solving Eigenvalue Problems Using XLPack

The VBA subroutine Dsyev or worksheet function WDsyev can compute all eigenvalues and corresponding eigenvectors, or just the eigenvalues of a symmetric matrix.

These functions utilize the LAPACK subroutine DSYEV, which employs Householder transformation for tridiagonalization and the QR method for computing eigenvalues and eigenvectors.

Example Problem

Find the eigenvalues and eigenvectors of the following symmetric matrix:

  
        ( 10 -3  5 )
    A = ( -3  2 -1 )
        (  5 -1  5 )

 

3.3.1 Solving Using Worksheet Functions

First, enter the symmetric matrix A into an appropriate location in the worksheet (orange-colored cells). Then, select a range for the solution (solution area + one additional row of cells) and input the worksheet function WDsyev (green-colored cells).

The required parameters for WDsyev are Jobz, Uplo, N, A. Setting Jobz = “V” computes both eigenvalues and eigenvectors, while Jobz = “N” computes only the eigenvalues. Setting Uplo = “U” uses the upper triangular portion of A, whereas Uplo = “L” uses the lower triangular portion. N represents the number of elements (3 in this example), and A is the cell range containing the symmetric matrix.

Here, all elements of matrix A are inputted, but WDsyev only requires the specified upper or lower triangular portion along with the diagonal elements, so the remaining elements do not need to be entered.

Once input is complete, press Ctrl + Shift + Enter.

This provides three eigenvalues λ along with their corresponding eigenvectors x (column vectors). The value 0 displayed below the eigenvalues represents a return code indicating successful execution.

3.3.2 Solving Using a VBA Program

The same example problem can be solved using a VBA program. Below is an example using Dsyev:

Sub Start()
    Const NMax = 10
    Dim N As Long, A(NMax, NMax) As Double, W(NMax) As Double
    Dim Info As Long, I As Long, J As Long
    '--- Input data
    N = 3
    For I = 0 To N - 1
        For J = 0 To N - 1
            A(I, J) = Cells(5 + I, 1 + J)
        Next
    Next
    '--- Compute eigenvalues and eigenvectors
    Call Dsyev("V", "L", N, A(), W(), Info)
    '--- Output result
    For I = 0 To N - 1
        For J = 0 To N - 1
            Cells(5 + I, 5 + J) = A(I, J)
        Next
        Cells(5 + I, 4) = W(I)
    Next
    Cells(8, 4) = Info
End Sub

To execute, enter the values of symmetric matrix A into the designated cells (orange-colored cells) and run the macro Start. Unlike using worksheet functions, simply entering the matrix values does not produce results. You must execute the VBA program.

Here, all elements are read into the array A(), but like in the worksheet method, Dsyev only requires the specified upper or lower triangular portion along with diagonal elements.

Published: May 1, 2025 (Last update: Apr 24, 2025)