Chapter 9 Inner Product Spaces and Orthogonal Structure: Exercises

The Jacobi Method¶

The Jacobi method is one of the oldest numerical algorithms for finding the eigenvalues of a real symmetric matrix. It was proposed by Carl Gustav Jacob Jacobi in 1846, more than a century before the modern QR algorithm.

Its central idea comes from a simple observation: the eigenvalues of a diagonal matrix can be read off at a glance—they are the entries on the diagonal. So if a matrix can be “reduced” step by step to diagonal form by a sequence of similarity transformations that leave the eigenvalues unchanged, the problem is solved.

Recall the spectral theorem of Chapter 9: a real symmetric matrix $\mathbf{A}$ is always orthogonally diagonalizable, that is, there exists an orthogonal matrix $\mathbf{Q}$ such that

\mathbf{Q}^\top \mathbf{A}\, \mathbf{Q} = \mathbf{\Lambda}

(1)

The Jacobi method approximates this $\mathbf{Q}$ constructively—at each step it chooses a plane rotation (a Givens rotation) $\mathbf{G}_{ij}$ that eliminates one off-diagonal entry $a_{ij}$ exactly, while guaranteeing that the overall “off-diagonal energy”

\text{off}(\mathbf{A})^2 = \sum_{i \neq j} a_{ij}^2

(2)

decreases strictly monotonically. Although after one entry is eliminated, other entries in the same row and column may be disturbed and no longer be zero, we will see in the exercise below that each rotation reduces $\text{off}^2$ by exactly $2a_{ij}^2$ ; this “conservation of energy” viewpoint is the key to analyzing the convergence of the algorithm.

Exercise 1 (The Jacobi Eigenvalue Method)

Let the symmetric matrix be

\mathbf{A} = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}

(3)

Part 1: A single rotation

Write down the general form of the Givens rotation matrix $\mathbf{G}(\theta)$ , and the formula that determines the rotation angle $\theta$ from the elimination condition.
Compute the angle $\theta$ needed to make the off-diagonal entries of $\mathbf{A}' = \mathbf{G}^\top \mathbf{A}\, \mathbf{G}$ zero.
Verify that the Frobenius norm is unchanged by the rotation: $\|\mathbf{A}'\|_F = \|\mathbf{A}\|_F$ .
Verify the exact decrease formula for the off-diagonal norm:

\text{off}(\mathbf{A}')^2 = \text{off}(\mathbf{A})^2 - 2a_{01}^2

(4)

Part 2: Geometric interpretation

What is the geometric meaning of the columns of $\mathbf{G}$ ? How are they related to the eigenvectors of $\mathbf{A}$ ?
What quantities of $\mathbf{A}$ do the diagonal entries of $\mathbf{A}'$ correspond to?

Part 3: Generalizing to $3\times 3$

Consider the symmetric matrix

\mathbf{B} = \begin{bmatrix} 4 & 2 & 0 \\ 2 & 3 & 1 \\ 0 & 1 & 2 \end{bmatrix}

(5)

Following the classical Jacobi strategy (at each step choose the off-diagonal entry of largest absolute value), decide which position $(i, j)$ the first rotation should target, and compute the corresponding rotation angle $\theta$ .
After performing one rotation, compute the new matrix $\mathbf{B}'$ and verify that $\text{off}(\mathbf{B}')^2 = \text{off}(\mathbf{B})^2 - 2b_{ij}^2$ .
Explain why, after the rotation, the entry $b_{02}$ (and $b_{20}$ ) of $\mathbf{B}'$ that was previously zero may no longer be zero, while $\text{off}(\mathbf{B}')^2$ still decreases strictly.